Изменения

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

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

456 байт добавлено, 12:42, 3 января 2013
Отмена правки 28697 участника Shagal (обсуждение)
<div>
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и Если есть правило вида <tex>A_i \rightarrow A_j \alpha </tex> и рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \rightarrow \delta_1 | \ldots | \delta_k</tex>. Заменить заменить каждое правило <tex>A_i \rightarrow A_j \alphagamma</tex> на <tex>A_i \rightarrow \delta_1\alphagamma | \ldots | \delta_k\alphagamma</tex>.
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>
Смысл вложенного цикла в томТаким образом, чтобы избавиться от правил вида после применения алгоритма все правила вывода имеют вид: *<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>A_i B_i \rightarrow A_j c \alpha \rightarrow A_k \ldots </tex> точно не придет в , где <tex>c</tex> {{---}} терминал;*<tex>A_iB_i \rightarrow B_j \alpha </tex>, а значит для где <tex>A_ii < j</tex> может быть применен алгоритм удаление непосредственной левой рекурсии.
==Алгоритм устранения левой рекурсии==
228
правок

Навигация