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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
<tex>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
 
<tex>A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m </tex>, где
 
<ul>
 
<ul>
<li> <tex>\alpha</tex> - непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \epsilon </tex>)</li>
+
<li> <tex>\alpha</tex> - непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \epsilon </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 \rightarrow \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 \rightarrow \alpha_1A^\prime\,  |\,  \ldots\, |\, \alpha_nA^\prime | \alpha_1\,  |\,  \ldots\, |\, \alpha_n</tex>. </li>
 
</li>
 
</li>
 
</ol>
 
</ol>
  
 
==Устранение произвольной левой рекурсии==
 
==Устранение произвольной левой рекурсии==
Пусть <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>
 
<div>
 
  for i = 1 to n {
 
  for i = 1 to n {
 
   for j = 1 to i – 1 {
 
   for j = 1 to i – 1 {
     рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \rightarrow \delta_1 | \ldots | \delta_k</tex>
+
     рассмотреть все правила вывода из <tex>A_j</tex>: <tex>A_j \rightarrow \delta_1 | \ldots | \delta_k</tex>.
     заменить каждое правило <tex>A_i \rightarrow A_j \gamma</tex> на <tex>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</tex>
+
     заменить каждое правило <tex>A_i \rightarrow A_j \gamma</tex> на <tex>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</tex>.
 
   }
 
   }
   устранить непосредственную левую рекурсию для <tex>A_i</tex>
+
   устранить непосредственную левую рекурсию для <tex>A_i</tex>.
 
  }
 
  }
 
</div>
 
</div>
  
 
Таким образом, после применения алгоритма все правила вывода имеют вид:  
 
Таким образом, после применения алгоритма все правила вывода имеют вид:  
*<tex>A \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал, <tex>A</tex> - произвольный нетерминал
+
*<tex>A \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал, <tex>A</tex> - произвольный нетерминал;
*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j</tex>, <tex>A_i , A_j</tex> - нетерминалы из исходной грамматики
+
*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j</tex>, <tex>A_i , A_j</tex> - нетерминалы из исходной грамматики;
*<tex>A_i^{\prime} \rightarrow A_j \alpha </tex>, где <tex>A_i^{\prime}</tex> - новый нетерминал, <tex>A_j</tex> - нетерминал из исходной грамматики
+
*<tex>A_i^{\prime} \rightarrow A_j \alpha </tex>, где <tex>A_i^{\prime}</tex> - новый нетерминал, <tex>A_j</tex> - нетерминал из исходной грамматики.
  
 
Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:
 
Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:
*<tex>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал
+
*<tex>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал;
*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>
+
*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>.
  
 
==Алгоритм  устранения левой рекурсии==
 
==Алгоритм  устранения левой рекурсии==
  
 
Для произвольной грамматики <tex>\Gamma</tex> левую рекурсию можно устранить следующим образом:
 
Для произвольной грамматики <tex>\Gamma</tex> левую рекурсию можно устранить следующим образом:
#Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</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 S \, | \, \epsilon </tex>
+
#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>.
  
  

Версия 03:54, 30 ноября 2011

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


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


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

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

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

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

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

for i = 1 to n {
  for j = 1 to i – 1 {
    рассмотреть все правила вывода из [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]A \rightarrow c \alpha [/math], где [math]c[/math] - терминал, [math]A[/math] - произвольный нетерминал;
  • [math]A_i \rightarrow A_j \alpha [/math], где [math]i \lt j[/math], [math]A_i , A_j[/math] - нетерминалы из исходной грамматики;
  • [math]A_i^{\prime} \rightarrow A_j \alpha [/math], где [math]A_i^{\prime}[/math] - новый нетерминал, [math]A_j[/math] - нетерминал из исходной грамматики.

Если теперь перенумеровать нетерминалы, сохранив порядок для старых и присвоив всем новым меньшие номера, то все правила будут иметь вид:

  • [math]B_i \rightarrow c \alpha [/math], где [math]c[/math] - терминал;
  • [math]B_i \rightarrow B_j \alpha [/math], где [math]i \lt j[/math].

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

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

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


Литература

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