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 Factory

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) = {$, +, -}

 

	a	b	(	)	+	–	*	$
S	S-> AS’’ | B*AS’	S-> B*AS’
S’					S’-> +AS’ | e	S’-> -AS’ | e		S’->e
S’’					S’’-> +SS’	S’’-> -SS’
B	B-> aB”	B-> bB’
B’			B’-> (a+B)B’ | e	B’->e			B’-> *aB’ | e
B’’	B”-> BB’	B”-> BB’	B”-> (a+B)B’
A	A->a

 

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)= { * , / }

if

then

else

:

=

id

[

]

(

)

+

–

*

/

const

$

S

S->if E then S S’

S-> V:=E

S’

S’-> εS’->else S

S’-> ε

V

V->id V’

V’

V’-> ε

V’-> εV’->[E]

V’-> ε

V’-> ε

E

E->T E’

E->T E’

E->T E’

E’

E’-> ε

E’-> ε

E’-> +TE’E’-> -TE’

E’-> +TE’

E’-> -TE’

E’-> ε

T

T’->FT’

T’->FT’

T’->FT’

T’

T-> ε

T-> ε

T’-> *FT’

T’->/FT’

F

F->V

F->(E)

F->const

3

S ->  a = A

A -> aA’ | bA’

A’ -> +AA’ | e

First (S) = { a }

First (A) = {a , b}

First (A’) = {+ , e }

Follow (S) = { $ }

Follow (A) = { $ , +}

Follow (A’) = { $ , + }

	$	+	a	b
S			S ->  a = A
A			A -> aA’ | bA’	A -> aA’ | bA’
A’	A’ -> e	A’ -> +AA’ A’ -> e

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	or	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’

bfbf à not bfbf àtruebf à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

www.binus.ac.id