留学生辅导 SDT 10 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
4. Bottom-Up Parsing and Syntax-Directed Translation
NYU Courant Institute
Compiler Construction (CSCI-GA.2130-001)

Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 1 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Acknowledgments
Adapted from CSCI-GA.2130-001 slides
by and : https://cs.nyu.edu/courses/spring19/CSCI-GA.2130-001/
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 2 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Translation
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 3 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Bottom-Up Basics
Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Translation
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 4 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Second compilation phase
Lexical Analysis
Syntax Analysis
Semantic Analysis
Intermediate Representation Generator Optimizer
Code Generator Machine-Dependent Code Optimizer
source program
Symbol Table
target machine code
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 5 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Definition
Bottom-up parsing: constructing a parse tree for an input string beginning at the leaves and working up towards the root.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 6 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Example parse
E→E+T|T T→T∗F|F F → ( E ) | id
id∗id GGF ∗id GGT ∗id GGT ∗ F GGT GGE id F FidT∗F T
id id F id T∗F id Fid
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 7 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Reduction and derivation
Reduction to start symbol if read left to right:
id ∗ id → F ∗ id → T ∗ id → T ∗ F → T → E
Reverse rightmost derivation if read right to left:
E⇒rm T⇒rm T∗F⇒rm T∗id⇒rm F∗id⇒rm id∗id
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 8 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Need to know:
􏰂 Reduce now or later?
􏰂 If now, by what production?
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 9 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Decision example
E→E+T|T T→T∗F|F
F → ( E ) | id
id ∗ id → F ∗ id → T ∗ id → E ∗ id
And we are stuck.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 10 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Bottom-Up Basics
Shift-Reduce Parsing
Recognizing Handles Beyond LR(0) Syntax-Directed Translation
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 11 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Handles informally
A handle is a production, reducing by which allows us to (eventually) reach the start symbol.
The “correct” production.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 12 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Using handles
id1 F id2 T∗F T
RIGHT SENTENTIAL FORM REDUCING PRODUCTION id1 ∗ id2 F→id
F∗id2 T→F T∗id2 F→id
T∗F T→T∗F T E→T
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 13 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Using handles
id1 F id2 T∗F T
RIGHT SENTENTIAL FORM REDUCING PRODUCTION id1 ∗ id2 F→id
F∗id2 T→F T∗id2 F→id
T∗F T→T∗F T E→T
id1∗id2 →F∗id2 →T∗id2 →T∗F→T→E
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 14 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Handles formally
then the production A → β (or simply β) is a handle of αβω
(in the position following α).
ω is a string of terminals. Why?
S⇒∗ αAω⇒αβω rm rm
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 15 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Handles graphically
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 16 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Using handles
S=γ0 ⇒rm γ1 ⇒rm ···⇒rm γn−1 ⇒rm γn =ω
If we knew the handles, we could:
􏰂 locate handle βn in γn,
􏰂 apply An → βn by replacing βn with An,
􏰂 the result is γn−1,
􏰂 repeat successively throughout the chain until S is reached.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 17 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Handle uniqueness
If a grammar is unambiguous, then every right-sentential form of that grammar has exactly one handle.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 18 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Shift-reduce parsing
A form of bottom-up parsing, where:
􏰂 a stack holds the grammar symbols currently being processed,
􏰂 an input buffer holds the rest of the string being parsed.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 19 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Shift-reduce actions
Shift Reduce
Accept Error
Shift the next input symbol (scanned left-to-right) onto the stack.
Replace symbols on stack with a head of some production.
Accept input once the stack has only the start symbol. Report syntax error.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 20 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Shift-reduce example
$T ∗ id2 $T ∗ F $T
INPUT ACTION id1 ∗ id2 $ shift
∗id2 $ reducebyF→id ∗id2 $ reducebyT→F ∗id2$ shift
id2$ shift
$ reducebyF→id
$ reducebyT→T∗F $ reducebyE→T
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 21 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Shift-reduce example
Handles always appear on top of stack:
$T ∗ id2 $T ∗ F $T
INPUT ACTION id1 ∗ id2 $ shift
∗id2 $ reducebyF→id ∗id2 $ reducebyT→F ∗id2$ shift
id2$ shift
$ reducebyF→id
$ reducebyT→T∗F $ reducebyE→T
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 22 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Conflicts during shift-reduce parsing
Shift-reduce parsing only works for certain context-free grammars – LR(k) grammars.
Otherwise may get:
􏰂 shift/reduce conflicts, 􏰂 reduce/reduce conflicts.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 23 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Conflicts during shift-reduce parsing
Ambiguous (and thus non-LR) grammar:
stmt → if expr then stmt
| if expr then stmt else stmt | other
STACK INPUT ACTION
$···if expr then stmt else···$ shift or reduce?
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 24 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Conflicts during shift-reduce parsing
stmt → id ( parameterlist ) (1)
stmt → expr := expr (2) parameterlist → parameterlist , parameter (3) parameterlist → parameter (4)
parameter → id (5) expr → id ( exprlist ) (6) expr → id (7)
exprlist → exprlist , expr (8) exprlist → expr (9)
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 25 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Conflicts during shift-reduce parsing
STACK INPUT ACTION
$···id ( id ,id )… reduce(5) or reduce(7)? Can get help from the lexical analyzer:
STACK INPUT ACTION
$···procid ( id ,id )… reduce(5)
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 26 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Recognizing handles
Handle prefixes form a regular language.
This enables efficient recognition with finite automata.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 28 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 29 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Using the automaton
The state stack is enough. The symbols are for our convenience.
􏰂 Start with state 0 on the stack. (Symbol $.)
􏰂 Look at the next input symbol a.
􏰂 If there is a transition from the top state on a, shift: 􏰂 Push the new state. (Add symbol a.)
􏰂 Otherwise, reduce by A → β:
􏰂 Pop the |β| top states. (Remove symbols β.)
􏰂 Transition from the new top on A.
􏰂 Push the destination state. (Add symbol A.)
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 30 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Shift-reduce with LR(0) automaton
$ T ∗ id2 $T∗F $T
id1 ∗ id2 $
id2 $ $ $ $ $
STACK ACTION
0 5 0 3 0 2 0 2 0 2 0 2 0 2 0 1
reduce byF→id reduce byT→F shift
7 shift
75 reduce byF→id
7 10 reduce byT→T∗F
reduce byE→T accept
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 31 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Building blocks
􏰂 LR(0) item: a rule with a dot at some position: A→.BCD, A→B.CD, A→BC.D, A→BCD.
􏰂 Canonical LR(0) collection: a particular collection of sets of items.
􏰂 LR(0) state: a set of “active” items from the canonical collection.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 32 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
LR(0) items
E→E+T|T T→T∗F|F
F → ( E ) | id
The dot indicates how much of a production we have seen:
E→.E+T, E→E.+T, E→E+.T, E→E+T. E→.T, E→T.
(An LR(1) item would be [X, a] for LR(0) item X and symbol a.)
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 33 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Canonical LR(0) collection
Introduce:
􏰂 Augmented grammar G′ with the new start symbol S′ → S. 􏰂 CLOSURE function to compute states.
􏰂 GOTO function to compute transitions.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 34 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Closure construction
For some set of items I, CLOSURE(I):
Add I to CLOSURE(I).
If A → α.Bβ in CLOSURE(I), and B → γ, then add B → .γ Repeat step 2 until fixed point.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 35 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Closure intuition
Assume A → α.Bβ in CLOSURE(I). During parsing:
􏰂 might see a substring derivable from Bβ as input, 􏰂 substring will have a prefix derivable from B (γ), 􏰂 therefore, need to add all B → .γ
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 36 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Closure example
Augment grammar:
Compute closure:
I = {[E′ → .E]} I0 = CLOSURE(I)
={[E′ →.E],
[E → .E + T], [E → .T], [T → .T ∗ F], [T → .F], [F → .(E)], [F → .id]}
2 3 4 5 6 7
E′ → E E→E+T E → T T→T∗F T→F
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 37 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Kernel items
Kernel items: initial S′ → .S, and all items whose dots are not at the left end.
Nonkernel items: all items with dot at the left end, except for initial S′ → .S.
Nonkernel items can be regenerated by closure process rather than stored.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 38 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Goto construction
For a set of items I and a grammar symbol X (terminal or nonterminal):
GOTO(I,X) is the closure of {[A → αX.β] | [A → α.Xβ] ∈ I}. Intuition: transition from state I on input X.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 39 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Goto example
GOTO(I, X) = CLOSURE({[A → αX.β] | [A → α.Xβ] ∈ I})
I0 ={[E′ →.E],[E→.E+T],[E→.T],[T→.T∗F],[T→.F],
[F → .(E)], [F → .id]}
I1 =GOTO(I0,E)={[E′ →E.],[E′ →E.+T]} I2 =GOTO(I0,T)={[E→T.],[T→T.∗F]}
I3 = GOTO(I0, F) = {[T → F.]}
I4 =GOTO(I0,()={[F→(.E)],[E→.E+T],[E→.T],
[T → .T ∗ F], [T → .F], [F → .(E)], [F → .id]}
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 40 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
LR(0) automaton structure
􏰂 States are described by CLOSURE sets,
􏰂 Transitions are described by GOTO functions, 􏰂 Nonkernel items are shaded.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 41 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 42 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
k in LR(k)
􏰂 LR(k) grammar: can recognize right side of a production in a right-sentential form with k symbols of lookahead.
􏰂 LR(k) parser: can determine when and how to reduce based on its current state and k symbols of lookahead.
􏰂 LR(0): No lookahead. No state can have a shift/reduce or reduce/reduce conflict.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 43 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
􏰂 Builds on LR(0).
􏰂 Solves conflicts by using lookahead and FOLLOW sets: reduce to S only if the lookahead is in FOLLOW(S).
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 45 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Canonical LR
􏰂 Upgrades LR(0) items to LR(1) items by including the lookahead.
􏰂 More expressive that SLR: reduce to S only on specific lookaheads, a subset of FOLLOW(S).
􏰂 Many more states than SLR.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 46 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
Lookahead LR
􏰂 Builds on LR(1) and merges similar states.
􏰂 Or builds on LR(0) and computes lookaheads.
􏰂 Same number of states as SLR.
􏰂 Between SLR and LR(1) in expressiveness: specific lookaheads but not on all productions.
Compiler Construction (CSCI-GA.2130-001) 4. Bottom-Up Parsing and SDT 47 / 72

Bottom-Up Basics Shift-Reduce Parsing Recognizing Handles Beyond LR(0) Syntax-Directed Tra
LR grammars
From least to most expressive:
􏰂 LR(0): no lookahead.
􏰂 SLR(1): overestimated lookahead.
􏰂 LALR(1): precise but part

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts