В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 18
Текст из файла (страница 18)
В этом случае нужно развернутьA в α, если текущий входной символ принадлежит F OLLOW (A) или еслидостигнут $ и $ ∈ F OLLOW (A).Алгоритм 4.8. Построение таблицы предсказывающего анализатора.Вход. КС-грамматика G = (N , T , P , S).Выход. Таблица M [A, a] предсказывающего анализатора, A ∈ N , a ∈ T ∪∪ {$}.Метод. Для каждого правила вывода A→α грамматики выполнить шаги1 и 2. После этого выполнить шаг 3.1. Для каждого терминала a из F IRST (α) добавить A→α к M [A, a].2. Если e ∈ F IRST (α), то добавить A → α к M [A, b] для каждого терминала b из F OLLOW (A).
Кроме того, если e ∈ F IRST (α) и $ ∈∈ F OLLOW (A), то добавить A → α к M [A, $].3. Положить все неопределенные входы равными «ошибка».Пример 4.8. Применим алгоритм 4.7 к грамматике из примера 4.3. ПосколькуF IRST (T E ′ ) = F IRST (T ) = {(, id }, в соответствии с правилом вывода E → T E ′входы M [E , ( ] и M [E , id ] становятся равными E → T E ′ .В соответствии с правилом вывода E ′ → +T E ′ значение M [E ′ , +] равно E ′ → ++T E ′ .
В соответствии с правилом вывода E ′ → e значения M [E ′ , )] и M [E ′ , $] равныE ′ → e, поскольку F OLLOW (E ′ ) = { ), $}.Таблица анализа, построенная по алгоритму 4.8 для этой грамматики, идентичнатабл. 4.1.4.4.4. LL(k)-грамматики. Алгоритм 4.8 построения таблицы предсказывающего анализатора может быть применен к любой КС-грамматике. Однако для некоторых грамматик построенная таблица может иметь неоднозначноопределенные входы. Например, нетрудно доказать, что если грамматикалеворекурсивна или неоднозначна, то таблица будет иметь по крайней мереодин неоднозначно определенный вход.Грамматики, для которых таблица предсказывающего анализатора не имеет неоднозначно определенных входов, называются LL(1)-грамматиками.88Глава 4.
Синтаксический анализПредсказывающий анализатор, построенный для LL(1)-грамматики, называется LL(1)-анализатором. Первая буква L в названии связана с тем, чтовходная цепочка читается слева направо, вторая L обозначает, что строитсялевый вывод входной цепочки, 1 — что на каждом шаге для принятиярешения используется один символ из непрочитанной части входной цепочки.Алгоритм 4.8 для каждой из LL(1)-грамматик G строит таблицу предсказывающего анализатора, распознающего все цепочки из L(G) и только этицепочки. Нетрудно доказать также, что если G — LL(1)-грамматика, то L(G)— детерминированный КС-язык.Справедлив также следующий критерий LL(1)-грамматики. ГрамматикаG = (N , T , P , S) является LL(1)-грамматикой тогда и только тогда, когда длякаждой пары правил A → α, A → β из P (т.
е. правил с одинаковой левойчастью) выполняются следующие два условия:1) F IRST (α) ∩ F IRST (β) = ∅;2) Если e∈F IRST (α), то F IRST (β) ∩ F OLLOW (A)= ∅.Пример 4.9. Неоднозначная грамматика не является LL(1). Примером можетслужить грамматика G = ({S , E}, {if , then, else, a, b}, P , S) со следующими правилами:S → if E then S | if E then S else S | a;E → b.Эта грамматика неоднозначна, что иллюстрируется на рис. 4.4.nnnnРис. 4.4Определение 4.3. КС-грамматика G = (N , Σ, P , S) называется LL(k)грамматикой для некоторого фиксированного k , если из1) S ⇒ ∗i ωAα ⇒ l ωβα ⇒∗ ωxи2) S ⇒ ∗i ωAα ⇒ l ωγα ⇒∗ ωy ,для которых F IRSTk (x) = F IRSTk (y), вытекает, что β = γ .Говоря менее формально, G будет LL(k)-грамматикой, если для даннойцепочки ωAα ∈ (N ∪ Σ)∗ и первых k символов (если они существуют),выводящихся из Aα, существует не более одного правила, которое можно4.4.
Предсказывающий разбор сверху-вниз89применить к A, чтобы получить вывод какой-нибудь терминальной цепочки,начинающейся с ω и продолжающейся упомянутыми k терминалами.Грамматика называется LL(k)-грамматикой, если она LL(k)-грамматикадля некоторого k . Доказано, что проблема определения, порождает ли грамматика LL-язык, является алгоритмически неразрешимой.Теорема 4.7. КС-грамматика G = (N , Σ, P , S) является LL(k)-грамматикой тогда и только тогда, когда для двух различных правил A → βи A → γ из Р пересечение F IRSTk (βα) ∩ F IRSTk (γα) пусто при всех такихωAα, что S ⇒ ∗l ωAα.Д о к а з а т е л ь с т в о . Н е о б х о д и м о с т ь .
Допустим, что ω , A, α,β и γ удовлетворяют условиям теоремы, а F IRSTk (βα) ∩ F IRSTk (γα) содержит x. Тогда по определению F IRST для некоторых y и z найдутся выводыS ⇒ ∗l ωAα ⇒ l ωβα ⇒ ∗l ωxyиS ⇒ ∗l ωAα ⇒ l ωγα ⇒ ∗l ωxz.(Заметим, что здесь мы использовали тот факт, что N не содержит бесполезных нетерминалов, как это предполагается для всех рассматриваемых грамматик.) Если |x| < k , то y = z = e. Так как β 6= γ , то G не LL(k)-грамматика.Д о с т а т о ч н о с т ь . Допустим, что 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 α| .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
