Изменения

|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная(к.с.КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию'''(англ. ''direct left recursion''), если она содержит правило вида <tex>A \rightarrow to A\alpha</tex>.

|definition=Говорят, что к.с. КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию''' (англ. ''left recursion''), если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.

Опишем процедуру, устраняющую все правила вида <tex>A \rightarrow to A\alpha</tex> , для фиксированного нетерминала <tex>A</tex>.

<li>Запишем все правила вывода из <tex>A</tex> в виде: <tex>A \rightarrow to A\alpha_1\,|\,mid \ldots\,|\,mid A\alpha_n\,|\,mid \beta_1\,|\,mid \ldots\,|\,mid \beta_m </tex>, где

<li> <tex>\alpha</tex> {{- --}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \epsilon varepsilon </tex>);</li><li> <tex>\beta</tex> {{--- }} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>

<li>Заменим правила вывода из <tex>A</tex> на: <tex>A \rightarrow to\beta_1A^\prime\, |\, mid \ldots\, |\, mid \beta_mA^\prime \,|\, mid \beta_1 \,|\, mid \ldots \,|\, mid \beta_m</tex> .</li>

<li>Создадим новый нетерминал <tex>{A^\prime } \rightarrow to \alpha_1Aalpha_1{A^\prime} \, |\, mid \ldots\, |mid \, \alpha_nAalpha_n{A^\prime | } \mid \alpha_1\, |\, mid \ldots\, |\, mid \alpha_n</tex> . </li>

Изначально нетерминал <tex>A</tex> порождает строки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой. ===Пример===Устранение <tex>A \to S\alpha \mid A\alpha</tex> <tex>S \to A\beta</tex> Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>. Новая грамматика: <tex>A \to S\alpha{A^{\prime}} \mid S\alpha</tex> <tex>A^{\prime} \to \alpha{A^{\prime} \mid \alpha}</tex> <tex>S \to A\beta</tex> В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex> ==Алгоритм устранения произвольной левой рекурсии==Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \varepsilon \rbrace</tex>. Упорядочим нетерминалы, например по возрастанию индексов, и будем добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \leqslant i</tex>.Если данное условие выполняется для всех <tex>A_i</tex>, то в грамматике нет <tex>A_i \Rightarrow^* A_i</tex>, а значит не будет левой рекурсии.  Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{- --}} упорядоченное множество всех нетерминалов.  '''for''' <divtex>A_i \in N</tex> '''for ''' <tex>A_j \in \{ N \mid 1 \leqslant j < i = 1 to n {\}</tex> '''for j = 1 ''' <tex>p \in \{ P \mid A_i \to i – 1 {A_j\gamma \}</tex> рассмотреть все правила вывода из удалить продукцию <tex>A_jp</tex>: '''for''' <tex>Q \to x_i \in \{A_j \rightarrow to \delta_1 | \mid \ldots | \mid \delta_k\}</tex> заменить каждое добавить правило <tex>A_i \rightarrow A_j to x_i\gamma</tex> на устранить непосредственную левую рекурсию для <tex>A_i </tex> Если <tex>\rightarrow varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \delta_1to S \gamma | , \ldots | mid \delta_k, \gammavarepsilon </tex>. } устранить непосредственную левую рекурсию для После <tex>i</tex> итерации внешнего цикла в любой продукции внешнего цикла в любой продукции вида <tex>A_k \to A_l\alpha, k < i</tex>, должно быть <tex>l > k</tex>. В результате при следующей итерации внутреннего цикла растет нижний предел <tex>m</tex> всех продукций вида <tex>A_i\to A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>i \leqslant m </tex>. } После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</divtex>, где <tex>j > i</tex>.Инвариант: Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть <tex>{A^\prime}_i </tex> новый нетерминал. Можно заметить, что нет правила вида <tex>j\ldots \to {A^\prime}_i</tex>, где <tex>{A^\prime}_i</tex> итераций внутреннего самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле. Для строгого поддержания инвариантов цикла для можно считать, что созданный на <tex>i</tex> итерации в процессе устранения непосредственной левой рекурсии нетерминал имеет номер <tex>A_{-i}</tex>(т.е. имеет номер, меньший всех имеющихся на данный момент нетерминалов). *для На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex>k j < i</tex> правые части правил вывода из заменяются на <tex>A_kA_i \to \delta_1\gamma \mid \ldots \mid \delta_k\gamma</tex> не начинаются с где <tex>A_1, A_2, A_j \to \delta_1 \mid \ldots \mid \delta_k</tex>. Очевидно, A_kчто одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным. ===Оценка времени работы===Пусть <tex>a_i</tex>*правые части количество правил вывода из для нетерминала <tex>A_i</tex> не начинаются с .Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>A_1O\left(\sum\limits_{A_i \to A_j, A_2j < i} a_j\right) + O(a_i)</tex>, что меньше чем <tex>O\left(\sum\limits_{i=1}^n a_j\ldots right)</tex>, A_jзначит асимптотика алгоритма <tex>O\left(n\sum\limits_{i=1}^n a_j\right)</tex>. ===Худший случай===*правые части правил вывода не начинаются с добавленных алгоритмом Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным. Пример грамматики для которой имеет значение порядок нетерминалов  <tex>A_1 \to 0 \mid 1</tex>A_k ^ <tex>A_{i+1} \primeto {A_i}0 \mid {A_i}1 </tex> для <tex>1 \leqslant i < n</tex>*грамматика не содержит ε-правил(проверяется индукцией Упорядочим множество нетерминалов по парам возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>(i</tex>,jа значит размер грамматики будет экспоненциальным.===Порядок выбора нетерминалов==={{Определение|definition=Говорят, что нетерминал <tex>X</tex> {{---}} '''прямой левый вывод''' (англ. ''direct left corner'')из <tex>A</tex>, если существует правило вида <tex>A \to X\alpha</tex>.}} {{Определение|definition='''Левый вывод''' (англ. ''left corner''){{---}} [[Транзитивное_отношение|транзитивное]], [[Рефлексивное_отношение|рефлексивное]] замыкание отношения «быть прямым левым выводом».}} Во внутреннем цикле алгоритма для всех нетерминалов <tex>A_i</tex> и <tex>A_j</tex>, таких что <tex>j < i</tex> и <tex>A_j</tex> {{---}} прямой левый вывод из <tex>A_i</tex> заменяем все прямые левые выводы <tex>A_j</tex> из <tex>A_i</tex> на все выводы из <tex>A_j</tex>.

Таким образом, после применения алгоритма все правила вывода имеют вид*Это действие удаляет левую рекурсию только если <tex>A \rightarrow c \alpha </tex>, где <tex>cA_i</tex> {{-- терминал, <tex>A</tex> - произвольный }} леворекурсивный нетерминал*и <tex>A_i \rightarrow A_j \alpha </tex>, где содержится в выводе <tex>i < jA_i</tex>, (то есть <tex>A_i , A_j</tex> {{- нетерминалы --}} левый вывод из исходной грамматики*<tex>A_i^{\prime} \rightarrow A_j \alpha </tex>, где в то время как <tex>A_i^{\prime}A_j</tex> {{-- новый нетерминал, -}} левый вывод из <tex>A_jA_i</tex> - нетерминал из исходной грамматики).

Если теперь перенумеровать нетерминалыПерестанем добавлять бесполезные выводы, сохранив порядок для старых и присвоив всем новым меньшие номеракоторые не участвуют в удалении левой рекурсии, то все правила будут иметь вид*упорядочив нетерминалы так: если <tex>B_i \rightarrow c \alpha j < i</tex>, где и <tex>cA_j</tex> {{-- терминал*-}} прямой левый вывод из <tex>B_i \rightarrow B_j \alpha A_i</tex>, где то <tex>i A_i</tex> {{---}} левый вывод из < jtex>A_j</tex>.Упорядочим их по уменьшению количества различных прямых левых выводов из них.

Для произвольной грамматики <tex>A \Gamma</tex> левую рекурсию можно устранить следующим образом:#Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>#Воспользуемся алгоритмом устранения произвольной левой рекурсии#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow to S \, | \, \epsilon alpha </tex>

Грамматика имеет вид  <tex>A \to S\alpha </tex> <tex>S \to{S}{\beta} \mid {S}{\alpha}{\gamma} \mid \beta</tex> Устраняем левую рекурсию для <tex>S</tex> <tex> S \to\beta{S_1}</tex> <tex> {S_1} \to\beta{S_1} \mid \alpha\gamma{S_1} \mid {\beta} \mid {\alpha}{\gamma} </tex> ==ЛитератураСм. также ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]* [[Удаление_eps-правил_из_грамматики | Удаления <tex> \varepsilon </tex>-правил из грамматики]] == Источники информации ==