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

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
__TOC__
 
 
{{Определение
 
{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (англ. ''direct left recursion''), если она содержит правило вида <tex>A \to A\alpha</tex>.
+
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (direct left recursion), если она содержит правило вида <tex>A \to A\alpha</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию'''  (англ. ''left recursion''), если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
+
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию (left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
 
}}
 
}}
  
[[Методы трансляции#Нисходящий разбор|Методы нисходящего разбора]] не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.
+
Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.
 +
 
  
 
==Устранение непосредственной левой рекурсии==
 
==Устранение непосредственной левой рекурсии==
Строка 14: Строка 14:
 
<ol>
 
<ol>
 
<li>Запишем все правила вывода из <tex>A</tex> в виде:  
 
<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>, где
+
<tex>A \to A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\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 \mid \ldots\ \mid \beta_mA^\prime \mid \beta_1 \mid \ldots \mid \beta_m</tex>.</li>
+
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime\, |\, \ldots\,  |\\beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \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>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime},  |\\ldots\, |\, \alpha_n{A^\prime} | \alpha_1\,  |\\ldots\, |\, \alpha_n</tex>. </li>
 
</li>
 
</li>
 
</ol>
 
</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</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>A \to S\alpha | A\alpha</tex>
  
 
<tex>S \to A\beta</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 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 \to S\alpha{A^{\prime}} | S\alpha</tex>
  
<tex>A^{\prime} \to \alpha{A^{\prime} \mid \alpha}</tex>
+
<tex>A^{\prime} \to \alpha{A^{\prime}}</tex>
  
 
<tex>S \to A\beta</tex>
 
<tex>S \to A\beta</tex>
  
В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>
+
В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex>A \Rightarrow S\alpha{A^{\prime}} \Rigtharrow 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> {{---}} упорядоченное множество всех нетерминалов.
 
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
 +
<div>
 +
for все нетерминалы <tex>A_i</tex>
 +
  for все нетерминалы <tex>A_j</tex>, такие, что <tex> 1 \leq j < i </tex> и
 +
    рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>.
 +
    заменить каждое правило <tex>A_i \to A_j \gamma</tex> на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
 +
  устранить непосредственную левую рекурсию для <tex>A_i</tex>.
 +
</div>
  
  '''for''' <tex>A_i \in N</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>A_i</tex>.
    '''for''' <tex>A_j \in \{ N \mid 1 \leqslant j < i \}</tex>
+
Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.
      '''for''' <tex>p \in \{ P \mid A_i \to A_j\gamma \}</tex>
 
        удалить продукцию <tex>p</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</tex>
 
  
Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, \mid \, \varepsilon </tex>.
+
Алгоритм не работает для грамматик с <tex>\varepsilon</tex> переходами и с грамматиками имеющими <tex>A \Rightarrow^+ A</tex>. Поэтому для произвольной грамматики необходимо сначала воспользоваться алгоритмом [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \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_1 \to 0 | 1</tex>
  
<tex>A_{i+1} \to {A_i}0 \mid {A_i}1 </tex>  для <tex>1 \leqslant i < n</tex>
+
<tex>A_{i+1} \to {A_i}0</tex>  для <tex>1 \leq 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='''Левый вывод''' (англ. ''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>A \to S\alpha </tex>
  
<tex>S \to S\beta \mid A\gamma \mid \beta</tex>
+
<tex>S \to S\beta | A\gamma | b</tex>
  
 
Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.  
 
Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.  
Строка 115: Строка 84:
 
<tex>A \to S\alpha </tex>
 
<tex>A \to S\alpha </tex>
  
<tex>S \to{S}{\beta} \mid {S}{\alpha}{\gamma} \mid \beta</tex>
+
<tex>S \to{S}{\beta} | {S}{\alpha}{\gamma} | \beta</tex>
  
 
Устраняем левую рекурсию для <tex>S</tex>
 
Устраняем левую рекурсию для <tex>S</tex>
Строка 121: Строка 90:
 
<tex> S \to\beta{S_1}</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>
+
<tex> {S_1} \to\beta{S_1} | \alpha\gamma{S_1}</tex>
 
 
== См. также  ==
 
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
 
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
 
* [[Удаление_eps-правил_из_грамматики | Удаления <tex> \varepsilon </tex>-правил из грамматики]]
 
  
== Источники информации ==
+
==Литература==
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing  Left  Recursion  from  Context-Free  Grammars ]
 
* ''Robert C. Moore'' — [http://aclweb.org/anthology-new/A/A00/A00-2033.pdf Removing  Left  Recursion  from  Context-Free  Grammars ]
Строка 134: Строка 98:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Нормальные формы КС-грамматик]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: