Nomor 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
Tentukan First, Follow dan Table dari Production diatas!
Jawaban:
– Left Recursive
S-> A+SS’ | A-SS’ | B*AS’
S’-> +AS’ | -AS’ | e
B-> aBB’ | a(a+B)B’ | bB’
B’-> (a+B)B’ | *aB’ | e
A->a
– Left Factoring
S-> AS” | B*AS’
S’-> +AS’ | -AS’ | e
S”-> +SS’ | -SS’
B-> aB” | bB’
B’-> (a+B)B’ | *aB’ | e
B”-> BB’ | (a+B)B’
A->a
First (S) = {a, b}
First (S’) = {+, -, e}
First (S”) = {+, -}
First (B) = {a, b}
First (B’) = {(, *, e}
First (B”) = {a, b, (}
First (A) = {a}
Follow (S) = {$, +, -}
Follow (S’) = {$, +, -}
Follow (S”) = {$, +, -}
Follow (B) = {), (, *}
Follow (B’) = {), (, *}
Follow (B”) = {), (, *}
Follow (A) = {$, +, -}
Nomor 2 :
S->if E the 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
Jawab:
S->if E then S S’ | V:=E
S’-> ε |else S
V->id V’
V’-> ε | [E]
E->T E’
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)={ $ , else }
Follow (S’)= { $ , else }
Follow (V)= { : , * , / }
Follow (V’)= { [ , : , * , / }
Follow (E)= { then, $ , else }
Follow (E’)= { then, $ , else }
Follow (T)= { + , – }
Follow (T’)= { + , – }
Follow (F)= { * , / }
Nomor 3 :
S -> a = A
A -> aA’ | bA’
A’ -> +AA’ | є
First :
First (S) = { a }
First (A) = {a , b}
First (A’) = {+ , є }
Follow :
Follow (S) = { $ }
Follow (A) = { $ , +}
Follow (A’) = { $ , + }
Table :
|
$ |
+ |
a |
b |
|
|
S |
S -> a = A | |||
|
A |
A -> aA’ | A -> bA’ | ||
|
A’ |
A’ -> e |
A’ -> +AA’ | e |
Nomor 4 :
be -> bt be’
be’ -> or bt be’
be’ -> e
bt -> bf bt’
bt’ -> and bf bt’
bt’ -> e
bf -> not bf
bf -> ( be)
bf -> true
bf -> false
Periksalah input sebagai berikut : not (true or false) and true and true and false not (false) true
a. Menentukan First
First (be) : not, (, true, false
First (be’) : or, e
First (bt) : not, (, true, false
First (bt’) : e, and
First (bf) : not, (, true, false
b. Menentukan follow
Follow (be) : { $, ) }
Follow (be’) : { $, ) }
Follow (bt) : { or, $, ) }
Follow (bt’) : { or, $, ) }
Follow (bf) : { or, $, ), and }
c. Tabel
| not | true | false |
|
and | ( | ) | $ | |
| be | be -> bt be’ | be -> bt be’ | be -> bt be’ | be -> bt be’ | ||||
| be’ | be’ -> or bt be’ | |||||||
| bt | bt -> bf bt’ | bt -> bf bt’ | bt -> bf bt’ | |||||
| bt’ | bt’ -> e | bt’ -> and bf bt’ | ||||||
| bf | bf -> not bf | bf ->true | bf ->false |
d. Pemeriksaan Input
| 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. | notbfbt’ 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. | truebt’ 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. | orbt 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. | falsebt’ 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. | truebt’ 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. | truebt’ 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. | falsebt’ be’ $ | false not (false) true $ | pop false |
| 32. | bt’ be’ $ | not (false) true $ | ditolak |