正则表达式

2024-6-1

编译原理

在上一节中，我们引入了词法分析器，并实现了数字和字符串字面量的提取。但是我们目前是手动进行匹配解析的。面对后续越来越多的情况，解析会显得繁杂。

这已经是一个解决了的问题，有状态机相关的一套理论。比如数字的解析，对应于如图 1 所示的状态机。进一步，正则表达式描述可以生成对应模式的状态机。

图1 状态机

所以，如代码清单 1 所示，我们将之前的数字和字符串提取过程，修改为使用正则表达式进行匹配。

代码清单 1 使用正则表达式
  1. class Tokenizer {
  2.     getNextToken() {
  3.         if (!this.hasMoreTokens()) {
  4.             return null;
  5.         }
  6.  
  7.         const string = this._string.slice(this._cursor);
  8.  
  9.         // Numbers: \d+
  10.         let matched = /^\d+/.exec(string);
  11.         if (matched !== null) {
  12.             this._cursor += matched[0].length;
  13.             return {
  14.                 type: 'NUMBER',
  15.                 value: matched[0],
  16.             };
  17.         }
  18.  
  19.         // String
  20.         matched = /"[^"]*"/.exec(string);
  21.         if (matched !== null) {
  22.             this._cursor += matched[0].length;
  23.             return {
  24.                 type: 'STRING',
  25.                 value: matched[0],
  26.             };
  27.         }
  28.         return null;
  29.     }
  30. }

这个过程还能进一步“抽象”，我们只要指定 token 对应的正则表达式，因为匹配逻辑是通用的。如代码清单 2 所示，我们定义了词法单元的 Spec 数组。词法解析过程就是，依次尝试匹配 Spec 里定义的规范，只要匹配了就返回 token 信息，否则接着后续尝试。都匹配不上的话，则抛出异常。

我们可以看到这套逻辑很好用，因为我们很轻松的添加了字符串的另一种形式（第 10 行）：使用单引号包围。

代码清单 2 Spec
  1. /**
  2.  * Tokenizer spec.
  3.  */
  4. const Spec = [
  5.     // Numbers:
  6.     [/^\d+/, 'NUMBER'],
  7.  
  8.     // Strings:
  9.     [/^"[^"]*"/, 'STRING'],
  10.     [/^'[^']*'/, 'STRING'],
  11. ];
  12.  
  13. class Tokenizer {
  14.     getNextToken() {
  15.         if (!this.hasMoreTokens()) {
  16.             return null;
  17.         }
  18.  
  19.         const string = this._string.slice(this._cursor);
  20.  
  21.         for (const [regexp, tokenType] of Spec) {
  22.             const tokenValue = this._match(regexp, string);
  23.  
  24.             if (tokenValue === null)
  25.                 continue;
  26.  
  27.             return {
  28.                 type: tokenType,
  29.                 value: tokenValue,
  30.             };
  31.         }
  32.  
  33.         throw new SyntaxError(`Unexpected token: "${string[0]}"`);
  34.     }
  35.  
  36.     _match(regexp, string) {
  37.         const matched = regexp.exec(string);
  38.         if (matched === null)
  39.             return null;
  40.  
  41.         this._cursor += matched[0].length;
  42.         return matched[0];
  43.     }
  44. }

在目前的基础上，我们继续增加空白符的跳过。如代码清单 3 的第 31 行所示，如果我们匹配上空白符，则跳过这些字符，匹配后续满足的 token。

递归的写法，看着逻辑会更加清晰。写成“内部”的 while 循环也是可以的。

代码清单 3 空白符
  1. /**
  2.  * Tokenizer spec.
  3.  */
  4. const Spec = [
  5.     // Whitespace:
  6.     [/^\s+/, null],
  7.  
  8.     // Numbers:
  9.     [/^\d+/, 'NUMBER'],
  10.  
  11.     // Strings:
  12.     [/^"[^"]*"/, 'STRING'],
  13.     [/^'[^']*'/, 'STRING'],
  14. ];
  15.  
  16. class Tokenizer {
  17.     getNextToken() {
  18.         if (!this.hasMoreTokens()) {
  19.             return null;
  20.         }
  21.  
  22.         const string = this._string.slice(this._cursor);
  23.  
  24.         for (const [regexp, tokenType] of Spec) {
  25.             const tokenValue = this._match(regexp, string);
  26.  
  27.             if (tokenValue === null)
  28.                 continue;
  29.  
  30.             if (tokenType === null)
  31.                 return this.getNextToken();
  32.  
  33.             return {
  34.                 type: tokenType,
  35.                 value: tokenValue,
  36.             };
  37.         }
  38.  
  39.         throw new SyntaxError(`Unexpected token: "${string[0]}"`);
  40.     }
  41. }

我们可以用以下测试用例检查一下流程，可以看到字符串前的空白符都如预期跳过了。当然，字符串里的空白符肯定是不受影响的。

  • const program = `   "  Hello world  "  `;

作为实验，代码中的注释信息，我们也不想保留。我们继续添加注释的正则表达式。如代码清单 4 所示，我们添加单行注释和多行注释的正则表达式。

多行注释需要跨行匹配，而且是非贪婪匹配。

代码清单 4 注释
  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.     // Numbers:
  14.     [/^\d+/, 'NUMBER'],
  15.  
  16.     // Strings:
  17.     [/^"[^"]*"/, 'STRING'],
  18.     [/^'[^']*'/, 'STRING'],
  19. ];

可以用以下测试用例验证单行注释和多行注释。

  • const program = `
  •     // Number:
  •     42
  • `;
  • const program = `
  •     /**
  •      * Documentation comment:
  •      */
  •     42
  • `;