Изменения

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

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

1086 байт убрано, 11:56, 7 января 2013
Алгоритм устранения произвольной левой рекурсии
for все нетерминалы <tex>A_i</tex>
for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \rightarrow Rightarrow \delta_1 | \ldots | \delta_k</tex>. заменить каждое правило <tex>A_i \rightarrow Rightarrow A_j \gamma</tex> на <tex>A_i \rightarrow Rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</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>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> {{---}} терминал;*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>. После <tex>i^ой</tex> итерации внешнего цикла в любой продукции вида <tex>A_k \rightarrow Rightarrow A_l\alpha</tex> где </tex> i > k </tex> будет <tex> l > k</tex>.В результате после каждой итерации растет нижний предел m, таких, что существует продукция всех продукций вида <tex>A_i \rightarrow Rightarrow A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>m \geq i</tex>. Затем из <tex>A_i</tex> устраняется непосредственная левая рекурсия и достигается m > i.
#Воспользуемся алгоритмом ''устранения произвольной левой рекурсии''.
#Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \varepsilon </tex>.
 
 
==Литература==
228
правок

Навигация