Building and Using SLR(1) Parsing Tables

The Bottom-Up Approach: Shift and Reduce

Imagine building a structure. The LL(1) top-down approach is like having a blueprint and starting from the roof, trying to build down to the foundation. The bottom-up approach is the more conventional method: you start with the foundation and individual bricks, and build upwards until you have the complete structure.

In parsing, the "bricks" are the terminals of our input string, and the "structure" is the start symbol of the grammar. A bottom-up parser scans the input and "shifts" tokens onto a stack. When the top of the stack matches the right-hand side (RHS) of a grammar rule—a pattern known as a handle—the parser "reduces" it by replacing the handle with the non-terminal from the left-hand side (LHS) of that rule. This process continues until the entire string is reduced to the start symbol.

The two fundamental actions are:

• Shift: Move the next input token onto the top of the stack.
• Reduce: Replace a sequence of symbols $\alpha$ on top of the stack with a non-terminal $A$, where $A\to \alpha$ is a production.

The core challenge for a bottom-up parser is to know exactly when to shift and when to reduce. This decision-making logic is encoded in an LR parsing table.

Building the Parser's "States": Canonical Collection of LR(0) Items

Before we can build the table, we need to define the "states" of our parser. Each state represents a set of possibilities for what we have seen so far and what we might see next. These possibilities are captured by LR(0) items.

An LR(0) item is simply a production from the grammar with a dot . placed somewhere on the right-hand side. For example, for the production A → (A), the LR(0) items are:

• A → . (A) (We expect to see ( next)
• A → ( . A ) (We have just seen ( and now expect A)
• A → ( A . ) (We have seen (A and now expect ))
• A → ( A ) . (We have seen the entire RHS; a reduction is possible)

To build the full set of states, we start with an augmented grammar (adding a new start production like S' → S) and apply two operations: closure() and goto(). These operations systematically generate all possible sets of LR(0) items, which form the states of our parser's control automaton.

The process of creating this collection of states is the foundation for all LR parsers.

The resulting diagram of states (I0, I1, I2, etc.) and transitions is called the Canonical Collection of LR(0) items. This is our map for building the parsing table.

Constructing the SLR(1) Parsing Table

The SLR(1) parsing table dictates the parser's actions. It has rows corresponding to the states (I0, I1, ...) and two main sections of columns:

1. ACTION: For all terminal symbols in the grammar. This part tells the parser whether to shift, reduce, or accept.
2. GOTO: For all non-terminal symbols. This part tells the parser which state to transition to after a reduction.

The crucial difference between an LR(0) parser and an SLR(1) parser lies in how reduce actions are placed in the table. LR(0) is naive: if a state contains a final item A → α ., it places a reduce action in the entire row for that state. This often leads to conflicts.

SLR(1) is smarter. It uses the FOLLOW set of the non-terminal on the LHS of the production to decide where to place reduce actions. This is the "1" in SLR(1)—it uses one lookahead symbol to make a more informed decision.

With this principle in mind, the table construction algorithm is as follows:
Let the set of LR(0) item states be $\{I_0,I_1,...,I_n\}$.

1. Shift Action: If state $I_i$ contains an item [A → α . a β] (where a is a terminal) and goto(I_i, a) = I_j, then set ACTION[i, a] = Shift j (or Sj).
2. Reduce Action: If state $I_i$ contains a final item [A → α .] (where A is not the augmented start symbol), then for every terminal t in FOLLOW(A), set ACTION[i, t] = Reduce by A → α (or Rk, where k is the production number).
3. Accept Action: If state $I_i$ contains the item [S' → S .], then set ACTION[i, $] = Accept.
4. GOTO Entry: If goto(I_i, A) = I_j (where A is a non-terminal), then set GOTO[i, A] = j.
5. All other entries are errors.

Let's see this algorithm applied to the states we generated earlier.

Parsing an Input String with the SLR(1) Table

With the table constructed, we can now parse an input string. The process uses a stack (which holds states and grammar symbols), the input string (terminated by $), and the parsing table.

The algorithm is simple:
At each step, let the state on top of the stack be s and the current input symbol be a.

1. Look up ACTION[s, a] in the table.
2. If it's Shift j: Push the input symbol a and then the state j onto the stack. Advance the input pointer.
3. If it's Reduce by A → α: Pop 2 * |α| symbols from the stack (each symbol and its corresponding state). Let the state now exposed at the top of the stack be s'. Push the non-terminal A onto the stack. Then push the state GOTO[s', A] onto the stack. Do not advance the input pointer.
4. If it's Accept: Parsing is successful.
5. If it's Error: The string is not in the language.

Let's watch this process in action.

To reinforce this, let's watch another detailed parsing example from Prof. Ravindrababu Ravula, which gives a very clear blow-by-blow account of the stack operations.

Conflicts: When a Grammar is Not SLR(1)

The power of SLR(1) is limited. Sometimes, the table construction algorithm results in a cell with more than one entry. This is a conflict, and it means the grammar is not SLR(1). There are two types of conflicts:

1. Shift-Reduce (S/R) Conflict: The parser doesn't know whether to shift the current token or reduce a handle on the stack. This occurs in a state I_i if it contains:

   • An item like [A → α . a β] (suggesting a shift on a).
   • And a final item [B → γ .] where a is in FOLLOW(B) (suggesting a reduce on a).

2. Reduce-Reduce (R/R) Conflict: The parser doesn't know which of two possible reductions to perform. This occurs in a state I_i if it contains:

   • A final item [A → α .].
   • And another final item [B → β .], where FOLLOW(A) ∩ FOLLOW(B) is not empty (i.e., they share a common lookahead symbol).

Understanding how these conflicts arise is key to diagnosing why a grammar fails to be SLR(1).

Conclusion

In this lesson, we made the significant leap from top-down to bottom-up parsing. We focused on the SLR(1) technique, which represents a sweet spot between simplicity and power.

Your key takeaways are:

• Bottom-up parsing works by shifting input symbols onto a stack and reducing handles (RHS of productions) to their corresponding non-terminals.
• The process starts by building the canonical collection of LR(0) items, which serve as the states of the parser.
• The SLR(1) parsing table is constructed using these states. Shift actions are determined by goto transitions on terminals, while Reduce actions are placed in the columns corresponding to the FOLLOW set of the production's LHS non-terminal.
• Conflicts (Shift-Reduce or Reduce-Reduce) arise when a state and a lookahead symbol lead to more than one possible action. A grammar with such conflicts is not SLR(1).

You are now equipped to construct an SLR(1) parser from scratch and use it to validate a string, a fundamental skill in compiler theory and a frequent topic in GATE.

In our next lesson, we will continue our exploration of bottom-up parsing by examining more powerful techniques: CLR(1) and LALR(1). These methods refine the concept of lookahead to handle a broader class of grammars, including many that are not SLR(1).