Syntax Analysis — The Parser

The parser takes the token stream from the lexer and checks that it conforms to the grammar of the language, building an Abstract Syntax Tree (AST) as output.

Parse Tree vs AST:
- Parse Tree (Concrete Syntax Tree): reflects every step of the grammar derivation, including all grammar symbols. Contains redundant nodes (parentheses, semicolons already encoded in structure).
- AST (Abstract Syntax Tree): stripped-down version — only semantically meaningful nodes. "2 + 3 * x" doesn't need parenthesis nodes if the tree structure encodes precedence.

Parsing strategies — top-down vs bottom-up:

TOP-DOWN PARSING (LL parsers):
Builds tree from root to leaves. Starts with start symbol S, predicts which production to apply based on current input token (lookahead). 

Recursive Descent Parser:
- Each grammar variable becomes a function
- Each function reads tokens and calls other variable functions
- Easiest to write by hand — what most hand-written parsers use (GCC was recursive descent)
- Requires grammar to be LL(k): no left recursion, must predict from k tokens of lookahead

Left Recursion problem: E → E + T fails in recursive descent (infinite loop). Must eliminate:
E → T E'   where E' → + T E' | ε

LL(1) parser: uses one token of lookahead. Parsing table drives decisions.
FIRST(A) = set of terminals that can begin strings derived from A
FOLLOW(A) = set of terminals that can follow A in some derivation

BOTTOM-UP PARSING (LR parsers):
Builds tree from leaves to root. Shifts tokens onto a stack, reduces when a production's RHS is on top.

Shift-Reduce parsing:
- SHIFT: push next input token onto stack
- REDUCE: pop RHS of a production, push LHS
- LR(0), SLR(1), LALR(1), LR(1): different amounts of lookahead and states

LALR(1) — most widely used (yacc, bison, most production parsers):
- More powerful than LL(1) — handles more grammars
- One token lookahead
- Compact parsing tables
- Can handle most programming language grammars

Parser generators: lex+yacc, flex+bison, ANTLR — you write the grammar, the tool generates the parser code. Python's parser is LALR(1) generated from Grammar/Grammar file.

Parsing errors: "SyntaxError: invalid syntax" — the parser found a token it didn't expect given the grammar. The parser can't continue (or tries to recover to report more errors).

