1. Perhatikan CFG berikut
S ->S+A | S – A | A+S | A-S | B*A
B -> aB | B(a+B) | B*a | a(a+B)|b
A-> a
Tentukan first , follow & table dari produksi di atas
Jawab:
S -> A+SS’ | A – SS’ | B * AS’
S’ -> +AS’ | -AS’ | ε
S = > AF | B * AS’
F -> +SS’ | -SS’
S’ -> +AS’ | -AS’ | ε
B -> aBB’ | a(a+B)B’ | bB’
B’-> (a+B)B’ | *aB’
B -> aG | bB’
G -> BB’ | (a+B)B’
B’ -> (a+B)B’ | *aB’
A -> a
First S -> {a,b}
First F -> {+,-}
First S’ -> {+,-, ε}
First B -> {a,b}
First G -> {a,b,(}
First B’ -> {(,*}
Follow S -> {$,+,-}
Follow S’ -> {$}
Follow B -> {$,a,b,)}
Follow B’ -> {$}
Follow F -> {$,+,-}
Follow G -> {$,a,b,)}
| a | b | + | – | * | ( | ) | $ | |
| S | S -> AF | S -> B*AS’ | ||||||
| S’ | S->+AS’ | S->-AS’ | S-> ε | |||||
| B | B->aG | B->bB’ | ||||||
| B’ | B->*aB’ | B’->(a +b)B’ |
||||||
| F | F->+SS’ | F->-SS’ | ||||||
| G | G->BB’ | G->BB’ |
|
G->(a+b)B’ |
2. S -> if E then S | if E then S else S | V:= E
S’->ε | else S
E-> TE’
E’-> TE’ | -TE’ | ε
T->FT’
T’-> FT’|/FT’|ε
F-> V|(E)|const
V-> id V’
V’-> ε|[E]
Tentukan first , follow & table dari produksi di atas
first(S) = {if, id}
first(S’) = {ε, else}
first(E) = { id, ( , const}
first(E’) = {+, -, ε}
first(T) = {id,(, const}
first(T’) = {*, /,ε }
first(F) = {id,(, const}
first(V) = {id}
first(V’) = {a b c}
follow(S) = {$}
follow(S’) = {$}
follow(E) = { then, $,),]}
follow(E’) = { then, $,),]}
follow(T) = {+, -}
follow(T’) = {+, -}
follow(F) = {*,/ }
follow(V) = {:}
follow(V’) = {:}
| if | Id | else | ( | const | + | – | * | / | [ | $ | then | ) | ] | : | |
| S | S-> if E then S S’ | S->V:=E | |||||||||||||
| S’ | S->else S | ||||||||||||||
| E | E->TE’ | E->TE’ | E->TE’ | ||||||||||||
| E’ | E’->TE’ | E’->TE’ | E’->TE’ | E->ε | E->ε | E->ε | |||||||||
| T | T->FT’ | T->FT’ | T->FT’ | ||||||||||||
| T’ | T’->ε | T’->ε | T’->*FT’ | T’->/FT’ | |||||||||||
| F | F->V | F->(E) | F->const | ||||||||||||
| V | V->idV’ | ||||||||||||||
| V’ | V’->[E] | V->ε |
3. Dari CFG berikut
S -> a=A
A ->a A’ | bA’
A’ -> +AA’ | ε
Tentukan first, follow & table dari produksi di atas
First (S) = {a} Follow (S) = {$}
First (A)={a,b} Follow(A)={$,+}
First(A’)={+,ε } Follow(A’)={$,+}
| a | b | + | $ | |
| S | S -> a=A | |||
| A | A-> aA’ | A-> bA’ | ||
| A’ | A’ -> +AA’ | A’ -> ε |
4. Diketahui Grammar:
be-> bt be’
be’ -> or bt be’
be’ -> e
bt-> bf bt’
bt’ -> and bf bt’
bt’-> ε
bf -> not bf
bf ->( be)
bf-> true
bf-> false
Perikas input sbb not(true or false) and true and false not(false) true
Jawab:
first (be) = not, (, true, false
first (be’) = or, ε
first (bt) = not, (, true, false
first (bt’) = and, ε
first (bf) = not, (, true, false
follow (be) = { $, )}
follow (be’) = { $, )}
follow (bt) = { or, $, )}
follow (bt’) = {or, $, )}
follow (bf) = {or, $, ), and}
| or | not | ( | ) | true | false | and | $ | |
| be | be-> bt be’ | be->bt be’ | be-> bt be’ | be->bt be’ | ||||
| be’ | be’-> or bt be’ | be’-> ε | be’-> ε | |||||
| bt | bt-> bf bt’ | bt->bf bt’ | bt->bf bt’ | bt->bf bt’ | ||||
| bt’ | bt’-> ε | bt’-> ε | bt’-> and bf bt’ | bt’-> ε | ||||
| bf | bf -> not bf | bf->(be) | bf->true | bf->false |
|
No |
Stack |
Input |
Output |
| 1. | be $ | not (true or false) and true and true and false not (false) true | be -> bt be’ |
| 2. | bt be’ $ | not (true or false) and true and true and false not (false) true | bt -> bf bt’ |
| 3. | bf bt’ be’ $ | not (true or false) and true and true and false not (false) true | bf -> not bf |
| 4. | not bf bt’ be’ $ | not (true or false) and true and true and false not (false) true | pop not |
| 5. | bf bt’ be’ $ | (true or false) and true and true and false not (false) true | bf -> (be) |
| 6. | (be) bt’ be’ $ | (true or false) and true and true and false not (false) true | pop ( |
| 7. | be) bt’ be’ $ | true or false) and true and true and false not (false) true | be -> bt be’ |
| 8. | bt be’) bt’ be’ $ | true or false) and true and true and false not (false) true | bt -> bf bt’ |
| 9. | bf bt’ be’) bt’ be’ $ | true or false) and true and true and false not (false) true | bf -> true |
| 10. | true bt’ be’) bt’ be’ $ | true or false) and true and true and false not (false) true | pop true |
| 11 | bt’ be’) bt’ be’ $ | or false) and true and true and false not (false) true | bt’ -> ε |
| 12 | be’) bt’ be’ $ | or false) and true and true and false not (false) true | be’ ->or bt be’ |
| 13. | or bt be’ ) bt’ be’ $ | or false) and true and true and false not (false) true | pop or |
| 14. | bt be’) bt’ be’ $ | false) and true and true and false not (false) true | bt -> bf bt’ |
| 15. | bf bt’ be’) bt’ be’ $ | false) and true and true and false not (false) true | bf -> false |
| 16. | false bt’ be’) bt’ be’ $ | false) and true and true and false not (false) true | pop false |
| 17. | bt’ be’) bt’ be’ $ | ) and true and true and false not (false) true | bt’ -> ε |
| 18. | be’) bt’ be’ $ | ) and true and true and false not (false) true | be’ -> ε |
| 19. | ) bt’ be’ $ | ) and true and true and false not (false) true | pop ) |
| 20. | bt’ be’ $ | and true and true and false not (false) true | bt’ -> and bf bt’ |
| 21. | and bf bt’ be’ $ | and true and true and false not (false) true | pop and |
| 22. | bf bt’ be’ $ | true and true and false not (false) true | bf -> true |
| 23. | true bt’ be’ $ | true and true and false not (false) true | pop true |
| 24. | bt’ be’ $ | and true and false not (false) true | bt’ -> and bf bt’ |
| 25. | and bf bt’ be’ $ | and true and false not (false) true | pop and |
| 26. | bf bt’ be’ $ | true and false not (false) true | bf -> true |
| 27. | true bt’ be’ $ | true and false not (false) true | pop true |
| 28. | bt’ be’ $ | and false not (false) true | bt’ -> and bf bt’ |
| 29. | and bf bt’ be’ $ | and false not (false) true | pop and |
| 30. | bf bt’ be’ $ | false not (false) true | bf -> false |
| 31. | false bt’ be’ $ | false not (false) true | pop false |
| 32. | bt’ be’ $ | not (false) true | ditolak |