Parsing - Introduction to Compiler Construction in a Java World - page 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

#

v a :::

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 conguration

Stack Input

# Y a :::

A non-deterministic finite-state automaton (NFA) that recognizes viable prefixes and
handles can be constructed from items like that in (3.32). The items record the progress in
parsing various language fragments. We also know that, given this NFA, we can construct
an equivalent DFA using the powerset construction that we saw in Section 2.7. The states
of the DFA for recognizing viable prefixes are derived from sets of these items, which record
the current state of an LR(1) parser. Here, we shall construct these sets, and so construct
the DFA, directly (instead of first constructing a NFA).
So, the states in our DFA will be constructed from sets of items like that in (3.32). We
call the set of states the canonical collection.
To construct the canonical collection of states, we first must augment our grammar G
with an additional start symbol S 0 and an additional rule,

S 0 ::= S

so as to yield a grammar G 0 , which describes the same language as does G, but which does
not have its start symbol on the right-hand side of any rule. For example, augmenting our
grammar (3.31) for simple expressions gives us the augmented grammar in (3.33).

(3.33)