Обсуждение:Устранение левой рекурсии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «По содержанию претензий вроде нет, зато есть по оформлению. Заменить все минусы на тире и р...»)
 
 
(не показаны 3 промежуточные версии 3 участников)
Строка 1: Строка 1:
По содержанию претензий вроде нет, зато есть по оформлению. Заменить все минусы на тире и расставить знаки препинания в концах всех предложений.
+
: {{tick}} написать, почему, собственно, надо ее устранять    верно ли что для нормального разбора сверху вних
 +
: {{tick}} англоязычные термины и источники
 +
: {{tick}} а сложность алгоритма какая? --[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:31, 7 декабря 2012 (GST)
 +
 
 +
 
 +
 
 +
 
 +
1)Таким образом, после применения алгоритма все правила вывода имеют вид:
 +
*<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>.
 +
 
 +
казалось бы это бред

Текущая версия на 17:00, 8 декабря 2012

написать, почему, собственно, надо ее устранять верно ли что для нормального разбора сверху вних
англоязычные термины и источники
а сложность алгоритма какая? --Дмитрий Герасимов 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].

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