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

Определение:

Говорят, что контекстно-свободная(КС) грамматика [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] может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

Левая рекурсия может быть:

• непосредственной(immidiate)

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

• произвольной(indirect)

[math]A_0 \rightarrow A_1\alpha[/math]

[math]A_1 \rightarrow A_0\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 \varepsilon [/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]S \rightarrow Aa|b[/math]

[math]A \rightarrow Ac|Sd|\epsilon[/math]

S леворекурсивен, так как [math]S \Rightarrow Aa \Rightarrow Sda[/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_i \rightarrow A_j \alpha [/math] и правила вывода из [math]A_j[/math]: [math]A_j \rightarrow \delta_1 | \ldots | \delta_k[/math].
    Заменить каждое правило [math]A_i \rightarrow A_j \alpha[/math] на [math]A_i \rightarrow \delta_1\alpha| \ldots | \delta_k\alpha[/math].
  устранить непосредственную левую рекурсию для [math]A_i[/math].

Смысл вложенного цикла в том, чтобы избавиться от правил вида [math]A_i \rightarrow A_j\alpha [/math] таких, что [math] i \lt j [/math].

После вложенного цикла цепочка выводов вида [math]A_i \rightarrow A_j \alpha \rightarrow A_k \ldots [/math] точно не придет в [math]A_i[/math], а значит для [math]A_i[/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. Moore — Removing Left Recursion from Context-Free Grammars