Разработка компиляторов



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


Опишем алгоритм устранения непосредственной леворекурсивности. Пусть G = (N, T, P, S) - КС-грамматика и правило представляет собой все правила из P, содержащие A в левой части, причем ни одна из цепочек vi не начинается с нетерминала A . Добавим к множеству N еще один нетерминал A' и заменим правила, содержащие 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

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




Содержание  Назад  Вперед