CLR Parsing

The canonical set of items is a parsing technique in which a look-ahead symbol is generated for constructing a set of items.  Hence, the collection of sets of items is one look ahead symbol in a set of items.

The following steps in CLR parsing technique are:

1. Construction of a canonical set of items along with a look-ahead symbol.
2. Building canonical LR parsing table.
3. Parsing the I/P string using a canonical LR parsing table.

Construction of a canonical set of items along with a look-ahead symbol.

1. For grammar ‘G’ initially add S’→ S in the set of items ‘C’.
2. For each set of item C and each grammar symbol ‘x’ (may be terminal (or) non-terminal) add closure (Ij,x).  This process should be repeated by applying goto (Ij,x) is not empty and not in ‘C’.
3. The closure function can be compiled as follows:

For each item A → α x βa and the role of X → r and β is not in I, then add X → r.

Similarly, the goto function can be computed as for each item [A→ α x β, a] is in I.

The rule [A→ α x β, a] is not in goto item then add [A→ α x β, a] to goto items.  This process is repeated until no more set of items can be added to the collection ‘C’.

Reference Link

CLR Parsing