二元表达式

2024-7-6

编译原理

目前我们的表达式还只是最简单的字面量。在这篇文章中，我们实现二元表达式的解析。

目前仅针对数学运算的二元表达式，即加减、乘除以及括号。这是一个经典的问题，让我们看看如何一步一步实现。

1. 加法

我们首先实现加法解析，如代码清单 1.1 所示，首先定义加法和减法的 token 解析规则。

代码清单 1.1 加减 token
  1. [/^[+\-]/, 'ADDITIVE_OPERATOR']

这边‘-’需要转义。因为它有特殊含义，比如 [a-z] 的用法，表示匹配任何小写字母。

如代码清单 1.2 所示，我们先写测试用例。我们定义二元表达式的 AST：类型是 BinaryExpression；operator 字段存储操作符；left 字段存储左侧操作数；right 字段存储右侧操作数。

代码清单 1.2 测试用例
  1. module.exports = test => {
  2.     // Addition
  3.     test(`2 + 2;`, {
  4.         type: 'Program',
  5.         body: [
  6.             {
  7.                 type: 'ExpressionStatement',
  8.                 expression: {
  9.                     type: 'BinaryExpression',
  10.                     operator: '+',
  11.                     left: {
  12.                         type: 'NumericLiteral',
  13.                         value: 2,
  14.                     },
  15.                     right: {
  16.                         type: 'NumericLiteral',
  17.                         value: 2,
  18.                     }
  19.                 }
  20.             }
  21.         ]
  22.     });
  23.  
  24.  
  25.     // Nested binary expressions:
  26.     test(`3 + 2 - 2;`, {
  27.         type: 'Program',
  28.         body: [
  29.             {
  30.                 type: 'ExpressionStatement',
  31.                 expression: {
  32.                     type: 'BinaryExpression',
  33.                     operator: '-',
  34.                     left: {
  35.                         type: 'BinaryExpression',
  36.                         operator: '+',
  37.                         left: {
  38.                             type: 'NumericLiteral',
  39.                             value: 3,
  40.                         },
  41.                         right: {
  42.                             type: 'NumericLiteral',
  43.                             value: 2,
  44.                         }
  45.                     },
  46.                     right: {
  47.                         type: 'NumericLiteral',
  48.                         value: 2,
  49.                     }
  50.                 }
  51.             }
  52.         ]
  53.     });
  54. }

代码清单 1.3 是加法的解析实现。我们关注它的文法定义，加法表达式可以是一个简单的字面量，也可以是加法表达式和字面量组合的嵌套表达式。

代码清单 1.3 加法解析
  1.     /**
  2.      * AdditiveExpression
  3.      *      : Literal
  4.      *      | AdditiveExpression ADDITIVE_OPERATOR Literal
  5.      *      ;
  6.      */
  7.     AdditiveExpression() {
  8.         let left = this.Literal();
  9.  
  10.         while (this._lookahead.type === 'ADDITIVE_OPERATOR') {
  11.             const operator = this._eat('ADDITIVE_OPERATOR').value;
  12.             const right = this.Literal();
  13.  
  14.             left = {
  15.                 type: 'BinaryExpression',
  16.                 operator,
  17.                 left,
  18.                 right,
  19.             };
  20.         }
  21.  
  22.         return left;
  23.     }

2. 乘法

我们接着实现乘法解析，如代码清单 2.1 所示，我们还是首先定义乘法和除法的 token 解析规则。

代码清单 2.1 乘除 token
  1. [/^[*\/]/, 'MULTIPLICATIVE_OPERATOR']

乘法的解析操作和加法类似。如代码清单 2.2 所示，乘法表达式可以是一个基本表达式，或者式乘法表达式和基本表达式的组合。目前基本表达式还只是字面量。

