Top-Down Parsing: Recursive Descent, LL(1), Predictive Parsing & Backtracking

What is Top-Down Parsing?

Top-down parsing is a syntax analysis technique where the parser starts with the start symbol of the grammar and derives sentences by expanding non-terminals into production rules. It builds the parse tree from the root down to the leaves, unlike bottom-up parsing which builds it from the leaves up.

Key Characteristics:

• Goal: Match the input string against the grammar.
• Direction: Top-down (start symbol → leaves).
• Method: Uses leftmost derivation (always expand the leftmost non-terminal).
• Tools: Recursive descent, LL(1) parsing tables, backtracking.

1. Recursive Descent Parsing

Recursive descent parsing is a direct implementation of top-down parsing using recursive functions, one for each non-terminal in the grammar.

How It Works:

1. The parser calls a function for the start symbol.
2. For each non-terminal, it matches the leftmost symbol and recursively processes the rest.
3. If a terminal is expected, it checks if it matches the current input token.
4. If no match, it backtracks (retry alternative productions).

Example Grammar:

Consider this simple grammar for arithmetic expressions:

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

This grammar is left-recursive (e.g., E → T E'), which causes infinite recursion in recursive descent. We eliminate left recursion to make it work:

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

After left-recursion elimination (replace A → Aα | β with A → β A' and A' → α A' | ε), it becomes:

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

Now, it is suitable for recursive descent.

Recursive Descent Implementation (Pseudocode):

def parse_E():
    parse_T()
    while current_token == '+':
        consume('+')
        parse_T()

def parse_T():
    parse_F()
    while current_token == '*':
        consume('*')
        parse_F()

def parse_F():
    if current_token == '(':
        consume('(')
        parse_E()
        consume(')')
    else:
        consume('id')

def consume(token):
    if current_token == token:
        current_token = next_token()
    else:
        error()

Trace of Parsing id + id * id:

2. LL(1) Parsing

LL(1) parsing is a table-driven top-down parsing method. It uses a parsing table to decide which production to apply next based on the current non-terminal and the next input token (1 lookahead).

LL(1) Grammar Requirements:

1. Leftmost derivation: Always expand the leftmost non-terminal.
2. Left-recursion free: No productions like A → Aα | β.
3. No common prefixes: No two productions of the same non-terminal can have the same prefix (e.g., A → αβ | αγ is allowed, but A → α | αβ is not).

Constructing the LL(1) Parsing Table:

1. Compute FIRST sets: For each non-terminal, find the set of terminals that can appear as the first symbol in any derivation.
2. Compute FOLLOW sets: For each non-terminal, find the set of terminals that can appear immediately after it in any derivation.
3. Fill the table: For each non-terminal A and terminal a, if A → α and a ∈ FIRST(α), add A → α to M[A, a]. If ε ∈ FIRST(α), add A → α to M[A, b] for all b ∈ FOLLOW(A).

Example: LL(1) Table for Arithmetic Expressions

Grammar (after left-recursion elimination):

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

FIRST and FOLLOW Sets:

LL(1) Parsing Table:

Parsing id + id * id Using LL(1) Table:

1. Start with E and input id + id * id $.
2. M[E, id] = E → T E' → Stack: T E', Input: + id * id $.
3. M[T, id] = T → F T' → Stack: F T' E', Input: + id * id $.
4. M[F, id] = F → id → Pop id, Input: + id * id $.
5. M[T', +] = T' → ε → Stack: E', Input: + id * id $.
6. M[E', +] = E' → + T E' → Stack: + T E', Input: id * id $.
7. Consume +, M[T, id] = T → F T' → Stack: F T' E', Input: * id $.
8. M[F, id] = F → id → Pop id, Input: * id $.
9. M[T', *] = T' → * F T' → Stack: * F T' E', Input: id $.
10. Consume *, M[F, id] = F → id → Pop id, Input: $.
11. M[T', $] = T' → ε, M[E', $] = E' → ε → Accept!

3. Backtracking in Top-Down Parsing

Backtracking is used when the parser tries one production and fails, then retries another. It is simple but inefficient for large grammars.

Example: Backtracking for Ambiguous Grammar

Grammar:

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

To parse id + id * id:

1. Try E → E + T:
   • First E derives id, then + matches, but the next T cannot derive id * id (fails).
2. Backtrack and try E → T:
   • T derives id * id (success).

Disadvantages of Backtracking:

• Inefficient: May explore many invalid paths.
• Not suitable for large grammars: Exponential time complexity in worst case.

4. Comparison: Recursive Descent vs. LL(1) Parsing

In the Real World

1. eSewa (Nepal):

   • Idea Used: Top-down parsing for validating user input in forms (e.g., checking if a submitted transaction follows the correct syntax for payment requests).
   • How: The backend compiler-like system uses parsing tables (similar to LL(1)) to ensure that API requests (e.g., pay?amount=1000&to=12345) conform to the expected grammar before processing.

2. Khalti (Nepal):

   • Idea Used: Recursive descent parsing for JSON/XML validation in API responses.
   • How: When a merchant sends a request like {"amount": 500, "to": "user123"}, Khalti’s backend uses a parser to verify the structure matches the expected schema (e.g., Order → {amount: Number, to: String}). If invalid, it rejects the request early.

3. YouTube (Global):

   • Idea Used: LL(1) parsing for query syntax validation.
   • How: When you search for "compiler design tutorials after 2020", YouTube’s backend first parses the query to ensure it follows the allowed syntax (e.g., query → term | term "after" year). This helps in generating correct search results and filtering invalid inputs.

4. Bank Loan Interest Calculators (Nepal: NMB, Global IME):

   • Idea Used: Top-down parsing for formula validation.
   • How: When you input a loan formula like interest = principal * rate * time, the calculator’s parser checks if the input follows the correct grammar (e.g., Expression → Term | Term + Term). If you enter interest = principal *, it flags the error before computation.

Visualizing Top-Down Parsing

1. Parse Tree for id + id * id

        E
       / \
      T   E'
     / \   / \
    F  T' +  T
   /    / \   / \
 id   *  F  F  T'
          / \    \
        id  T'    ε
             / \
            F   ε
           / \
         id   ε

A labelled parse tree for `id + id id` showing how top-down parsing builds the structure. (Image: AIProf, CC BY-SA 4.0, via Wikimedia Commons)

2. LL(1) Parsing Stack Trace

flowchart TD
    A["Stack: E\nInput: id + id * id $"] --> B["Action: E → T E'\nStack: T E'\nInput: id + id * id $"]
    B --> C["Action: T → F T'\nStack: F T' E'\nInput: id + id * id $"]
    C --> D["Action: F → id\nStack: T' E'\nInput: + id * id $"]
    D --> E["Action: T' → ε\nStack: E'\nInput: + id * id $"]
    E --> F["Action: E' → + T E'\nStack: + T E'\nInput: id * id $"]
    F --> G["Consume +\nStack: T E'\nInput: id * id $"]
    G --> H["Action: T → F T'\nStack: F T' E'\nInput: id * id $"]
    H --> I["Action: F → id\nStack: T' E'\nInput: * id $"]
    I --> J["Action: T' → * F T'\nStack: * F T' E'\nInput: id $"]
    J --> K["Consume *\nStack: F T' E'\nInput: id $"]
    K --> L["Action: F → id\nStack: T' E'\nInput: $"]
    L --> M["Action: T' → ε, E' → ε\nStack: ε\nInput: $"]
    M --> N["Accept!"]

3. Backtracking Example for E → E + T | T

flowchart TD
    A["Try E → E + T\nStack: E + T\nInput: id + id * id $"] --> B["First E → id\nStack: + T\nInput: + id * id $"]
    B --> C["Match +\nStack: T\nInput: id * id $"]
    C --> D["Try T → T * F\nFails: T cannot derive id * id"]
    D --> E["Backtrack to E → T\nStack: T\nInput: id + id * id $"]
    E --> F["T → id * id\nSuccess!"]

Exam Tip

1. Grammar Checks: Always verify if a grammar is LL(1) before attempting to build a parsing table. Check for:
   • Left recursion.
   • Common prefixes (e.g., A → αβ | αγ is okay, but A → α | αβ is not).
2. FIRST and FOLLOW Sets: Memorize how to compute them. For example:
   • FIRST(A) includes terminals derivable from A in one step.
   • FOLLOW(A) includes terminals that can appear after A in any derivation.
3. Parsing Table Construction: Practice filling the table for small grammars. A common mistake is forgetting to add ε productions for FOLLOW sets.
4. Recursive Descent vs. LL(1):
   • Recursive descent is easier to implement for simple grammars.
   • LL(1) is more efficient for complex grammars but requires table construction.
5. Backtracking: Only use it if the grammar is not LL(1). In exams, prefer LL(1) or recursive descent for efficiency.
6. Worked Examples: Always show stack/input traces for parsing steps. Examiners love detailed traces!
7. Real-World Links: Relate parsing to API validation (e.g., eSewa/Khalti) or query processing (e.g., YouTube search). This can earn bonus marks for application awareness.

Common Pitfalls to Avoid:

• Left Recursion: Forgetting to eliminate it can lead to infinite loops in recursive descent.
• Incomplete FIRST/FOLLOW Sets: Missing ε in FIRST sets or FOLLOW sets can cause parsing table errors.
• Ambiguous Grammars: LL(1) parsers cannot handle ambiguous grammars (e.g., E → E + E | E * E). Prefer unambiguous grammars.
• Stack Underflow: In LL(1), ensure the stack is managed correctly to avoid underflow errors.