Устранение левой рекурсии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(улучшил всевдокод)
(много мелких правок)
Строка 14: Строка 14:
 
<ol>
 
<ol>
 
<li>Запишем все правила вывода из <tex>A</tex> в виде:  
 
<li>Запишем все правила вывода из <tex>A</tex> в виде:  
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
+
<tex>A \to A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m </tex>, где
 
<ul>
 
<ul>
 
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
 
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
 
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
 
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
 
</ul>
 
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\,  |\\beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m</tex>.</li>
+
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime \mid \ldots\ \mid \beta_mA^\prime \mid \beta_1 \mid \ldots \mid \beta_m</tex>.</li>
  
<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime},  |\\ldots\, |\, \alpha_n{A^\prime} | \alpha_1\,  |\,  \ldots\, |\, \alpha_n</tex>. </li>
+
<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime} \mid \ldots \mid \alpha_n{A^\prime} \mid \alpha_1 \mid \ldots \mid \alpha_n</tex>. </li>
 
</li>
 
</li>
 
</ol>
 
</ol>
Строка 28: Строка 28:
  
 
===Пример===
 
===Пример===
<tex>A \to S\alpha | A\alpha</tex>
+
<tex>A \to S\alpha \mid A\alpha</tex>
  
 
<tex>S \to A\beta</tex>
 
<tex>S \to A\beta</tex>
Строка 36: Строка 36:
 
Новая грамматика:
 
Новая грамматика:
  
<tex>A \to S\alpha{A^{\prime}} | S\alpha</tex>
+
<tex>A \to S\alpha{A^{\prime}} \mid S\alpha</tex>
  
 
<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>
 
<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>
Строка 48: Строка 48:
  
 
Упорядочим нетерминалы, например по возрастанию индексов, и будем добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \leqslant i</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>A_i</tex>, то в грамматике нет <tex>A_i \Rightarrow^* A_i</tex>, а значит не будет левой рекурсии.  
  
 
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
 
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
Строка 56: Строка 56:
 
       '''for''' <tex>p \in \{ P \mid A_i \to A_j\gamma \}</tex>
 
       '''for''' <tex>p \in \{ P \mid A_i \to A_j\gamma \}</tex>
 
         удалить продукцию <tex>p</tex>  
 
         удалить продукцию <tex>p</tex>  
         '''for''' <tex>Q \to x_i \in \{A_j \to \delta_1 | \ldots | \delta_k\}</tex>
+
         '''for''' <tex>Q \to x_i \in \{A_j \to \delta_1 \mid \ldots \mid \delta_k\}</tex>
 
           добавить правило <tex>A_i \to x_i\gamma</tex>
 
           добавить правило <tex>A_i \to x_i\gamma</tex>
 
     устранить непосредственную левую рекурсию для <tex>A_i</tex>
 
     устранить непосредственную левую рекурсию для <tex>A_i</tex>
  
Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.
+
Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, \mid \, \varepsilon </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_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>.
Строка 67: Строка 67:
 
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть <tex>{A^\prime}_i </tex> новый нетерминал. Можно заметить, что нет правила вида <tex>\ldots \to {A^\prime}_i</tex>, где  <tex>{A^\prime}_i</tex> самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле.  
 
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть <tex>{A^\prime}_i </tex> новый нетерминал. Можно заметить, что нет правила вида <tex>\ldots \to {A^\prime}_i</tex>, где  <tex>{A^\prime}_i</tex> самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле.  
  
На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.
+
На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma \mid \ldots \mid \delta_k\gamma</tex> где <tex>A_j \to \delta_1 \mid \ldots \mid \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.
  
===Асимптотика===
+
===Оценка времени работы===
 
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
 
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
 
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.
 
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.
  
 +
===Худший случай===
 
Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.
 
Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.
  
 
Пример грамматики для которой имеет значение порядок нетерминалов
 
Пример грамматики для которой имеет значение порядок нетерминалов
  
<tex>A_1 \to 0 | 1</tex>
+
<tex>A_1 \to 0 \mid 1</tex>
  
<tex>A_{i+1} \to {A_i}0 | {A_i}1 </tex>  для <tex>1 \leqslant i < n</tex>
+
<tex>A_{i+1} \to {A_i}0 \mid {A_i}1 </tex>  для <tex>1 \leqslant i < n</tex>
  
 
Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным.
 
Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным.
 
