An Example of LR Parser Construction

The LR(1) machine discussed last time is what is constructed when an LR(1) grammar is processed to prepare for parsing. However, the LR(1) machine is not actually used in the form it is presented for parsing. Instead, two tables, an Action Table and a GOTO table, are constructed from the LR(1) machine. These two tables drive an LR(1) parse.

Here is the example grammar again that we used last time.

The Example Grammar

S → E $
E → E + T
E → T
T → T * P
T → P
P → id
P → ( E )

The LR(1) machine constructed from this grammar is given below.

The LR(1) Machine

The Action Table for the LR(1) Machine Example

From this LR(1) machine we can construct the action table. It is easy to do. Put all of the tokens of the grammar as column labels in this table (these correspond to the lookaheads). Place all state numbers of the LR(1) machine as the row labels. Then fill in the rows as follows.

For each state i,

if there is a dot in front of a token in some rule in state i, place an S (SHIFT) in the corresponding entry in row i and the column labeled by that token
if there is a dot at the end of a rule place an Rj (REDUCE by rule j, where j is the number of the rule we are looking at) in each column of row i that represents one of the tokens in the lookahead set at the end of the rule in question

This is called the Action Table, because it tells us at each step whether to SHIFT or REDUCE based on the current lookahead token.

NOTE: If, after correctly filling this table in from the LR(1) machine, there are any entries in the table that have more than one reduce action or some combination of reduce and shift actions, the table has either REDUCE-REDUCE conflicts and/or SHIFT/REDUCE conflicts. In this case the original grammar is not LR(1).

(Note: The A in row 1, column $ means that the input string should be accepted (i.e., it has parsed properly) if this situation is ever achieved.

The GOTO Table

The GOTO table is equaly easy to construct. The column headings are all nonterminals and terminals in the grammar. The row labels are all states. Use the LR(1) machine to fill out the entries in this table by way of the transitions. That is, if state i has a transition labeled with symbol a leading to state j, place a j in the entry that has row label i and column label a. That is, this table just indicates the next states of the LR(1) machine give the current state and the current top of stack symbol.

Action and GOTO Tables Together

Using the Action and GOTO tables we did a parse without referring to the LR(1) machine. Refer to your notes to refresh your memory.

Constructing the LR(1) machine.

The key to constructing an LR(1) parser is the construction of the LR(1) machine. We discuseed how this is done.

If you need a refresher on the entire process, check on Wikipedia, for example

http://en.wikipedia.org/wiki/LR_parser