Contents

• SLR Parsing
• Parse Tables
• Conflicts

SLR Parsing

SLR means simple LR; it is the weakest member of the LR family (i.e., every SLR grammar is also LALR and LR, but not vice versa). To understand SLR parsing we'll use a new example grammar (a very simple grammar for parameter lists):

PList	$\longrightarrow$	( IDList )
IDList	$\longrightarrow$	id
	|	IDList id

Building the Action and Goto Tables for an SLR Parser

Definition of an SLR item:

An item (for a given grammar) is a production with a dot somewhere on the right-hand side.

The item "PList $\longrightarrow$ . lparens IDList rparens" can be thought of as meaning "we may be parsing a PList, but so far we haven't seen anything".

The item "PList $\longrightarrow$ lparens . IDList rparens" means "we may be parsing a PList, and so far we've seen a lparens".

The item "PList $\longrightarrow$ lparens IDList . rparens" means "we may be parsing a PList, and so far we've seen a lparens and parsed an IDList.

We need 2 operations on sets of items: Closure and Goto

To compute Closure($I$), where $I$ is a set of items:

1. put $I$ itself into Closure($I$)

2. while
   	there exists an item in Closure(I of the form X $\longrightarrow$ $\alpha$ . B $\beta$ such that there is a production B $\longrightarrow$ $\gamma$, and B $\longrightarrow$ . $\gamma$ is not in Closure(I)
   do
   	add B $\longrightarrow$ . $\gamma$ to Closure($I$)

The idea is that the item "X $\longrightarrow$ $\alpha$ . B $\beta$" means "we may be trying to parse an X, and so far we've parsed all of $\alpha$, so the next thing we'll parse may be a B". And the item "B $\longrightarrow$ . $\gamma$" also means that the next thing we'll parse may be a B (in particular, a B that derives $\gamma$), but we haven't seen any part of it yet.

Example 1: Closure({ PList $\longrightarrow$ . lparens IDList rparens })

We'll begin by putting the initial item into the Closure (Step 1 above). So far, our set is: { PList $\longrightarrow$ . lparens IDList rparens}

Now, we will do step 2, checking the set we build for productions of the form B $\longrightarrow$ $\gamma$, where the item B $\longrightarrow$ . $\gamma$ is not in the set. There's only one item that we can check, and the symbol to the immediate right of the dot is lparens which is a terminal symbol. Obviously, there are no productions of the form B $\longrightarrow$ $\gamma$ with a terminal symbol on the left-hand side, so there's nothing else to check.

With Step 2 exhausted, we can return the set we've built up: Closure({ PList $\longrightarrow$ . lparens IDList rparens }) = { PList $\longrightarrow$ . lparens IDList rparens }

As with the previous example, we put the initial item into the Closure. So far, our set is { PList $\longrightarrow$ lparens . IDList rparens }

For step 2, we begin by selecting the only item in our working set, PList $\longrightarrow$ lparens . IDList rparens. We now look for productions with a left-hand side of IDList, since that's the symbol to the immediate right of the dot. One production of this form is "IDList $\longrightarrow$