假设你是一位餐厅大厨，客人递来一张手写菜单：“宫保鸡丁、西湖醋鱼、米饭”。你不会抓起食材就下锅——你得先看懂菜单，在脑子里画出一张“上菜逻辑图”：哪两道菜能并行做、哪道菜要等前一口锅空出来、汤为什么必须最后上。这张图，就是编译器世界里的抽象语法树（AST）。源代码就是那张手写菜单，一行行字符像连绵的墨迹；编译器前端把字符流按语法规则梳理成一张有层次的树：根节点是“整桌菜”，往下是“每道菜”“每个动作”“每种食材”。有了这棵树，后端才知道先做什么、后做什么，代码优化、类型检查、机器码生成全都有了依据。本文用“年夜饭中央厨房”做主线，讲清楚 AST 从哪来、节点怎么设计、属性怎么在树里上下流动、又怎么被遍历使用，最后带你亲手用 Python 搭一个迷你 AST 构建器。

岗位关联

掌握 AST 构建原理，是读懂编译器前端乃至 ESLint、Prettier、Semgrep 等一切代码分析工具的钥匙。对 AI 从业者而言，这是通往代码智能、静态分析与工具链开发的核心加分项。

目录
  1. 可视化演示
  2. 认识AST
  3. 节点类型设计
  4. 语法导向翻译
  5. 综合属性
  6. 继承属性
  7. 遍历与访问者模式
  8. Yacc与Bison实战
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

抽象语法树是源代码结构的树形表示，是编译器前后端的关键桥梁。本文详解AST节点类型设计、语法导向翻译方案、综合... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

AST节点类：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

认识AST

年夜饭开席前，大厨从不直接照着菜单往锅里倒菜。他会把菜单读一遍，在脑海中生成一张“上菜逻辑图”：米饭和热菜可以并行，糖醋鱼要等炸锅空闲，汤必须最后上以保持温度。这张图不是菜单本身，而是菜单背后的“结构”——它决定了整晚的操作次序。

编译器遇到源代码时，面对的是同样的难题：源代码本质上是一串字符，计算机要理解的却是“这段程序的骨架是什么”。抽象语法树（AST）就是编译器把字符流“翻译”出来的那张结构图。它以树的形式表达程序：根节点表示整个程序，内部节点表示语法构造（比如加法、循环），叶子节点表示变量名、数字这些最基本的记号。

形式上，AST 是一棵有序树，节点集合记录每个语法构造，边集合表示“包含/从属”关系。它与语法分析树（parse tree，也叫具体语法树）有本质区别：语法分析树忠实记录每一次产生式展开，连括号、分号这类辅助记号也要占据一席；AST 则是一次“去糖”——删掉对后续阶段没用的骨架噪音，只保留语义要点。AST 面向后端消费者设计：类型检查、代码生成都只需要语义骨架。

上菜顺序图一旦画好，后面的备菜、烹饪、传菜全都有章可循。AST 也一样：它是编译过程从“读”转向“想”的分水岭，前端后续的语义分析、中间代码生成都在这棵树上做文章。这张图，就是中央厨房里最值钱的那张纸。

G=(N,E)\displaystyle G = (N, E)
一棵树由“节点集合 N”和“边集合 E”构成，AST 也不例外：N 是程序中的语法构造，E 是构造之间的从属关系。
  1. 节点集合 N树中全部结点的集合。每个结点对应源代码里的一个语法构造，比如加法节点、函数节点、数字节点，是 AST 的基本组成单元。
    N={n1,n2,…,nk}N = \{ n_1, n_2, \dots, n_k \}
  2. 边集合 E结点间的父子连线。边 $(n_p, n_c)$ 表示 $n_c$ 是 $n_p$ 的子结点，体现了“谁包含谁”的从属关系。
    E={(np,nc)∣np 是 nc 的父结点}E = \{ (n_p, n_c) \mid n_p \text{ 是 } n_c \text{ 的父结点} \}

节点类型设计

大厨画上菜顺序图时，会用不同颜色的便签区分信息：红色代表“急火快炒”的动作，蓝色代表“食材”，绿色代表“装盘要求”。便签分得越清楚，后厨看到图就越不会慌张。AST 也有自己的“便签体系”——节点类型。

