- Vytvořte minimální deterministický konečný automat k regulárnímu výrazu
- 0*(10*1O*)*
- (a|b)*abb
- K zadané gramatice vytvořte levý a pravý rozklad věty i*i+i
a nakreslete derivační strom. Jak se liší stromy pro levý
a pravý rozklad? Za jakého předpokladu mohou být různé?
E -> T E'
E' -> * T E' | e
T -> F T'
T' -> + F T' | e
F -> i | ( E )
- Předveďte činnost LR analyzátoru na řetězcích (ii) a (i|i)
pro následující gramatiku a rozkladovou tabulku:
(1) E -> id (5) E1 -> E E1
(2) E -> '(' L ')' (6) E1 -> '|' E
(3) L -> e (7) E1 -> e
(4) L -> E E1
| id ( ) / # | E L E1
----+-----------------------------+----------------
0 | s2 s3 | 1
1 | acc |
2 | r1 r1 r1 r1 r1 |
3 | s2 s3 r3 | 5 4
4 | s8 |
5 | s2 s3 r7 s11 | 10 9
8 | r2 |
9 | r4 |
10 | s2 s3 r7 s11 | 10 13
11 | s2 s3 | 14
13 | r5 |
14 | r6 |
- Předveďte činnost LR analyzátoru na následujících gramatikách
a rozkladových tabulkách:
a) A -> a A | a
| a # | A
---+-----------+---
0 | s2 | 1
1 | acc |
2 | s2 r2 | 3
3 | r1 |
b) E -> E E + | E E * | id
| id + * # | E
---+---------------------+---
0 | s2 | 1
1 | s2 acc | 3
2 | r3 r3 r3 r3 |
3 | s2 s4 s5 | 3
4 | r1 r1 r1 r1 |
5 | r2 r2 r2 r2 |
c) E -> + E E | * E E | id
| id + * # | E
---+---------------------+---
0 | s4 s2 s3 | 1
1 | acc |
2 | s4 s2 s3 | 5
3 | s4 s2 s3 | 6
4 | r3 r3 r3 r3 |
5 | s4 s2 s3 | 7
6 | s4 s2 s3 | 8
7 | r1 r1 r1 r1 |
8 | r2 r2 r2 r2 |
d) R -> i | R R | R + R | ( R ) | R *
| i + ( ) * # | R
---+-------------------------------+---
0 | s2 s3 | 1
1 | s2 s5 s3 s6 acc | 4
2 | r1 r1 r1 r1 r1 r1 |
3 | s2 s3 | 7
4 | s2 r2 s3 r2 s6 r2 | 4
5 | s2 s3 | 8
6 | r5 r5 r5 r5 r5 r5 |
7 | s2 s5 s3 s9 s6 | 4
8 | s2 r3 s3 r3 s6 r3 | 4
9 | r4 r4 r4 r4 r4 r4 |
e) S -> ( L )
L -> L , N | N
N -> i | i = n
| ( ) , i = n # | S L N
---+------------------------------------+-----------
0 | s2 | 1
1 | acc |
2 | s5 | 3 4
3 | s6 s7 |
4 | r3 r3 r3 r3 r3 r3 r3 |
5 | r4 r4 r4 r4 s8 r4 r4 |
6 | r1 r1 r1 r1 r1 r1 r1 |
7 | s5 | 9
8 | s10 |
9 | r2 r2 r2 r2 r2 r2 r2 |
10 | r5 r5 r5 r5 r5 r5 r5 |
- Pro gramatiku z příkladu 4e) vytvořte graf nedeterministického konečného
automatu pro rozpoznávání perspektivních prefixů
a převeďte jej na deterministický.
- Řešte zadání příkladu 5 pro gramatiku
R -> R + K | K
K -> K I | I
I -> I * | ( R ) | id
- Vytvořte rozkladovou tabulku SLR(0) pro gramatiku
E -> E' T
E' -> E ,
E' -> e
T -> ( E )
T -> a
- Vytvořte rozkladovou tabulku SLR(0) pro gramatiku
S -> A )
A -> (
A -> A a
a předveďte činnost analyzátoru na řetězci (a(a)).
- Vytvořte kanonický soubor LR(0) položek pro gramatiku
E -> i | ( L )
L -> e | E E1
E1 -> E E1 | / E | e
- Na základě kanonického souboru LR(0) položek z příkladu 10
vytvořte SLR(1) rozkladovou tabulku. Lze vytvořit i LR(0)
tabulku?
- Pro gramatiku z příkladu 10 vytvořte nedeterministický
automat LR(0).
- Vytvořte LR(0) rozkladovou tabulku pro gramatiku
S -> A )
A -> ( | A a
a předveďte činnost analyzátoru na řetězci (a(a)). Porovnejte
chování tohoto analyzátoru s analyzátorem pro silnou LR(0)
gramatiku z příkladu 9.
- Pro následující gramatiku vytvořte množinu LR(1) položek,
automat a LR(1) rozkladovou tabulku:
E -> E E +
E -> E E *
E -> id
-
Vytvořte LR(1) a SLR(1) rozkladové tabulky pro gramatiku
S -> S ( S ) | e
a porovnejte činnost příslušných analyzátorů na řetězci ())$.
- Vytvořte LR(1) rozkladovou tabulku pro gramatiku
S -> a | ( S R
R -> ; S R | )
- Vytvořte nedeterministický konečný automat rozpoznávající
perspektivní prefixy pro LR(1) gramatiku
A -> A a | a
Automat převeďte na deterministický a sestavte na jeho
základě rozkladovou tabulku LR(1).
- Vytvořte LALR(1) rozkladovou tabulku pro gramatiku
a) S -> S a S b | e
b) E -> E E + | E E * | id
- Vytvořte LALR(1) rozkladovou tabulku na základě nejednoznačné
gramatiky
E -> E and E | E or E | id
Konflikty vyřešte tak, aby operátor and měl větší prioritu
než operátor or, přičemž oba operátory budou asociativní
zleva.
- Vytvořte a porovnejte SLR(1), LALR(1), resp. LR(1) rozkladové
tabulky pro gramatiky z příkladu 4.
- Uvažujte nejednoznačnou gramatiku
S -> A S | b
A -> S A | a
- Vytvořte k této gramatice soubor LR(0) položek.
- Vytvořte nedeterministický konečný automat, jehož stavy
jsou LR(0) položky z (a). Ukažte, že graf přechodů
kanonického souboru LR(0) položek této gramatiky je shodný
s deterministickým automatem sestrojeným z automatu
nedeterministického metodou konstrukce podmnožin.
- Vytvořte SLR rozkladovou tabulku.
- Ukažte všechny přechody, které umožňuje tabulka z (c) při
vstupu abab.
- Vytvořte kanonickou rozkladovou tabulku.
- Vytvořte LALR(1) rozkladovou tabulku.
- Uvažujte následující gramatiku:
E -> E + T | T
T -> T F | F
F -> F * | a | b
- Vytvořte pro tuto gramatiku SLR rozkladovou tabulku.
- Vytvořte LALR rozkladovou tabulku.
- Proveďte zhuštění rozkladových tabulek z příkladů 18-22.
- Ukažte, že následující gramatika
S -> A a A b | B b B a
A -> e
B -> e
je LL(1), ale není SLR(1).
- Ukažte, že gramatika
S -> A a | b A c | d c | b d a
A -> d
je LALR(1), ale není SLR(1).
- Ukažte, že gramatika
S -> A a | b A c | B c | b B a
A -> d
B -> d
je LR(1), ale není LALR(1).