IB102 – úkol 8, příklad 3 – řešení Odevzdání: 30. 11. 2015
Vypracoval(a): UČO:
Skupina:
3. [2 body] Uvažme bezkontextovou gramatiku G = (N, Σ, P, S), kde
N = {S, X, V }
Σ = {if, then, else, fi, while, do, done, ++, −−, a, b, ;}
P = {(1) S → X,
(2) S → X;S,
(3) X → if V then S else S fi,
(4) X → while V do S done,
(5) X → V ++,
(6) X → V −−,
(7) X → a,
(8) X → b,
(9) V → a,
(10) V → b}.
Pro gramatiku G sestrojte syntaktický analyzátor metodou zdola nahoru. Analyzujte slovo
„while a do b; a −− done“ a zapište čísla pravidel gramatiky G v pořadí, ve kterém
se při analýze tohoto slova použijí odpovídající přechody analyzátoru.
Poznámka: Dobře si všimněte, jaká je množina terminálů gramatiky, zejména, že terminály
jsou i znaky if, then, else, fi, while, do, done, ++, −− a ;. U všech terminálů
jsme použili tučné zvýraznění, abychom tím dali najevo, že jde o jeden terminál, i když
se některé z nich skládají ze dvou či více písmen. Bílé místo (mezery) ve slově je jen pro
lepší čitelnost, mezery nepatří mezi terminály.
Analyzátor je zásobníkový automat M = ({q, r}, Σ, N ∪ Σ ∪ {⊥}, δ, q, ⊥, {r}), kde
∀c ∈ Σ δ(q, c, ε) = {(q, c)}
δ(q, ε, X) = {(q, S)}
δ(q, ε, X; S) = {(q, S)}
δ(q, ε, if V then S else S fi) = {(q, X)}
δ(q, ε, while V do S done) = {(q, X)}
δ(q, ε, V ++) = {(q, X)}
δ(q, ε, V −−) = {(q, X)}
δ(q, ε, a) = {(q, X), (q, V )}
δ(q, ε, b) = {(q, X), (q, V )}
δ(q, ε, ⊥S) = {(r, ε)}
Automat akceptuje koncovým stavem.
IB102 – úkol 8, příklad 3 – řešení Odevzdání: 30. 11. 2015
Vypracoval(a): UČO:
Skupina:
Analýza slova „while a do b; a −− done“:
q,while a do b; a −− done, ⊥
while
q, a do b; a −− done, ⊥while
a
q, do b; a −− done, ⊥while a
ε
q, do b; a −− done, ⊥while V (9)
do
q, b; a −− done, ⊥while V do
b
q, ; a −− done, ⊥while V do b
ε
q, ; a −− done, ⊥while V do X (8)
;
q, a −− done, ⊥while V do X;
a
q, −− done, ⊥while V do X; a
ε
q, −− done, ⊥while V do X; V (9)
−−
q, done, ⊥while V do X; V −−
ε
q, done, ⊥while V do X; X (6)
ε
q, done, ⊥while V do X; S (1)
ε
q, done, ⊥while V do S (2)
done
q, ε, ⊥while V do S done
ε
q, ε, ⊥X (4)
ε
q, ε, ⊥S (1)
ε
r, ε, ε
Tedy automat slovo akceptuje.
Použitá pravidla: 9, 8, 9, 6, 1, 2, 4, 1.