设计 AST 的第一步，是决定节点类型怎么分类。业界约定俗成的三大类是 Expr（表达式）、Stmt（语句）和 Decl（声明）。表达式描述“怎么算”，语句描述“做什么”，声明描述“名字和类型绑定”。三者各司其职，覆盖了绝大多数语言的语法空间。

表达式节点包括二元运算（Add、Sub）、乘除法（Mul、Div）、字面量（Num）、变量引用（Var）；语句节点包括 If、While、Assign、Return；声明节点包括 VarDecl、FuncDecl、ClassDecl。每个节点还要携带源码位置（行号、列号），编译报错、调试映射都靠它。节点通过 children 指针互连成树，根节点通常是“程序”或“模块”。文法上，表达式的最简骨架可以写成：

便签分类让后厨协作高效，节点分类让编译后端“按类处理”：遍历时见到 Stmt 就走控制流逻辑，见到 Expr 就算值，见到 Decl 就登记符号表。分类的合理程度，直接决定后续语义分析代码好不好写。

E⟶E+T∣T\displaystyle E \longrightarrow E + T \mid T
一条产生式定义了“表达式可以长什么样”：它可以是“一个表达式加一个 T”，也可以直接是一个 T。这就是递归定义表达式的经典写法。
  1. 非终结符 E文法里代表“一个表达式”的抽象符号，在 AST 中对应 Expr 类节点，是设计节点类型时的顶层抽象。
    E⇒Expr 节点E \Rightarrow \text{Expr 节点}
  2. 产生式结构$E \rightarrow E + T$ 表示“表达式可以是一个表达式加一个 T”，这是左递归写法，用来表达任意长度的加法链；竖线 $\mid$ 表示“或者”，$E \rightarrow T$ 则提供递归出口。
    E+T(左递归, 支持加法连写)E + T \quad \text{(左递归, 支持加法连写)}

语法导向翻译

高档餐厅的菜谱不单纯列食材，每一行旁都附有“动作批注”：“鸡胸肉切 1 厘米丁”“花生米低温油炸 3 分钟”。大厨执行到哪一步，就照批注做哪一步。把“动作”直接贴在“规则”上，这个朴素思想在编译原理里叫语法导向翻译（Syntax-Directed Translation）。

语法制导翻译的核心做法：把语义动作附加在文法的每一条产生式上。解析器运行到某条产生式被归约的时刻，就顺带执行它附带的动作。这些动作的副产物，正是我们要构建的 AST 节点。于是“语法规则”和“翻译逻辑”合体，边解析边建树，无需额外专门构造结构。

技术术语上，这叫语法导向定义（SDD，Syntax-Directed Definition）：文法产生式 + 语义规则。动作可以写在产生式末尾，也可以嵌在右部符号之间。以加法为例，产生式末尾的动作是 makeNode(ADD, E1.node, T.node)，把两个子树的根拼成新的加法节点：

菜谱与批注合体，厨房效率倍增；产生式与动作合体，编译器前端就能“一步到位”产出 AST。这正是语法制导翻译成为编译器教科书经典方案的原因——文法描述与构建逻辑不再分家。

E→E1+T{E.node=makeNode(ADD,E1.node,T.node)}\displaystyle E \rightarrow E_1 + T \qquad \{ E.\textit{node} = \mathrm{makeNode}(\text{ADD}, E_1.\textit{node}, T.\textit{node}) \}
大括号里就是“动作批注”：归约到这条产生式时，把左右两个子表达式的节点拼成一个新的加法节点。
  1. E.node文法符号 E 携带的属性，表示“这个表达式对应的 AST 子树根节点”，是后续拼装的关键。
    E.node=新节点E.\textit{node} = \text{新节点}
  2. makeNode 工厂节点工厂函数，三个参数分别是“节点类型、左子树根、右子树根”，返回新创建的节点。
    makeNode(kind,left,right)→Node\mathrm{makeNode}(\text{kind}, \text{left}, \text{right}) \to \text{Node}
  3. 动作执行时机大括号里的动作为在解析器“归约”该产生式时执行——此时 E1 和 T 的子树都已建好，可以安全地取根节点。
    reduce(E→E1+T)⇒执行动作\mathrm{reduce}(E \to E_1 + T) \Rightarrow \text{执行动作}

综合属性

一道红烧肉的味道从哪来？答案藏在每一块食材和每一步火候里，直到装盘你尝一口才能说清。这种“过程跑完才涌现”的性质，对应 AST 属性体系里的综合属性（synthesized attribute）。

