Syntax Analysis (Parsing): Grammars, Parsing Tables, and Translation

Core Concepts: Grammars and Parsing

1. Grammars and Language Classification

A grammar $G=(V,\Sigma ,P,S)$ defines a formal language:

• $V$: Non-terminals (e.g., S, E, T).
• $\Sigma$: Terminals (e.g., +, *, id).
• $P$: Production rules (e.g., E → E + T | T).
• $S$: Start symbol.

Grammars are classified by Chomsky hierarchy:

• Type 0: Unrestricted (Turing-complete).
• Type 1: Context-sensitive (e.g., S → aSb | ε).
• Type 2: Context-free (used in compilers, e.g., E → E + T | T).
• Type 3: Regular (used in lexical analysis).

Classification of formal grammars (Image: TinyTedDanson, CC BY-SA 4.0, via Wikimedia Commons)

2. Parsing Methods: LL vs. LR

Parsing converts input strings into parse trees using grammars. Two dominant approaches:

Key Idea:

• LL(1): Leftmost derivation, left-to-right, leftmost expansion. Example: S → aSb | ε → aab (leftmost S expanded first).
• LR(1): Rightmost derivation, right-to-left, rightmost expansion. Example: S → aSb | ε → aab (rightmost S expanded first).

3. FIRST and FOLLOW Sets

Used to construct LL(1) parsing tables.

FIRST(X)

Set of terminals that can appear as the first symbol in any string derived from $X$. Rules:

1. If $X\to ϵ$, add $ϵ$ to FIRST(X).
2. If $X\to Y_1{Y}_2\dots Y_n$, add FIRST(Y₁) to FIRST(X).
   • If FIRST(Y₁) contains $ϵ$, add FIRST(Y₂) (and so on).
3. If no terminal can derive $X$, FIRST(X) = {$ϵ$}.

FOLLOW(X)

Set of terminals that can appear immediately after $X$ in any sentential form. Rules:

1. If $S$ is the start symbol, add $ (end-of-input) to FOLLOW(S).
2. If $A\to \alpha B\beta$, add FIRST(β) to FOLLOW(B).
   • If FIRST(β) contains $ϵ$, add FOLLOW(A) to FOLLOW(B).

Worked Example: FIRST and FOLLOW

Grammar:

S → ACB | CbB | Ba
A → da | BC
B → g | ε
C → h | ε

Compute FIRST and FOLLOW:

Step 1: FIRST Sets

Trace:

• FIRST(S) = FIRST(A) ∪ FIRST(C) = {d, B, h}.
• FIRST(A) = {d} ∪ FIRST(B) = {d, g, ε}.
• FIRST(B) = {g, ε} (given).
• FIRST(C) = {h, ε} (given).

Step 2: FOLLOW Sets

Trace:

• FOLLOW(S) = {$} (start symbol).
• For S → ACB:
  • FOLLOW(A) = FIRST(CB) = {h, g, ε} → {h, g, B, b, $}.
  • FOLLOW(C) = FIRST(B) = {g, ε} → {g, B, b, $}.
  • FOLLOW(B) = {$} (end of production).

4. LL(1) Parsing Table Construction

Algorithm:

1. For each production $A\to \alpha$:
   • For each terminal $a\in \text{FIRST}(\alpha )$, add $A\to \alpha$ to M[A, a].
   • If $ϵ\in \text{FIRST}(\alpha )$, add $A\to \alpha$ to M[A, b] for all $b\in \text{FOLLOW}(A)$.

Example Table for Above Grammar:

Check for LL(1) Conflict:

• No two entries in the same cell → LL(1).

5. LR Parsing: SLR(1) and LR(1)

SLR(1) Parsing Table

Uses FOLLOW sets to resolve shifts/reduces. Steps:

1. Build LR(0) items (augmented grammar + dot positions).
2. Construct LR(0) automaton (states = sets of items).
3. Add FOLLOW lookahead to resolve conflicts.

LR(1) Parsing Table

Extends LR(0) with look-ahead symbols in items. Item Format: [A → α • β, a] (where a is lookahead).

Worked Example: SLR(1) Table

Grammar:

S → aAa | bAb | ba

LR(0) Items:

