Formální jazyky a automaty
Syntaktická analýza, přímá a nepřímá levá rekurze, Greibachové
normální forma
Jan Křetínský
Fakulta informatiky, MU Brno
Jaro 2024
Bezkontextové gramatiky → zásobníkové automaty
Motivace 1: Jaká je třída jazyků rozpoznávaných zásobníkovými
automaty?
Motivace 2: Je dána bezkontextová gramatika G a slovo w.
Jak zjistit, zda se slovo w dá vygenerovat v gramatice G?
Problém syntaktické analýzy pro bezkontextové gramatiky:
pro danou bezkontextovou gramatiku G a slovo w rozhodnout,
zda w ∈ L(G).
2 / 21
Nedeterministická syntaktická analýza shora dolů
Věta 3.47.
Ke každé CFG G lze sestrojit PDA M takový, že L(G) = Le(M).
Důkaz. K dané gramatice G konstruujeme PDA M simulující
derivace v G
3 / 21
Nedeterministická syntaktická analýza shora dolů
Věta 3.47.
Ke každé CFG G lze sestrojit PDA M takový, že L(G) = Le(M).
Důkaz. K dané gramatice G konstruujeme PDA M simulující levé
derivace v G, tj. vždy rozvíjíme nejlevější neterminál:
▶ V levé derivaci je v jednom kroku odvození nahrazen (nejlevější)
neterminál A pravou stranou X1 . . . Xn nějakého A-pravidla.
▶ V M této situaci odpovídá náhrada A na vrcholu zásobníku
řetězem X1 . . . Xn.
M = ({q}, Σ, N ∪ Σ, δ, q, S, ∅), kde δ je definována:
▶ (expanze) δ(q, ε, A) obsahuje (q, α) právě když A → α ∈ P
▶ (čtení) δ(q, a, a) = {(q, ε)} pro všechna a ∈ Σ
3 / 21
Příkad
S → aAB δ(q, ε, S) = {(q, aAB)}
A → Aa | ε δ(q, ε, A) = {(q, Aa), (q, ε)}
B → SaA | b δ(q, ε, B) = {(q, SaA), (q, b)}
δ(q, a, a) = δ(q, b, b) = {(q, ε)}
S ⇒ aAB
⇒ aB
⇒ aSaA
⇒ aaABaA
⇒ aaBaA
⇒ aabaA
⇒ aaba
4 / 21
Korektnost
A ⇒∗
w ⇐⇒ (q, w, A) |
∗
(q, ε, ε)
(=⇒) Indukcí vzhledem k délce odvození m.
▶ m = 0: zřejmé.
▶ m ≥ 1: nechť tvrzení platí pro všechna m′
< m.
A ⇒ X1X2 . . . Xk ⇒∗
x1x2 . . . xk = w, kde Xi
mi
⇒ xi , 0 ≤ mi < m
z definice δ plyne (q, w, A) | (q, w, X1X2 . . . Xk ).
Je-li Xi ∈ N, pak dle indukčního předpokladu máme
(q, xi , Xi ) |
∗
(q, ε, ε).
Je-li Xi ∈ Σ, pak Xi = xi a z definice δ plyne
(q, xi , xi ) | (q, ε, ε).
Kompozicí dostáváme (q, w, A) |
+
(q, ε, ε).
5 / 21
(⇐=) Předpokládejme (q, w, A) |
n
(q, ε, ε) a ukažme A ⇒∗
w.
Indukcí vzhledem k délce výpočtu n.
▶ n = 0: zřejmé.
▶ n ≥ 1: nechť tvrzení platí pro všechna n′
< n.
(q, w, A) | (q, w, X1X2 . . . Xk ), tj. A → X1X2 . . . Xk ∈ P
w můžeme napsat jako w = x1x2 . . . xk takové, že
▶ je-li Xi ∈ N, pak (q, xi , Xi ) |
ni
(q, ε, ε), kde ni < n.
Dle IP Xi ⇒+
xi .
▶ je-li Xi ∈ Σ, pak Xi
0
⇒ xi .
Vhodnou kompozicí obdržíme
A ⇒ X1X2 . . . Xk ⇒∗
x1X2 . . . Xk ⇒∗
x1 . . . xk = w
což je levá derivace slova w v gramatice G.
6 / 21
Nedeterministická syntaktická analýza zdola nahoru
S → XY
X → ab
Y → c
7 / 21
Nedeterministická syntaktická analýza zdola nahoru
Věta 3.55.
Nechť G je libovolná CFG, pak lze zkonstruovat rozšířený PDA R
takový, že L(G) = L(R).
Důkaz. Vrchol zásobníku píšeme vpravo.
Konstruujeme rozšířený PDA R, který simuluje pravou derivaci v G
v obráceném pořadí.
PDA R má kroky dvojího typu:
1. (čtení) může kdykoli načíst do zásobníku symbol ze vstupu
2. (redukce) je-li na vrcholu zásobníku řetězec tvořící pravou stranu
nějakého pravidla v G, může ho nahradit odpovídajícím
levostranným neterminálem (a ze vstupu nic nečte)
8 / 21
Nedeterministická syntaktická analýza zdola nahoru
Věta 3.55.
Nechť G je libovolná CFG, pak lze zkonstruovat rozšířený PDA R
takový, že L(G) = L(R).
Důkaz. Vrchol zásobníku píšeme vpravo.
Konstruujeme rozšířený PDA R, který simuluje pravou derivaci v G
v obráceném pořadí.
PDA R má kroky dvojího typu:
1. (čtení) může kdykoli načíst do zásobníku symbol ze vstupu
2. (redukce) je-li na vrcholu zásobníku řetězec tvořící pravou stranu
nějakého pravidla v G, může ho nahradit odpovídajícím
levostranným neterminálem (a ze vstupu nic nečte)
Nechť G = (N, Σ, P, S).
Položme R = ({q, r}, Σ, N ∪ Σ ∪ {⊥}, δ, q, ⊥, {r}), kde ⊥ je nově
přidaný symbol a kde δ je definována takto:
1. δ(q, a, ε) = {(q, a)} pro všechna a ∈ Σ
2. je-li A → α pravidlo v P, pak δ(q, ε, α) obsahuje (q, A)
3. δ(q, ε, ⊥S) = {(r, ε)}
8 / 21
Příklad
krok výpočtu odpovídající pravidlo z G
(q, i + i ∗ i, ⊥) |i
(q, +i ∗ i, ⊥i) F → i
|ε
(q, +i ∗ i, ⊥F) T → F
|ε
(q, +i ∗ i, ⊥T) E → T
|ε
(q, +i ∗ i, ⊥E)
|+
(q, i ∗ i, ⊥E+)
|i
(q, ∗i, ⊥E + i) F → i
|ε
(q, ∗i, ⊥E + F) T → F
|ε
(q, ∗i, ⊥E + T)
|∗
(q, i, ⊥E + T∗)
|i
(q, ε, ⊥E + T ∗ i) F → i
|ε
(q, ε, ⊥E + T ∗ F) T → T ∗ F
|ε
(q, ε, ⊥E + T) E → E + T
|ε
(q, ε, ⊥E)
|ε
(r, ε, ε)
9 / 21
Korektnost
S ⇒∗
αAy
n
⇒ xy ⇐⇒ (q, xy, ⊥) |
∗
(q, y, ⊥αA),
kde S ⇒∗
αAy
n
⇒ xy je pravá derivace a A je nejpravější neterminál.
(=⇒) indukcí k délce odvození
(⇐=) indukcí k délce výpočtu
Pro A = S a α, y = ε dostáváme:
S ⇒∗
x ⇐⇒ (q, x, ⊥) |
∗
(q, ε, ⊥S) | (r, ε)
10 / 21
Efektivnost syntaktické analýzy
Nederministický PDA =⇒ nedeterministický algoritmus
=⇒ exponenciální deterministický algoritmus
Řešení:
▶ deterministický algoritmus složitosti O(n3
), kde n = |w|
(algoritmus Cocke - Younger - Kasami)
▶ deterministické zásobníkové automaty
a deterministické bezkontextové jazyky
▶ lineární algoritmy pro speciální třídy deterministických
bezkontextových jazyků
11 / 21
Kanonické tvary bezkontextových gramatik
▶ redukované bezkontextové gramatiky
▶ gramatiky bez ε-pravidel
▶ gramatiky bez jednoduchých pravidel
▶ vlastní gramatiky
▶ Chomského normální forma
▶ gramatiky bez levé rekurze
▶ Greibachové normální forma
12 / 21
Rekurzivní neterminály a gramatiky
Definice 3.28.
Neterminál A v CFG G = (N, Σ, P, S) se nazývá levorekurzivní jestliže
v G existuje derivace A ⇒+
Aβ.
CFG bez levorekurzivních neterminálů se nazývá nelevorekurzivní.
Je-li v CFG pravidlo tvaru A → Aα, hovoříme o přímé levé rekurzi na A.
Praktický význam: některé nástroje pro automatickou tvorbu parserů
k zadaným gramatikám vyžadují na vstupu nelevorekurzivní
gramatiku (např. ANTLR).
13 / 21
Algoritmus odstranění přímé levé rekurze
Nechť CFG G = (N, Σ, P, S) je necyklická a bez ε-pravidel, v níž
všechna A-pravidla (pravidla mající na levé straně A) jsou tvaru
A → Aα1 | . . . | Aαm | β1 | . . . | βn,
kde každý řetěz βi začíná symbolem různým od A.
14 / 21
Algoritmus odstranění přímé levé rekurze
Nechť CFG G = (N, Σ, P, S) je necyklická a bez ε-pravidel, v níž
všechna A-pravidla (pravidla mající na levé straně A) jsou tvaru
A → Aα1 | . . . | Aαm | β1 | . . . | βn,
kde každý řetěz βi začíná symbolem různým od A.
Nechť G′
= (N ∪ {A′
}, Σ, P′
, S), kde P′
obdržíme z P tak, že všechna
výše uvedená pravidla nahradíme pravidly:
A → β1 | . . . | βn | β1A′
| . . . | βnA′
A′
→ α1 | . . . | αm | α1A′
| . . . | αmA′
14 / 21
Algoritmus odstranění přímé levé rekurze
Nechť CFG G = (N, Σ, P, S) je necyklická a bez ε-pravidel, v níž
všechna A-pravidla (pravidla mající na levé straně A) jsou tvaru
A → Aα1 | . . . | Aαm | β1 | . . . | βn,
kde každý řetěz βi začíná symbolem různým od A.
Nechť G′
= (N ∪ {A′
}, Σ, P′
, S), kde P′
obdržíme z P tak, že všechna
výše uvedená pravidla nahradíme pravidly:
A → β1 | . . . | βn | β1A′
| . . . | βnA′
A′
→ α1 | . . . | αm | α1A′
| . . . | αmA′
Pak L(G) = L(G′
) a G′
je necyklická a bez ε-pravidel.
14 / 21
Lemma o substituci
Lemma 3.20. (o substituci)
Nechť G = (N, Σ, P, S) je CFG. Nechť A → α1Bα2 ∈ P.
Nechť B → β1 | . . . | βr jsou všechna pravidla v P tvaru B → α.
Definujme G′
= (N, Σ, P′
, S), kde
P′
= (P ∖ {A → α1Bα2}) ∪ {A → α1β1α2 | . . . | α1βr α2}.
Pak L(G) = L(G′
).
15 / 21
Lemma o substituci
Lemma 3.20. (o substituci)
Nechť G = (N, Σ, P, S) je CFG. Nechť A → α1Bα2 ∈ P.
Nechť B → β1 | . . . | βr jsou všechna pravidla v P tvaru B → α.
Definujme G′
= (N, Σ, P′
, S), kde
P′
= (P ∖ {A → α1Bα2}) ∪ {A → α1β1α2 | . . . | α1βr α2}.
Pak L(G) = L(G′
).
Příklad:
A → Bd | c
B → Bdd | Ccc | aAd
C → Aa
15 / 21
Algoritmus odstranění levé rekurze
Vstup: Vlastní CFG G = (N, Σ, P, S)
Výstup: Ekvivalentní nelevorekurzivní gramatika bez ε-pravidel
1: Uspořádej libovolně N, N = {A1, . . . , An}
2: for i ← 1 to n do
3: for j ← 1 to i − 1 do
4: for all pravidlo tvaru Ai → Aj α do
5: přidej pravidla Ai → β1α | . . . | βk α
6: (kde Aj → β1 | . . . | βk jsou všechna pravidla pro Aj )
7: vypusť pravidlo Ai → Aj α
8: odstraň případnou přímou levou rekurzi na Ai
16 / 21
Algoritmus odstranění levé rekurze
Vstup: Vlastní CFG G = (N, Σ, P, S)
Výstup: Ekvivalentní nelevorekurzivní gramatika bez ε-pravidel
1: Uspořádej libovolně N, N = {A1, . . . , An}
2: for i ← 1 to n do
3: for j ← 1 to i − 1 do
4: for all pravidlo tvaru Ai → Aj α do
5: přidej pravidla Ai → β1α | . . . | βk α
6: (kde Aj → β1 | . . . | βk jsou všechna pravidla pro Aj )
7: vypusť pravidlo Ai → Aj α
8: odstraň případnou přímou levou rekurzi na Ai
Příklad:
A → Bd | c
B → Bdd | Ccc | aAd
C → Aa
16 / 21
Korektnost algoritmu
Konečnost.
Ekvivalence gramatik: Všechny úpravy jsou dle Lemmatu o
substituci nebo odstraňují přímou levou rekurzi.
Výsledná gramatika je nelevorekurzivní:
1. po i-té iteraci vnějšího cyklu začíná každé Ai -pravidlo buď
terminálem nebo neterminálem Ak , kde k > i.
2. po j-té iteraci vnitřního cyklu začíná každé Ai -pravidlo buď
terminálem nebo neterminálem Ak , kde k > j.
Výsledná gramatika je bez ε-pravidel.
17 / 21
Greibachové normální forma
Definice 3.33.
Bezkontextová gramatika G = (N, Σ, P, S) je v Greibachové normální
formě (GNF), právě když
▶ G je bez ε-pravidel a
▶ každé pravidlo z P je tvaru A → aα, kde a ∈ Σ a α ∈ N∗
(s případnou vyjímkou pravidla S → ε).
Věta 3.34.
Každý bezkontextový jazyk lze generovat bezkontextovou gramatikou
v Greibachové normální formě.
Důkaz.
L = ∅: zřejmé (S → aS)
L ̸= ∅: 1. z vlastní gramatiky eliminujeme levou rekurzi
2. pak převedeme do GNF
18 / 21
Příklad
A → Ba | Db | c
B → CC
C → aE
D → CDa | Eb
E → bb
19 / 21
Algoritmus transformace do GNF
Vstup: Nelevorekurzivní CFG G = (N, Σ, P, S) bez ε-pravidel
Výstup: Ekvivalentní gramatika v GNF
1: Najdi lineární uspořádání ≺ splňující (A → Bα) ∈ P =⇒ A ≺ B
2: Označme N = {A1, . . . , An | Ai−1 ≺ Ai , 1 < i ≤ n}
3: for i ← n − 1 downto 1 do
4: for all pravidlo tvaru Ai → Aj α, kde j > i do
5: přidej pravidlo Ai → β1α | . . . | βk α
6: (kde Aj → β1 | . . . | βk jsou všechna Aj -pravidla)
7: vypusť pravidlo Ai → Aj α
8: Nahraď potřebné terminály novými neterminály a přidej příslušná
pravidla
20 / 21
Korektnost algoritmu
Konečnost.
Ekvivalence gramatik.
Výsledná gramatika je v GNF.
21 / 21