В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 19
Текст из файла (страница 19)
. . |βk α.Имеющиеся в грамматике e-правила могут быть удалены предварительно.Получающаяся грамматика без левой рекурсии может иметь e-правила.4.4.6. Левая факторизация. Oсновная идея левой факторизации в том,что в том случае, когда неясно, какую из двух альтернатив надо использовать для развертки нетерминала A, нужно изменить A-правила так, чтобыотложить решение до тех пор, пока не будет достаточно информации дляпринятия правильного решения.Если A → αβ1 | αβ2 — два A-правила и входная цепочка начинаетсяс непустой строки, выводимой из α, то мы не знаем, разворачивать липо первому правилу или по второму. Можно отложить решение, развернувA → αA′ .
Тогда после анализа того, что выводимо из α, можно развернутьпо A′ → β1 или по A′ → β2 . Левофакторизованные правила принимают видA → αA′ ;A′ → β1 | β2 .Алгоритм 4.10. Левая факторизация грамматики.Вход. КС-грамматика G.Выход. Левофакторизованная КС-грамматика G′ , эквивалентная G.Метод. Для каждого нетерминала A найти самый длинный префикс α,общий для двух или более его альтернатив. Если α 6= e, т. е. существуетнетривиальный общий префикс, то заменить все A-правилаA → αβ1 | αβ2 | . . . | αβn | z ,где z обозначает все альтернативы, не начинающиеся с α, наA → αA′ | z ;A′ → β1 | β2 | .
. . | βn ,где A′ — новый нетерминал. Применять это преобразование, пока существуетпара альтернатив, имеющих общий префикс.Пример 4.11. Рассмотрим вновь грамматику условных операторов из примера 4.9:92Глава 4. Синтаксический анализS → if E then S | if E then S else S | a;E → b.После левой факторизации грамматика принимает видS → if E then SS ′ | a;S ′ → else S | e;E → b.К сожалению, грамматика остается неоднозначной, а значит, и не LL(1)грамматикой.4.4.7.
Рекурсивный спуск. Выше был рассмотрен один из вариантовтаблично-управляемого предсказывающего анализа, когда магазин явно использовался в процессе работы анализатора. Возможен иной вариант предсказывающего анализа, в котором каждому нетерминалу сопоставляется процедура (вообще говоря, рекурсивная), а магазин образуется неявно при вызовахтаких процедур. Процедуры рекурсивного спуска могут быть записаны, какпоказано ниже.В процедуре A для случая, когда имеется правило A → ui , такое, чтоui ⇒ ∗ e (напомним, что не может быть больше одного правила, из котороговыводится e), приведены два варианта — 1.1 и 1.2. В варианте 1.1 делаетсяпроверка, принадлежит ли следующий входной символ F OLLOW (A).
Еслинет — выдается сообщение об ошибке. В варианте 1.2 этого не делается, такчто анализ ошибки перекладывается на процедуру, вызвавшую A.void A(){ // A → u1 | u2 | . . . | ukif (InSym ∈ F IRST (ui )) // только одному!if (parse(ui ))result("A → ui ;else error();else//Вариант 1:if (имеется правило A → ui такое, что ui ⇒∗ e)//Вариант 1.1if (InSym ∈ F OLLOW (A))result("A → ui ;else error();//Конец варианта 1.1//Вариант 1.2:result("A → ui ;//Конец варианта 1.2//Конец варианта 1//Вариант 2:if (нет правила A → ui такого, что ui ⇒∗ e)error();//Конец варианта 2}4.5. Разбор снизу-вверх типа сдвиг-свертка93boolean parse(u){ // из u не выводится e!v = u;while (v 6= e){ // v = Xzif (X - терминал a)if (InSym 6= a)return(false);else InSym = getInsym();else // X - нетерминал BB ();v = z;}return(true);}4.4.8.
Конструктор LL(1)-анализаторов на Java. В программном приложении приведен пакет LL1, содержащий LL(1)-конструктор и анализатор.4.4.9. Восстановление процесса анализа после синтаксических ошибок. В приведенных программах рекурсивного спуска была использована процедура реакции на синтаксические ошибки error(). В простейшемслучае эта процедура выдает диагностику и завершает работу анализатора.Но можно попытаться некоторым разумным образом продолжить работу. Дляразбора сверху вниз можно предложить следующий простой алгоритм.Если в момент обнаружения ошибки на верхушке магазина оказалсянетерминальный символ A и для него нет правила, соответствующего входному символу, то сканируем вход до тех пор, пока не встретим символ либоиз F IRST (A), либо из F OLLOW (A). В первом случае разворачиваем Aпо соответствующему правилу, во втором — удаляем A из магазина.Если на верхушке магазина терминальный символ, то можно удалитьвсе терминальные символы с верхушки магазина вплоть до первого (сверху)нетерминального символа и продолжать так, как это было описано выше.4.5.
Разбор снизу-вверх типа сдвиг-свертка4.5.1. Основа. В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной цепочки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как «свертку» цепочки wк начальному символу грамматики. На каждом шаге свертки подцепочка,которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шагевыбирается правильная подцепочка, то в обратном порядке прослеживаетсяправосторонний вывод (рис.
4.5). Здесь ко входной цепочке, так же как и прианализе LL(1)-грамматик, приписан концевой маркер $.94Глава 4. Синтаксический анализРис. 4.5Основой цепочки называется подцепочка сентенциальной формы, котораяможет быть сопоставлена правой части некоторого правила вывода, сверткапо которому к левой части правила соответствует одному шагу в обращенииправостороннего вывода.
Самая левая подцепочка, которая сопоставляетсяправой части некоторого правила вывода A → γ , не обязательно является основой, поскольку свертка по правилу A → γ может дать цепочку, не сводимуюк аксиоме.Формально, основа правой сентенциальной формы z — это правило выводаA → γ и позиция в z , в которой может быть найдена цепочка γ , такие, чтов результате замены γ на A получается предыдущая сентенциальная формав правостороннем выводе z .
Так, если S ⇒ ∗r αAβ ⇒ r αγβ , то A → γ в позиции,следующей за α, — это основа цепочки αγβ . Подцепочка β справа от основысодержит только терминальные символы.Вообще говоря, грамматика может быть неоднозначной, поэтому правосторонний вывод αγβ и основа могут не быть единственными. Если грамматикаоднозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминаллевой части называется отсечением основы.
Обращение правостороннеговывода может быть получено с помощью повторного применения отсеченияосновы, начиная с исходной цепочки w. Если w — слово в рассматриваемойграмматике, то w = αn , где αn — n-я правая сентенциальная форма ещенеизвестного правого вывода S = α0 ⇒ r α1 ⇒ r . . . ⇒ r αn−1 ⇒ r αn = w.Чтобы восстановить этот вывод в обратном порядке, выделяем основу γnв αn и заменяем γn на левую часть некоторого правила вывода An → γn ,получая (n − 1)-ю правую сентенциальную форму αn−1 . Затем повторяемэтот процесс, т.
е. выделяем основу γn−1 в αn−1 и сворачиваем эту основу,получая правую сентенциальную форму αn−2 . Если, повторяя этот процесс,мы получаем правую сентенциальную форму, состоящую только из начального символа S , то останавливаемся и сообщаем об успешном завершении4.5. Разбор снизу-вверх типа сдвиг-свертка95разбора.
Обращение последовательности правил, использованных в свертках,есть правый вывод входной строки.Таким образом, главная задача анализатора типа сдвиг-свертка — этовыделение и отсечение основы.4.5.2. LR(1)-анализаторы. В названии LR(1) символ L указывает на то,что входная цепочка читается слева-направо; R — на то, что строится правыйвывод; наконец, 1 указывает на то, что анализатор видит один символ непрочитанной части входной цепочки.LR(1)-анализ привлекателен по нескольким причинам:– LR(1)-анализ — наиболее мощный метод анализа без возвратов типасдвиг-свертка;– LR(1)-анализ может быть реализован довольно эффективно;– LR(1)-анализаторы могут быть построены для практически всех конструкций языков программирования;– класс грамматик, которые могут быть проанализированы LR(1)-методом,строго включает класс грамматик, которые могут быть проанализированы предсказывающими анализаторами (сверху-вниз типа LL(1)).Схематически структура LR(1)-анализатора изображена на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
