Обсуждение:Устранение левой рекурсии — различия между версиями
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 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)Таким образом, после применения алгоритма все правила вывода имеют вид:
- , где — терминал, — произвольный нетерминал;
- , где , — нетерминалы из исходной грамматики;
- , где — новый нетерминал, — нетерминал из исходной грамматики.
Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:
- , где — терминал;
- , где .
казалось бы это бред
