1632
правки
Изменения
м
rollbackEdits.php mass rollback
</ol>
Изначально нетерминал <tex>A</tex> порождает сроки строки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.
===Пример===
<tex>A \to S\alpha{A^{\prime}} \mid S\alpha</tex>
<tex>A^{\prime} \to \alpha{A^{\prime}\mid \alpha}</tex>
<tex>S \to A\beta</tex>
После <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>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.
<tex>A \to S\alpha </tex>
<tex>S \to{S}{\beta} \mid {S}{\alpha}{\gamma} \mid \beta</tex>
Устраняем левую рекурсию для <tex>S</tex>
<tex> S \to\beta{S_1}\mid \beta</tex>
<tex> {S_1} \to\beta{S_1} \mid \alpha\gamma{S_1} \mid {\beta} \mid {\alpha}{\gamma} </tex>
== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [httphttps://aclwebaclanthology.org/anthology-new/A/A00/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Нормальные формы КС-грамматик]]
