Левая факторизация

Пример 13

Устранение левой рекурсии

Грамматика является леворекурсивной, если в ней имеется нетерминал А, такой, что существует порождение А => Аα для некоторой строки α. Методы нисходящего разбора не в состоянии работать с леворекурсивными грамматиками, поэтому требуется преобра­зование грамматики, которое устранило бы из нее левую рекурсию. Рассмотрим общий случай. Леворекурсив­ная пара продукций А à Аα | β может быть заменена нелеворекурсивными продукциями

A à βА'

А' à αА' | λ

без изменения множества строк, порождаемых из А. Этого правила достаточно для мно­гих грамматик.

Рассмотрим следующую грамматику для арифметических выражений.

E à E+T | Т

T à t*f | f (5.10)

F à (E) | id

Устранив непосредственную левую рекурсию (продукции вида А —>Аα) из продукций для Е и Т, получим

E à TE'

E' à +TE' | λ

T à FT'

T' à *FT' | λ

F à (E) | id

Общее количество А-продукций роли не играет. Можно устранить непосредственную левую рекурсию из них с помощью следующей технологии. Вначале группируем А-продукции.

A à Aα₁ | Aα₂|…| Aα_m| β ₁| β ₂|…| β _n

где β_i не начинаются с А. Затем заменим эти А -продукции

A' -> α₁А' | α₂А' |…| α_mА' | λ

Нетерминал А порождает те же строки, что и ранее, но без левой рекурсии. Эта процеду­ра устраняет все непосредственные левые рекурсии из продукций для А и А' (при усло­вии, что ни одна строка α_i не является λ), но не устраняет левую рекурсию, вызванную двумя или более шагами порождения. Например в грамматике

S à Аа | b

А à Ac | Sd | λ (5.11)

Нетерминал S леворекурсивен, поскольку S => Аа => Sda, но эта рекурсия не является не­посредственной.

Алгоритм устранения левой рекурсии гаран­тированно работает с грамматиками, не имеющими циклов и λ –продукций. Из грамматики могут быть также удалены и цик­лы, и λ –продукции.

Левая факторизация представляет собой преобразование грамматики в пригодную для предиктивного анализа. Основная идея левой факторизации заключается в том, что когда не ясно, какая из двух альтернативных продукций должна использоваться для нетерминала А, A-продукции можно переписать так, чтобы отложить принятие решения до тех пор, пока из входного потока не будет прочитано достаточно символов для правильного выбора.

Например, если есть две продукции

stmt à if expr then stmt else stmt

| if expr then stmt (5.12)

то, обнаружив во входном потоке if, нельзя тут же выбрать ни одну из них. В общем случае, если А à αβ₁, | αβ₂ представляют собой две A-продукции и входной поток начинается с непустой строки, порождаемой α, то нельзя сказать какая продукция будет использоваться первая или вторая продукция. Однако можно отложить решение, расширив А до αА'. В этом случае, после того как рассмотрен входной поток, выводимый из α, работаем с А', расширяя его до β₁ или β₂. Таким образом, будучи левофакторизованными, исходные продукции становятся

А à αА'

А' à β₁| β₂

Дата добавления: 2014-12-27