词法分析器/语法分析器

2024-5-10

编译原理

编译原理在理论上往往让人望而却步。这边准备跟着教程先从实践入门。先从手写的递归下降进行入门。

如图 1 所示，我们先大致了解编译器前端的工作流程。

1. 源代码：最先输入的是源码。如图是 `print("hello")` 。

2. 词法分析器：代码首先被送入词法分析器。词法分析器的任务是把输入的代码分解成一系列的 token。在图中，"print" 被识别为标识符；"hello" 被识别为字符串。

3. 语法分析器：接下来，这些 token 被送入语法分析器。语法分析器根据这些 token 构建出抽象语法树，即 AST。在图中，创建了一个“函数调用”节点，节点名称是 "print"，参数是 "hello"。

图1 处理流程

理论不多说，我们先上代码。代码清单 1 是一个最简单的解析器，它只能处理仅含数字的字符串，并将其转换为 AST 节点。

代码清单 1 Parser.js
  1. class Parser {
  2.     /**
  3.      * Parse a string into AST
  4.      */
  5.     parse(string) {
  6.         this._string = string;
  7.  
  8.         return this.Program();
  9.     }
  10.  
  11.     /**
  12.      * Main entry point
  13.      *
  14.      * Program
  15.      *      : NumericLiteral
  16.      *      ;
  17.      */
  18.     Program() {
  19.         return this.NumericLiteral();
  20.     }
  21.  
  22.     /**
  23.      * NumericLiteral
  24.      *      : NUMBER
  25.      *      ;
  26.      */
  27.     NumericLiteral() {
  28.         return {
  29.             type: 'NumericLiteral',
  30.             value: Number(this._string),
  31.         };
  32.     }
  33. }
  34.  
  35. module.exports = {
  36.     Parser
  37. };

注释里显示的是 BNF（巴科斯-诺尔范式），一种用于表示上下文无关文法的符号系统。这边写的规则是，Program 由一个 NumericLiteral 非终结符构成。NumericLiteral 由 NUMBER 终结符构成。即，现在我们的程序文本只能是数字。

在文法中，非终结符是那些可以被进一步分解成其他非终结符或终结符的符号。

终结符是文法的基本单元，不能被进一步分解。

最后，如代码清单 2 所示，我们写测试程序进行调用验证。

代码清单 2 run.js
  1. const { Parser } = require("../src/Parser");
  2.  
  3. const parser = new Parser();
  4.  
  5. const program = '42';
  6.  
  7. const ast = parser.parse(program);
  8.  
  9. console.log(JSON.stringify(ast, null, 2));

JSON.stringify 函数将 JS 对象转换成 JSON 字符串。其接收三个参数：

1. value：要被转成 JSON 字符串的对象。

2. replacer（可选）：一个函数或数组，用于控制如何处理对象属性。

3. space（可选）：用于控制输出格式。像此处的数字，表示每个级别缩进使用的空格数。

可以看到程序能按预期打印。

  • {
  •   "type": "NumericLiteral",
  •   "value": 42
  • }