Bottom-Up Parsing: LR, SLR, LALR, CLR Parsers & Shift-Reduce

TAKEAWAYS:

• Bottom-up parsers use shift-reduce operations to build the parse tree from the bottom up, guided by a parsing table.
• LR(0), SLR, LALR, and CLR parsers differ in how they resolve conflicts and handle lookaheads.
• Parsing tables (action and goto) are constructed using the LR(0) automaton and augmented grammar.
• Shift-reduce conflicts (shift-shift or reduce-reduce) must be resolved manually or via lookaheads.
• LALR parsers are widely used because they balance efficiency and correctness.
• Real-world applications include compilers for programming languages (e.g., GCC, Java compilers) and syntax validation in IDEs.

1. Introduction to Bottom-Up Parsing

Bottom-up parsing constructs the parse tree starting from the leaves (terminals) and builds upward toward the root (start symbol). Unlike top-down parsing (e.g., recursive descent), it does not guess and backtrack; instead, it uses a stack to keep track of partially parsed input.

Key Concepts:

• Shift: Push the next input symbol onto the stack.
• Reduce: Replace the top of the stack with the right-hand side of a production (if the top matches the left-hand side).
• Accept: If the stack contains only the start symbol after processing all input, the input is valid.
• Error: If no valid shift/reduce/accept action exists, the input is invalid.

Example Grammar (for illustration):

E → E + T | T
T → T * F | F
F → ( E ) | id

This grammar is LR(1) (no conflicts), meaning it can be parsed unambiguously by an LR parser.

2. LR(0) Parsing

LR(0) parsing is the simplest bottom-up parsing technique. It uses an LR(0) automaton (a finite-state machine) to guide parsing decisions.

How LR(0) Works:

1. Augment the grammar by adding a new start symbol $S^{\prime }\to E$ (for our example).
2. Construct the LR(0) automaton using the closure and goto operations.
3. Build the parsing table (action and goto) from the automaton.
4. Parse the input using the stack and parsing table.

LR(0) Automaton Construction:

The automaton is built using:

• Closure(I): Adds all productions that can derive the first symbol of any item in $I$.
• Goto(I, X): Moves from state $I$ on symbol $X$, adding new items to the closure.

Example: LR(0) Automaton for $E\to E+T|T$

