数字/字符串

2024-5-18

编译原理

在上一篇文章中，我们已经实现了一个仅能够解析数字的解析器。虽然简单，但的确是一个非常好的开始。

数字和字符串都是字面量的范畴，这篇文章我们继续增加对字符串的处理。同时我们引入词法分析器，即分词器。

分词器的核心功能是从字符串中提取 token。我们看到代码清单 1 中分词器的实现，在 getNextToken 函数中，它识别提取数字 token 和字符串 token。

具体的提取方式也很简易：当检测到第一个字符是数字时，就一直往后读取数字字符，当作数字 token；当检测到第一个字符是双引号时，则一直读取直到下一个双引号，当作字符串 token。

代码清单 1 Tokenizer.js
  1. class Tokenizer {
  2.     init(string) {
  3.         this._string = string;
  4.         this._cursor = 0;
  5.     }
  6.  
  7.     isEOF() {
  8.         return this._cursor === this._string.length;
  9.     }
  10.  
  11.     hasMoreTokens() {
  12.         return this._cursor < this._string.length;
  13.     }
  14.  
  15.     getNextToken() {
  16.         if (!this.hasMoreTokens()) {
  17.             return null;
  18.         }
  19.  
  20.         const string = this._string.slice(this._cursor);
  21.  
  22.         // Numbers:
  23.         if (!Number.isNaN(Number(string[0]))) {
  24.             let number = '';
  25.             while (!Number.isNaN(Number(string[this._cursor]))) {
  26.                 number += string[this._cursor++];
  27.             }
  28.             return {
  29.                 type: 'NUMBER',
  30.                 value: number,
  31.             };
  32.         }
  33.  
  34.         // String
  35.         if (string[0] === '"') {
  36.             let s = '';
  37.             do {
  38.                 s += string[this._cursor++];
  39.             } while (string[this._cursor] !== '"' && !this.isEOF());
  40.             s += this._cursor++;
  41.             return {
  42.                 type: 'STRING',
  43.                 value: s,
  44.             };
  45.         }
  46.         return null;
  47.     }
  48. }
  49.  
  50. module.exports = {
  51.     Tokenizer
  52. };

顺带学 JavaScript：

JavaScript 中的 === 与 C 中的 == 在概念上是类似的。

JavaScript 中的 == 与 C++ 中隐式转换有点类似，但是转换规则着实令人费解。查了一下可能是历史包袱的设计原因，无需花时间多纠结。

接着我们改造之前的解析器逻辑，让其利用上分词器的功能。如代码清单 2 所示，我们在解析器的构造函数中引入分词器实例。

同时注意这边引入了一个 _lookahead 变量。lookahead 是典型的递归下降解析结构，使用 LL(1) 策略。这边“LL”表示“从左到右扫描（Left-to-right）”，以及“最左推导（Leftmost derivation）”；“1”表示向前看一个 token。即我们每次会向前看一个 token，进而进行决策制定。

代码清单 2 _lookahead
  1. class Parser {
  2.     constructor() {
  3.         this._string = '';
  4.         this._tokenizer = new Tokenizer();
  5.     }
  6.  
  7.     /**
  8.      * Parse a string into AST
  9.      */
  10.     parse(string) {
  11.         this._string = string;
  12.         this._tokenizer.init(string);
  13.  
  14.         this._lookahead = this._tokenizer.getNextToken();
  15.  
  16.         return this.Program();
  17.     }
  18. }

我们再看到 _lookahead 的维护，如代码清单 3 所示，我们看到增加的 _eat 函数。它的作用是“吃掉”、消费掉一个 token，确保它符合预期的类型，并更新 _lookahead 到下一个 token。

代码清单 3 _eat
  1. class Parser {
  2.     _eat(tokenType) {
  3.         const token = this._lookahead;
  4.  
  5.         if (token == null) {
  6.             throw new SyntaxError(
  7.                 `Unexpected end of input, expected: "${tokenType}"`,
  8.             );
  9.         }
  10.  
  11.         if (token.type !== tokenType) {
  12.             throw new SyntaxError(
  13.                 `Unexpected token: "${token.value}", expected: "${tokenType}"`,
  14.             );
  15.         }
  16.  
  17.         this._lookahead = this._tokenizer.getNextToken();
  18.  
  19.         return token;
  20.     }
  21. }

我觉得这个 _eat 更有意义的一点是，它能确保解析过程严格遵循语法规则。它不仅控制 token 进展，还检查 token 的正确性。

最后我们感受 LL(1) 决策的体现。看到代码清单 4 中的 Literal() 函数，它根据 token 的类型决定如何处理字面量。

同时注意语法规范在设计上的改动，新增了 Program，作为更加抽象的顶层。新增了 Literal，包含 NumericLiteral 和 StringLiteral。

代码清单 4 决策
  1. class Parser {
  2.     /**
  3.      * Main entry point
  4.      *
  5.      * Program
  6.      *      : Literal
  7.      *      ;
  8.      */
  9.     Program() {
  10.         return {
  11.             type: 'Program',
  12.             body: this.Literal(),
  13.         };
  14.     }
  15.  
  16.     /**
  17.      * Literal
  18.      *      : NumericLiteral
  19.      *      | StringLiteral
  20.      *      ;
  21.      */
  22.     Literal() {
  23.         switch (this._lookahead.type) {
  24.             case 'NUMBER':
  25.                 return this.NumericLiteral();
  26.             case 'STRING':
  27.                 return this.StringLiteral();
  28.         }
  29.         throw new SyntaxError(`Literal: unexpected literal production`);
  30.     }
  31.  
  32.     /**
  33.      * StringLiteral
  34.      *      : STRING
  35.      *      ;
  36.      */
  37.     StringLiteral() {
  38.         const token = this._eat("STRING");
  39.         return {
  40.             type: 'StringLiteral',
  41.             value: token.value.slice(1, -1),
  42.         };
  43.     }
  44.  
  45.     /**
  46.      * NumericLiteral
  47.      *      : NUMBER
  48.      *      ;
  49.      */
  50.     NumericLiteral() {
  51.         const token = this._eat("NUMBER");
  52.         return {
  53.             type: 'NumericLiteral',
  54.             value: Number(token.value),
  55.         };
  56.     }
  57. }