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

Материал из Викиконспекты
Версия от 17:00, 8 декабря 2012; 94.25.228.65 (обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
написать, почему, собственно, надо ее устранять верно ли что для нормального разбора сверху вних
англоязычные термины и источники
а сложность алгоритма какая? --Дмитрий Герасимов 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].

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