语法与语义

语法定义合法的程序，语义定义程序的含义。本章讲上下文无关文法与 BNF、抽象语法树、操作语义与指称语义的直觉，并用一个小表达式语言展示从文法到解释器的完整过程。

语法：上下文无关文法

语法的标准形式是上下文无关文法（CFG）（严格讨论见上下文无关文法与下推自动机）。工程写法是 BNF：

\begin{aligned} \text{expr} &\to \text{expr} + \text{term} \mid \text{expr} - \text{term} \mid \text{term} \\ \text{term} &\to \text{term} * \text{factor} \mid \text{factor} \\ \text{factor} &\to (\text{expr}) \mid \text{number} \end{aligned}

两个经典问题：

歧义文法：同一串有两个解析树。代表是悬空 else（if a then if b then x else y 中 else 归属哪个 if）。多数语言的规定是"else 归最近的 if"——用文法或语义消歧。
左递归：expr -> expr + term 会让递归下降解析器死循环，工程上要改写（提取左因子、改右递归）。

运算符优先级与结合性就是文法的层次：优先级高的离原子更近，左结合用左递归形式表达。

解析树与抽象语法树

**解析树（parse tree）**保留文法的全部结构（包括括号与中间节点）；**抽象语法树（AST）**只保留语义相关的部分——AST 是编译器所有阶段的中间表示，词法、语法、语义分析、优化、代码生成都围绕它。

# 小表达式语言的 AST 与求值器
from dataclasses import dataclass

@dataclass
class Num:
    value: float

@dataclass
class BinOp:
    op: str
    left: "Expr"
    right: "Expr"

Expr = Num | BinOp

def evaluate(e: Expr, env: dict) -> float:
    match e:
        case Num(value=v):
            return v
        case BinOp(op="+", left=l, right=r):
            return evaluate(l, env) + evaluate(r, env)
        case BinOp(op="*", left=l, right=r):
            return evaluate(l, env) * evaluate(r, env)

递归下降解析器与这个求值器几乎同构——文法 → 解析器 → AST → 解释器是一条流水线，也是多数"迷你语言"（配置、模板、DSL）的完整实现路径。

语义：程序的含义

语法只说"这串是合法程序"，语义回答"它做什么"。两大形式化路径：

操作语义（operational）：定义"执行一步"的规则（小步）或"整个程序求值到值"（大步）——解释器的形式化，直觉上是"抽象机器"。上面 evaluate 就是一个大步操作语义。
指称语义（denotational）：每个程序片段映射到一个数学对象（函数）——"程序就是函数"的观点，适合证明与推导。

工程上的对应：解释器是操作语义的实现，优化器的正确性论证常用指称式的推理（"这个变换保持程序的指称"——见编译器优化）。

语法糖与核心语言

大多数语言特性都能脱糖为少数核心构造：

for 循环 → while + 赋值；
类与方法 → 记录 + 函数指针（虚表）；
async/await → 状态机 + 回调；
推导式 → 匿名函数 + 高阶函数。

语法糖不是贬义：它改变的是表达力的人体工学，而非可计算性。语言设计的问题不是"能不能实现"，而是"脱糖后还剩下什么、成本在哪里"——async/await 脱糖成状态机，成本是每个 await 点的状态保存（→ I/O 模型与事件驱动）。

本章要点

语法定义合法的程序，语义定义程序的含义；两者是不同的问题
CFG + BNF 描述语法；歧义文法（悬空 else）与左递归是两个经典坑
AST 是编译器所有阶段的中间表示；递归下降解析器与求值器同构
操作语义 = 抽象机器（解释器），指称语义 = 程序即函数（证明）
大多数语言特性都能脱糖为少数核心构造；糖的成本在脱糖之后