**This post is still somewhat incomplete.**

LR(0) and SLR(1) grammars produce identical *non-deterministic finite automata* (NFA), and consequently, the same *deterministic finite automata* (DFA). However, they don’t produce the same tables.

Here’s how to build them.

# How to construct the NFA for LR(0) and SLR(1) parser grammars

## Augment the Grammar

**Note**: If the grammar’s leading non-terminal has only one production rule, skip this step.

Create a new production rule: Goal → YourOldStartingNonTerminal. E.g., convert *A → ( A ) | a* into:

- A’ → A # This new production provides an unambiguous goal state.
- A → ( A ) | a

## Create the item list.

First, rewrite the grammar as having one production rule per line. Using the above grammar, we get:

- A’ → A # rule 1
- A → ( A ) # rule 2
- A → a # rule 3

Next, “walk the dot.” For each production rule, transcribe it:

- with a dot before the first symbol
- with a dot before the second symbol
- …
- with a dot before the last symbol
- with a dot after the last symbol

The resulting item list grows rapidly. Using our example from above, we get the following:

- A’ → • A # from rule 1
- A’ → A • # from rule 1
- A → • ( A ) # from rule 2
- A → ( • A ) # from rule 2
- A → ( A • ) # from rule 2
- A → ( A ) • # from rule 2
- A → • a # from rule 3
- A → a • # from rule 3

## Build the NFA Using the Item List

Quick definition: the *current symbol* is the symbol following the • marker.

- Draw a state containing the initial (goal) item.
Draw a transition from State 0 on

*current symbol*to State 1. (In our example, this means drawing an edge, labeled A, from the 1st item to the 2nd. It would look something like this:For each remaining item:

**IF**the current symbol is non-terminal, draw ε-edges to the initial states for that symbol.- Transition on the current symbol from the current state to the item in which the • marker has advanced past that symbol.

## Next Time, Gadget! Next Time!

Next planned post on this subject: NFA to Table for LR(0) and SLR(1) Grammars

## Glossary

**Initial states**for a non-terminal symbol P are states containing items such that:- P is the left-hand-side of the production rule
- The • marker is left of all symbols in the production rule.

For example: the initial states for A in the above grammar are:

- A → • ( A )
- A → • a

**ε-edges**are transitions that may occur without having to read any additional characters. See: NFA with ε-moves (Wikipedia) for more details.