1from dataclasses import dataclass
2from typing import Optional, Union
3
4# ── AST Node definitions ───────────────────────────────
5@dataclass
6class Num:
7    value: float
8    def __repr__(self): return f"Num({self.value})"
9
10@dataclass
11class Var:
12    name: str
13    def __repr__(self): return f"Var({self.name})"
14
15@dataclass
16class BinOp:
17    left:  object
18    op:    str
19    right: object
20    def __repr__(self): return f"BinOp({self.left}, {self.op}, {self.right})"
21
22@dataclass
23class UnaryOp:
24    op:    str
25    operand: object
26    def __repr__(self): return f"UnaryOp({self.op}, {self.operand})"
27
28@dataclass
29class Assign:
30    name:  str
31    value: object
32    def __repr__(self): return f"Assign({self.name}, {self.value})"
33
34@dataclass
35class If:
36    condition: object
37    then_body: list
38    else_body: list
39    def __repr__(self): return f"If({self.condition}, ...)"
40
41@dataclass
42class Return:
43    value: object
44
45# ── Recursive Descent Parser ───────────────────────────
46class Parser:
47    """
48    Grammar:
49    program  → stmt*
50    stmt     → assign ';' | return ';' | if_stmt
51    assign   → ID '=' expr
52    return   → 'return' expr
53    if_stmt  → 'if' '(' expr ')' '{' stmt* '}' ('else' '{' stmt* '}')?
54    expr     → term (('+' | '-') term)*
55    term     → factor (('*' | '/') factor)*
56    factor   → NUMBER | ID | '(' expr ')' | '-' factor
57    """
58    def __init__(self, tokens):
59        self.tokens = tokens
60        self.pos    = 0
61
62    def peek(self):
63        return self.tokens[self.pos]
64
65    def consume(self, expected_type=None):
66        tok = self.tokens[self.pos]
67        if expected_type and tok.type != expected_type:
68            raise SyntaxError(f"Expected {expected_type}, got {tok.type} ({tok.value!r}) at line {tok.line}")
69        self.pos += 1
70        return tok
71
72    def match(self, *types):
73        return self.peek().type in types
74
75    # ── Grammar rules ──────────────────────────────────
76    def parse_program(self):
77        stmts = []
78        while not self.match(TT.EOF):
79            stmts.append(self.parse_stmt())
80        return stmts
81
82    def parse_stmt(self):
83        if self.match(TT.RETURN):
84            return self.parse_return()
85        if self.match(TT.IF):
86            return self.parse_if()
87        return self.parse_assign()
88
89    def parse_return(self):
90        self.consume(TT.RETURN)
91        val = self.parse_expr()
92        self.consume(TT.SEMI)
93        return Return(val)
94
95    def parse_if(self):
96        self.consume(TT.IF)
97        self.consume(TT.LPAREN)
98        cond = self.parse_expr()
99        self.consume(TT.RPAREN)
100        self.consume(TT.LBRACE)
101        then_body = []
102        while not self.match(TT.RBRACE):
103            then_body.append(self.parse_stmt())
104        self.consume(TT.RBRACE)
105        else_body = []
106        if self.match(TT.ELSE):
107            self.consume(TT.ELSE)
108            self.consume(TT.LBRACE)
109            while not self.match(TT.RBRACE):
110                else_body.append(self.parse_stmt())
111            self.consume(TT.RBRACE)
112        return If(cond, then_body, else_body)
113
114    def parse_assign(self):
115        name = self.consume(TT.ID).value
116        self.consume(TT.ASSIGN)
117        val = self.parse_expr()
118        self.consume(TT.SEMI)
119        return Assign(name, val)
120
121    def parse_expr(self):
122        left = self.parse_term()
123        while self.match(TT.PLUS, TT.MINUS):
124            op = self.consume().value
125            left = BinOp(left, op, self.parse_term())
126        return left
127
128    def parse_term(self):
129        left = self.parse_factor()
130        while self.match(TT.STAR, TT.SLASH):
131            op = self.consume().value
132            left = BinOp(left, op, self.parse_factor())
133        return left
134
135    def parse_factor(self):
136        tok = self.peek()
137        if tok.type == TT.NUMBER:
138            return Num(self.consume().value)
139        if tok.type == TT.FLOAT:
140            return Num(self.consume().value)
141        if tok.type == TT.ID:
142            return Var(self.consume().value)
143        if tok.type == TT.LPAREN:
144            self.consume(TT.LPAREN)
145            expr = self.parse_expr()
146            self.consume(TT.RPAREN)
147            return expr
148        if tok.type == TT.MINUS:
149            self.consume(TT.MINUS)
150            return UnaryOp("-", self.parse_factor())
151        raise SyntaxError(f"Unexpected token: {tok}")
152
153# ── Test ───────────────────────────────────────────────
154source = "result = 2 + 3 * 4;
155"
156lexer  = Lexer(source)
157tokens = lexer.tokenize()
158parser = Parser(tokens)
159ast_nodes = parser.parse_program()
160print("Source:", source.strip())
161print("AST:   ", ast_nodes)
162
163source2 = "x = 10;
164if (x) {
165    y = x + 1;
166} else {
167    y = 0;
168}
169"
170lexer2  = Lexer(source2)
171tokens2 = lexer2.tokenize()
172parser2 = Parser(tokens2)
173ast2 = parser2.parse_program()
174print("
175Source:
176" + source2)
177print("AST:")
178for node in ast2:
179    print(f"  {node}")