И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 12
Текст из файла (страница 12)
Рассмотренные выше s-грамматики являются q-грамматиками, обратное неверно.Итерации в КС-грамматикахПри описании синтаксиса языков программирования часто встречаются правила, описывающие последовательность однотипных конструкций, отделенных друг от друга какимлибо знаком-разделителем (например, список идентификаторов при описании переменных,список параметров при вызове процедур и функций и т. п.). Такие правила обычно имеютвид: L → a | a, LВместо обычных правил КС-грамматик для описания синтаксиса языков программирования нередко используют их модификации, например БНФ 22).
В БНФ, в частности, допускаются конструкции вида {α}, где фигурные скобки — это спецсимволы для выделенияфрагмента α, который может отсутствовать или повторяться произвольное число раз. Называют такую конструкцию итерацией.С помощью итерации грамматику L → a | a, L можно переписать так: L → a {, a}.Наоборот, если в грамматике есть правило вида X → α{β}γ, содержащее итерацию{β}, то его можно заменить серией эквивалентных правил без итерации {β}:X → αYγY → βY | ε,где Y — новый нетерминальный символ, добавляемый в алфавит нетерминалов грамматики.Чтобы применить метод рекурсивного спуска для грамматики L → a {, a}, преобразуем эту грамматику в эквивалентную без итерации:L → aMM → ,aM|ε22)Бэкуса-Наура формула.61Элементы теории трансляции / Синтаксический анализМетод применим к данной грамматике, так как first ( , a ) ∩ follow (M ) = ∅.Можно построить систему рекурсивных процедур по преобразованной грамматике, нолучше, убедившись, что для преобразованной грамматики метод применим, вернуться к начальному варианту с итерацией.Реализовать итерацию {β} (где β = bβ′, b ∈ T ) удобно с помощью цикла: «пока текущий символ равен b, считать со входа следующий символ и проанализировать цепочку β′».Для правила с итерацией L → a {, a} процедура-анализатор реализуется так:void L (){if ( c != 'a' )throw c;gc ();while ( c == ',' ){gc ();if ( c != 'a' )throw c;elsegc ();}}Рассмотрим пример еще одной грамматики.Gsequence:S → LB⊥L → a {, a}B → ,bЕсли для этой грамматики сразу написать анализатор, не убедившись в применимостиметода к преобразованной (без итерации) грамматике, то цепочка а,а,а,b будет признанатаким анализатором ошибочной, хотя в действительности а,а,а,b принадлежит порождаемому Gsequence языку.
Это произойдет потому, что процедура L( ) захватит чужую запятую —ту, что выводится из B, и далее не обнаружив символ а, сообщит об ошибке.Следует сначала проверить применимость метода, исключив из грамматики итерациюрассмотренным выше способом:S → LB⊥L → aMM → ,aM|εB → ,bКак видим, first (, a) ∩ follow (M ) = { , } ≠ ∅ и поэтому метод рекурсивного спуска неприменим 23). Можно попытаться поискать другую эквивалентную грамматику, к которой методприменим.
Некоторые полезные для этого эквивалентные преобразования грамматик будут23)Если бы в Gsequence последовательность терминалов, перечисляемых через запятую, завершалась отличнымот запятой символом (например, точкой с запятой), как это обычно и бывает в реальных языках программирования, то метод рекурсивного спуска был бы применим.62Элементы теории трансляции / Синтаксический анализрассмотрены ниже. Однако, как следует из утверждения 12, успех в поиске эквивалентнойграмматики, для которой метод применим, не гарантирован.Преобразования грамматикЕсли грамматика не удовлетворяет требованиям применимости метода рекурсивногоспуска, то можно попытаться преобразовать ее, т. е. получить эквивалентную грамматику,пригодную для анализа этим методом.(1) Если в грамматике есть нетерминалы, правила вывода которых непосредственнолеворекурсивны, т.
е. имеют вид:A → Aα1 | ... | Aαn | β1 | ... | βm,+*где αi ∈ (T ∪ N ) для i = 1, 2, ..., n; βj ∈ (T ∪ N ) для j = 1, 2, ..., m, то в таком случае применять метод рекурсивного спуска нельзя, поскольку first(Aαi) ∩ first(Aαk) ≠ ∅ для некоторыхi ≠ k, или βj = ε для некоторого j и first (Аαi) ∩ follow (A) ≠ ∅ для i = 1, 2, ..., n.Левую рекурсию всегда можно заменить правой:A → β1 A′ | ... | βm A′A′ → α1 A′ | ... | αn A′ | εБудет получена грамматика, эквивалентная данной, т.к.
из нетерминала A попрежнему выводятся цепочки вида βj {αi}, где i = 1, 2, ..., n; j = 1, 2, ..., m.(2) Если в грамматике есть нетерминал, у которого несколько правил вывода начинаются одинаковыми терминальными символами, т. е. имеют видA → aα1 | aα2 | ... | aαn | β1 | ... |βm,*где a ∈ T ; αi, βj ∈ (T ∪ N ) , βj не начинается с a, i = 1, 2,..., n, j = 1, 2,..., m, то непосредственно применять метод рекурсивного спуска нельзя, т. к. first(aαi) ∩ first(aαk) ≠ ∅ для i ≠ k.Можно преобразовать правила вывода данного нетерминала, объединив правила с общиминачалами в одно правило:A → aA′ | β1 | ... | βmA′ → α1 | α2 | ...
| αnБудет получена грамматика, эквивалентная данной.(3) Если в грамматике есть нетерминал, у которого несколько правил вывода, и срединих есть правила, начинающиеся нетерминальными символами, т. е. имеют вид:A → B1α1 | ... | Bnαn | a1β1 | ... | amβmB1 → γ11 | ... | γ1k…Bn → γn1 | ...
| γnp,*где Bi ∈ N; aj ∈ T; αi, βj, γij ∈ ( T ∪ N ) , то можно заменить вхождения нетерминаловBi их правилами вывода в надежде, что правила нетерминала A станут удовлетворять условиям применимости метода рекурсивного спуска:A → γ11α1 | ... | γ1kα1 | ... | γn1αn | ... | γnpαn | a1β1 | ... | amβm63Элементы теории трансляции / Синтаксический анализ(4) Если есть правила с пустой альтернативой вида:A → α1 A | ... | αn A | β1 | ...
| βm| εB → αAβи first(A) ∩ follow(A) ≠ ∅ (из-за вхождения А в правила вывода для В), то можно построитьтакую грамматику:B → αA′A′ → α1A′ | ... | αn A′ | β1β | ... | βmβ | βПолученная грамматика будет эквивалентна исходной, т. к. из B по-прежнему выводятся цепочки вида α {αi} βj β либо α {αi} β.Однако правило вывода для нетерминального символа A′ будет иметь альтернативы,начинающиеся одинаковыми терминальными символами (т. к.
first(A) ∩ follow(A) ≠ ∅); следовательно, потребуются дальнейшие преобразования, и успех не гарантирован.Пример. Рассмотрим грамматику Gorigin:GoriginS → fASd | εA → Aa | Ab | dB | fB → bcB | εfirst(Aa) = first(Ab) = {d, f }first(bcB) = {b}, follow(B) = {a, b, d, f }Условия применимости метода рекурсивного спуска не выполняются для Gorigin. Спомощью преобразований приведем эту грамматику к каноническому виду для рекурсивногоспуска. Будем подчеркивать не удовлетворяющие каноническому виду правила и припереходе к новой грамматике указывать номер примененного преобразования ⇒(i) , 1 ≤ i ≤ 4 :Gorigin:SAB→ fASd | ε→ Aa | Ab | dB | f→ bcB | εGtransform1:⇒(1)SAA'B→→→→fASd | εdBA' | fA'aA' | bA' | εbcB | ε⇒(4)first(S) = { f }, follow( S ) = { d },first (S) ∩ follow(S) = ∅;first(A') = {a, b}, follow(A') ={ f, d }, first (A') ∩ follow(A') = ∅;first(B) ={b}, follow(B) ={a, b, f, d }, first(B) ∩ follow(B) ={b}≠ ∅.Gtransform2:⇒(4)64SAB'A'→ fASd | ε→ dB' | fA'→ bcB' | A'→ aA' | bA' | εGtransform3:⇒(3)SAB'A'→→→→fASd | εdB' | fA'bcB' | aA' | bA' | εaA' | bA' | εЭлементы теории трансляции / Синтаксический анализGtransform4:⇒(2)Gobject:SAB'CA'→ fASd | ε→ dB' | fA'→ bC | aA' | ε→ cB' | A'→ aA' | bA' | ε⇒(3)SAB'CA'→→→→→fASd | εdB' | fA'bC | aA' | εcB' | aA' | bA' | εaA' | bA' | εfirst(B') ={a, b}, follow(B') ={f, d}; first(B') ∩ follow(B') = ∅;first(A') ={a, b}, follow(A') = {f, d}; first(A') ∩ follow(A') = ∅;first(C) ={a, b, c}, follow(C) ={f, d}; first(C) ∩ follow(C) = ∅.Т.
е. получили эквивалентную грамматику Gobject, к которой применим метод рекурсивногоспуска. Gobject удобна для построения системы рекурсивных процедур, так как ее правилаимеют канонический вид.Задача разбора для неоднозначных грамматикДля неоднозначных грамматик задача синтаксического анализа (задача разбора) может быть поставлена двумя основными способами.(1) Даны КС-грамматика G и цепочка x.
Требуется проверить: x ∈ L(G)? Если да, топостроить все деревья вывода для x (или все левые выводы для x, или все правые выводы дляx) 24).Для решения этой задачи можно обобщить метод рекурсивного спуска, чтобы он работал с возвратами, пробуя различные подходящие альтернативы.(2) Даны КС-грамматика G и цепочка x.
Требуется проверить: x ∈ L(G)? Если да, топостроить одно дерево вывода для x (возможно, наиболее подходящее в некотором смысле).При такой постановке для некоторых неоднозначных грамматик удается модифицировать обычный РС-метод без возвратов так, что получаемый анализатор корректен, и строит наиболее подходящее в некотором смысле дерево.Неприменимость метода рекурсивного спуска в «чистом» виде для неоднозначныхграмматик обусловлена невозможностью однозначно спрогнозировать выбор альтернативыпри разборе цепочки (прогноз может состоять из нескольких подходящих альтернатив). Модификация метода состоит в следущем: одна из альтернатив объявляется «наиболее подходящей», и процедура анализа всегда выбирает эту альтернативу, игнорируя другие.Рассмотрим пример, иллюстрирующий ситуацию с условными (полным и сокращенным) операторами в языке Паскаль.Gif-then = 〈 {if, then, else, a, b}, {S }, P, S, S′ 〉,где P = { S → if b then S S′ | a ; S′ → else S | ε }.
В этой грамматике прогноз для S′ по else неоднозначен, так как first(else S) ∩ follow(S′) ={else}≠ ∅. Для цепочки if b then if b then a else aможно построить два различных дерева вывода, показанных на рис. 101 (а, б).Если при построении анализатора отдать предпочтение непустой альтернативе для S′,то такой анализатор построит дерево, изображенное на рис. 101 (а), в котором else соотносится с ближайшим (на его уровне вложенности) if, что соответствует правилам, принятым в24)Цепочка в неоднозначной грамматике может иметь и бесконечно много деревьев вывода. В таком случаеможно ограничиться построением всех деревьев, высота которых не превосходит некоторой константы.65Элементы теории трансляции / Синтаксический анализязыке Паскаль при разрешении подобных неоднозначностей в комбинациях условных операторов.Итак, мы модифицировали РС-метод для данного примера неоднозначной грамматики, отдав предпочтение одной из альтернатив (и получив тем самым подходящее для семантики языка Паскаль дерево разбора).Нетрудно убедиться, что получаемый для грамматики Gif-then анализатор корректен:он не зацикливается, распознает правильные цепочки и отвергает неправильные.Отметим, что подобная модификация РС-метода не всегда приводит к построениюкорректного анализатора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
