Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 25
Текст из файла (страница 25)
рнтельно требуется лишь немного внданзыеннть Исходную трам. матику. Прнмененке методов аптимнзацнн позволяет су7цестаенио укеньшнть размер 3ЕК(1)- илн ЕЛ1К(1)-анализатора. Обычно имеет смысл исключить свертки по цепнмм правнлаы. Дальнейшее уменьшенне размера анализатора возможно, если ЕЛЕК(!)-анализатор реализуется в виде анализатора на языке Флойда — Эванса из равд. 7.2. Элементы действия каждой ЕК(!). таблицы можно представить в виде последовательности операторов переноса, за которымн следуют операторы свертки, за которымк в свою очередь следует один безусловный оператор ошибки. Если все операторы свертки включаю! одно н то же правнло, то всех их вместе с последующим операторомошибки можно заменнть одним оператором, свертывающнм в соответствии с зтям правилом независнмо от входной цепочки.
Способность анализатора обнаруживать ошибки прн такой о>пимизацин не затрагивается. См. упр. 7.3.23 н 7.5.13. Элементы перехода каждой СК(1)- таблицы, отличные от 97, запоминаются в виде списка пар (А, Т), означающих, что на нетерминале А в верхушку магазина помещается таблица Т. Переходы, отвечающне терминалам, можно закодировать в самых операторах переноса, Заметим, что элел7енты 37 запоминать не требуется. После этога можно пользоваться методами оптимизации, описанными в разя. 7.2 н состоящими в том, что общие последовательности операторан слнваются. Такие подходы к построению анализаторов обладают рядом практических преимуществ. Во-первых, полученный анализатор можно чисто механически отладить, порождая входные цепочки, позволяющнс проверить поведение анализатора. Например, легко построить входные цепочки, проверяккцие каждый полезный злемегп 1Л.(1)- илн СК(1)-таблицы Др>гас преимущество 1Л.(1)- н ЕК(1)-аналнзаторов, особенно первого из них, связано с тем, Гл г иэтоды аптиризлпии гиитАксичесхил АИАлизАтароз эпрлжншгия что небольшие излгенения в синтаксис или семантику можно внести, просто изменив соответствующие элементы таблицы разбора.
Наконец, читатель может убедиться в толг, что некоторые неоднозначные грамматики имеюз "1.1". или *'Йшанализаторы, образованные в результате того, что конфликты разбора разрешаются некоторым произвольным образом (упр. ?.5.!4]. Конструирование анализаторов такого типа составляет предмет дальнейших исследований. эпнджниния 7.5.1. Постройте для грамматики 6, анализирующий автомат М. Постройте па М эквивалентные расщепленный, палуприведеииый и привспсиный автоматы. 7.5.2.
Пощройте анализирующие автоматы для всех грамма. тик из упр. 7.3!. 7.5.3, Расшспитс состоянии авточатоа из упр. 7.5.2 для по. строешш приведенных анализирующих автоматов. 7.5.4. Докажите лемму 7.4. 7.5.5. Докажите, что определение приведенного автомата, данное в равд. 7.5.2, корректно, т.
е. если Р=.д, та 6(р, а) =- =— 6(д, а) для всех а из 2'Г) (е). 7.5.0. Докажите теорему 7.13. Определение. Пусть 6 = (Х, 2, Р, 5') — пополненная КС-грамматика, правила которой занумерованы числами О, 1, .. так, по нулевое правило есп 5' Я. пусть 2' = (ял„жл„..., Йр)— мнажсагао специальных симполов, не принадлежащих Х Г) Тш Пусть г-е правило имеет вид А 1! и 5'~',аАш=л,абш. Тогда афНА, называется характериипишслай цепочкой иразоаыводимой цепочки абш.
*7.5.7. 11окажите, что множество характеристических цепочек для !ГС-грамматикгг регулярно. 7.5.8. Покажите, что КС.грамматииа 6 однозначна тогда и талька тогда, когда каждая правоаыводимая цепочки грамматики 6, за исключением 5', имеет едггиственгтую характеристическую цепочку. 7.5.9. Поиажите, что КС-грамматика является 1К(Д)-грамматикой тогда и только тогда, когда любая правовыводимая цепочка гфш, дли которой 5'=->',аАш=-л,абю, имеет характеристическую цепочку, которую можно найти, зная толька сф и 1:1((ЯТА(ш).
7.5.10. Пусть 6 = (Х, 2, Р, 5) — 1.0(0)-грамматика и ( а, Т,)— ее каноническое множества СК(0)-таблиц. Пусть М = ('.", т 1! ш', 6, Т, (Т,))-. канонический анализирующий автомат для 6. П) сгь М'=(ГО (47), д 1!2', 6', Т„(4 )] -детеРминиРованный конечный автомат, построенный по М следующим образам: (1) б'(Т, а) = 6(Т, а) для всех 7'бш и а02, (2) б'(Т, ф",) --4, если 6(7', Т') определено и Т' состояние свертки, вызйвающее свертку по правилу г. Покажите, что 7(М')- множество характеристических цепочек для 6.
7.5.11. Напишите алгоритм слияния „эквивалентных" состоя- ний полуприведенного автомата, построенного для Г.К(1)-грэм. матикн. Эквивалентггыми здесь начываютси состояния, переходы из которых помечены одним и тем жс множеством символов, причем одинаково помеченные переходы ведут в эквивалентные состояния ').
7.5.12. Предположим, что мы изменили определение эквива- лентности, данное в упр. 7.5.11, так, что эквивалентными тсасрь считаются и те состояния, переходы из котарьж, помеченные символом а, всегда, когда они существуют, ведут в эквивалент- ные состояния. Будет ли полученный автомат эквивалентен (в формальном смысле, т. е. при условии, что перенос вапрегцен, если исходный автомат сообщил об ошибке) полуприведеннаму автомату? 7.5.!3. Предположим, что в СК(1)-анализнругошелг автомате из состояния чтения Т переходы происходят талька в состояния выталкивания, свертывающие по одному и тому же правилу. Покажите, что если исключить Т и слить асе эти состоинии выталкивания в одно состояияе, то новый автомат будет сверты- вать независимо от ававцепочки, но останется эквивалентным исходному автомату.
7.5.14. Пусть 6 †однозначн грамматика с правилами 5 Н Ь (реп ЯЕ)а Е е1зе Я!е (а) Покажите, что !.(6) ие является Б).-языколг. (б) Постройте для 6 (.предсказьгваю~ций анализатор, считая, что всякий раз, когда в верхушке магазина находится символ Е, а следующим входным символом является е!эе, нужно примешгть правила Е еЬеЯ. (в) При аналогичных предположениях постройте для 6 Г.К(!)- анализатор. ') Эгз определение иажча сделать точзыи, зззлэ атаошеииз клх шо Хсллласл з лемме 7.2. 137 Гл г методы Оптимизации синтАксических АнАлнзАтОРОЕ Проблемы ддя исследозания 7.5.15. Примените используемый метод, а именно разбиение анализатора на ряд активных компонент и слияние пли исключение неноторых из них, к анализаторам, отличным от СК-анализаторов.
Например, в методе, описанном в равд. 7.2, активными компонентами были строки матрицы предшествовапия. Разработайте методы, применимые к [.[.-Енализаторалг и различным типам анализаторов предшествования. 7.5.15. Некоторые состояния канонического аналивирующего автомата обладают тем свойством, что автомат с такими состояниями распознает только регулярные множества. Рассмотрим задачу расщепления состояний переноса Анализирующего автомата на состояния просмотра н заталкинания. В состоянии просмотра могут просматриваться входные символы и генерироваться выходная цепочка, но не производится никаких действий с магазином.
После состояния просмотра управление передашся в другое состояние просмотра или в состояние заталкнвания. Таким образом, множество состояний просмотра работасг как конечный преобразователь. В состоянии заталкивапия в магазин помещается имя текущего состояния, Разработайте преобразояания, с помощью которых можно оптнл|изиравать анализируюплий автомат с состояниями просыотра и заталкивания, а также с расщепленными состояниями свертки. 7.5.17.
Опишите методы оптимизации из равд. 7.3 в терминах методов из разд. 7.5 и наоборот. уорпжнония но программирование 7.5,13. Разработайте элементарные операции, необходимые для реализации расщепленного еанонического автомата Постройтс для них интерпретатор. 7.5.10. Напишите программу, получающую на вход расщепленный канонический автомат н строшцую по нему последоиательность элементарных операций, моделирующую поведение впали Аярующего автомата. 7.5.20.
Постройте для одной из грамматик из приложения к тому 1 дна С[((Г)-аналллзатора. Один БК(!)-анализатор должен быль Г.К(1)-анализатором интерпретиру!Он!его типа, работающим с множеством БК(1)-таблиц. Другой- -последовательностью элементарных операций, моделирующей аналязнр)ющий автоиат. Сравните размеры и скорости работы этих анализаторов. Замечания по литературе подход, есчоллзуюшие юалезаруюшее автомат, предложен дз Ремерам 119еэ! Одуедедензе хгракъоишдческое кепочки, пгедшес~зуюшее учр 7.5 Т, ззичслвонднс зэ того же зстсчочхг. [ыыссн эеодеозедчнмх грамматик, рдзОеолечнд Ы- илз Гй-заадизегораяз, рассматривались Ахо з др.
[[9ТЕ!. ТЕОРИЯ 8 ДЕТЕРМИНИРОВАННОГО РАЗБОРА В гл. 5 мы познакомились с различными классами грамматик, для которых удается построить эффективные детерминированные синтаксические анализаторы. Были продемонстрированы некоторые отношения включения на классах грамматнн. Например, мы показали, что каждая (т, й)-ОПК-грамматика является Ы(д).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
