语句

2024-6-9

编译原理

目前我们的解析器已经初具规模了。我们已经实现了数字和字符串的解析，实现了空白符和注释的跳过。在这篇文章中，我们继续添加 语句 的解析。

语句是表示某种操作的独立代码单元。在很多编程语言中，语句以分号结束，我们也采用这种方式。

程序代码由多条语句组成。所以如代码清单 1 所示，我们修改程序的文法定义，现在程序由 StatementList 组成。

代码清单 1 Program
  1.     /**
  2.      * Main entry point
  3.      *
  4.      * Program
  5.      *      : StatementList
  6.      *      ;
  7.      */
  8.     Program() {
  9.         return {
  10.             type: 'Program',
  11.             body: this.StatementList(),
  12.         };
  13.     }

如代码清单 2 所示，StatementList 的文法定义是左递归形式的，不断用“StatementList Statement”替换“StatementList”，可以看到 StatementList 就是由多条 Statement 组成的。

理论化的左递归转右递归，看着过于繁杂。实际中的概念非常简单。

代码清单 2 StatementList
  1.     /**
  2.      * StatementList
  3.      *      : Statement
  4.      *      | StatementList Statement
  5.      *      ;
  6.      */
  7.     StatementList() {
  8.         const statementList = [this.Statement()];
  9.  
  10.         while (this._lookahead != null) {
  11.             statementList.push(this.Statement());
  12.         }
  13.         return statementList;
  14.     }

如代码清单 3 所示，目前语句只包含表达式语句。

代码清单 3 Statement
  1.     /**
  2.      * Statement
  3.      *      : ExpressionStatement
  4.      *      ;
  5.      */
  6.     Statement() {
  7.         return this.ExpressionStatement();
  8.     }

如代码清单 4 所示，表达式语句的文法是表达式，后接分号。所以我们此时需要“吃掉”一个分号并移进到下一个 token。

代码清单 4 ExpressionStatement
  1.     /**
  2.      * ExpressionStatement
  3.      *      : Expression ';'
  4.      *      ;
  5.      */
  6.     ExpressionStatement() {
  7.         const expression = this.Expression();
  8.         this._eat(';');
  9.         return {
  10.             type: 'ExpressionStatement',
  11.             expression,
  12.         };
  13.     }

如代码清单 5 所示，目前表达式就是之前实现的字面量。

代码清单 5 Expression
  1.     /**
  2.      * Expression
  3.      *      : Literal
  4.      *      ;
  5.      */
  6.     Expression() {
  7.         return this.Literal();
  8.     }

现在分号已经需要具有 token 含义了，所以如代码清单 5 所示，我们添加分号 token 解析（第 14 行）。

代码清单 6 分号
  1. /**
  2.  * Tokenizer spec.
  3.  */
  4. const Spec = [
  5.     // Whitespace:
  6.     [/^\s+/, null],
  7.  
  8.     // Single-line comments:
  9.     [/^\/\/.*/, null],
  10.     // Multi-line comments:
  11.     [/^\/\*[\s\S]*?\*\//, null],
  12.  
  13.     // Symbols, delimiters
  14.     [/^;/, ';'],
  15.  
  16.     // Numbers:
  17.     [/^\d+/, 'NUMBER'],
  18.  
  19.     // Strings:
  20.     [/^"[^"]*"/, 'STRING'],
  21.     [/^'[^']*'/, 'STRING'],
  22. ];

AST 节点的设计可以参照 astexplorer.net 这个网站。

增加测试用例

我们引入 TDD（Test-Driven Development）开发模式，即测试驱动开发。在此之前，我们需要把目前已经实现了的功能，补上测试用例。

如代码清单 7 所示，我们指定字面量的测试用例。

代码清单 7 literals-test.js
  1. module.exports = test => {
  2.     test(`42;`, {
  3.         type: 'Program',
  4.         body: [
  5.             {
  6.                 type: 'ExpressionStatement',
  7.                 expression: {
  8.                     type: 'NumericLiteral',
  9.                     value: 42,
  10.                 }
  11.             }
  12.         ]
  13.     });
  14.  
  15.     test(`"hello";`, {
  16.         type: 'Program',
  17.         body: [
  18.             {
  19.                 type: 'ExpressionStatement',
  20.                 expression: {
  21.                     type: 'StringLiteral',
  22.                     value: 'hello',
  23.                 }
  24.             }
  25.         ]
  26.     });
  27.  
  28.     test(`'hello';`, {
  29.         type: 'Program',
  30.         body: [
  31.             {
  32.                 type: 'ExpressionStatement',
  33.                 expression: {
  34.                     type: 'StringLiteral',
  35.                     value: 'hello',
  36.                 }
  37.             }
  38.         ]
  39.     });
  40. };

顺带学 JavaScript：

这边导出的是箭头函数，基本语法为 (parameters) => { // 函数体 };。如果只有一个参数，可以省略参数周围的括号。

箭头函数可以按 C++ 的 lambda 函数理解。此处传入的 test 参数，可以当成函数指针理解。

代码清单 8 是本节语句解析的测试用例。

代码清单 8 statement-list-test.js
  1. module.exports = test => {
  2.     test(
  3.         `
  4.         "hello";
  5.  
  6.         // Number
  7.         42;
  8.         `,
  9.         {
  10.             type: 'Program',
  11.             body: [
  12.                 {
  13.                     type: 'ExpressionStatement',
  14.                     expression: {
  15.                         type: 'StringLiteral',
  16.                         value: 'hello',
  17.                     }
  18.                 },
  19.                 {
  20.                     type: 'ExpressionStatement',
  21.                     expression: {
  22.                         type: 'NumericLiteral',
  23.                         value: 42,
  24.                     }
  25.                 }
  26.             ]
  27.         });
  28. };

最后，我们来看如何使用测试用例。如代码清单 9 所示，我们首先定义需要传递的“基础”测试函数 test，它解析 input 字符串，将得到的 ast 和 expected 进行比较，如果不一致就代表测试失败。

我们将多个测试函数导出，存放在 tests 数组，并用 forEach 方法依次遍历调用。

代码清单 9 使用测试用例
  1. const tests = [
  2.     require("./literals-test.js"),
  3.     require("./statement-list-test.js")
  4. ];
  5.  
  6. function test(program, expected) {
  7.     const ast = parser.parse(program);
  8.     assert.deepEqual(ast, expected);
  9. }
  10.  
  11. tests.forEach(testRun => testRun(test));