Левая факторизация КС-грамматики

End

For j:= 1 to i-1 do begin

Алгоритм устранение левой рекурсии, не являющейся непосредственной рекурсией

Устранение прямой рекурсии в общем случае

1. Группируем - продукции в виде

2. Заменим эти - продукции

Переменная порождает те же строки, но без левой рекурсии.

Гарантированно работает с грамматикой, не имеющей циклов (т.е. ) и -правил.

Вход. КС-грамматика без циклов и -правил.

Выход. Эквивалентная грамматика без левой рекурсии.

Алгоритм.

1. Расположить переменные в некотором порядке: .

2. For I:= 1 to n do begin

Заменить каждую продукцию вида

продукциями ,

где - все текущие -продукции.

Устранить непосредственную левую рекурсию.

End.

Пример. …

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

Пример. Есть два правила

Обнаружив во входном потоке терминал , мы не в состоянии тут же выбрать одно из этих правил.

В общем случае, если - два -правила. Какую правую часть выбрать?

Перепишем правила в виде:

Дата добавления: 2013-12-14