Java Reference
In-Depth Information
The LR(1) Parsing Algorithm
Before showing how the tables are constructed, let us see how they are used to parse a
sentence. The LR(1) parser algorithm is common to all LR(1) grammars and is driven by
two tables, constructed for particular grammars: an Action table and a Goto table.
The algorithm is a state machine with a pushdown stack, driven by two tables: Action
and Goto. A configuration of the parser is a pair, consisting of the state of the stack and
the state of the input:
Stack
Input
s
0
X
1
s
1
X
2
s
2
:::X
m
s
m
a
k
a
k+1
:::a
n
where the s
i
are states, the X
i
are (terminal or non-terminal) symbols, and a
k
a
k+1
:::a
n
are the unscanned input symbols. This configuration represents a right sentential form in a
right-most derivation of the input sentence,
X
1
X
2
:::X
m
a
k
a
k+1
:::a
n
Search WWH ::
Custom Search