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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Устранение непосредственной левой рекурсии)
(Устранение непосредственной левой рекурсии)
Строка 14: Строка 14:
 
<ol>
 
<ol>
 
<li>Запишем все правила вывода из <tex>A</tex> в виде:  
 
<li>Запишем все правила вывода из <tex>A</tex> в виде:  
<tex>A \Rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\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 \Rightarrow \beta_1A^\prime\, |\, \ldots\,  |\,  \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \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 \Rightarrow \alpha_1A^\prime\,  |\,  \ldots\, |\, \alpha_nA^\prime | \alpha_1\,  |\,  \ldots\, |\, \alpha_n</tex>. </li>
+
<li>Создадим новый нетерминал <tex>A^\prime \to \alpha_1A^\prime\,  |\,  \ldots\, |\, \alpha_nA^\prime | \alpha_1\,  |\,  \ldots\, |\, \alpha_n</tex>. </li>
 
</li>
 
</li>
 
</ol>
 
</ol>
  
Нетерминал A порождает те же строки, что и ранее, но без левой рекурсии. Эта процедура устраняет все непосредственные рекурсии из продукций для A.
+
Изначально нетерминал <tex>A</tex> порождает сроки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A_i}</tex>, а <tex>A_i</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.
  
 
==Алгоритм  устранения произвольной левой рекурсии==
 
==Алгоритм  устранения произвольной левой рекурсии==

Версия 15:37, 7 января 2013

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


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


Методы нисходящего разбора (top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида [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\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\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\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m[/math].
  3. Создадим новый нетерминал [math]A^\prime \to \alpha_1A^\prime\, |\, \ldots\, |\, \alpha_nA^\prime | \alpha_1\, |\, \ldots\, |\, \alpha_n[/math].

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

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

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

for все нетерминалы [math]A_i[/math] 
  for все нетерминалы [math]A_j[/math], такие, что [math] 1 \leq j \lt  i [/math] и 
    рассмотреть все правила вывода из [math]A_j[/math]: [math]A_j \Rightarrow \delta_1 | \ldots | \delta_k[/math].
    заменить каждое правило [math]A_i \Rightarrow A_j \gamma[/math] на [math]A_i \Rightarrow \delta_1\gamma | \ldots | \delta_k\gamma[/math].
  устранить непосредственную левую рекурсию для [math]A_i[/math].

После [math]i[/math] итерации внешнего цикла в любой продукции вида [math] A_k \Rightarrow A_l\alpha [/math] где [math] i \gt k [/math] будет [math] l \gt k[/math]. В результате после каждой итерации растет нижний предел m всех продукций вида [math]A_i \Rightarrow A_m\alpha[/math] до тех пор, пока не будет достигнуто [math]m \geq i[/math]. Затем из [math]A_i[/math] устраняется непосредственная левая рекурсия и достигается m > i.

Пример

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

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

[math]S \Rightarrow S\beta | A\gamma | b[/math]

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

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

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

[math]S \Rightarrow {S}{\beta} | {S}{\alpha}{\gamma} | \beta[/math]

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

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

[math] {S_1} \Rightarrow \beta{S_1} | \alpha\gamma{S_1}[/math]



Для произвольной грамматики [math]\Gamma[/math] левую рекурсию можно устранить следующим образом:

  1. Воспользуемся алгоритмом удаления [math] \varepsilon [/math]-правил. Получим грамматику без [math] \varepsilon [/math]-правил для языка [math]L(\Gamma) \setminus \lbrace \varepsilon \rbrace[/math].
  2. Воспользуемся алгоритмом устранения произвольной левой рекурсии.
  3. Если [math]\varepsilon[/math] присутствовал в языке исходной грамматики, добавим новый начальный символ [math]S'[/math] и правила [math]S' \rightarrow S \, | \, \varepsilon [/math].

Литература

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