2. AST数据结构：节点类型定义、树形结构遍历、Python中AST库的基本使用

好，咱们今天聊聊AST的数据结构。说实话，很多做HDL优化的朋友，一听到「抽象语法树」就觉得头大。我当年刚接触的时候也一样，觉得这东西太抽象了。但后来我发现，你只要搞懂三件事——节点长什么样、树怎么走、Python里怎么用——剩下的就水到渠成了。

2.1 节点类型定义：AST的「积木块」

AST说白了就是一棵树。树的每个节点，都代表源代码里的一个语法结构。比如一个if语句、一个assign赋值、一个module声明，都会被拆成独立的节点。

我习惯把节点分成三类：

• 根节点：代表整个设计文件，比如Module节点
• 语句节点：代表可执行语句，比如Assign、If、Always
• 表达式节点：代表运算或值，比如BinaryOp、Identifier、Number

举个例子，Verilog里写一句 assign c = a & b;，AST会拆成：

Module
 └── Assign (语句节点)
      ├── Identifier: c (表达式节点)
      └── BinaryOp: & (表达式节点)
           ├── Identifier: a
           └── Identifier: b

每个节点都有自己的属性。比如BinaryOp节点，除了左右子节点，还得存一个op属性，告诉你这是与、或还是异或。我在项目中踩过坑——一开始没给节点加line_number属性，结果报错时根本定位不到源码位置。后来我强制每个节点都带上行列号，调试效率翻倍。

2.2 树形结构遍历：怎么「走」这棵树？

树建好了，你得会走。遍历方式就两种：深度优先（DFS）和广度优先（BFS）。做代码优化时，90%的情况用DFS就够了。

DFS又分前序、中序、后序。我个人的经验是：

• 前序遍历：先处理父节点，再处理子节点。适合做「代码生成」——先输出模块头，再输出内部逻辑。
• 后序遍历：先处理子节点，再处理父节点。适合做「表达式化简」——先把子表达式算完，再合并到父节点。
• 中序遍历：二叉表达式树专用，比如把 a + b * c 还原成中缀表达式。

我曾经接手过一个项目，同事用BFS遍历AST做常量传播，结果因为没处理好层级关系，导致优化后的代码逻辑全乱了。后来我改成后序遍历，先算最内层的常量表达式，再往外一层一层替换，问题就解决了。

2.3 Python中AST库的基本使用

Python自带的ast模块，其实是个宝藏。虽然它针对的是Python语法，但它的设计思想完全可以迁移到HDL的AST处理上。

咱们先看一个最简单的例子——解析Python表达式：

import ast

code = "x = a + b * 2"
tree = ast.parse(code)
print(ast.dump(tree, indent=2))

输出结果长这样：

Module(
  body=[
    Assign(
      targets=[Name(id='x', ctx=Store())],
      value=BinOp(
        left=Name(id='a', ctx=Load()),
        op=Add(),
        right=BinOp(
          left=Name(id='b', ctx=Load()),
          op=Mult(),
          right=Constant(value=2))))])

你看，BinOp节点对应二元运算，Name节点对应变量名，Constant对应常量。这和咱们前面讲的HDL节点类型，本质上是一回事。

那怎么遍历呢？Python提供了NodeVisitor基类：

class MyVisitor(ast.NodeVisitor):
    def visit_BinOp(self, node):
        print(f"发现二元运算: {type(node.op).__name__}")
        self.generic_visit(node)  # 继续遍历子节点

    def visit_Name(self, node):
        print(f"发现变量: {node.id}")
        self.generic_visit(node)

visitor = MyVisitor()
visitor.visit(tree)

运行后会输出：

发现变量: a
发现二元运算: Add
发现变量: b
发现二元运算: Mult
发现常量: 2

嗯，这里要注意——NodeVisitor默认是深度优先前序遍历。如果你想做后序遍历，可以自己控制generic_visit的调用时机。

2.4 从Python AST到HDL AST的迁移思路

说白了，Python的ast模块给了我们一个很好的模板。做HDL的AST时，你完全可以照搬它的设计：

Python AST	HDL AST（示例）	说明
Module	DesignFile	顶层节点，代表整个文件
Assign	ContinuousAssign	连续赋值语句
BinOp	BinaryOp	二元运算，如 &、|、^
Name	Identifier	信号或变量名
Constant	Number	数值常量

我建议你直接用Python的ast模块做原型验证。先写一个简单的Verilog解析器，把Verilog转成Python的AST节点结构，然后用NodeVisitor做遍历和优化。等逻辑跑通了，再换成C++或Rust实现高性能版本。

---

公众号:蓝海资料掘金营，微信deep3321