1501167380 – Angela Muliawan

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

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

3. Soal :

S ->  a = A

A -> aA’ | bA’

A’ -> +AA’ | e

First :

First (S) = { a }

First (A) = {a , b}

First (A’) = {+ , e }

Follow :

Follow (S) = { $ }

Follow (A) = { $ , +}

Follow (A’) = { $ , + }

Table :

4. Diketahui grammar :

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

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

Menentukan follow

Follow (be)         : { $, ) }

Follow (be’)        : { $, ) }

Follow (bt)          : { or, $, ) }

Follow (bt’)         : { or, $, ) }

Follow (bf)          : { or, $, ), and }

Tabel

Pemeriksaan Input

www.binus.ac.id