Рекурсивный спуск с возвратами

Алгоритм устранения леворекурсивности

Леворекурсивные грамматики

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

Предположим, что необходимо построить анализатор языка, порождаемого следующей грамматикой:

E → E + T | E – T | T

T → T * F | T / F | F

F → num | (E)

Терминалы множества FIRST(T) принадлежат также множеству FIRST(E+T), поэтому нельзя однозначно определить последовательность вызовов процедур, которую необходимо выполнить при анализе входной цепочки. Проблема заключается в том, что нетерминал E встречается на первой позиции правой части правила, левая часть которого также E. В такой ситуации нетерминал E называется непосредственно леворекурсивным.

Нетерминал A КС-грамматики G называется леворекурсивным, если в грамматике существует вывод A =>* Aw.

Грамматика, имеющая хотя бы одно леворекурсивное правило, не может быть LL(1) -грамматикой.

С другой стороны, известно, что каждый КС-язык определяется хотя бы одной нелеворекурсивной грамматикой.

Пусть G = (N, T, P, S) – КС-грамматика и правило A→Aw₁ | Aw₂ | … | Aw_n | v₁ | v₂ | … | v_m представляет собой все правила из P, содержащие A в левой части, причем ни одна из цепочек v_i не начинается с нетерминала A.

Добавим к множеству N еще один нетерминал A' и заменим правила, содержащие A в левой части, на следующие:

A → v₁ | v₂ | … | v_m | v₁A’ | v₂ A’ | … | v_m A'

A’ → w₁ | w₂ | … | w_n | w₁ A’ | w₂ A’ | … | w_n A'

Можно доказать, что полученная грамматика эквивалентна исходной.

В результате применения этого преобразования к приведенной выше грамматике, описывающей арифметические выражения, получим следующую грамматику:

E → T | TE'

E' → +T | +TE'

T → F | FT'

T'→ *F | *FT'

F → (E) | num

Нетрудно показать, что получившаяся грамматика обладает свойством LL(1).

Еще одна подобная проблема связана с тем, что два правила для одного и того же нетерминала начинаются одними и теми же символами.

Например,

S → if E then S else S

S → if E then S

В этом случае добавим еще один нетерминал, который будет соответствовать различным окончаниям этих правил. Получим следующие правила:

S → if E then S S’

S' →

S'→ else S

Для полученной грамматики может быть реализован метод рекурсивного спуска.

Для того, чтобы иметь возможность применить метод рекурсивного спуска, необходимоыпреобразовать грамматику к виду, в котором множества FIRST не пересекаются, что является сложным процессом, поэтому на практике используется прием, называемый рекурсивным спуском с возвратами.

Для этого лексический анализатор представляется в виде объекта, у которого помимо традиционных методов scan, next и т. д., есть также копирующий конструктор. Затем во всех ситуациях, где может возникнуть неоднозначность, перед началом разбора надо запомнить текущее состояние лексического анализатора (т. е. сделать копию лексического анализатора) и продолжить разбор текста, считая, что имеем дело с первой из возможных в данной ситуации конструкций. Если этот вариант разбора заканчивается неудачей, то надо восстановить состояние лексического анализатора и пытаться заново разобрать тот же самый фрагмент с помощью следующего варианта грамматики и т. д. Если все варианты разбора заканчиваются неудачно, то сообщается об ошибке.

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

Дата добавления: 2014-01-11