08-03-2012, 03:49 PM
CSE302:Compiler Design
[attachment=18124]
Top-Down Parsing
Finding a leftmost derivation for an
input string
Recursive-descent parsing
Predictive parsing for LL(1) grammars
Non-recursive version
An Example
Balanced parentheses
S → ( S ) S | ε
Input string: ( )
Parsing stack Input buffer Action
… … …
This process reflects the rightmost derivation
but in a reverse order
Right-sentential forms
Grammars are always augmented with a new
start symbol
When to shift and when to reduce depend
on the parsing states
The LR(0) Parsing Algorithm
LR(0) parsing cannot handle a
grammar that in its DFA there is a
state s
s contains a shift item A → α.Xβ and a
complete item B → δ.
s contains two complete items A → γ.
and B → δ.
Another Example
A → ( A ) | a
LR(0) items, NFA, and DFA
Schematic view for parsing ((a))
