Christine Sotanto

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

http://binus.ac.id