1501166213-Antonius TS
06PFT
1.S -> S + A | S – A | A + S | A – S | B * A
B -> aB | B(a + B) | B * a | a(a + B) | b
A -> a
Jawab :
S-> AS’’ | B*AS’
S’ -> +AS’ | -AS’ | ε
S’’ -> +SS’ | -SS’
B -> aB’’ | bB’
B’ -> (a+B)B’ | *aB’ | ε
B’’ -> BB’ | (a+B)B’
A -> a
| First (S) | -> | {a,b } |
| First (S’) | -> | { +,-, ε } |
| First (S’’) | -> | {+,- } |
| First (B) | -> | {a,b } |
| First (B’) | -> | { (,*,ε } |
| First (B’’) | -> | { a,b,(} |
| First (A) | -> | {a } |
| Follow (S) | -> | { $} |
| Follow (S’) | -> | { $} |
| Follow (V) | -> | {:} |
| Follow (V’) | -> | {:} |
| Follow (E) | -> | { then,$,),]} |
| Follow (E’) | -> | { then,$,),]} |
| Follow (T) | -> | { +,-} |
| Follow (T’) | -> | { +,- } |
| Follow (F) | -> | { *,/ } |
| a | b | + | – | * | ( | $ | |
| S | S-> AS’’| B*AS’ | S->B*AS’ | |||||
| S’ | S’ -> +AS’ | S’ -> -AS’ | S’ -> ε | ||||
| S’’ | S’’ -> +SS’ | S’’ -> -SS’ | |||||
| B | B -> aB’’ | B -> bB’’ | |||||
| B’ | B’-> ε | B’->*aB’| ε | B’ -> (a+B)B’ | ε | ||||
| B’’ | B’’ -> BB’ | B’’ -> BB’ | B’’->(a+B)B’ | ||||
| A | A -> a |
2. 2. S -> if E then S | if E then S else S | V := E
V -> id | id [E]
E -> E + T | E – T | T
T -> T * F | T / F | F
F -> V | (E) | const
S -> if E then S S’ | V := E
S’ -> ε | else S
V -> idV’
V’ -> ε | [E]
E -> TE’
E’ -> +TE’ | -TE’ | ε
T -> FT’
T ‘-> *FT’ | /FT’ | ε
F -> V | (E) | const
| First (S) | -> | {if,id } |
| First (S’) | -> | { ε,else } |
| First (V) | -> | { id} |
| First (V’) | -> | { ε ,[} |
| First (E) | -> | { id,(,const} |
| First (E’) | -> | { +,-, ε } |
| First (T) | -> | { id,(,const} |
| First (T’) | -> | { *,/, ε } |
| First (F) | -> | { id,(,const} |
| Follow (S) | -> | { $} |
| Follow (S’) | -> | { $} |
| Follow (V) | -> | {:} |
| Follow (V’) | -> | {:} |
| Follow (E) | -> | { then,$,),]} |
| Follow (E’) | -> | { then,$,),]} |
| Follow (T) | -> | { +,-} |
| Follow (T’) | -> | { +,- } |
| Follow (F) | -> | { *,/ } |
3.S-> a = A
A -> aA’ | bA’
A’ -> +AA’ | ε
First (S) : { a }
First (A) : { a, b }
First (A’) : { +, ε }
Follow (S) : { $ }
Follow (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’ -> ε
bt-> bf bt’
bt -> and bf bt’
bt’-> ε
bf -> not bf
bf -> (be)
bf -> true
bf -> false
Inputan: not (true or false) and true and true and false not (false) true
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 |