Разработка компиляторов
Алгоритм устранения леворекурсивности
Опишем алгоритм устранения непосредственной леворекурсивности. Пусть 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
Для полученной грамматики может быть реализован метод рекурсивного спуска.
