Cvičení druhé

LL(k), SLL(k), SLL(k) analyzátor, Tra-ce LL(1) gramatik I

1) Ověřte, zda gramtika je LL(2)

 S -> X
 X -> Y | bYa
 Y -> a | epsilon

2) Ověřte, zda gramtika je LL(3)

 S -> aAaB | bAbB
 A -> a | ab
 B -> aB | a

3) Ukažte, že gramatika není LL(k) pro žádné k

 S -> A | B
 A -> aAb | 0
 B -> aBbb | 1

4) Ukažte, že gramatika je LL(k)

S -> aT T -> SA | A A -> bB | c B -> b^k-1d | epsilon

5) Ověřte, zda gramtika je SLL(2)

 S -> X
 X -> Y | bYa
 Y -> a | epsilon

6) Ověřte, zda gramtika je SLL(3)

 S -> aAaB | bAbB
 A -> a | ab
 B -> aB | a

7) Navrhěte gramatiku která není LL(k) pro žádné k.

8) Najděte nejmenší i takové, že gramatika je SLL(k), ale není SLL(i) pro žádné i menší než k.

 S -> dBC
 S -> dCB
 A -> epsilon
 A -> aA
 B -> bAaS
 B -> b
 C -> cC
 C -> c

9)Navrhněte gramatiku, která je SLL(2) ale není SLL(1)

10) Navrhněte SLL(3) anlyzátor pro gramatiku a analyzujte slova bababab,acaac,abaac

 (1) S -> baAa
 (2) S -> baBb
 (3) A -> aA
 (4) A -> aB
 (5) B -> bA
 (6) B -> epsilon

 (1) S -> aAaA
 (2) S -> aBaB
 (3) A -> aA
 (4) A ->c
 (5) B -> bD
 (6) D -> bD
 (7) D -> epsilon

11) Aplikujte rohovou substituci na následující gramatiky

 S -> AB
 A -> aA | epsilon
 B -> bA | epsilon

12) Odstraňte levou rekurzi v následující gramatice

 S -> SAb | SBa | Scc | AaB | bc
 A -> aAa | epsilon
 B -> BbB | b

13) Aplikujte levou faktorizaci na gramatiky

 A -> abB | acC | acdB | bBb | bbC
 B -> bbaB | bbadC | cBC
 C -> aA | b

 A -> aBxx | aCyy | zy | zx
 B -> aBx | z
 C -> yCy | z

 A -> aB | CB
 C -> aC | bB
 B -> cB | d

 A -> Bc |Dd
 B -> bx | y
 D -> Bz

 S -> A | AbcB |bc
 A -> a
 B -> A | dd

 S -> A | B
 A -> aAb | epsilon
 B -> aBc | epsilon