3.1.7 Odstranění levé rekurze

Neterminál rekurzivní zleva

Neterminální symbol rekurzivní zleva je takový neterminální symbol \(A\), pro který existuje derivace \(A \Rightarrow^+ A\beta\), kde \(\beta \in (N \cup \Sigma)^*\). Rozlišujeme dva typy levé rekurze:

přímá rekurzivita zleva, která je vidět přímo v pravidlech pro daný neterminál (např. \(A \to Aa\)),
nepřímá rekurzivita zleva, která není vidět přímo v pravidlech pro daný neterminál (např. \(A \to Ba, B \to Ac\)).

Definice (Zleva rekurzivní gramatika)

Zleva rekurzivní gramatika

Zleva rekurzivní gramatika je taková gramatika, která má alespoň jeden neterminální symbol rekurzivní zleva.

Jak z bezkontextové gramatiky odstraníme přímou levou rekurzi?

Odstranění přímé levé rekurze

Pravidla tvaru \(A \to A\alpha \mid \beta\) lze zaměnit za:

\[ A \to \beta A' \mid \beta, \quad A' \to \alpha A' \mid \alpha \quad (\alpha, \beta \in (N \cup \Sigma)^*, A \in N) \]

Pro více výskytů \(\alpha, \beta\) lze vzorec intuitivně rozšířit následovně:

\(A \to A\alpha_1 \mid A\alpha_2 \mid \beta_1 \mid \beta_2\) lze zaměnit za:

\[ A \to \beta_1 A' \mid \beta_2 A' \mid \beta_1 \mid \beta_2, \quad A' \to \alpha_1 A' \mid \alpha_2 A' \mid \alpha_1 \mid \alpha_2 \]

Jak z bezkontextové gramatiky odstraníme levou rekurzi (přímou i nepřímou)?

Algoritmus odstranění levé rekurze

Gramatiku nejprve převedeme na vlastní bez jednoduchých pravidel. Tedy odstraníme \(\varepsilon\)-pravidla, jednoduchá pravidla a pak zbytečné symboly.
Zvolíme libovolné uspořádání neterminálů \((A_1, A_2, \dots, A_r)\). Následně začneme upravovat pravidla pro jednotlivé neterminály v gramatice, přičemž začneme zleva od začátku uspořádání. Pravidla pro jednotlivé neterminály \(A_i\) upravíme tak, že:
- Pravidla pro neterminál \(A_i\) začínající na pravé straně terminálním symbolem – tj. \(A_i \to a\alpha\), kde \(a \in \Sigma, \alpha \in (N \cup \Sigma)^*\) – neupravujeme.
- Pravidla pro neterminál \(A_i\) začínající na pravé straně neterminálním symbolem \(A_i\), nebo neterminálem \(A_j\), jenž je ve zvoleném uspořádání za neterminálem \(A_i\) – tj. \(A_i \to A_j\alpha\), kde \(j \ge i, \alpha \in (N \cup \Sigma)^*\) – neupravujeme.
- Pravidla pro neterminál \(A_i\) začínající na pravé straně neterminálním symbolem \(A_j\), jenž je ve zvoleném uspořádání před neterminálem \(A_i\) – tj. \(A_i \to A_j\alpha\), kde \(j < i, \alpha \in (N \cup \Sigma)^*\) – upravíme tak, že za neterminál \(A_j\) dosadíme (pozor, dosazovat je občas nutné opakovaně).
- Jakmile pravidla pro neterminál \(A_i\) začínají na pravé straně pouze terminálním symbolem nebo neterminálním symbolem \(A_i\) či neterminálním symbolem, který je ve zvoleném uspořádání za neterminálem \(A_i\), pak zkontrolujeme, zdali se v pravidlech pro neterminál \(A_i\) vyskytuje přímá levá rekurze. Pokud ano, standardně ji odstraníme.