Introduction to Compiler Construction in a Java World

Parsing 99

the item indicates that α has been parsed (and so is on the stack) but that there is

still β to parse from the input:

Stack Input

#γα va. . .

where β

∗

⇒ v, where v is a string of terminals.

• If the position marker comes at the end of the right-hand side in an item,

[Y ::= α β ·, a]

the item indicates that the parser has successfully parsed αβ in a context where Y a

would be valid, the αβ can be reduced to a Y , and so αβ is a handle. That is, the

parse is in the configuration

Stack Input

#γαβ a. . .

and the reduction of αβ would cause the parser to go into the configuration

Stack Input

#γY a. . .

A non-deterministic finite-state automaton (NFA) that ...