Kernel Items

When we have an item with the marker immediately to the left of some non-terminal, then this tells us that the next step in the parse is to recognise some sequence of symbols which correspond to this non-terminal. To do this, we have to examine the rules for that non-terminal, and proceed from there.

For instance, the item $B\, \rightarrow\, {\bf c}{}_{\triangle} C$ tells us that the next step is to recognise a $C$; we can do this by recognising one of the two r.h.s. of the production rules for $C$. This item is thus equivalent to: $C\, \rightarrow\, {}_{\triangle} B{\bf d}$ and $C\, \rightarrow\, {}_{\triangle} {\bf d}$.

An item with the `` ${}_{\triangle}$'' on the far left of the r.h.s. is called a non-kernel item. Anywhere we have the `` ${}_{\triangle}$'' to the immediate left of a non-terminal is equivalent to each of the non-kernel items for that non-terminal.