Обсуждение:Устранение левой рекурсии

Материал из Викиконспекты
Перейти к: навигация, поиск
написать, почему, собственно, надо ее устранять верно ли что для нормального разбора сверху вних
англоязычные термины и источники
а сложность алгоритма какая? --Дмитрий Герасимов 22:31, 7 декабря 2012 (GST)



1)Таким образом, после применения алгоритма все правила вывода имеют вид:

  • [math]A \rightarrow c \alpha [/math], где [math]c[/math] — терминал, [math]A[/math] — произвольный нетерминал;
  • [math]A_i \rightarrow A_j \alpha [/math], где [math]i \lt j[/math], [math]A_i , A_j[/math] — нетерминалы из исходной грамматики;
  • [math]A_i^{\prime} \rightarrow A_j \alpha [/math], где [math]A_i^{\prime}[/math] — новый нетерминал, [math]A_j[/math] — нетерминал из исходной грамматики.

Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:

  • [math]B_i \rightarrow c \alpha [/math], где [math]c[/math] — терминал;
  • [math]B_i \rightarrow B_j \alpha [/math], где [math]i \lt j[/math].

казалось бы это бред