228
правок
Изменения
→Алгоритм устранения произвольной левой рекурсии
После <tex>i</tex> итерации внешнего цикла в любой продукции вида <tex> A_k \Rightarrow A_l\alpha </tex> где <tex> i > k </tex> будет <tex> l > k</tex>.
В результате после каждой итерации растет нижний предел m всех продукций вида <tex>A_i \Rightarrow A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>m \geq i</tex>. Затем из <tex>A_i</tex> устраняется непосредственная левая рекурсия и достигается m > i.
==Пример==
Дана грамматика
<tex>A \Rightarrow S\alpha </tex>
<tex>S \Rightarrow S\beta | A\gamma | b</tex>
Среди продукций <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла продукция <tex> S \Rightarrow A\gamma </tex> переходит в <tex> S \Rightarrow S\alpha\gamma </tex>.
Грамматика имеет вид
<tex>A \Rightarrow S\alpha </tex>
<tex>S \Rightarrow {S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>
Устраняем левую рекурсию для <tex>S</tex>
<tex> S \Rightarrow \beta{S_1}</tex>
<tex> {S_1} \Rightarrow \beta{S_1} | \alpha\gamma{S_1}</tex>
