В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 19
Текст из файла (страница 19)
Допустим, что G не LL(k)-грамматика. Тогда найдутся такие два выводаS ⇒ ∗l ωAα ⇒ l ωβα ⇒ ∗l ωxиS ⇒ ∗l ωAα ⇒ l ωγα ⇒ ∗l ωy ,что цепочки x и y совпадают в первых k позициях, но β 6= γ . Поэтому A → βи A → γ — различные правила из P и каждое из множеств F IRSTk (βα)и F IRSTk (γα) содержит цепочку F IRSTk (x), совпадающую с цепочкойF IRSTk (y).Пример 4.10. Грамматика G, состоящая из двух правил S → aS | a, не будетLL(1)-грамматикой, так какF IRST1 (aS) = F IRST1 (a) = a.Интуитивно это можно объяснить так: видя при разборе цепочки, начинающейсясимволом a, только этот первый символ, мы не знаем, какое из правил S → aS илиS → a надо применить к S . С другой стороны, G — это LL(2)-грамматика.
В самомделе, в обозначениях теоремы 4.7 если S ⇒ ∗l ωAα, то A = S и α = e. Так как для Sданы только два указанных правила, то β = aS и γ = a. Поскольку F IRST2 (aS) = aaи F IRST2 (a) = a, то по последней теореме G будет LL(2)-грамматикой.90Глава 4. Синтаксический анализ4.4.5. Удаление левой рекурсии. Основная трудность при использовании предсказывающего анализа — это нахождение такой грамматики длявходного языка, по которой можно построить таблицу анализа с однозначноопределенными входами.
Иногда с помощью некоторых простых преобразований грамматику, не являющуюся LL(1), можно привести к эквивалентнойLL(1)-грамматике. Среди этих преобразований наиболее эффективными являются левая факторизация и удаление левой рекурсии. Здесь необходимосделать два замечания. Во-первых, не всякая грамматика после этих преобразований становится LL(1), и, во-вторых, после таких преобразованийполучающаяся грамматика может стать менее понятной.Непосредственную левую рекурсию, т. е. рекурсию вида A → Aα, можноудалить следующим способом.
Сначала группируем A-правила:A → Aα1 | Aα2 | . . . | Aαm | β1 | β2 | . . . | βn ,где никакая из строк βi не начинается с A. Затем заменяем этот набор правилнаA → β1 A′ | β2 A′ | . . . | βn A′ ;A′ → α1 A′ | α2 A′ | . . . | αm A′ | e.где A′ — новый нетерминал. Из нетерминала A можно вывести те же цепочки,что и раньше, но теперь нет левой рекурсии.
С помощью этой процедурыудаляются все непосредственные левые рекурсии, но не удаляется леваярекурсия, включающая два или более шагов. Нижеследующий алгоритмпозволяет удалить все левые рекурсии из грамматики.Алгоритм 4.9. Удаление левой рекурсии.Вход. КС-грамматика G без e-правил (вида A → e).Выход. КС-грамматика G′ без левой рекурсии, эквивалентная G.Метод. Выполнить шаги 1 и 2.1. Упорядочить нетерминалы грамматики G в произвольном порядке.2. Выполнить следующую процедуру:for (i=1;i<=n;i++){for (j =1;j <=i-1;j ++){пусть Aj → β1 |β2 | . .
. |βk - все текущие правиладля Aj ;заменить все правила вида Ai → Aj αна правила Ai → β1 α|β2 α| . . . |βk α;}удалить правила вида Ai → Ai ;удалить непосредственную левую рекурсию вправилах для Ai ;}4.4. Предсказывающий разбор сверху-вниз91После (i − 1)-й итерации внешнего цикла на шаге 2 для любого правилавида Ak → As α, где k < i, выполняется s > k . В результате на следующей итерации (по i) внутренний цикл (по j ) последовательно увеличиваетнижнюю границу по m в любом правиле Ai → Am α, пока не будет m > i.Затем, после удаления непосредственной левой рекурсии для Ai -правил, mстановится больше i.Алгоритм 4.9 применим, если грамматика не имеет e-правил (правил видаA → e), поскольку при наличии таких правил может нарушиться инвариантцикла при замене правил вида Ai → Aj α на правила Ai → β1 α|β2 α| . .
. |β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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
