Изменения

Перейти к: навигация, поиск

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

463 байта добавлено, 15:06, 11 июня 2016
Алгоритм устранения произвольной левой рекурсии
После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть <tex>{A^\prime}_i </tex> новый нетерминал. Можно заметить, что нет правила вида <tex>\ldots \to {A^\prime}_i</tex>, где <tex>{A^\prime}_i</tex> самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле. Для строгого поддержания инвариантов цикла можно считать, что созданный на <tex>i</tex> итерации в процессе устранения непосредственной левой рекурсии нетерминал имеет номер <tex>A_{-i}</tex> (т.е. имеет номер, меньший всех имеющихся на данный момент нетерминалов).
На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma \mid \ldots \mid \delta_k\gamma</tex> где <tex>A_j \to \delta_1 \mid \ldots \mid \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.
292
правки

Навигация