Изменения

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

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

18 байт добавлено, 02:35, 27 ноября 2011
Нет описания правки
===Устранение произвольной левой рекурсии===
Пусть множество всех нетерминалов <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>j</tex> итераций внутреннего цикла для <tex>i</tex>
*для <tex>k < i</tex> правые части правил вывода из <tex>A_k</tex> не начинаются с <tex>A_1, A_2, \ldots , A_k</tex>
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/13521»

Навигация