代码清单 2.2 乘法解析
  1.     /**
  2.      * MultiplicativeExpression
  3.      *      : PrimaryExpression
  4.      *      | MultiplicativeExpression MULTIPLICATIVE_OPERATOR PrimaryExpression
  5.      *      ;
  6.      */
  7.     MultiplicativeExpression() {
  8.         let left = this.PrimaryExpression();
  9.  
  10.         while (this._lookahead.type === 'MULTIPLICATIVE_OPERATOR') {
  11.             const operator = this._eat('MULTIPLICATIVE_OPERATOR').value;
  12.             const right = this.PrimaryExpression();
  13.  
  14.             left = {
  15.                 type: 'BinaryExpression',
  16.                 operator,
  17.                 left,
  18.                 right,
  19.             };
  20.         }
  21.  
  22.         return left;
  23.     }
  24.  
  25.     /**
  26.      * PrimaryExpression
  27.      *      : Literal
  28.      *      ;
  29.      */
  30.     PrimaryExpression() {
  31.         return this.Literal();
  32.     }

因为目前增加了乘法，需要考虑加法和乘法的优先级，所以我们需要对原先的加法解析进行“改造”。如代码清单 2.3 所示，加法表达式现在变为单个乘法表达式，或者加法表达式和乘法表达式相加的组合。

代码清单 2.3 加法解析
  1.     /**
  2.      * AdditiveExpression
  3.      *      : MultiplicativeExpression
  4.      *      | AdditiveExpression ADDITIVE_OPERATOR MultiplicativeExpression
  5.      *      ;
  6.      */
  7.     AdditiveExpression() {
  8.         let left = this.MultiplicativeExpression();
  9.  
  10.         while (this._lookahead.type === 'ADDITIVE_OPERATOR') {
  11.             const operator = this._eat('ADDITIVE_OPERATOR').value;
  12.             const right = this.MultiplicativeExpression();
  13.  
  14.             left = {
  15.                 type: 'BinaryExpression',
  16.                 operator,
  17.                 left,
  18.                 right,
  19.             };
  20.         }
  21.  
  22.         return left;
  23.     }

代码清单 2.4 是乘法解析的测试用例。重点关注优先级的测试用例：“2 + 2 * 2”的左侧要是“2”，右侧要是“2 * 2”。

代码清单 2.4 测试用例
  1. module.exports = test => {
  2.     test(`2 * 2;`, {
  3.         type: 'Program',
  4.         body: [
  5.             {
  6.                 type: 'ExpressionStatement',
  7.                 expression: {
  8.                     type: 'BinaryExpression',
  9.                     operator: '*',
  10.                     left: {
  11.                         type: 'NumericLiteral',
  12.                         value: 2,
  13.                     },
  14.                     right: {
  15.                         type: 'NumericLiteral',
  16.                         value: 2,
  17.                     }
  18.                 }
  19.             }
  20.         ]
  21.     });
  22.  
  23.     // Precedence of operations
  24.     test(`2 + 2 * 2;`, {
  25.         type: 'Program',
  26.         body: [
  27.             {
  28.                 type: 'ExpressionStatement',
  29.                 expression: {
  30.                     type: 'BinaryExpression',
  31.                     operator: '+',
  32.                     left: {
  33.                         type: 'NumericLiteral',
  34.                         value: 2,
  35.                     },
  36.                     right: {
  37.                         type: 'BinaryExpression',
  38.                         operator: '*',
  39.                         left: {
  40.                             type: 'NumericLiteral',
  41.                             value: 2,
  42.                         },
  43.                         right: {
  44.                             type: 'NumericLiteral',
  45.                             value: 2,
  46.                         }
  47.                     },
  48.                 }
  49.             }
  50.         ]
  51.     });
  52. }

3. 括号

代码清单 3.1 是括号的 token 解析规则。

代码清单 3.1 括号 token
  1. [/^\(/, '('],
  2. [/^\)/, ')']

乘法的优先级比加法大，括号的优先级比乘法大。如代码清单 3.2 所示，我们把括号表达式放在基本表达式中解析，让其和字面量“平级”。括号表达式的文法定义是，括号里包着一个表达式。

代码清单 3.2 括号表达式解析
  1.     /**
  2.      * PrimaryExpression
  3.      *      : Literal
  4.      *      | ParenthesizedExpression
  5.      *      ;
  6.      */
  7.     PrimaryExpression() {
  8.         switch (this._lookahead.type) {
  9.             case '(':
  10.                 return this.ParenthesizedExpression();
  11.             default:
  12.                 return this.Literal();
  13.         }
  14.     }
  15.  
  16.     /**
  17.      * ParenthesizedExpression
  18.      *      : '(' Expression ')'
  19.      *      ;
  20.      */
  21.     ParenthesizedExpression() {
  22.         this._eat('(');
  23.         const expression = this.Expression();
  24.         this._eat(')');
  25.  
  26.         return expression;
  27.     }

代码清单 3.3 是括号的测试用例。“(2 + 2) * 2”因为括号作用，现在左侧要是“2 + 2”，右侧要是“2”。

代码清单 3.3 测试用例
  1. module.exports = test => {
  2.     test(`(2 + 2) * 2;`, {
  3.         type: 'Program',
  4.         body: [
  5.             {
  6.                 type: 'ExpressionStatement',
  7.                 expression: {
  8.                     type: 'BinaryExpression',
  9.                     operator: '*',
  10.                     left: {
  11.                         type: 'BinaryExpression',
  12.                         operator: '+',
  13.                         left: {
  14.                             type: 'NumericLiteral',
  15.                             value: 2,
  16.                         },
  17.                         right: {
  18.                             type: 'NumericLiteral',
  19.                             value: 2,
  20.                         }
  21.                     },
  22.                     right: {
  23.                         type: 'NumericLiteral',
  24.                         value: 2,
  25.                     }
  26.                 }
  27.             }
  28.         ]
  29.     });
  30. }

4. 复用解析操作

从代码清单 1.3 和 2.2 中可以看到，加法和乘法的解析过程基本是一样的。不一样的仅是操作符，以及解析操作数的解析函数。所以如代码清单 4.1 所示，我们把这段逻辑“抽离”出来。

代码清单 4.1 通用解析
  1.     /**
  2.      * Generic binary expression
  3.      */
  4.     _BinaryExpression(builderName, operatoerToken) {
  5.         let left = this[builderName]();
  6.  
  7.         while (this._lookahead.type === operatoerToken) {
  8.             const operator = this._eat(operatoerToken).value;
  9.             const right = this[builderName]();
  10.  
  11.             left = {
  12.                 type: 'BinaryExpression',
  13.                 operator,
  14.                 left,
  15.                 right,
  16.             };
  17.         }
  18.  
  19.         return left;
  20.     }

这样，如代码清单 4.2 所示，我们就可以在加法和乘法解析中，复用解析操作。

代码清单 4.2 复用
  1.     /**
  2.      * AdditiveExpression
  3.      *      : MultiplicativeExpression
  4.      *      | AdditiveExpression ADDITIVE_OPERATOR MultiplicativeExpression
  5.      *      ;
  6.      */
  7.     AdditiveExpression() {
  8.         return this._BinaryExpression(
  9.             'MultiplicativeExpression',
  10.             'ADDITIVE_OPERATOR'
  11.         );
  12.     }
  13.  
  14.     /**
  15.      * MultiplicativeExpression
  16.      *      : PrimaryExpression
  17.      *      | MultiplicativeExpression MULTIPLICATIVE_OPERATOR PrimaryExpression
  18.      *      ;
  19.      */
  20.     MultiplicativeExpression() {
  21.         return this._BinaryExpression(
  22.             'PrimaryExpression',
  23.             'MULTIPLICATIVE_OPERATOR'
  24.         );
  25.     }