Post on 03-Jan-2016
description
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
Constructing SLR (Simple LR) parser (2/9)
• 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
Constructing SLR (Simple LR) parser (3/9)
• 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
Constructing SLR (Simple LR) parser (4/9)
• 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
Constructing SLR (Simple LR) parser (5/9)
• 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
Constructing SLR (Simple LR) parser (6/9)
• 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
Constructing SLR (Simple LR) parser (7/9)
• 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
Constructing SLR (Simple LR) parser (8/9)
• 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
Constructing SLR (Simple LR) parser (9/9)
• 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
Constructing LR Parsing Table (2/3)
• 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
Constructing LR Parsing Table (3/3)
• 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 >