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

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

Говорят, что контекстно-свободная(КС) грамматика $\Gamma$ содержит непосредственную левую рекурсию, если она содержит правило вида $A \rightarrow A\alpha$.

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

Говорят, что КС-грамматика $\Gamma$ содержит левую рекурсию, если в ней существует вывод вида $A \Rightarrow^* A\alpha$.

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

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

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

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

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

for i = 1 to n 
  for j = 1 to i – 1 
    рассмотреть все правила вывода из $A_j$: $A_j \rightarrow \delta_1 | \ldots | \delta_k$.
    заменить каждое правило $A_i \rightarrow A_j \gamma$ на $A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma$.
  устранить непосредственную левую рекурсию для $A_i$.

Таким образом, после применения алгоритма все правила вывода имеют вид:

• $A \rightarrow c \alpha$, где $c$ — терминал, $A$ — произвольный нетерминал;
• $A_i \rightarrow A_j \alpha$, где $i \lt j$, $A_i , A_j$ — нетерминалы из исходной грамматики;
• $A_i^{\prime} \rightarrow A_j \alpha$, где $A_i^{\prime}$ — новый нетерминал, $A_j$ — нетерминал из исходной грамматики.

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

• $B_i \rightarrow c \alpha$, где $c$ — терминал;
• $B_i \rightarrow B_j \alpha$, где $i \lt j$.

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

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

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

Литература

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