constructing SLR parsing tables - The Logic Tutorial

 Constructing SLR parsing tables involves a similar process to constructing LR(0) parsing tables, but with an additional check to avoid conflicts due to the limitations of SLR parsers. Here's a breakdown of the steps:

1. Define the Augmented Grammar:

• Introduce a new start symbol (e.g., S') and add a production rule S' -> S.
• This ensures the parsing process always starts with the new start symbol and ends when it reaches the original start symbol.

2. Generate the Canonical Collection of LR(0) Items:

This step is identical to the one used for LR(0) parsing:

• Start with an item set containing [S' -> •S, $].
• Iteratively apply GOTO and SHIFT operations to generate new item sets based on the existing ones.
• Use the FOLLOW sets of non-terminals to determine lookaheads for SHIFT actions.

3. Identify SLR Conflicts (Optional):

This step distinguishes SLR parsing table construction from LR(0):

• After generating the LR(0) collection of items, check for conflicts within each state.
• A conflict occurs when an item set contains both:
  • A shift action for a terminal a and
  • A reduce action for a production with a in its FOLLOW set.
• This conflict arises because the SLR parser cannot distinguish between shifting a onto the stack and reducing the current rule based on just a single lookahead symbol.

4. Resolve SLR Conflicts:

There are two primary strategies to resolve SLR conflicts:

• Shift-Reduce (SR) Conflict:
  • If both actions are valid, favor the SHIFT action. This prioritizes consuming input symbols before attempting reductions.
• Reduce-Reduce (RR) Conflict:
  • If both are reduce actions for different productions, report an error. SLR parsers are unable to choose between these alternatives reliably.

5. Construct the Parsing Table:

• Fill the table entries based on the generated item sets and resolved conflicts:
  • SHIFT: When the state has a GOTO action for a terminal a in an item set, write "SHIFT n" (where n is the target state), indicating to shift a onto the stack and move to state n.
  • REDUCE: When the state has an item with the dot at the end of a production rule (A -> α •), and the lookahead symbol is in the FOLLOW set of A, write "REDUCE r" (where r is the production number), indicating to reduce the current rule by popping symbols from the stack and replacing them with A.
  • ACCEPT: When the state contains an item [S' -> S •, $], write "ACCEPT", indicating successful parsing when the end-of-file symbol is encountered.
  • Error: If no valid action exists, leave the entry blank or mark it as "ERROR".

6. Use the Parsing Table:

• The completed parsing table can be used to guide the SLR parser in processing an input string.
• The parser reads the current state, the next input symbol, and uses the table to determine the appropriate action (SHIFT, REDUCE, ACCEPT, or ERROR).
• This process continues until the entire input is consumed and either the ACCEPT state is reached or an error occurs.

Note:

• SLR parsing tables offer a simpler and more efficient way to handle a wider range of grammars compared to predictive parsers.
• However, SLR parsers are still limited by their inability to resolve all ambiguities.
• For highly ambiguous grammars, more powerful parsing techniques like LALR(1) might be necessary.