Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 5
Текст из файла (страница 5)
Прид)майте алгоритм, который но матрице гЧ с элементами — 1, О, Р 1, „пусто" н па константе й выясняет, сущесгвукгг гщ икие векторы / и й, что (1) если М»= — 1, то /, +й -.. д, (2) если Мы=0, то )/,— й )(й, (3) если гИ„=+1, то /, чл 8, +й. Определение. Пусть М вЂ” матрица слабого предшествовання, Последовательность целых чисел (о 1„ ..., гм где й — четное число, ббльшее 3, назовем цпклол~ матрицы гЧ, если (1) М0г,,= — 1 длЯ нечетных /, тЧ, г =-+(длЯ четных/ ю юг! и гИг,г, =- + 1 илн (2) Мг;,=+1 для нечетных /, Мг я = — ! для четных / 7.1.8.
Покажите, что фувкции слабого предшествааания для матрицы слабого предн|ествования существуют тогда и только тогда, когда она не содержит циклов. 7.1.9. Пусть М- матрица слабого предшествования и г, /, й, ! — такие индексы, что (1) Мм=Мгг =-' — 1, М „.—. +1 и Мн есть „пусто", 26 упРАжнения или (2) М, .—..Мн==-(-1, М =- — ! и Мн есть „пусто".
Пусть М' получается в результате замены в матрице гЧ элемента Мн на — ! в случае (1) или на Р1 в случае (2). Поиажите, что / и 8 — функции слабщо предшествования для М тогда и то.гько тогда, когда они являются фуикциячи слабого пред- шествования для МС Определение. Будем говорить что две строки (два столбца) матрицы предшествоваиия сгммсстимы, если во всех случаях, когда их соответствуюгцие элементы ае совпадают, один из вих п)стой. Совместимые строки (столбцы) можно слить, заменив их яозой строкой (столбцам) так, что ненустые элементы каждой из прежних строк (столбцов) совпадшот с соответствующими непустыми элементами новой строки (столбца).
7.1.10. Покажите, что операции слияния строк н столбцов сохраняют свойства матрицы не иметь лииеаризующих ф)з!Епий. Фувкггии предшествованвя Агожно применять также для представления отношений АЕ и ', используемых фупкпией свертки в алгоритме разбора типа „перенос- -свертка", построенном па алгоргньгу 5.12. Сяачала найдем матрипу слабого прсдшестзования М, в которой †! представляет чзю -1-! представляет а пустые элементы представляют и йэ, и ошибку.
Затем попытаемся отыскать для АИ функции пред~пегтвованыя, опять пробтя заменить возможна большее чясло пустых элементов иулятщ. 7.1.11. Представые отношения чд и ', привсленные нз рис. 7.13, функциями предшествования. С помощью теоремы 7.2 найдите существенные пустые элементы и попытайтесь сохранить их. *7.1.12. Покажите, что если принять определение строгой эквивалентности анализаторов слабого предшествования, то пустой элемент (Х, !') матрицы отношений предшествовання Вирта— Вебера будет существенным тогда и только тогда, когда удовлетворяется одно из следующих условий: (1) Х и У принадлежат 2 Ц (3), (2) Х принадлежит )АС У принадлежит БВ(3) и есть такое правило Х ау, что ХйР,У. В следующих задачах термин „эквивалентность" пониыается в смысле примера 7.8.
*7.!.13. Пусть .4, и .4 — те же алгоритмы разбора типа „пе. рснос — спертка" для граиматики просто~о предшествоаания, что и в теореме 7.2. Докажите, что онн эквивалентны тогда и только 27 Гл т. методы оптиьтиздцин синтдксических АндлиЗАтоРОн Т.Я. ОПТИЫИЗАЦИЯ АНАЛИЗАТОРОВ ФЛОЙДА — ЭПАНСА тогда, когда удовлетворяются следующие условия: (!) а) Если Х чшУ, то Х ц У, (б) если Х Т,У, то Х вЂ” 'У, (в) если Х.>,а, то Х Уга. (2) Если Ь),а, то Ь суп ложна.
(3) Если Ар,а н Аеа нли А '. а, то вет такого вывода А =э,цтХт~,... =Та Х, т .1, что Х)а и Х, Уда длЯ 1(1<го и Х„зд,а или Մ— терминал и Х„РО. (4) Если А, ела или А, ' а для йекоторого а, то нет вывода А, =эАТ~... ~ А„=э Вц, и) 1, символа Х и правила В -- Уй, для которых (а) Хр,АО но Х се А„где 2(! "т; (б) Х?,В, но Х сеВ1 (в) Хц У. 7.1.14. Покажите, что анализатор, использующий функцви пред!Нествования нз примера 7.8, эквивалентен каноническому анализатору првдшествоваиия для С,. 7.1.15. Пусть М вЂ матри отношений предшествования, полученная из матрицы канонических отношений предшествования Вирта — Вебера М, в результате замены некоторых пустых элсыентов на тъ.
Покажите, что анализаторы, построенные по М и М, с помощью алгоритма 5.!2 (или 5.!4), эквивалентны. *7.1.15. Рассмотрим алгорити разбора типа „перенос--свертка" для грамматики простого прсдшествования, в котором после каждой свертки проверяетсн, какое из отношений су или выполняется между символом, стоящим непосредственно слева от основы, и символом, в который свертывается основа. При каких условиях произвольная матрица отношений предшествовашш будет порождать анализатор, строго эквивалентный (или эквивалентный) анализатору такого типа, построенному по матрице канонических Отяошений предшествования Вирта Вебера? **7.1.17. Покажите, что всякий КЕ-язык порождается грамматикой предшествования (не обязательно обратимой), для которой можно найти функции предшествования.
Лрсблемм дяя исследования 7.1.18. Придумайте эффективный алгоритм нахождения функций предшествования для грамматики слабого пред!яешвавания С, позволяющий построить анализатор, эквивалентный каноническому анализатору предшествования для С. 7.1.19. Разработайте хорошие процедуры нейтрализации ошибок, которыми можно было бы воспользоваться при разборе с помощью функций предшествовання.
Упражнения ла программ!Трепание 7.1.20. Разработайте программу, реализующую алгоритм 7.1. 7.1.21. Напишите программу, реализующую алгоритм разбора типа „перенос — свертка", который использует в качестве функций ! и 8 фуякции предшествоваиия. 7.1.22. Напишите программу, определяющую, является ли КО-грамматика грамматикой предшествования, для которой существуют функпии предшествования. 7.1.23.
Напишите программу, которая получает на вход граыматику простого предшествования С, имеющую функции пред- шествования, а выдает для С рнализвтор типа „перенос — свертка", использующий функции предшествования. Замечании но литературе флойд !19631 прпменне фунннвп нредшествоввння дея предстввве ~ня мвтрпны отншжппй опсрвторпого прсдшсствоввння. Внрт н Вебер 119661 предшжнлн прнменюь нь дея прсдстввлення отнопшннй предшестювення Вирта — Вебере Алгорнтмы вычнслення фтнкпнй предшествоввмня быяв дени флойдом (1962), Внргом !!9661, Бонзом 119691, Мвртнпоч (!972), в тввже Аяо н Ульмвнам (!972е). Теореме 7,2 взята нв рвбтты Аго н Удьчвяе (19726!. где садержвтся также ответы нв напра ы, сформуенроввнные в унр 7 1 13 ° 7.1 16. Упр 7.1.17 зенмствоввпо у Мартина 119721.
7.2. ОПТИМИЗАЦИЯ АНАЛИЗАТОРОВ ФЛОЙДА — ЭВАНСА Алгорвтм разбора типа „перенос в свертка" демоастрнрует принципиально простой метод разбора. Однако при реализации двух функций анализатора мы сталкиваемся с проблевгамн эффективности. В настоящем разделе будет исследован вопрос о том, как сконструировать алгоритм разбора типа „перенос в свертка" для обратимой грамматики слабого предшествоввниа, пользуясь языком Флойда †Эван.
В центре внимания будут методы, позволяющие уменьшать объем получаемой программы на языке Флойда †Эван, не затрагивая поведения анализатора. Хотя здесь рассматриваются только грамматики предшсствованин, методы этого раздела применимы также при реализации анализаторов Хля всех остальных классов грамматик, описэнных в гл. 5 (том 11. Гл 7.
методы оптимизлпии синтАксических АнллизлтаРав У.ЙД. Меканическое построение анализаторов Фпойда— Эввмса дпя грамматик слабого предшествованпв Начнем с того, что покажем, как можно механически построить анализатор на языке Флойда †Эван для обратимой грамматики слабого предшествования. Язык Флойда †Эван описан в равд.
5.4.4. Ллгоритм проиллюстрируем примером. Как всегда, возьмем для примера грамматику слабого пред- шествования бг, с правилалги ()) Е Е+Т (2) Е Т (3) Т ТАР (4) Т Р (5) Р (Е) (6) Р- ° и ЭЕ(5 Е! допуск Ошибка 7) Введение вычисляемого опер гара переходя азхачхет рвсшярезкс яэн«х Флойда — Эллнсл по сгллхсзэю с сягсхзлсч гга э Рээд.
В.4.4. Вго расшзрскэг ээххючэгтсз з гам, что схгхуюшлэ метка может бшъ змрхжсэзгк, ссхгрмхшчк экхк .ф, который, кзк В в Рззх. З 4Л, средсгхзлвст кехэвестэна сэмзах, гаотэетстзуюгциа сзквалт, Рхсэалсжечнаму э у эзл В Л сэнсчх з стене, ВАВ сзкзоху, Вх «старий Вгахсхсшгг элгхллнэлзяе Взгрел. Мм хе будем сстээзтмкззтьсэ Вг дгтхххх рсалкэзсзз гхкога аперхтора, Ва чзмгехь Макет слм уб*дзглся, что эзедгэзиг элгсл внчксххгкмс азсрхтари Вггехслх лагко ргалкэазэть Вэ дссгтпэай еку знчзсхзтехы7ай мэшкзс. за Отношения предшествования Вирта — Вебера для б„приведены на рис. 7 9.
По каждой стране этой ыатри7>ы предшествования будем генерировать операторы анализатора на языке Ф 7айда †Эван. Б>дгм пользоватьс77 четырьмя типами операторов: оператор переноса, оператор свертки, оператор проверки и вычисляемый операгор перехода '). Операторам будем присваивать символьные метки, указывшощие как на тип оператора, так к па верхний свлгвол магазина. В таких метках буква 5 означает перепас, )7 †сверт, С в проверку и 6- †перех.
За шими бюгнами в метках стоит сичзол, находящийся в верхушке магазина. Сначала сгенсрпруслг операторы переноса, а затем свертки. >(ля граммагики слабого нредшествовання отношения предВмствовапия се и ,'. означают перенос, а ) †сверт. Е-строка на рис. 7.9 порождает операторы (7.2. () 5Е: Е !) — Е) ! л 5) Е(-~- Е+! В5+ 7.2. ОПТИМИЗАЦИЯ АНАЛИЗАТОРОВ ФЛОЙДА — ЭВАНСА Первын Оператор Означает, что если Е иалаюп я в верхушке магазина и текущий входной символ есть ), то ) помшцается в верхушиу магазина, считывается следующий свмвол и проис.
ходит переход на оператор, пом ченный 51. Если первый оператор неприменим, проверяем, является ли текущий входнОЙ символ знаком +. Если второй оператор неприлгепим, опять проВеряем, сОвпадает ли текуп!Вй входной символ с гимволом 5. Соответствующим действием анализатора будет тогда переход в заключительное состояние допуск, если в магазине содержится цепочка 5Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