stateDiagram-v2
    I0: [E' → •E]
    I1: [E → •E + T, E' → E•]
    I2: [E → E + •T, E' → E•]
    I3: [T → •T * F, E → E + T•]
    I4: [T → T * •F, E → E + T•]
    I5: [F → •( E ), T → T * F•]
    I6: [F → ( •E ), T → T * F•]
    I7: [F → ( E •), T → T * F•]
    I8: [E → •T, F → ( E )•]
    I9: [T → •F, F → ( E )•]
    I10: [F → •id, T → T * F•]
    I11: [T → •id, F → id•]

    I0 -->|E| I1
    I1 -->|+| I2
    I2 -->|T| I3
    I3 -->|*| I4
    I4 -->|F| I5
    I5 -->|(| I6
    I6 -->|E| I7
    I7 -->|)| I8
    I8 -->|T| I9
    I9 -->|F| I10
    I10 -->|id| I11
    I11 -->|id| I11

Parsing Table for LR(0):

Parsing Example: Input id + id * id

Final Parse Tree:

      E
    / | \
   E  +  T
  /    \   \
 id     T   F
       / \  \
      T  *  id
     / \
    id  F
        |
       id

3. Shift-Reduce Conflicts

LR(0) parsers may encounter conflicts:

1. Shift-Shift Conflict: Two states suggest shifting on the same input symbol.
2. Reduce-Reduce Conflict: Two states suggest reducing by different productions.

stateDiagram-v2
    [*] --> Shift
    Shift --> Reduce: Conflict
    Reduce --> [*]
    Shift --> Shift: Conflict
    Shift --> Accept
    note right of Shift
        Shift-Shift
        Reduce-Reduce
    end note

Example Conflict:

Consider the grammar:

S → A a | b
A → B a
B → b

• Conflict: On input b a, LR(0) may suggest:
  • Shift b (from $S\to Aa$).
  • Reduce $B\to b$ (from $A\to Ba$).

Resolving Conflicts:

• SLR(1): Use FOLLOW sets to resolve conflicts.
• LALR(1): Merge states with identical cores (more efficient than SLR).
• CLR(1): Uses look-ahead sets (most powerful but computationally expensive).

4. SLR(1) Parsing

SLR(1) resolves conflicts using FOLLOW sets. It is more powerful than LR(0) but may still have conflicts.

FOLLOW Set Construction:

For a non-terminal $A$, $\text{FOLLOW}(A)$ contains all terminals that can appear immediately after $A$ in any derivation.

Example FOLLOW Sets:

For $E\to E+T|T$:

• $\text{FOLLOW}(E)=\{\$,)\}$
• $\text{FOLLOW}(T)=\{\$,+,)\}$

SLR(1) Parsing Table:

• If a shift-shift conflict occurs, resolve by checking which shift is valid based on FOLLOW sets.
• If a reduce-reduce conflict occurs, it is unresolvable (grammar is not SLR(1)).

5. LALR(1) Parsing

LALR(1) merges LR(0) states with identical cores (sets of items without lookaheads). It is more efficient than SLR(1) and resolves more conflicts.

LALR(1) vs. SLR(1):

Example: LALR(1) State Merging

Two LR(0) states with the same core (items without lookaheads) are merged in LALR(1). This reduces table size.

6. CLR(1) Parsing

CLR(1) uses full lookahead sets (including one token of lookahead). It is the most powerful but computationally expensive.

When to Use CLR(1):

• When SLR(1) and LALR(1) fail to resolve conflicts.
• For highly ambiguous grammars.

7. Parsing Table Construction Steps

1. Augment the grammar with $S^{\prime }\to S$.
2. Compute the LR(0) automaton using closure and goto.
3. Resolve conflicts (for SLR/LALR/CLR).
4. Build the parsing table (action and goto).
5. Parse the input using the stack and table.

Example: Parsing Table for $E\to E+T|T$

8. Real-World Applications

In the Real World:

1. GCC (GNU Compiler Collection):

   • Uses LALR(1) parsers for C, C++, and other languages.
   • Efficiently handles complex grammars while minimizing conflicts.

2. Java Compiler (javac):

   • Employs LR parsing for syntax analysis.
   • Resolves ambiguities using look-ahead techniques (similar to CLR(1)).

3. SQL Parsers (e.g., MySQL, PostgreSQL):

   • Uses bottom-up parsing to validate SQL queries.
   • Example: Parsing SELECT * FROM users WHERE age > 25 involves shift-reduce operations to build the abstract syntax tree (AST).

4. eSewa (Nepalese Government Service):

   • The backend parser for API request validation (e.g., JSON/XML) uses LR techniques to ensure correct syntax before processing payments or license renewals.

5. Khalti (Digital Payment System):

   • Parses transaction requests (e.g., transfer(amount, from, to)) using LR parsers to validate input before executing payments.

9. Worked Example: Parsing id * id + id with LALR(1)

Input: id * id + id $

Grammar:

E → E + T | T
T → T * F | F
F → id

LALR(1) Parsing Steps:

Parse Tree:

      E
    / | \
   E  +  T
  /    \   \
 T      T   F
/ \     / \
T  *   T   id
/ \   / \
F  id id  F
|    |    |
id   id   id

10. Advantages and Disadvantages

11. Exam Tip

1. Understand LR(0) Automaton Construction:

   • Know how to compute closure and goto.
   • Practice building automata for given grammars.

2. Parsing Table Questions:

   • Expect questions on action/goto table construction.
   • Be able to resolve conflicts using FOLLOW/lookahead sets.

3. Shift-Reduce Conflicts:

   • Identify shift-shift and reduce-reduce conflicts.
   • Explain how SLR/LALR/CLR resolve them.

4. Worked Examples:

   • Trace parsing steps for given inputs.
   • Draw parse trees for valid inputs.

5. Real-World Links:

   • Relate LR parsers to compilers (GCC, javac) and API parsers (eSewa, Khalti).
   • Explain why LALR(1) is preferred in practice.

6. Common Pitfalls:

   • Forgetting to augment the grammar ($S^{\prime }\to S$).
   • Miscomputing FOLLOW sets or lookaheads.
   • Not handling error recovery (though not in syllabus, useful for exams).

Final Note: Bottom-up parsing is fundamental to compiler design. Mastering LR parsers will help you understand how real compilers (like those in GCC or Java) validate and process code. Practice constructing automata and parsing tables—this is where most exam marks lie!

In the real world

• GCC Compiler (GNU Compiler Collection) uses LALR(1) parsing tables to validate C/C++ syntax. When you write int x = 5 + 3 * 2;, the compiler’s parser resolves operator precedence via LALR(1) states, ensuring * is evaluated before + without conflicts.
• WhatsApp’s Message Parser employs bottom-up shift-reduce parsing (similar to LR(1)) to validate emoji sequences like 😊👍🔥. Conflicts (e.g., invalid emoji combos) trigger error messages.
• Nepali Banking Apps (e.g., NMB Bank’s mobile app) use SLR(1) parsers to validate transaction formats like account: 123456789, amount: 5000. The parser checks if the input matches the grammar Transaction → AccountNumber Amount before processing.