二元表达式
目前我们的表达式还只是最简单的字面量。在这篇文章中,我们实现二元表达式的解析。
目前仅针对数学运算的二元表达式,即加减、乘除以及括号。这是一个经典的问题,让我们看看如何一步一步实现。
1. 加法
我们首先实现加法解析,如代码清单 1.1 所示,首先定义加法和减法的 token 解析规则。
- [/^[+\-]/, 'ADDITIVE_OPERATOR']
这边‘-’需要转义。因为它有特殊含义,比如 [a-z] 的用法,表示匹配任何小写字母。
如代码清单 1.2 所示,我们先写测试用例。我们定义二元表达式的 AST:类型是 BinaryExpression;operator 字段存储操作符;left 字段存储左侧操作数;right 字段存储右侧操作数。
- module.exports = test => {
- // Addition
- test(`2 + 2;`, {
- type: 'Program',
- body: [
- {
- type: 'ExpressionStatement',
- expression: {
- type: 'BinaryExpression',
- operator: '+',
- left: {
- type: 'NumericLiteral',
- value: 2,
- },
- right: {
- type: 'NumericLiteral',
- value: 2,
- }
- }
- }
- ]
- });
- // Nested binary expressions:
- test(`3 + 2 - 2;`, {
- type: 'Program',
- body: [
- {
- type: 'ExpressionStatement',
- expression: {
- type: 'BinaryExpression',
- operator: '-',
- left: {
- type: 'BinaryExpression',
- operator: '+',
- left: {
- type: 'NumericLiteral',
- value: 3,
- },
- right: {
- type: 'NumericLiteral',
- value: 2,
- }
- },
- right: {
- type: 'NumericLiteral',
- value: 2,
- }
- }
- }
- ]
- });
- }
代码清单 1.3 是加法的解析实现。我们关注它的文法定义,加法表达式可以是一个简单的字面量,也可以是加法表达式和字面量组合的嵌套表达式。
- /**
- * AdditiveExpression
- * : Literal
- * | AdditiveExpression ADDITIVE_OPERATOR Literal
- * ;
- */
- AdditiveExpression() {
- let left = this.Literal();
- while (this._lookahead.type === 'ADDITIVE_OPERATOR') {
- const operator = this._eat('ADDITIVE_OPERATOR').value;
- const right = this.Literal();
- left = {
- type: 'BinaryExpression',
- operator,
- left,
- right,
- };
- }
- return left;
- }
2. 乘法
我们接着实现乘法解析,如代码清单 2.1 所示,我们还是首先定义乘法和除法的 token 解析规则。
- [/^[*\/]/, 'MULTIPLICATIVE_OPERATOR']
乘法的解析操作和加法类似。如代码清单 2.2 所示,乘法表达式可以是一个基本表达式,或者式乘法表达式和基本表达式的组合。目前基本表达式还只是字面量。
- /**
- * MultiplicativeExpression
- * : PrimaryExpression
- * | MultiplicativeExpression MULTIPLICATIVE_OPERATOR PrimaryExpression
- * ;
- */
- MultiplicativeExpression() {
- let left = this.PrimaryExpression();
- while (this._lookahead.type === 'MULTIPLICATIVE_OPERATOR') {
- const operator = this._eat('MULTIPLICATIVE_OPERATOR').value;
- const right = this.PrimaryExpression();
- left = {
- type: 'BinaryExpression',
- operator,
- left,
- right,
- };
- }
- return left;
- }
- /**
- * PrimaryExpression
- * : Literal
- * ;
- */
- PrimaryExpression() {
- return this.Literal();
- }
因为目前增加了乘法,需要考虑加法和乘法的优先级,所以我们需要对原先的加法解析进行“改造”。如代码清单 2.3 所示,加法表达式现在变为单个乘法表达式,或者加法表达式和乘法表达式相加的组合。
- /**
- * AdditiveExpression
- * : MultiplicativeExpression
- * | AdditiveExpression ADDITIVE_OPERATOR MultiplicativeExpression
- * ;
- */
- AdditiveExpression() {
- let left = this.MultiplicativeExpression();
- while (this._lookahead.type === 'ADDITIVE_OPERATOR') {
- const operator = this._eat('ADDITIVE_OPERATOR').value;
- const right = this.MultiplicativeExpression();
- left = {
- type: 'BinaryExpression',
- operator,
- left,
- right,
- };
- }
- return left;
- }
代码清单 2.4 是乘法解析的测试用例。重点关注优先级的测试用例:“2 + 2 * 2”的左侧要是“2”,右侧要是“2 * 2”。
- module.exports = test => {
- test(`2 * 2;`, {
- type: 'Program',
- body: [
- {
- type: 'ExpressionStatement',
- expression: {
- type: 'BinaryExpression',
- operator: '*',
- left: {
- type: 'NumericLiteral',
- value: 2,
- },
- right: {
- type: 'NumericLiteral',
- value: 2,
- }
- }
- }
- ]
- });
- // Precedence of operations
- test(`2 + 2 * 2;`, {
- type: 'Program',
- body: [
- {
- type: 'ExpressionStatement',
- expression: {
- type: 'BinaryExpression',
- operator: '+',
- left: {
- type: 'NumericLiteral',
- value: 2,
- },
- right: {
- type: 'BinaryExpression',
- operator: '*',
- left: {
- type: 'NumericLiteral',
- value: 2,
- },
- right: {
- type: 'NumericLiteral',
- value: 2,
- }
- },
- }
- }
- ]
- });
- }
3. 括号
代码清单 3.1 是括号的 token 解析规则。
- [/^\(/, '('],
- [/^\)/, ')']
乘法的优先级比加法大,括号的优先级比乘法大。如代码清单 3.2 所示,我们把括号表达式放在基本表达式中解析,让其和字面量“平级”。括号表达式的文法定义是,括号里包着一个表达式。
- /**
- * PrimaryExpression
- * : Literal
- * | ParenthesizedExpression
- * ;
- */
- PrimaryExpression() {
- switch (this._lookahead.type) {
- case '(':
- return this.ParenthesizedExpression();
- default:
- return this.Literal();
- }
- }
- /**
- * ParenthesizedExpression
- * : '(' Expression ')'
- * ;
- */
- ParenthesizedExpression() {
- this._eat('(');
- const expression = this.Expression();
- this._eat(')');
- return expression;
- }
代码清单 3.3 是括号的测试用例。“(2 + 2) * 2”因为括号作用,现在左侧要是“2 + 2”,右侧要是“2”。
- module.exports = test => {
- test(`(2 + 2) * 2;`, {
- type: 'Program',
- body: [
- {
- type: 'ExpressionStatement',
- expression: {
- type: 'BinaryExpression',
- operator: '*',
- left: {
- type: 'BinaryExpression',
- operator: '+',
- left: {
- type: 'NumericLiteral',
- value: 2,
- },
- right: {
- type: 'NumericLiteral',
- value: 2,
- }
- },
- right: {
- type: 'NumericLiteral',
- value: 2,
- }
- }
- }
- ]
- });
- }
4. 复用解析操作
从代码清单 1.3 和 2.2 中可以看到,加法和乘法的解析过程基本是一样的。不一样的仅是操作符,以及解析操作数的解析函数。所以如代码清单 4.1 所示,我们把这段逻辑“抽离”出来。
- /**
- * Generic binary expression
- */
- _BinaryExpression(builderName, operatoerToken) {
- let left = this[builderName]();
- while (this._lookahead.type === operatoerToken) {
- const operator = this._eat(operatoerToken).value;
- const right = this[builderName]();
- left = {
- type: 'BinaryExpression',
- operator,
- left,
- right,
- };
- }
- return left;
- }
这样,如代码清单 4.2 所示,我们就可以在加法和乘法解析中,复用解析操作。
- /**
- * AdditiveExpression
- * : MultiplicativeExpression
- * | AdditiveExpression ADDITIVE_OPERATOR MultiplicativeExpression
- * ;
- */
- AdditiveExpression() {
- return this._BinaryExpression(
- 'MultiplicativeExpression',
- 'ADDITIVE_OPERATOR'
- );
- }
- /**
- * MultiplicativeExpression
- * : PrimaryExpression
- * | MultiplicativeExpression MULTIPLICATIVE_OPERATOR PrimaryExpression
- * ;
- */
- MultiplicativeExpression() {
- return this._BinaryExpression(
- 'PrimaryExpression',
- 'MULTIPLICATIVE_OPERATOR'
- );
- }