Изменения

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

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

758 байт добавлено, 22:35, 11 февраля 2018
м
Ошибка в примере устранения непосредственной левой рекурсии. Смотри 3-ий пункт процедуры устранения. Порождается ещё и строка вида A'->a
<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1\,|\,mid \ldots\,|\,mid A\alpha_n\,|\,mid \beta_1\,|\,mid \ldots\,|\,mid \beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<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}, |\, mid \ldots\, |\, mid \alpha_n{A^\prime} | \mid \alpha_1\, |\, mid \ldots\, |\, mid \alpha_n</tex>. </li>
</li>
</ol>
Изначально нетерминал <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 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_i \to A_j\alpha</tex>, где <tex>j \leqslant i</tex>.
Если данное условие выполняется для всех <tex>A_i</tex>, то в грамматике нет <tex>A_i \toRightarrow^* A_i</tex>, а значит не будет левой рекурсии.
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
'''for''' <tex>A_i \in N</tex>
'''for''' <tex>A_j \in \{ N \mid 1 \leqslant j < i \}</tex>
'''for''' <tex>production p \in \{P \mid A_i \to A_j\gamma \}</tex> удалить продукцию <tex>productionp</tex> <font color=darkgreen>#production {{---}} правило вывода</font> '''for''' <tex>P 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</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_i \to A_j\alpha</tex>, где <tex>j > 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}</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>i</tex> итерация внешнего цикла будет выполняться за <tex>O\left(\sum\limits_{A_i \to A_j, j < i} a_j\right) + O(a_i)</tex>, что меньше чем <tex>O\left(\sum\limits_{i=1}^n a_j\right)</tex>, значит асимптотика алгоритма <tex>O\left(n\sum\limits_{i=1}^n a_j\right)</tex>.
===Худший случай===
Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.
Пример грамматики для которой имеет значение порядок нетерминалов
<tex>A_1 \to 0 | \mid 1</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>, а значит размер грамматики будет экспоненциальным.
===Порядок выбора нетерминалов===
{{Определение
|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_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>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>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>
== См. также ==
1
правка

Навигация