54
правки
Изменения
много мелких правок
}}
== Постановка задачи ==[[Методы трансляции#Нисходящий разбор|Методы нисходящего разбора]] (англ. ''top-down parsers'') не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.
==Устранение непосредственной левой рекурсии==
==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon varepsilon \rbrace</tex>.
Упорядочим нетерминалы и будем добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \leqslant i</tex>.
Если данное условие выполняется для всех<tex>A_i</tex>, то в грамматике нет <tex>A_i \to^* A_i</tex>, а значит не будет левой рекурсии.
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
удалить <tex>production</tex>
'''for ''' <tex>P \to x_i \in \{A_j \to \delta_1 | \ldots | \delta_k\}</tex>
добавить правило <tex>A_i \to x_i\gamma</tex>
устранить непосредственную левую рекурсию для <tex>A_i</tex>.</div>
Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.
==Пример==
Дана грамматика:
<tex>A \to S\alpha </tex>
<tex>S \to S\beta | \mid A\gamma | \mid \beta</tex>
Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
