Изменения

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

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

578 байт убрано, 00:07, 17 января 2016
Алгоритм устранения произвольной левой рекурсии
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
стало:
<div>
for <tex>A_i \in N</tex>
добавить правило <tex>A_i \to x_i\gamma</tex>
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>
было:
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leqslant j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>
54
правки

Навигация