Editing LR parser (section)

== Constructing LR(0) parsing tables ==
=== Items ===
<!-- This section is linked from [[LALR parser]] -->

The construction of these parsing tables is based on the notion of ''LR(0) items'' (simply called ''items'' here) which are grammar rules with a special dot added somewhere in the right-hand side. For example, the rule E → E + B has the following four corresponding items:
: E → <big>{{color|#f7f|•}}</big> E + B
: E → E <big>{{color|#f7f|•}}</big> + B
: E → E + <big>{{color|#f7f|•}}</big> B
: E → E + B <big>{{color|#f7f|•}}</big>
Rules of the form ''A'' → ε have only a single item ''A'' → <big>{{color|#f7f|•}}</big>. The item E → E <big>{{color|#f7f|•}}</big> + B, for example, indicates that the parser has recognized a string corresponding with E on the input stream and now expects to read a '+' followed by another string corresponding with B.

=== Item sets ===

It is usually not possible to characterize the state of the parser with a single item because it may not know in advance which rule it is going to use for reduction. For example, if there is also a rule E → E * B then the items E → E <big>{{color|#f7f|•}}</big> + B and E → E <big>{{color|#f7f|•}}</big> * B will both apply after a string corresponding with E has been read. Therefore, it is convenient to characterize the state of the parser by a set of items, in this case the set { E → E <big>{{color|#f7f|•}}</big> + B, E → E <big>{{color|#f7f|•}}</big> * B }.

=== Extension of Item Set by expansion of non-terminals ===

An item with a dot before a nonterminal, such as E → E + <big>{{color|#f7f|•}}</big> B, indicates that the parser expects to parse the nonterminal B next.  To ensure the item set contains all possible rules the parser may be in the midst of parsing, it must include all items describing how B itself will be parsed.  This means that if there are rules such as B → 1 and B → 0 then the item set must also include the items B → <big>{{color|#f7f|•}}</big> 1 and B → <big>{{color|#f7f|•}}</big> 0. In general this can be formulated as follows:

: If there is an item of the form ''A'' → ''v'' <big>{{color|#f7f|•}}</big> ''Bw'' in an item set and in the grammar there is a rule of the form ''B'' → ''w' '' then the item ''B'' → <big>{{color|#f7f|•}}</big> ''w' '' should also be in the item set.

=== Closure of item sets ===

Thus, any set of items can be extended by recursively adding all the appropriate items until all nonterminals preceded by dots are accounted for. The minimal extension is called the ''closure'' of an item set and written as '''clos'''(''I'') where ''I'' is an item set. It is these closed item sets that are taken as the states of the parser, although only the ones that are actually reachable from the begin state will be included in the tables.

=== Augmented grammar ===

Before the transitions between the different states are determined, the grammar is augmented with an extra rule
: (0) S → E eof

where S is a new start symbol and E the old start symbol. The parser will use this rule for reduction exactly when it has accepted the whole input string.

For this example, the same grammar as above is augmented thus:
: (0) S → E eof
: (1) E → E * B
: (2) E → E + B
: (3) E → B
: (4) B → 0
: (5) B → 1

It is for this augmented grammar that the item sets and the transitions between them will be determined.