+
===Порядок выбора нетерминалов===
 
{{Определение
 
{{Определение
 
|definition=Говорят, что нетерминал <tex>X</tex> {{---}} '''прямой левый вывод''' (англ. ''direct left corner'') из <tex>A</tex>, если существует правило вида <tex>A \to X\alpha</tex>.
 
|definition=Говорят, что нетерминал <tex>X</tex> {{---}} '''прямой левый вывод''' (англ. ''direct left corner'') из <tex>A</tex>, если существует правило вида <tex>A \to X\alpha</tex>.
Строка 91: Строка 92:
 
}}
 
}}
  
Во внутреннем цикле алгоритма для всех нетерминалов <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_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_i</tex> - леворекурсивный нетерминал и <tex>A_j</tex> содержится в выводе <tex>A_i</tex> (то есть <tex>A_i</tex> - левый вывод из <tex>A_j</tex>,в то время как <tex>A_j</tex> - левый вывод из <tex>A_i</tex>).
+
Это действие удаляет левую рекурсию только если <tex>A_i</tex> {{---}} леворекурсивный нетерминал и <tex>A_j</tex> содержится в выводе <tex>A_i</tex> (то есть <tex>A_i</tex> {{---}} левый вывод из <tex>A_j</tex>,в то время как <tex>A_j</tex> {{---}} левый вывод из <tex>A_i</tex>).
  
Перестанем добавлять бесполезные выводы, которые не участвуют в удалении левой рекурсии, упорядочив нетерминалы так: если <tex>j < i</tex> и <tex>A_j</tex> - прямой левый вывод из <tex>A_i</tex>, то <tex>A_i</tex> - левый вывод из <tex>A_j</tex>.
+
Перестанем добавлять бесполезные выводы, которые не участвуют в удалении левой рекурсии, упорядочив нетерминалы так: если <tex>j < i</tex> и <tex>A_j</tex> {{---}} прямой левый вывод из <tex>A_i</tex>, то <tex>A_i</tex> {{---}} левый вывод из <tex>A_j</tex>.
 
Упорядочим их по уменьшению количества различных прямых левых выводов из них.
 
Упорядочим их по уменьшению количества различных прямых левых выводов из них.
  
Так как отношение "быть левым выводом" транзитивно,то если <tex>C</tex> - прямой левый вывод из <tex>B</tex>, то каждый левый вывод из С также будет левым выводом из <tex>B</tex>. А так как отношение "быть левым выводом" рефлексивно, <tex>B</tex> явлеяется своим левым выводом, а значит если <tex>C</tex> - прямой левый вывод из <tex>B</tex> - он должен следовать за <tex>B</tex> в упорядоченном множестве, если только <tex>B</tex> не является левым выводом из <tex>C</tex>.
+
Так как отношение "быть левым выводом" транзитивно,то если <tex>C</tex> {{---}} прямой левый вывод из <tex>B</tex>, то каждый левый вывод из С также будет левым выводом из <tex>B</tex>. А так как отношение "быть левым выводом" рефлексивно, <tex>B</tex> явлеяется своим левым выводом, а значит если <tex>C</tex> {{---}} прямой левый вывод из <tex>B</tex> {{---}} он должен следовать за <tex>B</tex> в упорядоченном множестве, если только <tex>B</tex> не является левым выводом из <tex>C</tex>.
  
 
==Пример==
 
==Пример==
Строка 114: Строка 115:
 
<tex>A \to S\alpha </tex>
 
<tex>A \to S\alpha </tex>
  
<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>
+
<tex>S \to{S}{\beta} \mid {S}{\alpha}{\gamma} \mid \beta</tex>
  
 
Устраняем левую рекурсию для <tex>S</tex>
 
Устраняем левую рекурсию для <tex>S</tex>
Строка 120: Строка 121:
 
<tex> S \to\beta{S_1}</tex>
 
<tex> S \to\beta{S_1}</tex>
  
<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1} | {\beta} | {\alpha}{\gamma} </tex>
+
<tex> {S_1} \to\beta{S_1} \mid \alpha\gamma{S_1} \mid {\beta} \mid {\alpha}{\gamma} </tex>
  
 
== См. также  ==
 
== См. также  ==

Версия 17:54, 17 января 2016

