NewsWWW

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

·

user

书接上回，在《 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. 当然这都是人为划定的，你也可以都把他们当成同样的节点也是可以的。不过，合理的分类能够帮助我们更好地理解代码结构，并为后续的编译阶段提供更清晰的语义信息。

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *