А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 55
Текст из файла (страница 55)
каждое е!ве ближайшему незанятому г!геп™. Это правило устранения неоднозначности теоретически может быть внедрено непосредственно в грамматику, но на практике его редко реализуют в виде продукций. Пример 4.6. Мы можем переписать грамматику (4.9) как однозначную. Идея заключается в том, что инструкция, появляющаяся между г!Ееп и е!яе, должна быть "сбалансированная'* (шаЕс)гее!), т.е. не должна оканчиваться открытым или не соответствующим некоторому еЬе ключевым словом г!зеп.
Такая "сбалансированная" инструкция может либо представлять собой полную инструкцию !Р-г!геп-е!ве, не содержащую открытых инструкций, либо быть любой инструкцией, отличающейся от условной. Таким образом, мы получаем грамматику, показанную на рис. 4.10. Эта грамматика генерирует те же строки, что и грамматика с висящим еЬе (4.9), но для строки (4.10) дает только одно дерево разбора, а именно — то, которое связывает каждое еЬе с ближайшим незанятым г!геп. и 276 Глава 4. Синтаксический анализ без изменения строк, порождаемых из А. Одного этого правила достаточно для большого количества грамматик. Пример 4.7. Повторенная здесь нелеворекурсивная грамматика для выражений (4.2) Š— ~ Т Е' Е' — +Т Е' ) е Т вЂ” ГТ' получается путем устранения непосредственной левой рекурсии из грамматики выражений (4.1).
Леворекурсивная пара продукций Š— Е+ Т ~ Т заменяется двумя продукциями, Š— Т Е' и Е' — +Т Е' ~ е. Новые продукции для Т и Т' получаются аналогично прн устранении левой рекурсии из продукции Т- Т* Е~Е. о Непосредственная левая рекурсия может быть устранена при помощи следующего метода, который работает для любого количества А-продукций. Вначале сгруппируем А-продукции следующим образом А — Агг~ ! Ааг ( ' ' ( Ас~ ) (3г ! ~3з ) ' ' ' ) (3 Здесь ни одно 13; не начинается с А. Затем заменим эти А-продукции следующим образом: А — ~ ДА' ) )3зА' ! . ) Д~А' А' — ~ агА' ( азА' ) ! о,„А' ! е Я вЂ” ~ Аа1Ь А — А с1Я Н1е (4.1 1) Нетерминал 5 леворекурсивен, поскольку Я =~ Аа ~ Яда, но эта рекурсия не является непосредственной. Алгоритм 4.8, приведенный ниже, систематически удаляет из грамматики левую рекурсию.
Он гарантированно работает с грамматиками, не имеющими циклов (порождений типа А =~ А) и е-продукций (продукций вида А — е). Циклы, как и е-продукцни, также могут быть удалены из грамматики систематическим образом (см. упражнения 4.4.6 и 4.4.7). Нетерминал А порождает те же строки, что и ранее, но без левой рекурсии. Эта процедура устраняет все левые рекурсии из продукций для А и А' (прн условии, что ни одна строка ои не является е), но не устраняет левую рекурсию, вызванную двумя или более шагами порождения.
Рассмотрим, например, грамматику 277 4.3. Разработка грамматики Алгоритм 4.8. Устранение левой рекурсии Вход: грамматика С без циклов и е-продукций. Выход: эквивалентная грамматика без левой рекурсии, Метод: применить алгоритм, приведенный на рис. 4.1!. Обратите внимание, что получающаяся грамматика без левых рекурсий может иметь г-продукции. о 1) Расположить нетерминалы в некотором порядке Аы Аз,..., А„.
2) 1ог(каждоезот 1 до п ) ( 3) 1ог( каждое 3 от 1 до1 — 1) ( 4) заменить каждую продукцию вида А, — А продукциями А; — буу(бзу(. )бьу,гдеА — бу!бз~ . ° (бь — все текущие А -продукции 5) ) 6) устранить непосредственную левую рекурсию среди А;-продукций 7) Рис.
4.1!. Алгоритм для устранения левой рекурсии из грамматики Процедура на рис. 4.11 работает следующим образом. В первой итерации для ! = 1 внешний цикл в строках 2-7 устраняет непосредственную левую рекурсию из Ау-продукций. Все остальные Ау-продукции вида Ау -~ А!а должны, таким образом, иметь ! > 1. После! — 1-й итерации внешнего цикла все нетерминалы Аы где к < г, оказываются "чистыми", т.е. все продукции Аь — А!а должны иметь ! > !с. В результате на 1-й итерации внутренний цикл в строках 3 — 5 постепенно поднимает нижнюю границу всех продукций А, — А о, пока мы не получим т > 1.
Затем устранение непосредственной левой рекурсии из А;-продукций в строке 6 делает т больше !. Пример 4.9. Применим алгоритм 4.8 к грамматике (4.!1). Технически из-за наличия е-продукции алгоритм может не работать, но в данном случае продукция А — е не мешает работе. Мы располагаем нетермнналы в порядке УУ, А.
Непосредственной левой рекурсии среди Я-продукций нет, так что в процессе работы внешнего цикла при 1 = 1 ничего не происходит. При 1 = 2 мы подставляем Я-продукцию в А — Я г( для получения следующих А-продукций: А- Ас!Аао!Ьг)~г 278 Глава 4. Синтаксический анализ Устранение непосредственной левой рекурсии среди А-продукций дает грамма- тику Я вЂ” ~ Аа(Ь А — Ь с» А') А' А' — ~ сА'(ас»А'(е 4.3.4 Левая факторизация Певал факторизация (1ей Гасюппй) представляет собой преобразование грамматики в пригодную для предиктивного, или нисходящего, синтаксического анализа.
Когда не ясно, какая из двух альтернативных продукций должна использоваться для нетерминала А, А-продукции можно переписать так, чтобы отложить принятие решения до тех пор, пока из входного потока не будет прочитано достаточно символов для правильного выбора. Например, если есть продукции з»т» — и ехрг Феп з»т» е!ае з»т» Ы ехрг тпеп з»т» то, обнаружив во входном потоке Ы, мы не в состоянии тут же выбрать ни одну из них.
В общем случае, если А — а»Уз ~ сг»3з представляют собой две А-продукции и входной поток начинается с непустой строки, порождаемой сз, то мы не знаем, будет ли использоваться первая или вторая продукция. Однако можно отложить решение, расширив А до аА'. В этом случае, после того как рассмотрен входной поток, порождаемый а, мы расширяем А' до»з1 или»зз. Таким образом, будучи левофакторизованными, исходные продукции превращаются в А — стА' А' — »з1 ~ А Алгоритм 440. Левая факторизация грамматики ВхОд: грамматика С.
Вьгход: эквивалентная левофакторизованная грамматика. Метод: для каждого нетерминала А находим самый длинный префикс ст, общий для двух или большего числа альтернатив. Если ст ф с, т.е. имеется нетривиальный общий префикс, заменим все продукции А — сгД ! а»уз ~ ) ст»» ~ 7, где 7 представляет все альтернативы, не начинающиеся с сз, продукциями А — сгА(» А' — »з1 (,9з ) .
)»3„ 4.3. Разработка грамматики 279 Здесь А' — новый нетерминал. Выполняем это преобразование до тех пор, пока никакие две альтернативы нетерминала не будут иметь общий префикс. и Пример 4.11. Следующая грамматика абстрагирует проблему "висящего е!яе": Я вЂ” ~ 1Е15(1Е1Яе5)а Š— Ь (4.12) Здесь г, 1 и е означают Ы, гйеп и е1яе, Е и Я соответствуют "условному выраже- нию" и "инструкции". Будучи левофакторизованной, эта грамматика принимает следующий вид: Š— 1Е1ЕУ ~ а ,э' — ~ еЯ)е Š— Ь (4.13) Таким образом, можно расширить Е до 1ЕгоУ для входного 1 и подождать, пока из входного потока не будет считано ГЕГБ, чтобы затем решить, расширять ли У до е5 или до е. Конечно, обе эти грамматики неоднозначны и при обнаружении во входном потоке е будет неясно, какая из альтернатив для У должна быть выбрана.
В примере 4.19 обсуждается путь решения этой дилеммы. и 4.3.5 Не контекстно-свободные языковые конструкции Некоторые синтаксические конструкции, имеющиеся в типичных языках программирования, не могут быть определены только лишь одной грамматикой.
Здесь мы рассмотрим две такие конструкции с использованием для иллюстрации возникающих сложностей простых абстрактных языков. Пример 4.12. Язык в этом примере абстрагирует проблему проверки того, что идентификаторы объявлены до их использования в программе. Язык состоит из строк вида юсш, где первое ю представляет объявление идентификатора ю, а второе ю — его использование. Упомянутый абстрактный язык — Б1 = 1юсю ~ ю Е (а ~ Ь)*). Б1 состоит из всех слов, образованных повторяющимися строками из а и Ь, разделенными символом с, например апЬсааЬ.
Хотя доказательство того, что Б1 не является контекстно-свободным языком, выходит за рамки данной книги, из этого факта непосредственно следует, что такие языки программирования, как С и 1ака, требующие обьявления идентификаторов до их использования н допускающие существование идентификаторов произвольной длины, не являются контекстно- свободными. По этой причине грамматики С или 1ача не различают идентификаторы, являющиеся различными строками символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