Определение:
Говорят, что контекстно-свободная (КС) грамматика [math]\Gamma[/math] содержит непосредственную левую рекурсию (англ. direct left recursion), если она содержит правило вида [math]A \to A\alpha[/math].


Определение:
Говорят, что КС-грамматика [math]\Gamma[/math] содержит левую рекурсию (англ. left recursion), если в ней существует вывод вида [math]A \Rightarrow^* A\alpha[/math].


Методы нисходящего разбора не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида [math]A \Rightarrow^* A\alpha[/math] может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

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

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

  1. Запишем все правила вывода из [math]A[/math] в виде: [math]A \to A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m [/math], где
    • [math]\alpha[/math] — непустая последовательность терминалов и нетерминалов ([math]\alpha \nrightarrow \varepsilon [/math]);
    • [math]\beta[/math] — непустая последовательность терминалов и нетерминалов, не начинающаяся с [math]A[/math].
  2. Заменим правила вывода из [math]A[/math] на [math]A \to\beta_1A^\prime \mid \ldots\ \mid \beta_mA^\prime \mid \beta_1 \mid \ldots \mid \beta_m[/math].
  3. Создадим новый нетерминал [math]{A^\prime} \to \alpha_1{A^\prime} \mid \ldots \mid \alpha_n{A^\prime} \mid \alpha_1 \mid \ldots \mid \alpha_n[/math].

Изначально нетерминал [math]A[/math] порождает сроки вида [math]\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}[/math]. В новой грамматике нетерминал [math]A[/math] порождает [math]\beta{A^\prime}[/math], а [math]A^\prime[/math] порождает строки вида [math]\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}[/math]. Из этого очевидно, что изначальная грамматика эквивалентна новой.

Пример

[math]A \to S\alpha \mid A\alpha[/math]

[math]S \to A\beta[/math]

Есть непосредственная левая рекурсия [math]A \to A\alpha[/math]. Добавим нетерминал [math]A^\prime[/math] и добавим правила [math]A \to S\alpha{A^{\prime}}[/math], [math] A^{\prime} \to \alpha{A^{\prime}} [/math].

Новая грамматика:

[math]A \to S\alpha{A^{\prime}} \mid S\alpha[/math]

[math]A^{\prime} \to \alpha{A^{\prime}}[/math]

[math]S \to A\beta[/math]

В новой грамматике нет непосредственной левой рекурсии, но нетерминал [math]A[/math] леворекурсивен, так как есть [math] A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} [/math]

Алгоритм устранения произвольной левой рекурсии

Воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил. Получим грамматику без [math] \varepsilon [/math]-правил для языка [math]L(\Gamma) \setminus \lbrace \varepsilon \rbrace[/math].

Упорядочим нетерминалы, например по возрастанию индексов, и будем добиваться того, чтобы не было правил вида [math]A_i \to A_j\alpha[/math], где [math]j \leqslant i[/math]. Если данное условие выполняется для всех [math]A_i[/math], то в грамматике нет [math]A_i \Rightarrow^* A_i[/math], а значит не будет левой рекурсии.

Пусть [math]N = \lbrace A_1, A_2, \ldots , A_n \rbrace[/math] — упорядоченное множество всех нетерминалов.

 for [math]A_i \in N[/math]
   for [math]A_j \in \{ N \mid 1 \leqslant j \lt  i \}[/math]
     for [math]p \in \{ P \mid A_i \to A_j\gamma \}[/math]
       удалить продукцию [math]p[/math] 
       for [math]Q \to x_i \in \{A_j \to \delta_1 \mid \ldots \mid \delta_k\}[/math]
         добавить правило [math]A_i \to x_i\gamma[/math]
   устранить непосредственную левую рекурсию для [math]A_i[/math]

Если [math]\varepsilon[/math] присутствовал в языке исходной грамматики, добавим новый начальный символ [math]S'[/math] и правила [math]S' \to S \, \mid \, \varepsilon [/math].

После [math]i[/math] итерации внешнего цикла в любой продукции внешнего цикла в любой продукции вида [math]A_k \to A_l\alpha, k \lt i[/math], должно быть [math]l \gt k[/math]. В результате при следующей итерации внутреннего цикла растет нижний предел [math]m[/math] всех продукций вида [math]A_i \to A_m\alpha[/math] до тех пор, пока не будет достигнуто [math]i \leqslant m [/math].

