IB102 – úkol 8, příklad 2 – řešení Odevzdání: 30. 11. 2015
Vypracoval(a): UČO:
Skupina:
2. [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 shora dolů. 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}, Σ, N ∪ Σ, δ, q, S, ∅), kde
δ(q, ε, S) = {(q, X), (q, X; S)}
δ(q, ε, X) = {(q, if V then S else S fi), (q, while V do S done),
(q, V ++), (q, V −−), (q, a), (q, b)}
δ(q, ε, V ) = {(q, a), (q, b)}
∀c ∈ Σ δ(q, c, c) = {(q, ε)}
Automat akceptuje prázdným zásobníkem.
IB102 – úkol 8, příklad 2 – ř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, S
ε
q,while a do b; a −− done, X (1)
ε
q,while a do b; a −− done, while V do S done (4)
while
q, a do b; a −− done, V do S done
ε
q, a do b; a −− done, a do S done (9)
a
q, do b; a −− done, do S done
do
q, b; a −− done, S done
ε
q, b; a −− done, X;S done (2)
ε
q, b; a −− done, b;S done (8)
b
q, ; a −− done, ;S done
;
q, a −− done, S done
ε
q, a −− done, X done (1)
ε
q, a −− done, V −− done (6)
ε
q, a −− done, a −− done (9)
a
q, −− done, −− done
−−
q, done, done
done
q, ε, ε
Tedy automat slovo akceptuje.
Použitá pravidla: 1, 4, 9, 2, 8, 1, 6, 9.