Pertemuan 8-9 Bottom-Up Parsing

1

Pertemuan 8-9Bottom-Up Parsing

Matakuliah : T0522 / Teknik Kompilasi

Tahun : 2005

Versi : 1/6

2

Learning Outcomes

Pada akhir pertemuan ini, diharapkan mahasiswa

akan mampu :• Mahasiswa dapat mendemonstrasikan prinsip

kerja botton up parsing (C3)• Mahasiswa dapat mendemonstrasikan

pembuatan tabel LR parsing (C3)

3

Outline Materi

• Definisi bottom-up parsing

• Shift reduce parsing

• Implementasi dengan stack

• Operator precedence parsing

• LR-parsing

• algoritma LR parsing

• Konstruksi LR parse table

4

Contents

• Introduction of Bottom-Up Parsing• Handles of String• Stack Implementation of Shift-Reduce Parsing• Conflict During Shift-Reduce Parsing• LR Parsers

– LR(k) Parsers– Constructing SLR (Simple LR) Parser– Constructing LR Parsing Table– LALR Parsing Table

• Using Ambiguous Grammars

5

Introduction of Bottom-Up Parser

• Bottom-Up Parser– Also called shift-reduce parser – Construct a parse tree for an input string beginning at

the leaves and working up toward the root• Reducing a string w to the start symbol S

– At each reduction step, a particular substring RHS of production is replaced with by the symbol on LHS

– e.g.• S → aABe A → Abc | b B → d • process w = abbcde

– Then abbcde → aAbcde → aAde → aABe → S (reduction steps) – S → aABe → aAde → aAbcde → abbcde (rightmost derivation)

6

Handles of String (1/2)

• Handles of a string – A substring that matches the right side of a production

and whose reduction to the non-terminal on LHS presents one step along the reverse of a right derivation

– Formally, handle of a right sentential form γ is a production A → β and a position of γ where the string β may be found and replaced by A to produce the previous right sentential form in a rightmost derivation of γ

– e.g. From the above example abbcde is a right sentential form whose handle is A → b and aAbcde has a handle A → Abc and so on.

– If a grammar is unambiguous, there exist only one handle for every right sentential form

7

Handles of String (2/2)

• Ambiguous Grammar Case – Example 1)

E → E + E

E → E * E

E → (E)

E → id – Example 1 has two different rightmost derivations of

the same string id + id * id• implies that some of the right sentential form has more than

one handle• e.g E → id and E → E + E are handles from E + E * id

8

Stack Implementation of Shift-Reduce Parsing

• Shift – Next input symbol is

shifted onto the top of the stack

• Reduce – A handle on the stack is

replaced by the corresponding non-terminal (A handle always appears on the top of the stack)

• Accept – Announce the

successful completion

　 Stack Content

Input Action

1 $id + id * id

$shift

2 id $ + id * id $reduce by E →

id

3 E $ + id * id $ shift

4 + E $ id * id $ shift

5 id + E $ * id $reduce by E →

id

6 E + E $ * id $ shift

7 * E + E $ id $ shift

8 id * E + E $ $reduce by E →

id

9 E * E + E $ $reduce by E →

E*E

10 E + E $ $ reduce by E+E

11 E $ $ accept

9

Conflict During Shift-Reduce Parsing

• Shift/Reduce conflict – Cannot decide shift or reduce

• Reduce/Reduce conflict – Cannot decide which production to use for reduce

• e.g. – stmt → if expr then stmt

| if expr then stmt else stmt

| other

stack has a handle "if expr them stmt" : shift/reduce conflict

10

LR(k) Parsers

• Concept – left to right scan and rightmost derivation with

k lookahead symbols

LRParsing Program

Action/Goto Table

Input tape

Sta

ck output

Parsing Table

11

Constructing SLR (Simple LR) parser (1/9)

• Viable Prefix – A prefix of a right sentential form that does not continue

past the rightmost handle of that sentential form. It always appears the top of the stack of the shift-reduce parser

• LR(0) item of G – A production of G with a dot at some position of the

RHS

• e.g. A → XYZ ⇒ A → ·XYZ , A → X·YZ , A → XY·Z , A → XYZ·

• Central idea of SLR – construct a DFA that recognize viable prefixed. The

state of the DFA consists of a set of items

12


• Three operations for construction – Augmenting a grammar

• Add S' → S to indicate the parser when it should stop and accept

– closure operation• Suppose I is a set of items for G, then closure(I) 〓

① every item in I is added to closure(I) ② If A → α·Bβ closure(I) ∈ ＆ B → γ exists, then add B → ·γ to cloasure(I)

• e.g. – E' → E, E → E + T | T, T → T * F | F, F → (E) | id – Start with I = { E' → ·E}, then closure(I) =

