Syntax Analysis: Parsing, Grammars, and Abstract Syntax Trees

What is Syntax Analysis?

Syntax analysis (or parsing) is the second phase of compilation (after lexical analysis) that checks whether a program’s tokens follow the grammar rules of the language and constructs a parse tree or abstract syntax tree (AST). It ensures the program’s structure is valid before semantic analysis.

Key Definitions

• Grammar: A set of production rules defining valid sentences (programs) in a language.
• Parse Tree: A tree structure showing how tokens derive from grammar rules.
• Abstract Syntax Tree (AST): A simplified parse tree that omits non-semantic details (e.g., parentheses in arithmetic expressions).
• Ambiguity: When a grammar can generate multiple parse trees for the same input (e.g., if-else precedence).

Context-Free Grammars (CFGs)

A CFG is a 4-tuple $G=(V,\Sigma ,P,S)$, where:

• $V$: Non-terminal symbols (e.g., E, T).
• $\Sigma$: Terminal symbols (e.g., +, id, ().
• $P$: Production rules (e.g., E → E + T).
• $S$: Start symbol (e.g., Program).

Example: Arithmetic Expressions

graph TD
  E["E"] --> T["T"]
  E -->|"'+'"| E2["E"]
  E2 --> T2["T"]
  T -->|"'id'"| id1["id"]
  T2 -->|"'id'"| id2["id"]

CFG parse tree for E → T + T (left-recursive rule) Grammar Rules:

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

Input: id + id Parse Tree:

      E
     / \
    E   +
   / \   \
 id  +   T
     / \
    id  id

In the Real World

1. eSewa App (Nepal):

   • Uses CFGs internally to validate user inputs (e.g., transaction syntax like pay <amount> <phone>). The parser checks if the command follows the grammar before processing.
   • Example: The rule Transaction → "pay" Amount Phone ensures pay 500 9800000000 is valid, but payto 500 9800000000 is rejected.

2. Khalti’s API Requests:

   • Khalti’s backend parses JSON/XML requests using ASTs to extract fields like amount, merchant_id, and signature. Ambiguity in grammar could lead to incorrect transaction routing (e.g., {"amount": 100, "currency": "NPR"} vs. {"currency": 100, "amount": "NPR"}).

3. NTC’s Traffic Route Planning (Nepal):

   • Syntax analysis ensures road network grammars (e.g., Route → Start → Junction → End) are followed when parsing GPS data. A misparsed route (e.g., missing →) could send a bus to a dead end.

Parsing Techniques

Parsing converts input tokens into a parse tree using two main approaches:

1. Top-Down Parsing (LL Parsers)

• Starts with the start symbol and expands non-terminals.
• Uses recursive descent or predictive parsing.
• Requires left-recursive grammars to be eliminated (e.g., A → Aα | β → A → βA').

Example: Eliminating Left Recursion Original:

E → E + T | T

After elimination:

E → T E'
E' → + T E' | ε

Mermaid Flowchart: Top-Down Parsing for id + id

Code Example (Recursive Descent in C):

void E() {
    T();
    E_prime();
}

void E_prime() {
    if (token == '+') {
        match('+');
        T();
        E_prime();
    }
}

void T() {
    if (token == 'id') match('id');
    else if (token == '(') { match('('); E(); match(')'); }
}

Trace for id + id:

2. Bottom-Up Parsing (LR Parsers)

• Starts with the input string and reduces it using grammar rules.
• Uses shift-reduce or LR(0)/SLR/LALR/LR(1) parsers.
• Handles right-recursive grammars naturally.

Example: LR(0) Parsing for id * id Grammar:

E → E * T | T
T → id

Input: id * id $ LR(0) States:

State 0: {E → •E * T, E → •T, T → •id}
State 1: {E → E • * T, E → •T, T → •id}
State 2: {E → E * •T, T → •id}
State 3: {E → E * T •, E → •T, T → •id}
State 4: {E → T •, E → •T, T → •id}
State 5: {E → T •}

Trace:

Abstract Syntax Trees (ASTs)

An AST represents the logical structure of code, ignoring syntax noise (e.g., parentheses, semicolons). It’s used for:

• Semantic analysis (type checking).
• Code optimization.
• Code generation.

Example: AST for a = b + c * d

Conversion from Parse Tree to AST:

1. Remove redundant nodes (e.g., + in (a + b)).
2. Flatten common subtrees (e.g., * before + in a + b * c).

Handling Ambiguity

Ambiguity occurs when multiple parse trees are valid. Solutions:

1. Grammar Restrictions:
   • Prefer left-recursive or right-recursive rules.
   • Example: Use E → T E' instead of E → E + T to avoid ambiguity in a + b + c.
2. Precedence Rules:
   • * has higher precedence than +, so a + b * c parses as a + (b * c).
3. Disambiguating Symbols:
   • Use begin/end for blocks (e.g., if (cond) begin ... end).

Ambiguous Grammar Example:

E → E + E | E * E | id

Input: a + b * c Possible Parse Trees:

1. (a + b) * c
2. a + (b * c)

Solution: Add precedence rules or rewrite as:

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

Comparison: Top-Down vs. Bottom-Up Parsing

Exam Tip

1. Grammar Questions:

   • Always derive the parse tree for given inputs.
   • Show all steps of leftmost/rightmost derivations.
   • Example: For if (x > 0) y = 1;, draw the parse tree using the grammar rules.

2. Parsing Algorithms:

   • Trace stack/input for LR(0) or recursive calls for LL(1).
   • Highlight shift/reduce/accept actions in LR parsing.

3. ASTs:

   • Focus on logical structure (ignore syntax).
   • Example: Convert (a + b) * c to * with children + (children a, b) and c.

4. Ambiguity:

   • Identify ambiguous grammars and propose fixes (e.g., precedence rules).
   • Example: For a = b = c, clarify as (a = b) = c or a = (b = c).

5. Real-World Links:

   • Relate parsing to API validation (e.g., Khalti’s JSON grammar) or compiler tools (e.g., GCC’s Yacc/Bison).