1. [S' → •S, $]
2. [S → •aAa, $]
3. [S → a•Aa, $]
4. [S → aA•a, $]
5. [S → •bAb, $]
6. [S → b•Ab, $]
7. [S → bA•b, $]
8. [A → •a, $]
9. [A → a•, $]

SLR(1) Table:

Trace for Input aab:

1. Start in state 0, read a → shift to state 2.
2. Read a → shift to state 8.
3. Read b → reduce A → a (state 8 → state 7).
4. Read $ → reduce S → aAa → accept.

6. Syntax-Directed Translation

Definition: Attach semantic actions (e.g., code generation) to grammar productions. Example: Evaluate arithmetic expressions.

Grammar:

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

Annotated Parse Tree for (5*3+2)*5:

graph TD
    A["*"] --> B[(5*3+2)]
    A --> C["5"]
    B --> D["+"]
    D --> E[(5*3)]
    D --> F["2"]
    E --> G["*"]
    G --> H["5"]
    G --> I["3"]

Semantic Actions:

def E(node):
    if node.left and node.right:  # E + T
        return E(node.left) + T(node.right)
    else:                         # T
        return T(node)

def T(node):
    if node.left and node.right:  # T * F
        return T(node.left) * F(node.right)
    else:                         # F
        return F(node)

Trace for (5*3+2)*5:

1. Parse (5*3+2) → 5*3+2 = 15+2 = 17.
2. Multiply by 5 → 17*5 = 85.

In the Real World

1. eSewa (Nepal):

   • Uses LR parsing to validate user inputs (e.g., payment = amount + tax).
   • Grammar ensures correct syntax for transaction rules.

2. Khalti API (Nepal):

   • LL(1) parsers validate JSON requests (e.g., {"amount": 1000, "currency": "NPR"}).
   • Rejects malformed queries early (e.g., missing currency).

3. YouTube’s Algorithm (Global):

   • Syntax-directed translation ranks videos by parsing user watch history as a grammar:

     WatchHistory → Video+
     Video → (Category | Tags)+
     

   • Generates recommendations via semantic actions (e.g., if Category(X) matches then suggest Y).

4. Ncell Billing System:

   • LR(1) parsers process calls in the format:

     Call → Duration Unit
     Unit → "min" | "sec"
     

   • Computes charges as cost = Duration * Rate(Unit).

Exam Tip

1. Grammar Classification:

   • Always check if a grammar is LL(1) or LR(1) before building tables.
   • LL(1) Conflict: Two productions for the same non-terminal and lookahead.
   • LR Conflict: Shift-reduce or reduce-reduce in the same state.

2. Parsing Tables:

   • LL(1): Use FIRST/FOLLOW to fill the table.
   • LR(1): Draw the automaton and resolve conflicts with lookahead.
   • Common Mistake: Forgetting to add $ to FOLLOW(S).

3. Syntax-Directed Translation:

   • Annotate parse trees with semantic rules (e.g., E → E + T { = $1 + $3 }).
   • Exam Trick: For expressions like (5*3+2)*5, show both the parse tree and the evaluation steps.

4. Real-World Tie-Ins:

   • Relate grammars to APIs (Khalti), billing (Ncell), or validation (eSewa).
   • Example: "How would you parse a Daraz order confirmation email?" → Use LR(1) for structured data.

Comparison Table: LL vs. LR Parsing

Mermaid: LR(0) Automaton Construction

flowchart TD
    A["Start: [S'→•S, ]"] --> B["State 0"]
    B --> C["Action: shift S → [S→•aAa, ]"]
    C --> D["State 1: [S→a•Aa, ]"]
    D --> E["Action: shift A → [A→•a, ]"]
    E --> F["State 2: [A→a•, ], [S→aA•a, ]"]
    F --> G["Action: reduce A→a"]
    G --> H["State 3: [S→aAa•, ]"]
    H --> I["Action: accept"]

Code Example: Recursive Descent Parser (LL(1))

def parse_E():
    parse_T()
    while lookahead == '+':
        match('+')
        parse_T()

def parse_T():
    parse_F()
    while lookahead == '*':
        match('*')
        parse_F()

def parse_F():
    if lookahead == '(':
        match('(')
        parse_E()
        match(')')
    else:
        match('id')

Trace for Input 5*3+2:

Key Takeaways

• Grammars define the syntax; parsers validate and translate them.
• LL(1) is simpler but restrictive; LR(1) handles more grammars.
• FIRST/FOLLOW are critical for LL(1) tables; LR(0) automata for LR(1).
• Syntax-directed translation attaches meaning to parse trees (e.g., code generation).
• Real-world: APIs, billing systems, and validation tools rely on parsing techniques.