{ E' → ·E, E → ·E + T, E →·T, T → ·T * F, T → ·F, F → · (E) F → ·id }

• kernel items (dots are not at the left end) vs. non-kernel items

13


• Three operations for construction – goto operation

• Suppose I be a set of items and X be a grammar symbol, then goto(I, X) = the closure of the set of all items [A → αX·β] such that A → α·Xβ I∈

• e.g. Suppose I = { E' → E·, E → E·+ T}, then goto(I, +) 〓

{ E → E + ·T, T → ·T * F, T → ·F, F → · (E), F → ·id }

14


• Draw state diagram for the following augmented grammar– e.g.

• E' → E , E → E + T | T, T → T * F | F, F → (E) | id

TT*F· TT*·FF· (E)F·id F(E) ·

E`·EE·E+T

E·TT·T*FT·F

F· (E)F·id

ET·TT·*F

EE·+TF(E·)

TF·

Fid·E`E.EE.+T

EE+·TT·T*FT·F

F· (E)F·id

EE+T·TT·*F

F(·E)E·E+T

E·TT·T*FT.F

F· (E)F·id

+

T

idid

T

F

(id

F

E

)*

F(

(

(

I10 I7I11

I8

I0

I1

I6

I9

I5

I2

I3

I4

I6

E

+

I3F

I4

* I7

15


• SLR Parsing table – ① Build a DFA from the given grammar – ② Find follow(A) nonterminal ∀– ③ determine parsing actions for each I

• a) if [A → α aβ] Ii and goto(Ii, a) = Ij ․ ∈then set action[i,a] = shift j(Sj)

• b) if [A → α·] Ii ∈then set action[i, a] = reduce A → α a in FOLLOW(A) ∀

except A = S'

• c) if [S' → S·] Ii ∈then set action[i, $] = accept

– ④ For all nonterminal A • if goto(Ii, A) = Ij

then set goto[i, A] = j

16


• SLR Parsing table – ⑤ For all other entries are made "error" – ⑥ Initial state is one containing [S' → S·]

– e.g • 1) E → E + T

2) E → T3) T → T * F, 4) T → F5) F → (E)6) F → id

• FOLLOW(E) = { +, $, )}FOLLOW(T) = {*,+,$,)}FOLLOW(F) = {*,+,$,)}

　Action Goto

id + * ( ) $ E T F

0S

5　　 S

4　　 1 2 3

1 　 S6　　　 Accep

t　　　

2 　 r2S

7　 r2 r2 　　　

3 　 r4 r4 　 r4 r4 　　　

4S

5　　 S

4　　 8 2 3

5 　 r6 r6 　 r6 r6 　　　

6S

5　　 S

4　　　 9 3

7S

5　　 S

4　　　　 10

8 　 S6　　 S1

1　　　　

9 　 r1S

7　 r1 r1 　　　

10　 r3 r3 　 r3 r3 　　　

11　 r5 r5 　 r5 r5 　　　

17


• Executing a parser with the parsing table – configuration

• (S0X0S1X1 … XmSm, aiai+1…am$) = (stack content, unexpended input)

– Resulting configuration after action[Sm, ai]

• i) = Sj (shift and goto state j)

(S0X0S1X1 … XmSmaiS, ai+1…an$)

• ii) = rp (reduce A → β)

(S0X0S1X1 … Xm-rSm-rAS, aiai+1…an$) where S = goto[Sm-r, A] and r =

• iii) accept (parsing is completed) • iv) error (error recovery is needed)

18


• Executing a parser with the parsing table

stack input action

1 0$id * id +

id$shift

2 5id0$ * id + id$ reduce F → id

3 3F0$ * id + id$ reduce T → F

4 2T0$ * id + id$ shift

5 7*2T0$ id + id$ shift

6 5id7*2T0$ + id$ reduce F → id

710F7*2T0

$+ id$

reduce T → T * F

8 2T0$ + id$ reduce E → T

9 1E0$ + id$ shift

10 6+1E0$ id$ shift

115

id6+1E0$$ reduce F → id

12 3F6+1E0$ $ reduce T → F

139T6+1E0

$$

reduce E → E + T

14 1E0$ $ accept

19


• A grammar that is not ambiguous, not SLR(1) – S → L = R , S → R , L → * R , L → id , R → L

Then, FOLLOW(R) = FLLOW(S) = FOLLOW(L) = { = }

– Action[2, =] → Shift or Reduce • Because SLR is not powerful enough to remember sufficient

left context to decide next action on "="

S`·SS·L=R

S·RL·*RL·idR·L

SL·=RRL·

SL=·RR·LL·*RL·id

I0

I2

I6

L

=

20

Constructing LR Parsing Table (1/3)

• Central idea – In SLR, reduction of A → α is determined by looking to

see if a comes after α while LR sees if βAa is allowed

• Redefinition of items to include a terminal symbol [A → α·β, a]

• The lookahead symbol a has no effect when β ≠ ε

• a FOLLOW(A) ∈

• How to find the collection of sets of valid items

21


• Closure(I) – if [A → α·Bβ, a] I, ∈

for each B → γ in G'

add [ B → ·γ, FIRST(βα)] to I

repeat until no more production is added.

• goto[I, x] – if [A → α·Xβ, a] I, create J with [A → αX·β, ∈

a], and find closure(J)

22


• Example– S' → S, S → CC, C → cC | d

Cd·, c/d CcC·, c/d

S`·S, $S·CC, $

C·cC, c/dC·d, c/d

Cc·C, c/dC·cC, c/dC·d, c/d

SC·C, $C·cC, $C·d, $

Cc·C, $C·cC, $C·d, $

SCC·, $ Cd·, $

CcC·, $

S`S, $

d C

c

CS

C d

c

C

I4 I8

I3I0

I1

I2I5

I6

I9

I7I5

c

c

<LR(1) Finite State Diagram>

State

Action Goto

c d $ S C

0 S3 S4 　 1 2

1 　　 Accept

　　

2 S6 S7 　　 53 S3 S4 　　 84 R3 R3 　　　5 　　 R1 　　6 S6 S7 　　 97 　　 R3 　　8 R2 R2 　　　9 　　 R2 　　

<LR(1) Parsing Table >

Pertemuan 8-9 Bottom-Up Parsing

Documents

Transcript of Pertemuan 8-9 Bottom-Up Parsing