Kuis 1 April 2014 Teknik Kompilasi

Posted April 1st, 2014 by agungroyat

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 Parsing!

Jawab:

S -> A+SS’ | A – SS’ | B * AS’

S’ -> +AS’ | -AS’ | ε

S = >  AF | B * AS’

S’ -> +AS’ | -AS’ | ε

S’’ -> +SS’ | -SS’

B -> aBB’ | a(a+B)B’ | bB’

B’-> (a+B)B’ | *aB’

B -> aG | 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,(}

Follow S -> {$,+,-}

Follow S’ -> {$}

Follow B -> {$,a,b,)}

Follow B’ -> {$}

Follow S’’ -> {$,+,-}

Follow B’’ -> {$,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, dan Table Parsing!

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. S -> a = A

A -> aA’ | bA’

A’ -> +AA’ | ε

Tentukan First, Follow, dan Table Parsing!

Jawab:

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 sbb:

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

Tentukan input ini diterima atau ditolak!

not(true or false) and true 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,flase

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

www.binus.ac.id