综合属性的定义：只依赖于节点自身子节点属性的属性。它在归约时沿着语法分析树自底向上计算——子节点先算完，父节点再汇总。现实中的典型例子就是表达式的数值：叶子节点的 val 来自词法值，内部节点的 val 由孩子 val 运算而来。前面讲的 E.node 其实也是一种综合属性：AST 子树正是在归约过程中“从叶子向上生长”的。

在 SDD 写法里，产生式左部符号的综合属性定义在右部符号的属性上。表达式求值最经典的规则：

味道逐层汇聚，综合属性把叶片上的细节汇总成整棵树的结论。好消息是：只要 AST 建立时用的是自底向上的归约，这类属性不增加额外遍历成本，一遍就能全部算完。

E.val=E1.val+T.val\displaystyle E.\textit{val} = E_1.\textit{val} + T.\textit{val}
整条规则读作：“整个表达式的值，等于左边子表达式的值加右边项的值”。值从叶子一路传上来，这就是综合属性的自底向上。
  1. E.val归约后表达式节点的综合值。它写在等号左边，由右边两个孩子的值相加获得，代表“本层汇合的结论”。
    E.val=…E.\textit{val} = \dots
  2. E1.val / T.val两个子表达式的综合值。归约顺序保证它们已经算完，体现了“先孩子、后父亲”的依赖顺序。
    E1.val,  T.val 已求得E_1.\textit{val},\; T.\textit{val}\ \text{已求得}
  3. 整体方向值从叶子一路向上汇聚到根——这与自底向上语法分析的归约顺序完全吻合，不需要额外遍历。
    叶子→内部→根\text{叶子} \to \text{内部} \to \text{根}

继承属性

有些信息不是菜本身的味道，而是“环境”给的。比如今晚定了川菜宴席，那么每一道菜都默认要够辣——这个“辣度标准”由宴席主题自上而下传达到每道菜。这种从上下文注入的属性，叫继承属性（inherited attribute）。

继承属性的定义：由父节点或兄弟节点的属性计算而来，沿树自顶向下传递。它回答的问题是“我现在处在什么环境里”：这个变量是整型还是字符串、这个 break 跳转的是哪个循环、这个函数在哪个作用域里。环境信息必须在看到子树之前就已知，所以方向必然是向下的。

最经典的例子是声明语句 decl → type id：变量的类型来自声明的类型。写成属性规则：

宴席主题定调，每道菜都带着主题气质；继承属性让“环境”一路下传，AST 节点一出生就知道自己身在何方。综合属性与继承属性这对“上下行”组合，构成了属性文法的完整画像。

id.type=decl.type\displaystyle \mathrm{id}.\textit{type} = \mathrm{decl}.\textit{type}
标识符自己没有类型，它的类型是“从父声明那里领来的”。这就是继承属性：信息从环境自上而下注入。
  1. decl.type声明节点的类型属性，是“环境信息”的源头，比如 int、float，由声明语句的类型部分决定。
    decl.type=int\mathrm{decl}.\textit{type} = \mathrm{int}
  2. id.type标识符节点继承到的类型。它没有自己的类型信息，必须从父声明那里“领取”，随声明绑定。
    id.type←decl.type\mathrm{id}.\textit{type} \leftarrow \mathrm{decl}.\textit{type}
  3. 传递方向与综合属性相反，继承属性由父到子，常用于需要“上下文”的场合，如作用域和类型环境。
    父→子\text{父} \to \text{子}

遍历与访问者模式

上菜顺序图挂出来后，不同角色都要“看图办事”：营养师算总热量，传菜员排上菜次序，采购员核食材数量。如果每个人都把“自己的查看逻辑”写进图纸里，这张图迟早被涂得没法看。访问者模式（visitor pattern）的思路是：图纸保持干净，每个角色自带一套“看图规则”，轮流进场。

对 AST 而言，“看图”就是遍历（traversal）。常见的遍历顺序有前序、中序、后序：表达式求值需要后序（先孩子后父亲），打印程序结构常用前序。遍历本身只是“移动方式”，真正有价值的是每到一处节点执行的操作——这些操作千差万别：类型检查、符号登记、中间代码生成。

访问者模式把“节点结构”与“节点操作”分离：操作封装进独立的 visitor 对象，每个节点提供一个 accept(visitor) 回调，把自身分发给 visitor 的 visit 方法。visit 按节点类型分派到不同处理逻辑。用递归定义刻画：

