SLR table generation

The example provided on the page on LR parsing illustrates that, even for simple grammars, the parse table is not intuitive. There are several techniques for generating the parse table from a grammar table. SLR is one of the simpler methods. Not all LR grammars produce a table using the SLR algorithm - those that do are known as SLR grammars.

Concepts

An LR(0) item of a grammar G is a production of G with a marker (here represented using a ·) at a point in the right hand side. An item for a production Y -> '(' Y ')' might be Y -> '(' · Y ')' or Y -> '(' Y ')' ·. The marker indicates how much of a production we have seen at a given point in the input. That is, for my first example above, we have seen the first '(' and are looking for the remainder of the production.

The LR(0) closure of a set of LR(0) items is formed by taking each of the items in the set and for a rule X -> a · B c, and production B -> d, adding the item B -> · d. This is process is repeated until no new productions can be added.

goto(I, X), where I is a set of items, and X is a grammar symbol. This operation is performed by, for each of the productions A -> a · X b in I, putting the production A -> a X · b in a new set of items J. The result of the operation is the closure of J.

An augmented grammar - for a grammar G with start symbol S, G' (the augmented grammar) is the grammar G with production S' -> S added, where S' is a new symbol.

The canonical collection of sets of LR(0) items (C) for an augmented grammar G' is formed by first taking the closure of the set of items {[ S' -> S ]}, and adding it as the first set in C (referred to as I₀). C is completed by repeatedly adding goto(I,X) to C (as I_n), where I is a set of items within C, X is a grammar symbol and goto(I,X) is not empty or already in C.

Under construction