Kuis Teknik Kompilasi – Top Down Parsing

Kuis Teknik Kompilasi

 

  1. Perhatikan CFG (Context Free Grammar) berikut ini :

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 & Table dari Production data.

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 :

–          First (S)         = { a,b }

–          First (Sˈ)       = { +,-,ԑ }

–          First (Sˈˈ)      = { +,- }

–          First (B)        = { a,b }

–          First (Bˈ)       = { (,a,ԑ }

–          First (Bˈˈ)      = { a,b,c }

–          First (A)        = { a }

Follow :

–          Follow (S)    = { $ }

–          Follow (Sˈ)   = { $ }

–          Follow (Sˈˈ) = { $ }

–          Follow (B)    = { *,),(,a }

–          Follow (Bˈ)  = { *,),(,a }

–          Follow (Bˈˈ) = { *,),(,a }

–          Follow (A)   = { +,-,$ }

Tabel Produksi dari hasil diatas:

a

b

+

(

)

*

$

S

S -> ASˈˈ

S -> B*AS

Sˈ -> +ASˈ

Sˈ -> ASˈ

Sˈ -> ԑ

Sˈˈ

Sˈˈ -> +SSˈ

Sˈˈ -> -SSˈ

B

B -> aBˈˈ

B -> bBˈ

Bˈ -> aBˈ , Bˈ -> ԑ

Bˈ -> (a+B)Bˈ , Bˈ -> ԑ

Bˈ -> ԑ

Bˈ -> ԑ

Bˈˈ

Bˈˈ -> BBˈ

Bˈˈ -> BBˈ

Bˈˈ -> (a+B)Bˈ

A

A -> a

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

Tentukan first, follow, dan tabel dari produksi tersebut.

Jawab

S -> if E then S’ | v := E

S’ ->ε | else S

V -> idV’

V’ -> ε | [E]

E ->TE’

E’ -> +TE’ | -TE’ | ε

T -> FT’

T’ -> *FT’ | /FT’ | ε

F -> V | (E) | const

  • Menentukan first

first (S) = { id, if }

first (S’) = { ε, else }

first (V) = { id }

first (V’) = { ε, [ }

first (E) = { id, (, const }

first (E’) = { +, -,  ε }

first (T) = { id, (, const }

first (T’) = { *, / ,  ε }

first (F) = { id, (, const }

  • Menentukan follow

follow (S) = { $, else }

follow (S’) = { $, else }

follow (V) = { : }

follow (V’) = { : }

follow (E) = { ], ) }

follow (E’) = { ], ) }

fololw (T) = { +, -, ], ) }

follow (T’) = { +, -, ], ) }

follow (F) = { *, /, +, -, ] , ) }

  • Tabel

id

if

else

[

(

const

+

*

/

:

)

]

$

S

S->V:=E

S->if E then S S’

S’

S’->else S

S’->ε

V

V->idV’

V’

V’->[E]

V’->ε

E

E->TE’

E->TE’

E’->TE’

E’

E’->+TE’

E’->-TE’

E’-> ε

E’->ε

T

T->FT’

T->FT’

T->FT’

T’

T’-> ε

T’-> ε

T’-> *FT’

T’->/FT’

T’-> ε

T’->ε

F

F->V

F->(E)

F->const

 

3. S -> a= A

A -> aA’|bA’

A’ -> + AA’ |  ԑ

Carilah First dan Follow serta buatlah tabel produksinya!

First (S) = {a}

First (A) = {a,b}

First (A’) = {+, ԑ}

Follow (S) = {$} menggunakan syarat algoritma follow 1

Follow (A) = {$, +} menggunakan syarat algoritma follow 2 dan 3a

Follow (A’) = {$, +} menggunakan syarat algoritma follow 2

Sehingga tabel produksinya adalah

a

b

+

$

S

S -> a=A

A

A -> aA’

A ->bA’

A’

A’ -> +AA’ , A’-> ԑ

A’ -> ԑ

4. 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

Cek string sbb: not (true or false) and true and true and false not (false) true

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$

Rejected

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *