Hulo 编程语言开发 —— 从源代码到 AST 的魔法转换

[ansurfen]

书接上回，在《 Hulo 语言架构：从源代码到目标代码的完整流程》一文中，我们介绍了Hulo编程语言的整体架构和编译流程。今天，让我们深入探讨编译流程中的第一个关键环节——解析器。

解析器可以说是源代码到目标语言最重要的基础，它负责将结构化的文本实例化为抽象语法树(AST)，这个过程也被称之为编译前端。解析器通过词法分析器(Lexer)将源代码分解为标记流(Token Stream)，再通过语法分析器(Parser)将标记流转换为抽象语法树，最终将人类可读的源代码转换为机器可处理的树形数据结构。这个树形结构保留了源代码的语法结构信息，为后续的语义分析、类型检查、优化和代码生成等编译后端阶段提供了必要的数据基础。

听起来好像云里雾里是吧，别急，接下来我们举一个简单的例子来说明：

假设我们现在有这样一段代码：print("Hello, World!")

Token （标记）

Token 是词法分析的最小单位，每个 Token 都包含类型和值信息。对于上面的代码，词法分析器会将其分解为以下 Token 序列：

类型	值
IDENT	print
LPAREN	(
STRING	"Hello, World!"
RPAREN	)

• IDENT 是标识符(Identifier)的缩写，一般变量名、函数名、类名、类型这些都归为标识符。
• LPAREN 、RPAREN 分别是 Left 和 Right 与 Paren 单词组合，就是简单的左括号和右括号。
• STRING 则很显而易见，Hello, World 整体是一个字符串的字面量。

Ps. 字面量是一种很常见的说法，比如说 3.14 、10 、0644 这些数字就可以被成为 NUMBER 类型的字面量，而 true 和 false 则是 BOOL 类型的字面量。

也就是说，Token 的作用就是将结构化的语法每个部分进行细分，细分到不可再分为止。我们可以在看一个稍微复杂的例子：

class User {
    name: str
    age: bool
}

类型	值	说明
CLASS	class	类声明关键字
IDENT	User	类名标识符
LBRACE	{	左大括号，类体开始
IDENT	name	字段名标识符
COLON	:	类型声明分隔符
IDENT	str	类型名标识符
IDENT	age	字段名标识符
COLON	:	类型声明分隔符
IDENT	bool	类型名标识符
RBRACE	}	右大括号，类体结束

Lexer （词法分析器）

词法分析器负责将源代码字符串分解为 Token 流。它的工作过程如下：

1. 字符扫描：从左到右逐个扫描源代码字符
2. 模式匹配：根据预定义的规则识别不同类型的 Token
3. Token 生成：为每个识别出的模式生成对应的 Token

例如，对于print("Hello, World!")：

• 扫描到print → 识别为标识符(IDENT)
• 扫描到( → 识别为左括号(LPAREN)
• 扫描到"Hello, World!" → 识别为字符串字面量(STRING)
• 扫描到) → 识别为右括号(RPAREN)

经过词法分析器的处理，源代码被分解为 Token[] 数组，每个 Token 都包含了类型和值信息。

Parser （语法分析器）

语法分析器负责将 Token 流转换为抽象语法树(AST)。它根据语言的语法规则，将 Token 组织成有意义的语法结构。

对于print("Hello, World!")，语法分析器会构建如下 AST：

CallExpr
├── Fun: Ident("print")
└── Args: [StringLiteral("Hello, World!")]

这个 AST 表示：

• 这是一个函数调用表达式(CallExpr)
• 函数名是"print"
• 参数是一个字符串字面量"Hello, World!"

看到这里，是不是感觉有点熟悉了？在大部分现代化语言的标准库中，往往都包含着解析成该语言 AST 的库。例如：