После [math]i[/math] итерации внешнего цикла в грамматике будут только правила вида [math]A_i \to A_j\alpha[/math], где [math]j \gt i[/math]. Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть [math]{A^\prime}_i [/math] новый нетерминал. Можно заметить, что нет правила вида [math]\ldots \to {A^\prime}_i[/math], где [math]{A^\prime}_i[/math] самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле.

На [math]i[/math] итерации внешнего цикла все правила вида [math]A_i \to A_j \gamma[/math] где [math] j \lt i [/math] заменяются на [math]A_i \to \delta_1\gamma \mid \ldots \mid \delta_k\gamma[/math] где [math]A_j \to \delta_1 \mid \ldots \mid \delta_k[/math]. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

Оценка времени работы

Пусть [math]a_i[/math] количество правил для нетерминала [math]A_i[/math]. Тогда [math]i[/math] итерация внешнего цикла будет выполняться за [math]O(\sum\limits_{A_i \to A_j, j \lt i} a_j) + O(a_i)[/math], что меньше чем [math]O(\sum\limits_{i=1}^n a_j)[/math], значит асимптотика алгоритма [math]O(n\sum\limits_{i=1}^n a_j)[/math].

Худший случай

Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

[math]A_1 \to 0 \mid 1[/math]

[math]A_{i+1} \to {A_i}0 \mid {A_i}1 [/math] для [math]1 \leqslant i \lt n[/math]

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для [math]A_i[/math] будут представлять из себя все двоичные вектора длины [math]i[/math], а значит размер грамматики будет экспоненциальным.

Порядок выбора нетерминалов

Определение:
Говорят, что нетерминал [math]X[/math]прямой левый вывод (англ. direct left corner) из [math]A[/math], если существует правило вида [math]A \to X\alpha[/math].


Определение:
Левый вывод (англ. left corner) — транзитивное, рефлексивное замыкание отношения "быть прямым левым выводом".


Во внутреннем цикле алгоритма для всех нетерминалов [math]A_i[/math] и [math]A_j[/math], таких что [math]j \lt i[/math] и [math]A_j[/math] — прямой левый вывод из [math]A_i[/math] заменяем все прямые левые выводы [math]A_j[/math] из [math]A_i[/math] на все выводы из [math]A_j[/math].

Это действие удаляет левую рекурсию только если [math]A_i[/math] — леворекурсивный нетерминал и [math]A_j[/math] содержится в выводе [math]A_i[/math] (то есть [math]A_i[/math] — левый вывод из [math]A_j[/math],в то время как [math]A_j[/math] — левый вывод из [math]A_i[/math]).

Перестанем добавлять бесполезные выводы, которые не участвуют в удалении левой рекурсии, упорядочив нетерминалы так: если [math]j \lt i[/math] и [math]A_j[/math] — прямой левый вывод из [math]A_i[/math], то [math]A_i[/math] — левый вывод из [math]A_j[/math]. Упорядочим их по уменьшению количества различных прямых левых выводов из них.

Так как отношение "быть левым выводом" транзитивно,то если [math]C[/math] — прямой левый вывод из [math]B[/math], то каждый левый вывод из С также будет левым выводом из [math]B[/math]. А так как отношение "быть левым выводом" рефлексивно, [math]B[/math] явлеяется своим левым выводом, а значит если [math]C[/math] — прямой левый вывод из [math]B[/math] — он должен следовать за [math]B[/math] в упорядоченном множестве, если только [math]B[/math] не является левым выводом из [math]C[/math].

Пример

Дана грамматика:

[math]A \to S\alpha [/math]

[math]S \to S\beta \mid A\gamma \mid \beta[/math]

Среди правил [math]A[/math] непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит. Во время второй итерации внешнего цикла правило [math] S \to A\gamma [/math] переходит в [math] S \to S\alpha\gamma [/math].

Грамматика имеет вид

[math]A \to S\alpha [/math]

[math]S \to{S}{\beta} \mid {S}{\alpha}{\gamma} \mid \beta[/math]

Устраняем левую рекурсию для [math]S[/math]

[math] S \to\beta{S_1}[/math]

[math] {S_1} \to\beta{S_1} \mid \alpha\gamma{S_1} \mid {\beta} \mid {\alpha}{\gamma} [/math]

См. также

Источники информации

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
  • Robert C. MooreRemoving Left Recursion from Context-Free Grammars