营养师进场看完，传菜员再进场，谁也不改图纸。新增一种操作只需新增一个访问者——ESLint、Prettier 正是靠这种模式，在共享的 AST 上叠加几百种规则。

visit⁡(n)={f(n)n 是叶子g(n,⨁c∈children⁡(n)visit⁡(c))否则\displaystyle \operatorname{visit}(n) = \begin{cases} f(n) & n \text{ 是叶子} \\ g\left(n, \bigoplus_{c \in \operatorname{children}(n)} \operatorname{visit}(c)\right) & \text{否则} \end{cases}
访问一棵树 = 把每个节点的子结果汇聚起来，再和当前节点信息合并。具体“怎么合并”，由访问者的操作决定。
  1. visit(c) 递归先对每个子节点递归调用访问函数，得到子结果；$\bigoplus$ 表示把所有子结果按某种方式汇聚（求和、拼接、取最大等）。
    ⨁c∈children(n)visit⁡(c)\bigoplus_{c \in \mathrm{children}(n)} \operatorname{visit}(c)
  2. g(n, 子结果)把当前节点信息和子结果合并，产出本层结果；叶子则直接应用 f，没有子节点可递归。
    g(n,子结果)→本节点结果g(n, \text{子结果}) \to \text{本节点结果}

Yacc与Bison实战

手写几百条菜谱的处理逻辑太累，中央厨房购入一台“菜谱编译器”：你把菜谱规则输进去，它自动生成一位执行标准流程的厨师长。对编译器开发者来说，这台机器叫 Yacc（GNU 版本叫 Bison），输入的是文法，输出的是解析器。

Bison 的输入是 .y 文件，分三段：声明段（%token 定义记号）、文法规则段（每条产生式附语义动作）、用户代码段（辅助函数）。Bison 根据这套文法生成 C 语言的 yyparse() 函数，它自动完成 LALR(1) 的移进-归约分析；与词法分析器（如 Flex 的 yylex()）配合，每次拿一个 token，归约时执行动作。

文法规则段的写法是每条产生式后跟动作块，核心约定：$$ 表示产生式左部的语义值，$1、$2、$3 表示右部第 1、2、3 个符号的语义值。一个经典片段： 自动生成的解析器把 token 流轰隆隆归约成 AST，编译器前端这扇门就此打通。AST 再交给语义分析器、中间代码生成器，一路走到后端——它正是编译器前后端之间那条最关键的传送带。

expr→expr + term{$$=makeNode(ADD,$1,$3);}\displaystyle \mathrm{expr} \to \mathrm{expr} \ \mathrm{+}\ \mathrm{term} \qquad \{ \$\$ = \mathrm{makeNode}(\text{ADD}, \$1, \$3); \}
这条规则说：“当解析器把 expr + term 归约成一个 expr 时，把左操作数（$1）和右操作数（$3）拼成 ADD 节点，作为归约结果（$$）。”句句都是建树动作。
  1. 左部语义值$$ 表示产生式左部的语义值，即归约后新建的 AST 节点，相当于动作函数的“返回值”。
    $$=归约结果节点\$\$ = \text{归约结果节点}
  2. 右部语义值$1 和 $3 表示右部第 1、3 个符号的语义值，分别是左操作数和右操作数的子树。
    $1=左子树,$3=右子树\$1 = \text{左子树}, \quad \$3 = \text{右子树}
  3. 动作块执行花括号内的 C 代码在归约发生时执行，完成 makeNode 调用，把两棵子树焊成一棵新树。
    {C 代码, 归约时执行}\{ \text{C 代码, 归约时执行} \}

AI 应用场景

IDE 智能补全与实时语法提示

阶段：语法分析（前端解析）

解决的问题：传统编译器是“写完再编译”的批处理，写错一个括号要等编译报错才知道；IDE 需要“边敲边懂”。解析器把当前文件持续解析成 AST，编辑器在光标节点上做上下文查询，就能实时给出补全与报错。就像大厨一边备菜一边照上菜图核对，发现漏了食材立刻补上。

具体案例：VS Code 打开大型 TypeScript 项目，输入 obj. 的瞬间弹出成员列表，背后就是语言服务器对 obj 对应 AST 节点做成员查找；红色波浪线则是语法错误在 AST 位置上的精准标注。

代码格式化与自动修复

阶段：代码转换（AST 重写与再生成）

解决的问题：手工整理缩进、批量修改运算符，费时且容易手滑改坏逻辑。工具先把源码解析成 AST，以树为操作对象做结构化修改，再打印回文本——因为操作在语义骨架上进行，不会打破语法结构。就像在结构图上改一道菜的摆盘，而不是在成品菜盘里用筷子翻找。

具体案例：Prettier 的格式化流程是“解析 → 按统一风格重排 AST → 打印”；ESLint 的 --fix 自动修复把 == 换成 ===，本质是定位 BinaryExpression 节点并替换运算符字段。

静态漏洞扫描

阶段：语义分析（AST 遍历与模式匹配）

解决的问题：人工审计代码量大、漏检率高；扫描器用访问者遍历 AST，在特定节点类型处做模式匹配，把“危险调用”精确到行列报出来。就像卫生检查员拿着固定清单，逐间厨房核对。

具体案例：Semgrep 的规则引擎先把你写的模式编译成小 AST，再在目标代码的 AST 上做子树匹配，能查出 SQL 拼接、危险 eval 调用等；GitHub 的 CodeQL 也把代码建模成可查询的数据库。

Python 演示

python118 行
import re # 简单的词法分析器: 把源码切成 token 流def tokenize(code):    pattern = re.compile(r'\s*(?:(\d+)|(\+)|(\*)|(\()|(\)))')    tokens = []    pos = 0    while pos < len(code):        m = pattern.match(code, pos)        if not m:            raise ValueError('无法识别的字符: ' + code[pos])        if m.group(1):            tokens.append(('num', int(m.group(1))))        elif m.group(2):            tokens.append(('+', '+'))        elif m.group(3):            tokens.append(('*', '*'))        elif m.group(4):            tokens.append(('(', '('))        elif m.group(5):            tokens.append((')', ')'))        pos = m.end()    tokens.append(('EOF', None))    return tokens # AST 节点类: kind 表示类型, value 存字面值, children 连子树class Node:    def __init__(self, kind, value=None):        self.kind = kind        self.value = value        self.children = [] def printable(node, depth=0):    print('  ' * depth + node.kind + (' ' + str(node.value) if node.value is not None else ''))    for c in node.children:        printable(c, depth + 1) # 语法导向的递归下降解析器: 解析的同时构建 ASTclass Parser:    def __init__(self, tokens):        self.tokens = tokens        self.pos = 0     def peek(self):        return self.tokens[self.pos]     def advance(self):        self.pos += 1     def parse(self):        ast = self.expr()        if self.peek()[0] != 'EOF':            raise ValueError('语法错误')        return ast     def expr(self):        node = self.term()        while self.peek()[0] == '+':            self.advance()            right = self.term()            new = Node('Add')            new.children = [node, right]            node = new        return node     def term(self):        node = self.factor()        while self.peek()[0] == '*':            self.advance()            right = self.factor()            new = Node('Mul')            new.children = [node, right]            node = new        return node     def factor(self):        t = self.peek()        if t[0] == 'num':            self.advance()            return Node('Num', t[1])        if t[0] == '(':            self.advance()            node = self.expr()            if self.peek()[0] != ')':                raise ValueError('缺少右括号')            self.advance()            return node        raise ValueError('语法错误') # 访问者 1: 后序遍历求值class Evaluator:    def visit(self, node):        if node.kind == 'Num':            return node.value        if node.kind == 'Add':            return self.visit(node.children[0]) + self.visit(node.children[1])        if node.kind == 'Mul':            return self.visit(node.children[0]) * self.visit(node.children[1]) # 访问者 2: 输出后缀表达式class Printer:    def visit(self, node):        if node.kind == 'Num':            return str(node.value)        if node.kind == 'Add':            return self.visit(node.children[0]) + ' ' + self.visit(node.children[1]) + ' +'        if node.kind == 'Mul':            return self.visit(node.children[0]) + ' ' + self.visit(node.children[1]) + ' *' if __name__ == '__main__':    tokens = tokenize('2 + 3 * 4')    ast = Parser(tokens).parse()    print('===== AST =====')    printable(ast)    print('===== 求值 =====')    print(Evaluator().visit(ast))    print('===== 后缀 =====')    print(Printer().visit(ast))
目的：用 200 行不到的 Python，完整演示“词法切分 → 语法导向建树 → 访问者遍历”的 AST 构建链路。
  1. pattern = re.compile(r'\s*(?:(\d+)|(\+)|(\*)|(\()|(\)))')用正则一次性定义 token 的“长相”，数字、加号、乘号、括号各自进一个捕获组
  2. tokens.append(('num', int(m.group(1))))数字字符串转成整数，保留“类型+值”的 token 对
  3. new.children = [node, right]把两棵子树挂到新建节点上，这正是语法导向翻译里“边归约边建树”的核心动作
  4. while self.peek()[0] == '+':用循环处理连续加法，天然实现左结合
  5. return Node('Num', t[1])数字 token 直接变成叶子节点，整棵树的“食材”就此落地
  6. self.visit(node.children[0]) + self.visit(node.children[1])后序遍历：先算子树再合并，对应综合属性的自底向上
  7. ast = Parser(tokens).parse()解析器入口，返回完整的 AST 根节点
  8. print(Evaluator().visit(ast))一个访问者算值，一个访问者打印后缀式，同一棵树叠加两种操作

常见误区

误区我听说编译器解析完代码会生成一棵树，那语法分析树和 AST 应该是一个东西吧？考试的时候混着写也没关系。

正解两者的层级完全不同。语法分析树（具体语法树）忠实记录每个产生式的展开过程，连括号、分号都要占节点；AST 在此基础上“去糖”，只保留语义骨架。好比备菜流程记录了“切丁、焯水、下锅”每一步，而上菜结构图只关心“鸡肉配花生，一起装盘”。后端只需要语义骨架，所以 AST 更精简、更稳定，删掉一个多余括号根本不影响 AST。

为何常见：教材常常先把语法分析树画满一页，学习者先入为主，以为“树越完整越好”，不知道 AST 是面向后续阶段的“定制视图”。

误区我看到所有表达式树都是两个孩子的二叉结构，那 AST 一定也是二叉树吧？设计时照着二叉来准没错。

正解AST 的度由语言构造的语义决定，不是铁定的二叉。a+b+c 可以画成左结合链，也可以合并成一个带三个孩子的 Add 节点；If 语句节点甚至可能有 condition、then、else 三个分支。硬套二叉会让节点种类爆炸，反而破坏 AST 的简洁性。

为何常见：入门教材几乎都用二元运算做求值讲解，二叉图画得太多，形成了“表达式树 = 二叉树”的思维惯性。

误区既然综合属性是自底向上、继承属性是自顶向下，那肯定要先自底向上算完综合属性，再自顶向下跑一遍算继承属性，所以至少两遍。

正解遍数由属性依赖图决定，不是由属性的“种类”决定。日常常见的 L 属性文法里，两类属性可以在同一次分析过程中穿插计算：归约时既读上下文（继承）又汇总孩子值（综合）。例如声明语句中，类型先下传（id.type = decl.type），随后表达式的值照常上汇，两者在同一条归约链上顺序完成，根本不需要两次完整遍历。

为何常见：教材为了讲清楚概念，把两类属性分节独立介绍，读者把“分开讲”误解成了“分开算”。

误区教材上的访问者模式示例都是 accept/visit 双分派，那我写 AST 工具时不写 accept 就不算用访问者模式。

正解accept/visit 只是双分派的一种实现方式。在 Python、JavaScript 这类动态语言中，一个按 node.kind 分发的 visit(node) 函数就能实现同样的解耦——新增操作 = 新增一个分发函数，节点类完全不用动。访问者模式的本质是“结构遍历与节点操作的解耦”，accept 是手段而不是定义。

为何常见：设计模式教材以 C++/Java 的双分派示范居多，读者容易把特定实现当成模式本身。

面试题

Q1. 关于抽象语法树（AST）最准确的说法是？

单选题 · easy

  • A.存储源码字符颜色的数据结构
  • B.源代码结构的树形抽象表示← 正确答案
  • C.只包含叶子节点的线性列表
  • D.专用于数据库查询的索引树

答案：B。AST 是编译器前端把字符流解析后得到的树形结构，保留语法骨架与语义要点。它必然分层，不是线性列表，也与颜色、数据库索引无关。好比菜单变成上菜结构图，关键在“结构”与“骨架”。

Q2. 与语法分析树相比，AST 的典型特征是？

单选题 · easy

  • A.完整记录每个归约过程细节
  • B.必须包含括号和分号节点
  • C.删除辅助记号，更加精简← 正确答案
  • D.只有根节点没有叶子节点

答案：C。语法分析树忠于产生式展开，括号、分号也要占位；AST 去糖后只留语义骨架，更精简且对源码表面改动不敏感。备菜记录 vs 上菜图，后者只需要结构，C 正确。

Q3. 综合属性（synthesized attribute）的计算方向是？

单选题 · mid

  • A.从父节点到子节点
  • B.从子节点到父节点← 正确答案
  • C.同层兄弟节点之间传递
  • D.与树结构完全无关

答案：B。综合属性在归约时由子节点值计算父节点属性，自底向上。“味道从食材逐层汇成整道菜”就是这个方向。A 描述的是继承属性，C、D 不符合属性文法的定义。

Q4. 下列哪种场景更依赖继承属性？

单选题 · mid

  • A.表达式求值，叶子数字向上汇合
  • B.从一个变量先算出的值影响另一个变量
  • C.标识符类型来自所在声明← 正确答案
  • D.统计树的节点总数

答案：C。继承属性传递“上下文环境”，标识符类型由声明决定，属于自上而下的环境注入。A、D 是综合属性的典型，B 描述的并不是属性文法机制。

Q5. 访问者模式（visitor pattern）的核心价值是？

单选题 · mid

  • A.让遍历速度更快
  • B.将节点结构与节点操作解耦← 正确答案
  • C.替代词法分析
  • D.把树改造成链表

答案：B。访问者把“遍历结构”与“对节点的操作”分离，新增操作等于新增访问者，节点类不需要改动。好比不同专家各自带规则看图，图纸本身保持干净。B 准确描述了这一价值。

Q6. 在 Yacc/Bison 文法动作中，$$ 表示什么？

单选题 · hard

  • A.右部最后一个符号的语义值
  • B.产生式左部符号的语义值← 正确答案
  • C.词法分析器的输入流
  • D.当前 token 的类型

答案：B。$$ 指归约后左部非终结符的语义值，即新建的 AST 节点；$1、$3 才指右部符号的语义值。它像动作函数的“返回值”，把子节点拼成新节点后向上传递。A、C、D 都不符合 Yacc 约定。

Q7. 语法导向翻译（语法制导翻译）中，语义动作放在哪里？

单选题 · easy

  • A.产生式右部的合适位置← 正确答案
  • B.词法分析的正则表达式里
  • C.操作系统内核模块中
  • D.数据库的存储过程里

答案：A。语义动作附着在文法产生式上，归约时执行。就像菜谱每一步旁贴动作批注，跟文本解析链路完全耦合；与词法正则、操作系统、数据库均无关。

Q8. 以下哪些阶段通常需要遍历 AST？

多选题 · hard

  • A.语义分析（类型检查）← 正确答案
  • B.中间代码生成← 正确答案
  • C.代码优化← 正确答案
  • D.文本字体渲染

答案：ABC。类型检查、中间代码生成、代码优化都以 AST 或中间表示为对象做遍历访问；字体渲染处理的是轮廓点数据，与 AST 无关。因此 A、B、C 都需要遍历 AST。

Q9. 关于 AST 节点类型设计，下列说法正确的有？

多选题 · mid

  • A.通常按 Expr、Stmt、Decl 三大类设计← 正确答案
  • B.节点应记录源码位置便于报错← 正确答案
  • C.所有节点必须只有两个子节点
  • D.节点通过 children 指针互连成树← 正确答案

答案：ABD。三大分类是业界惯例；行号列号对报错和调试映射至关重要；子节点连接构成树。C 错误，AST 的度由语义决定，并非限定二叉。

Q10. 当属性文法同时需要综合与继承属性时，正确的说法有？

多选题 · hard

  • A.需要几遍计算由属性依赖图决定← 正确答案
  • B.可以一边下传上下文一边上汇结果← 正确答案
  • C.两类属性无法在同一次归约中出现
  • D.继承属性常用于传递声明类型等环境信息← 正确答案

答案：ABD。遍数取决于属性依赖图；像 L 属性文法这类常见情形允许单遍穿插计算，归约动作中同时读写两类属性。C 明显错误：类型下传（继承）与值上汇（综合）可以在同一条归约链上顺序完成。