В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 18
Текст из файла (страница 18)
4.1). Пустые клетки таблицы соответствуют элементу «ошибка».Т а б л и ц а 4.1Нетер-Входной символминалidEE →T E ′E′T*()$E →T E ′E ′→+T E ′E ′→e E ′→eT →F T ′T′F+T →F T ′T ′ →eT ′ →∗F T ′F →idT ′→e T ′→eF →(E)При разборе входной цепочки id + id ∗ id$ анализатор совершает последовательность шагов, описанную в табл.
4.2. Заметим, что анализатор осуществляет в точности левый вывод. Если за уже просмотренными входными символами поместитьсимволы грамматики в магазине, то можно получить в точности левые сентенциальные формы вывода. Дерево разбора для этой цепочки приведено на рис. 4.3.Рис. 4.384Глава 4. Синтаксический анализТ а б л и ц а 4.2МагазинВходE$id + id ∗ id$Выход′TE $id + id ∗ id$ E → T E ′F T ′E′$id + id ∗ id$ T → F T ′id T ′ E ′ $id + id ∗ id$ F → id′′T E$+id ∗ id$E′$+id ∗ id$T′ → e+T E ′ $+id ∗ id$E ′ → +T ET E′$id ∗ id$′FT E $id ∗ id$T → FT′id T ′ E ′ $id ∗ id$F → id′′′∗id$T E$∗F ′ T ′ E ′ $ ∗id$F T ′E′$′′id T E $′′T E$′T ′ → ∗F T ′id$id$F → id$E$$T′ → e$$E′ → e4.4.2.
Функции F IRST и F OLLOW . При построении таблицыпредсказывающего анализатора нам потребуются две функции — F IRSTи F OLLOW .Пусть G = (N , T , P , S) — КС-грамматика. Для α — произвольной цепочки, состоящей из символов грамматики, определим F IRST (α) как множествотерминалов, с которых начинаются строки, выводимые из α. Если α ⇒∗ e, то eтакже принадлежит F IRST (α).Определим F OLLOW (A) для нетерминала A как множество терминаловa, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме грамматики, т. е. множество терминалов a, таких, чтосуществует вывод вида S ⇒ ∗ αAaβ для некоторых α, β ∈ (N ∪ T )∗ . Заметим,что между A и a в процессе вывода могут находиться нетерминальные символы, из которых выводится e.
Если A может быть самым правым символомнекоторой сентенциальной формы, то $ также принадлежит F OLLOW (A).4.4. Предсказывающий разбор сверху-вниз85Рассмотрим алгоритмы вычисления функции F IRST .Алгоритм 4.5. Вычисление F IRST для символов КС-грамматики.Вход. КС-грамматика G = (N , T , P , S).Выход. Множество F IRST (X) для каждого символа X ∈ (N ∪ T ).Метод. Выполнить шаги 1–3:1. Если X — терминал, то положить F IRST (X) = {X}; если X — нетерминал, то положить F IRST (X) = ∅.2. Если в P имеется правило X → e, то добавить e к F IRST (X).3. Пока существуют множества F IRST (X), к которым можно добавлятьновые элементы, выполнять:do {continue = false;Для каждого нетерминала XДля каждого правила X → Y1 Y2 ...Yk{i=1; nonstop = true;while (i 6 k && nonstop){добавить F IRST (Yi ) \ {e} к F IRST (X );if (Были добавлены новые элементы)continue = true;if (e ∈/ F IRST (Yi )) nonstop = false;else i+ = 1;}if (nonstop) {добавить e к F IRST (X);continue = true;}}}while (continue)Алгоритм 4.6.
Вычисление F IRST для цепочки.Вход. КС-грамматика G = (N , T , P , S).Выход. Множество F IRST (X1 X2 . . . Xn ), Xi ∈ (N ∪ T ).Метод. Выполнить шаги 1–3:1. При помощи алгоритма 4.5 вычислить F IRST (X) для каждого X ∈ (N ∪∪ T ).2. Положить F IRST (X1 X2 . . . Xn ) = ∅.3. {i = 1; nonstop = true;while (i 6 n && nonstop){добавить F IRST (Xi ) \ {e} к F IRST (u);/ F IRST (Xi )nonstop = false;if (e ∈86Глава 4.
Синтаксический анализelse i+ = 1;}if (nonstop) {добавить e к F IRST (u);}Рассмотрим алгоритм вычисления функции F OLLOW .Алгоритм 4.7. Вычисление F OLLOW для нетерминалов грамматики.Вход. КС-грамматика G = (N , T , P , S).Выход. Множество F OLLOW (X) для каждого символа X ∈ N .Метод. Выполнить шаги 1–4:1. Положить F OLLOW (X) = ∅ для каждого символа X ∈ N .2. Добавить $ к F OLLOW (S).3. Если в P eсть правило вывода A → αBβ , где α, β ∈ (N ∪ T )∗ , то всеэлементы из F IRST (β), за исключением e, добавить к F OLLOW (B).4.
Пока существуют множества F OLLOW (X), к которым можно добавлятьновые элементы, выполнять:если в P есть правило A → αB или A → αBβ , α, β ∈ (N ∪ T )∗ , гдеF IRST (β) содержит e (β ⇒∗ e), то все элементы из F OLLOW (A) добавить к F OLLOW (B).Пример 4.7. Рассмотрим грамматику из примера 4.3. Для нее:F IRST (E) = F IRST (T ) = F IRST (F ) = {(, id};F IRST (E ′ ) = {+, e};F IRST (T ′ ) = {∗, e};F OLLOW (E) = F OLLOW (E ′ ) = { ), $};F OLLOW (T ) = F OLLOW (T ′ ) = {+, ), $};F OLLOW (F ) = {+, ∗, ), $}.Например, id и левая скобка добавляются к F IRST (F ) на шаге 3 при i = 1,поскольку F IRST (id) = {id} и F IRST (() = {(”} в соответствии с шагом 1. На шаге3 при i = 1, в соответствии с правилом вывода T → F T ′ , к F IRST (T ) добавляютсятакже id и левая скобка. На шаге 2 в F IRST (E ′ ) включается e.При вычислении множеств F OLLOW на шаге 2 в F OLLOW (E) включается $.
На шаге 3, на основании правила F → (E), к F OLLOW (E) добавляется также правая скобка. На шаге 4, примененном к правилу E → T E ′ ,в F OLLOW (E ′ ) включаются $ и правая скобка. Поскольку E ′ ⇒ ∗ e, они такжепопадают и во множество F OLLOW (T ). В соответствии с правилом вывода E → T E ′на шаге 3 в F OLLOW (T ) включаются и все элементы из F IRST (E ′ ), отличныеот e.Мы определили F IRST как множество цепочек длины не более 1. Точнотак же можно определить функцию F IRSTk (α), где k — натуральное число4.4. Предсказывающий разбор сверху-вниз87и α ∈ (N ∪ Σ)∗ : F IRSTk (α) = {w ∈ Σ∗ | либо |w| < k и α ⇒ G w, либо |w| = kи α ⇒ G wx для некоторого x ∈ Σ∗ }.Если α ∈ Σ∗ , то F IRSTk (α) = {w}, где w — это первые k символовцепочки α при |α| > k и w = α при |α| < k .4.4.3.
Конструирование таблицы предсказывающего анализатора.Для конструирования таблицы предсказывающего анализатора по грамматикеG может быть использован алгоритм, основанный на следующей идее. Предположим, что A → α — правило вывода грамматики и a ∈ F IRST (α). Тогдаанализатор делает развертку A по α, если входным символом является a.Трудность возникает, когда α = e или α ⇒∗ e. В этом случае нужно развернуть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)-грамматика.Д о с т а т о ч н о с т ь .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
