27
правок
Изменения
Нет описания правки
<tex>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> - непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \epsilon </tex>);</li>
<li> <tex>\beta</tex> - непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex> .</li>
<li>Создадим новый нетерминал <tex>A^\prime \rightarrow \alpha_1A^\prime\, |\, \ldots\, |\, \alpha_nA^\prime | \alpha_1\, |\, \ldots\, |\, \alpha_n</tex> . </li>
</li>
</ol>
==Устранение произвольной левой рекурсии==
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> - множество всех нетерминалов.
<div>
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>.
}
</div>
Таким образом, после применения алгоритма все правила вывода имеют вид:
*<tex>A \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал, <tex>A</tex> - произвольный нетерминал;*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j</tex>, <tex>A_i , A_j</tex> - нетерминалы из исходной грамматики;*<tex>A_i^{\prime} \rightarrow A_j \alpha </tex>, где <tex>A_i^{\prime}</tex> - новый нетерминал, <tex>A_j</tex> - нетерминал из исходной грамматики.
Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:
*<tex>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал;*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>.
==Алгоритм устранения левой рекурсии==
Для произвольной грамматики <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>.
