Nedeterministická syntaktická analýza shora dolů
– příklady k procvičení
Příklad 1
Mějme bezkontextovou gramatiku G = ({S, A, B}, {a, b}, P, S), kde množina pravidel P je definována
takto:
S → Aa | bBS
A → aB | SA | b
B → bAB | aa
Úkoly:
1. Zkonstruujte zásobníkový automat M pro nedeterministickou syntaktickou analýzu shora
dolů.
2. Proveďte nedeterministickou syntaktickou analýzu shora dolů na slově abbaaa.
Příklad 2
Mějme bezkontextovou gramatiku G = ({S, X, Y }, {0, 1}, P, S), kde množina pravidel P je
definována takto:
S → 0X0 | 1X | 1Y X
X → 0 | 1Y 1
Y → 1 | SY
Úkoly:
1. Zkonstruujte zásobníkový automat M pro nedeterministickou syntaktickou analýzu shora
dolů.
2. Zapište akceptující výpočet automatu M na slově 100010.
Příklad 3
Mějme bezkontextovou gramatiku G = ({S, R, T}, {t, u, v}, P, S), kde množina pravidel P je
definována takto:
S → tR | uT | TtS
R → v | ε
T → vuR | RRt | vu
Úkoly:
1. Zkonstruujte zásobníkový automat M pro nedeterministickou syntaktickou analýzu shora
dolů.
2. Zapište akceptující výpočet automatu M na slově vutuvt.
1
Příklad 4
Mějme bezkontextovou gramatiku G = ({S, A, B}, {a, b, c, d}, P, S), kde:
P = {S → ε | ad | bc | aAd | bBc,
A → ad | aAd | bBc | bc,
B → bc | bBc}
1. Zkonstruujte zásobníkový automat M pro nedeterministickou syntaktickou analýzu shora
dolů.
2. Proveďte nedeterministickou syntaktickou analýzu shora dolů na slově abbccd
2