Next: About this document ...
Up: Parsing (II)
Previous: Bottomup parsing
KEY IDEAS.
 The LR parsing method is the most general nonbacktrackingshiftreduce parsing method known.
 LR parsers can parse a strictly larger class of grammars than (topdown) predictive parsers.
 LR parsers can usually recognize all programming language construct that can be specified by contextfree grammars.
 LR parsers detect errors fast.
 Drawback: it is too much work to construct an LR parser by hand.
 Fortunately, we can use an LR parser generator such as YACC.
THE LR PARSING PRINCIPLE
Figure 9:
Model of an LR parser.

An LRParser uses
 states to memorize information during the parsing process,
 an action table to make decision (such as shift or reduce)
and to compute states
 a goto table to compute states
These states are embedded with grammar symbols in a stack.
More, precisely, after eahc iteration, the stack stores a word
of the form
s_{0}X_{1}s_{1}X_{2}^{ ... }s_{m1}X_{m}s_{m} where
s_{0} is the endofstack symbol and s_{m} is the state on top of the stack.
For a state s and a terminal a, the entry
action[s, a] has one of
the four following forms

shift s' where s' is a state,

reduce A ,

accept,

error.
Algorithm 10
Next: About this document ...
Up: Parsing (II)
Previous: Bottomup parsing
Marc Moreno Maza
20041202