Изменения
Нет описания правки
Для произвольной грамматики <tex>\Gamma</tex> левую рекурсию можно устранить следующим образом:
#Воспользоваться [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>
#Воспользоваться алгоритмом для новой грамматикиустранения левой рекурсии
#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавить новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>
for i = 1 to n {
for j = 1 to i – 1 {
рассмотреть все правила вывода из <tex>A_j</tex> : <tex>A_j \rightarrow \delta_1 | \ldots | \delta_k</tex> заменить каждое правило <tex>A_i \rightarrow A_j \gamma</tex> на <tex>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</tex>
}
устранить непосредственную левую рекурсию для <tex>A_i</tex>
