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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 35: Строка 35:
 
===Устранение произвольной левой рекурсии===
 
===Устранение произвольной левой рекурсии===
 
Пусть множество всех нетерминалов <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex>
 
Пусть множество всех нетерминалов <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex>
: for i = 1 to n {
+
<div>
::for j = 1 to i – 1 {
+
for i = 1 to n {
:::* рассмотреть все правила вывода из <tex>A_j</tex>
+
  for j = 1 to i – 1 {
:::<tex>A_j \rightarrow \delta_1 | \ldots | \delta_k</tex>
+
    рассмотреть все правила вывода из <tex>A_j</tex>
:::* заменить каждое правило <tex>A_i \rightarrow A_j \gamma</tex> на
+
    <tex>A_j \rightarrow \delta_1 | \ldots | \delta_k</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>
 
Инвариант: после <tex>j</tex> итераций внутреннего цикла для <tex>i</tex>
 
Инвариант: после <tex>j</tex> итераций внутреннего цикла для <tex>i</tex>
 
*для <tex>k < i</tex> правые части правил вывода из <tex>A_k</tex> не начинаются с <tex>A_1, A_2, \ldots , A_k</tex>
 
*для <tex>k < i</tex> правые части правил вывода из <tex>A_k</tex> не начинаются с <tex>A_1, A_2, \ldots , A_k</tex>

Версия 02:35, 27 ноября 2011

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


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


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

Приведем алгоритм, позволяющий для к.с. грамматики без ε-правил построить эквивалентную ей к.с. грамматику (без ε-правил), не содержащую левой рекурсии.

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

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

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

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

Запишем все правила вывода из [math]A[/math] в виде

[math]A \rightarrow A\alpha_1\,|\,\ldots\,|\,A\alpha_n\,|\,\beta_1\,|\,\ldots\,|\,\beta_m [/math]

где

  • [math]\alpha[/math] - непустая последовательность терминалов и нетерминалов ([math]\alpha \ne \epsilon [/math])
  • [math]\beta[/math] - непустая последовательность терминалов и нетерминалов, не начинающаяся с [math]A[/math].

Заменим правила вывода из [math]A[/math] на:

[math]A \rightarrow \beta_1A^\prime\, |\, \ldots\, |\, \beta_mA^\prime \,|\, \beta_1 \,|\, \ldots \,|\, \beta_m[/math]

И создадим новый нетерминал

[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]j[/math] итераций внутреннего цикла для [math]i[/math]

  • для [math]k \lt i[/math] правые части правил вывода из [math]A_k[/math] не начинаются с [math]A_1, A_2, \ldots , A_k[/math]
  • правые части правил вывода из [math]A_i[/math] не начинаются с [math]A_1, A_2, \ldots , A_j[/math]
  • правые части правил вывода не начинаются с добавленных алгоритмом нетерминалов [math]A_k ^{\prime}[/math]
  • грамматика не содержит ε-правил

(проверяется индукцией по парам [math](i,j)[/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]

Литература

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