• Golang: go/ast - 提供 Go 语言的 AST 定义和解析功能
• TypeScript: @typescript-eslint/parser - TypeScript 的官方解析器
• Python: ast模块 - Python 标准库中的抽象语法树模块
• JavaScript: @babel/parser - Babel 生态中的 JavaScript 解析器
• Rust: syn库 - Rust 的语法解析库
• Java: javac编译器内置的 AST 处理
• C#: Roslyn 编译器平台提供的语法树 API

这些库不仅为语言本身提供了强大的代码分析能力，也为开发者构建工具链、代码格式化、静态分析、代码生成等提供了基础支持。通过使用这些标准化的 AST 库，开发者可以更容易地实现代码转换、优化和工具开发。

回到分析器本身，我们已经完成了从源代码到结构化实例的转换，是的，编译前端就是在做这样的工作，将难以操作的字符串转换成一个个对象，例如 CallExpr 表达式对象、IfStmt 语句对象、ClassDecl 声明对象... 这些转换将代码变得可操作了起来，它不再是只能靠正则表达式或者字符串处理的语法。

在 AST 中，节点通常分为三大类：

• Expr (Expression): 表达式节点，表示会产生值的代码片段。例如：

  • CallExpr: 函数调用表达式，如 print("hello")
  • BinaryExpr: 二元运算表达式，如 a + b
  • Ident: 标识符表达式，如变量名 x
  • StringLiteral: 字符串字面量，如 "hello"

• Stmt (Statement): 语句节点，表示执行动作的代码片段。例如：

  • IfStmt: if 条件语句，如 if (x > 0) { ... }
  • WhileStmt: while 循环语句，如 while (i < 10) { ... }
  • AssignStmt: 赋值语句，如 x = 10
  • ReturnStmt: 返回语句，如 return result

• Decl (Declaration): 声明节点，表示定义新实体的代码片段。例如：

  • ClassDecl: 类声明，如 class User { ... }
  • FuncDecl: 函数声明，如 function add(a, b) { ... }
  • VarDecl: 变量声明，如 var x = 10

这种分类方式使得 AST 具有清晰的层次结构，便于后续的语义分析、类型检查和代码生成。

Ps. 当然这都是人为划定的，你也可以都把他们当成同样的节点也是可以的。不过，合理的分类能够帮助我们更好地理解代码结构，并为后续的编译阶段提供更清晰的语义信息。

[vfs]

为什么需要一种脚本编译成另一种脚本？ 自身的定位就是脚本，那支持跨平台不就可以了吗？

[xuanwu]

木兰项目用 rply 生成 python 语法树：
https://gitee.com/MulanRevive/mulan-rework
项目源码用中文命名，方便阅览：

[ansurfen]

@vfs 因为 bash powershell batch vbs 直接与操作系统捆绑着，他们自带 runtime ，其他语言如 python 、js 都需要安装运行时。而且 bash 在 linux 上面的地位有目共睹，大部分的批处理基本上都用 bash 实现。

[ansurfen]

@xuanwu Hulo 使用 ANTLR4 生成语法树 https://github.com/hulo-lang/hulo/blob/main/syntax/hulo/parser/grammar/huloParser.g4
使用 ANTLR4 有很高的容错性，一旦语法树解析错误也能继续递归， 这种机制使其在处理不完整或有误的输入时仍能保持一定的解析能力（例如 IDE 中的实时语法检查）

[xgdgsc]

https://github.com/goplus/xgo 怎么感觉跟这个的功能有点重合，直接编译到机器码得了？

[xgdgsc]

还有 Julia1.12 也会开始实验支持编译类型稳定代码到小体积二进制了

[ansurfen]

@xgdgsc 这差的很多吧，Hulo 的目标是编译成 Bash 、Powershell 、VBS 、Batch 统一批处理脚本，作为批处理脚本的中间语言，你可以理解成批处理脚本的 LLVM ，然后在写一个提升器，将 Bash 转化成 Hulo ，就可以实现 Hulo 到其他批处理脚本的转换

[xuanwu]

@ansurfen 几年前试过一点 antlr： https://zhuanlan.zhihu.com/p/32792684
https://zhuanlan.zhihu.com/p/32939695