3.4. Левый и правый проходы, левое и правое порождения

 

 
  Левый и правый проходы определяются прямым или обратным просмотром цепочки. На практике чаще применяют левые проходы.
Левое порождение генерируется, если в каждый момент раскрывается самый левый нетерминал, правое порождение соответственно моделируется, елси в каждый момент раскрывается самый правый нетерминал.
В соответствие с типами проходов и порождений различают типы алгоритмов: LL, LR, RL, RR.
Часто, левые и правые порождения невозможно определить однозначно, в таких случаях говорят, что грамматика неоднозначна. На практике неоднозначность обычно приводит к неопределенности в порядке выполнения арифметических операций. На практике, для восстановления правильного порядка применяются дополнительные методы, т.е. непосредственно грамматика помогает только проверить отсутствие синтаксических ошибок в выражениях. Описания операторов однозначны.


Построение LL-анализатора по грамматике.
Идея детерминированного LL-анализатора: цепочка просматривается слева направо (от начала программы к концу), моделируется левое порождение, т.е. применяется нисходящий анализ. Детерминированность алгоритма пытаемся обеспечить на основании текущего символа входной цепочки, и возможно нескольких символов за текущим. Обратим внимание, что неоднозначными могут быть только операции замены нетерминала в стеке.
Рассмотрим подробнее идею на примере:

S -> S+S| S*S| (S)|a
a+(a*a)+(a*a)+a

Глядя на эту грамматику, очень трудно предположить, как сделать первый переход в зависимости от символа входной цепочки (к-й очевидно может быть только символом “a”). Главной причиной неудобства является левая рекурсия, т.е. возможность вывода нетерминала из самого себя без сдвига по входной цепочке за конечное число применения Л-переходов.

Примеры левой рекурсии: S->S+S S->S*S (за 1 переход)

S → Aa A → Bb | f B → Cc C → Dd | e D → Az
Здесь леворекурсивный цикл, вовлекающий A, B, C, D.
Чтобы заменить этот цикл прямой левой рекурсией, упорядочим
нетерминалы следующим образом: S, A, B, C, D.
Рассмотрим все порождающие правила вида
Xi → Xj γ,
где Xi и Xj – нетерминалы, а Фи – смешанная цепочка. В отношении правил, для которых j ≥ i, никакие действия не производятся. Однако это неравенство не может выдерживаться для всех правил, если есть левый рекурсивный цикл. При выбранном нами порядке мы имеем дело с единственным нарушением в правиле:
D → Az
так как A предшествует D в этом упорядочении. Теперь начнем замещать A, пользуясь всеми правилами, имеющими A в левой части. В результате получаем
D → Bbz | fz
Поскольку B предшествует D в упорядочении, процесс повторяется:
D → Ccbz | fz
Затем он повторяется еще раз:
D → Ddcbz| ecbz | fz
Теперь грамматика выглядит так:
S → Aa C→ Dd| e
A → Bb |f D → Ddcbz |ecBz | fz
B → Cc


Далее, рассмотрим правила для D. Очевидно, что порождаемая из D цепочка будет начинаться на ecBz или fz, а далее от 0 до бесконечности раз будет повторятся подцепочка dcbz. Эту закономерность можно описать и так:
D -> ecBzE|fzE|ecBz|fz
E -> dcbzE|dcbz
Таким образом, мы избавились от левой рекурсии за счет добавления одного нетерминала Е в грамматику. Действуя подобным образом, мы можем любую КС-грамматику избавить от левой рекурсии.

Пример. Избавим от левой рекурсии и преобразуем к удобному виду грамматику:
S->S+S|S*S|(S)|a

S->(S)+S|(S)*S|a+S|a*S|(S)|a

S->A+S|A*S|A
A->(S)|a

S->AB
A->(S)|a
B->+S|*S|л

S->AB
A->(S)|a
B->+AB|*AB|л

S->(S)B|aB
A->(S)|a
B->+AB|*AB|л

Теперь, мы можем составить таблицу рекомендуемых применений правил в зависимости от входной цепочки.

+ * ( ) a Исч.
S (S)B aB
A (S) a
B +AB *AB л л л л

Таким образом, у нас имеется LL(1)-анализатор. В общем случае, мы можем построить LL(k)-анализатор (в этом случае столбцы будут соответствовать различным последовательностям из k терминальных символов. Очевидно, что для того, что строить таблицу LL(1)-анализатора удобно по грамматике, где правила приведены к виду:

A->a фи (нормальная форма Грейбаха)

В этом случае, LL(1)-анализатор можно построить, если первые терминалы правых частей различных правил не совпадают при совпадении нетерминалов в левой части
Для построения LL(2)-анализатора (и исследовании грамматики на ее возможность) соответственно следует привести грамматику к виду

A->abФи

И Т.д
Очевидный способ аналаза текста программы на отсутствии синтаксических ошибок – построение LL(k)-анализатора с минимально-возможном значением k и в соответствие с таблицей реализация МА с наложенной на него стратегией выбора применяемых в случае неодназначности применяемых переходов с соответствие с таблицей анализатора (неодназночность может возникнуть, как отмечалась выше, только если в вершине стека нетерминал).