index předchozí 1 2 3 4 5 6 7 následující

Cvičení první

Funkce FIRST a FOLLOW

1) Je dána gramatika G. Navrhněte PDA (zásobníkový automat), který
analyzuje slova nad abecedou {a,b,c} metodou shora dolů.

  S -> aSa | bSc | aA
  A -> bbAb | epsilon

2) Navrhněte LL(1) jednoduchou gramatiku pro

{1ⁿ a 0ⁿ 1^m a 0^m | n>0, m>0}
{1ⁿ a 0ⁿ 1^m a 0^m | n>0, m>=0}

3) Počítejte FI_k(S,BBb,SacB) a FO_k(S,A,C) pro k=1,2,3,4 a pro danou gramtiku G:

  S -> aAa | B
  A ->  aA | bSCe | epsilon
  B ->  aC | epsilon
  C ->   d | epsilon

4) Podle algoritmu pro počítání fce FIRST řešte následující:

First₂(A) pro
```
 A -> Aa | b 
```
First₃(A) pro
```
 A -> Aa | b 
```
First₂(A) First₂(B) pro
```
 A -> aB | a
 B -> bB | d | epsilon 
```

5) Vypočítejte FOLLOW_k pro k=1,2,3,4 pro všechny neterminály této gramatiky:

  S -> aABbCD
  S -> epsilon
  A -> ASd
  A -> epsilon
  B -> SAc
  B -> xC
  B -> epsilon
  C -> Sy
  C -> Cz
  C -> epsilon
  D -> aBD
  D -> epsilon

  S -> aBcB
  A -> aA | Aa
  B -> DAc| bA
  C -> cBc | aaB
  D -> d | dC