Skip to content

Latest commit

 

History

History
508 lines (376 loc) · 19.2 KB

014.ANTLR:在浏览器中玩语法解析.md

File metadata and controls

508 lines (376 loc) · 19.2 KB

ANTLR:在浏览器中玩语法解析

作者简介 zqlu 蚂蚁金服·数据体验技术团队

一、前言

在前端开发中,通常提到语法解析等功能,这是都是有后端负责提供接口,前端调用。那么前端是否能自主完成语法解析相关的功能,并在浏览器中运行呢?答案是肯定,本文将描述一种简化的语言称为Expr语言,并在浏览器中完成对输入的Expr代码做错误验证、执行和翻译等等功能。

二、简化的 Expr 语言

首先,介绍下我们的Expr语言,Expr语言是本文假设的一种简化的类 C 的语言,代码片段如下:

a = 2;
b = 3
c = a * (b + 2);
d = a / (c - 1);

a; // 应该输出2
b; // 应该输出3
c;
d;

前 4 行的行为是大家熟悉的赋值表达式,最后 4 行为打印语句,即依次打印各个变量的值,当然这里也包含了我们熟悉的注释。

问题来了,我们能在前端自主解析 Expr 语法的代码,并解释执它们吗? 如果代码片段中有错误,我们能给出准确的错误提示信息吗?还有更多有趣的问题,我们的 Expr 语言采用了中缀表达式,我们能把输入代码翻译成前缀表达式代码吗?我们能对输入的代码片段做代码格式化吗?我们能把 Expr 代码翻译成其他语言的源码吗?

首先看看最后的Demo,我们可以在 Demo 页面代码框输入 Expr 语言的代码,点击执行按钮,即可以看到执行后的结果:

Demo

这些功能是在浏览器利用 ANTLR v4 来完成语法解析,并最终实现了语法验证、解释执行等功能。

三、初识 ANTLR v4

ANTLR 的介绍

Antlr4 是 ANother Tool for Language Recognition 即另一个语言识别工具,官方介绍为 Antlr4 是一款强大的解析器生成工具,可用来读取、处理、执行和翻译结构化文本或二进制文件。

Antlr4 生成的解析器包含了词法分析程序和语法分析程序,没错,这就是编译原理课程中的词法分析和语法分析。写了几年前端是不是都忘记了,我们只需要知道词法分析程序是将输入的代码字符序列转换成标记(Token)序列的程序,而语法分析程序则是将标记序列转换成语法树的程序。好在按照 Antlr4 规范制定了语法定义,Antlr4 就可以为我们生成解析器源码,它不仅可以生成 Java 源码,还可以生成我们前端方便的 JavaScript 和 TypeScript 源码。不错,在本文,我们就是要用 Antlr4 生成的 TypeScript 版的解析器,来解析我们的 Expr 语言代码。

ANTLR v4 的安装使用

关于 Antlr4 的安装和使用,大家可以参照 Github 上的Getting Started with ANTLR v4,这里不作介绍。简单来说,使用 ANTLR v4,一般分为三步:

  • 按照 ANTLR v4 的编写待解析语言的语法定义文件,主流语言的 ANTLR v4 语法定义可以找仓库antlr/grammars-v4中找到,一般以 g4 为语法定义文件后缀
  • 运行 ANTLR 工具,生成指定目标语言的解析器源代码
  • 使用生成的解析器完成代码的解析等

四、Expr 语言的语法定义

按照上述的介绍,为了实现解释执行我们的 Expr 语言,首先第一步需要按照 ANTLR v4 的规范来定义 Expr 语言的语法定义文件 Expr.g4。这里简单介绍下 ANTLR v4 的语法定义的思路,更多详细介绍可以参照 ANTLR 作者的著作《The Definitive ANTLR 4 Reference》。

语法规则

ANTLR v4 的语法定义文件以语法声明语句和一系列语法规则语法,大致结构如下:

grammar Name; # 申明名为Name的语法

# 一次定义语法规则
rule1
rule2
...
ruleN

其中每条语法规则结构如:

ruleName: alternative1 | alternative2 | alternative3 ;

这条语法规则申明一条名为ruleName的规则,其中|表名为分支、即改规则可以匹配三个分支中的任何一个。

最后,ANTLR v4 的语法规则分为词法(Lexer)规则和语法(Parser)规则:词法规则定义了怎么将代码字符串序列转换成标记序列;语法规则定义怎么将标记序列转换成语法树。通常,词法规则的规则名以大写字母命名,而语法规则的规则名以小写字母开始。

Expr 语法

具体到我们的 Expr 语法,定义的语法 Expr.g4 如下:

grammar Expr;

prog
    : stat+ ;

stat
    : exprStat
    | assignStat
    ;

exprStat
    : expr SEMI
    ;

assignStat
    : ID EQ expr SEMI
    ;

expr
    : expr op = (MUL | DIV ) expr   # MulDivExpr
    | expr op = ( ADD | SUB ) expr   # AddSubExpr
    | INT                       # IntExpr
    | ID                        # IdExpr
    | LPAREN expr RPAREN        # ParenExpr
    ;

MUL     : '*' ;
DIV     : '/' ;
ADD     : '+' ;
SUB     : '-' ;
LPAREN  : '(' ;
RPAREN  : ')' ;

ID      : LETTER (LETTER | DIGIT)*  ;
INT     : [0-9]+ ;
EQ      : '=' ;
SEMI    : ';' ;
COMMENT : '//' ~[\r\n]* '\r'? '\n'? -> channel(HIDDEN);
WS      : [ \r\n\t]+ -> channel(HIDDEN);

fragment
LETTER  : [a-zA-Z] ;
fragment
DIGIT   : [0-9] ;

可以看到,语法定义是采用自顶向下的设计方法,我们的 Expr 代码以规则prog作为根规则,prog由多条语句stat组成;而语句stat可以是表达式语句exprState活着赋值语句assignState;依次向下,到最后一层语法规则表达式expr,表达式可以是由表达式组成的加减乘除运算,或者是整数INT、变量ID,注意expr规则使用了递归的表达,即在expr规则的定义中引用了expr,这也是 ANTLR v4 的一个特点。 最后这里定义的词法规则包含了加减乘除、括号、变量、整数、赋值、注释和空白等规则;注意其中的注释(COMMENT)和空白(WS)规则定义的channel(HIDDEN),这是标记我们的语法解析需要忽略注释和空白。

有了语法定义Expr.ge,就可以生成我们需要的解析器源码了,这里采用 antlr4ts,在 package.json 中添加 script:

"scripts": {
  "antlr4ts": "antlr4ts -visitor Expr.g4 -o src/parser"
},
"dependencies": {
  "antlr4ts": "^0.4.1-alpha.0"
}
"devDependencies": {
  "antlr4ts-cli": "^0.4.0-alpha.4",
  "typescript": "^2.5.3",
},

执行 npm run antlr4ts,就可以在src/parser目录看到生成的 Expr 解析器的 TypeScript 源代码了。

五、 Expr 语言解释器

有了 Expr 语言的解析器,我们就可以利用解析器来实现我们的 Expr 语言解释器,具体需要达到的目的即,输入 Expr 语言代码,最后能打印出执行结果。

代码和语法树

具体如何利用 ANTLR 来解释执行输入的 Expr 代码呢,我们先看下对以下输入代码,ANTLR 生成的 Token 序列和语法树是怎样的?

a = 1;
b = a + 1;
b;

词法解析得到的 Token 序列如下图所示,共解析为 22 个 Token,每个 Token 包含了 Token 的序号,Token 的文本,Token 的类型;如序号为 0 的 Token,文本为'a',类型为'ID',即匹配了我们上面在Expr.g4的词法规则ID

expr-tokens

语法树结构如下图所示,树中的节点都对应了在Expr.g4中定义的语法规则或词法规则,有一点需要注意的是,语法树中所有的叶子节点都对应到词法规则或者字符常量,这也是我们在设计Expr.g4中自顶向下的设计方法一样的。

expr-ast-1.png

可以看到,跟节点为prog规则节点,它的子节点为三个语句stat节点,其中前两个子节点为赋值语句assignStat节点,最后一个的子节点为表达式语句节点statExpr。根据在第一部分的定义,针对这段代码,我们需要识别出代码中的表达式语句并打印该表达式的值。具体到这个例子中,这段输入代码中只用一个表达式语句,其中的表达式为变量 b,为了打印 b 的值,我们需要通过解释前两条语句,计算出 b 的值(这里给出舍得,变量的引用必须在变量的定义之后)。所以,整体的思路即我们需要按顺序解释每条语句,并记住语句解释过程中出现的变量和其值,在后续语句的解释过程中,如果遇到变量的引用,需要查找该变量的值。

使用 Visitor 来访问语法树

为了实现上述的解释过程,我们需要区遍历访问解析器解析出来的语法树,ANTLR 提供了两种机制来访问生成的语法树:Listener 和 Visitor,使用 Listener 模式来访问语法树时,ANTLR 内部的ParserTreeWalker在遍历语法树的节点过程中,在遇到不同的节点中,会调用提供的 listener 的不同方法;而使用 Visitor 模式时,visitor 需要自己来指定如果访问特定类型的节点,ANTLR 生成的解析器源码中包含了默认的 Visitor 基类/接口ExprVisitor.ts,在使用过程中,只需要对感兴趣的节点实现 visit 方法即可,比如我们需要访问到exprStat节点,只需要实现如下接口:

export interface ExprVisitor<Result> extends ParseTreeVisitor<Result> {
  ...

  /**
   * Visit a parse tree produced by `ExprParser.exprStat`.
   * @param ctx the parse tree
   * @return the visitor result
   */
  visitExprStat?: (ctx: ExprStatContext) => Result;

  ...
}

介绍完了如果使用 Visitor 来访问语法树中的节点后,我们来实现 Expr 解释器需要的 Visitor:ExprEvalVisitor

上面提到在访问语法树过程中,我们需要记录遇到的变量和其值、和最后的打印结果,我们使用 Visitor 内部变量来保存这些中间值:

class ExprEvalVisitor extends AbstractParseTreeVisitor<number>
  implements ExprVisitor<number> {

  // 保存执行输出结果
  private buffers: string[] = [];

  // 保存变量
  private memory: { [id: string]: number } = {};

}

我们需要访问语法树中的哪些节点呢?首先,为了最后的结果,对表达式语句exprState的访问是最重要的,我们访问表达式语句中的表达式得到表达式的值,并将值打印到执行结果中。由于表达式语句是由表达式加分号组成,我们需要继续访问表达式得到这条语句的值,而对于分号,则忽略:

class ExprEvalVisitor extends AbstractParseTreeVisitor<number>
  implements ExprVisitor<number> {

  // 保存执行输出结果
  private buffers: string[] = [];

  // 保存变量
  private memory: { [id: string]: number } = {};

  // 访问表达式语句
  visitExprStat(ctx: ExprStatContext) {
    const val = this.visit(ctx.expr());
    this.buffers.push(`${val}`);
    return val;
  }
}

上面递归的访问了表达式语句中的表达式节点,那表达式阶段的访问方法是怎样的?回到我们的语法定义 Expr.g4,表达式是由 5 条分支组成的,对于不同的分支,处理方法不一样,因此我们对不同的分支使用不同的访问方法。我们在不同的分支后面添加了不同的注释,这些注释生成的解析器中,可以用来区分不同类型的节点,在生成的 Visitor 中,由可以看到不同的接口:

export interface ExprVisitor<Result> extends ParseTreeVisitor<Result> {
  ...

  /**
	 * Visit a parse tree produced by the `MulDivExpr`
	 * labeled alternative in `ExprParser.expr`.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	visitMulDivExpr?: (ctx: MulDivExprContext) => Result;

	/**
	 * Visit a parse tree produced by the `IdExpr`
	 * labeled alternative in `ExprParser.expr`.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	visitIdExpr?: (ctx: IdExprContext) => Result;

	/**
	 * Visit a parse tree produced by the `IntExpr`
	 * labeled alternative in `ExprParser.expr`.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	visitIntExpr?: (ctx: IntExprContext) => Result;

	/**
	 * Visit a parse tree produced by the `ParenExpr`
	 * labeled alternative in `ExprParser.expr`.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	visitParenExpr?: (ctx: ParenExprContext) => Result;

	/**
	 * Visit a parse tree produced by the `AddSubExpr`
	 * labeled alternative in `ExprParser.expr`.
	 * @param ctx the parse tree
	 * @return the visitor result
	 */
	visitAddSubExpr?: (ctx: AddSubExprContext) => Result;

	...
}

所以,在我们的ExprEvalVisitor中,我们通过实现不同的接口来访问不同的表达式分支,对于AddSubExpr分支,实现的访问方法如下:

visitAddSubExpr(ctx: AddSubExprContext) {
  const left = this.visit(ctx.expr(0));
  const right = this.visit(ctx.expr(1));
  const op = ctx._op;

  if (op.type === ExprParser.ADD) {
    return left + right;
  }
  return left - right;
}

对于MulDivExpr,访问方法相同。对于IntExpr分支,由于其子节点只有INT节点,我们只需要解析出其中的整数即可:

visitIntExpr(ctx: IntExprContext) {
  return parseInt(ctx.INT().text, 10);
}

对于IdExpr分支,其子节点只有变量ID,这个时候就需要在我们的保存的变量中去查找这个变量,并取出它的值:

visitIdExpr(ctx: IdExprContext) {
  const id = ctx.ID().text;
  if (this.memory[id] !== undefined) {
    return this.memory[id];
  }
  return 0;
}

对于最后一个分支ParenExpr,它的访问方法很简单,只需要访问到括号内的表达式即可:

visitParenExpr(ctx: ParenExprContext) {
  return this.visit(ctx.expr());
}

到这里,你可以发现了,我们上述的访问方法加起来,我们只有从 memory 读取变量的过程,没有想 memory 写入变量的过程,这就需要我们访问赋值表达式assignExpr节点了:对于赋值表达式,需要识别出等号左边的变量名,和等号右边的表达式,最后将变量名和右边表达式的值保存到 memory 中:

visitAssignStat(ctx: AssignStatContext) {
  const id = ctx.ID().text;
  const val = this.visit(ctx.expr());
  this.memory[id] = val;
  return val;
}

解释执行 Expr 语言

至此,我们的 VisitorExprEvalVisitor已经准备好了,我们只需要在对指定的输入代码,使用 visitor 来访问解析出来的语法树,就可以实现 Expr 代码的解释执行了:

// Expr代码解释执行函数
// 输入code
// 返回执行结果
function execute(code: string): string {
  const input = new ANTLRInputStream(code);
  const lexer = new ExprLexer(input);
  const tokens = new CommonTokenStream(lexer);
  const parser = new ExprParser(tokens);
  const visitor = new ExprEvalVisitor();

  const prog = parser.prog();
  visitor.visit(prog);

  return visitor.print();
}

六、Expr 代码前缀表达式翻译器

通过前面的介绍,我们已经通过通过 ANTLR 来解释执行 Expr 代码了。结合 ANTLR 的介绍:ANTLR 是用来读取、处理、执行和翻译结构化的文本。那我们能不能用 ANTLR 来翻译输入的 Expr 代码呢?在 Expr 语言中,表达式是我们常见的中缀表达式,我们能将它们翻译成前缀表达式吗?还记得数据结构课程中如果利用出栈、入栈将中缀表达式转换成前缀表达式的吗?不记得么关系,利用 ANTLR 生成的解析器,我们也可以简单的换成转换。

举例,对如下 Expr 代码:

a = 2;
b = 3;
c = a * (b + 2);
c;

我们转换之后的结果如下,我们支队表达式做转换,而对赋值表达式则不做抓换,即代码中出现的表达式都会转换成:

a = 2;
b = 3;
c = * a + b 2;
c;

前缀翻译 Visitor

同样,这里我们使用 Visitor 模式来访问语法树,这次,我们直接 visit 根节点prog,并返回翻译后的代码:

class ExprTranVisitor extends AbstractParseTreeVisitor<string>
  implements ExprVisitor<string> {
  defaultResult() {
    return '';
  }

  visitProg(ctx: ProgContext) {
    let val = '';
    for (let i = 0; i < ctx.childCount; i++) {
      val += this.visit(ctx.stat(i));
    }
    return val;
  }

  ...
}

这里假设我们的 visitor 在 visitor 语句stat的时候,已经返回了翻译的代码,所以visitProg只用简单的拼接每条语句翻译后的代码即可。对于语句,前面提到了,语句我们不做翻译,所以它们的 visit 访问也很简单:对于表达式语句,直接打印翻译后的表达式,并加上分号;对于赋值语句,则只需将等号右边的表达式翻译即可:

visitExprStat(ctx: ExprStatContext) {
  const val = this.visit(ctx.expr());
  return `${val};\n`;
}

visitAssignStat(ctx: AssignStatContext) {
  const id = ctx.ID().text;
  const val = this.visit(ctx.expr());
  return `${id} = ${val};\n`;
}

下面看具体如何翻译各种表达式。对于AddSubExprMulDivExpr的翻译,是整个翻译器的逻辑,即将操作符前置:

visitAddSubExpr(ctx: AddSubExprContext) {
  const left = this.visit(ctx.expr(0));
  const right = this.visit(ctx.expr(1));
  const op = ctx._op;

  if (op.type === ExprParser.ADD) {
    return `+ ${left} ${right}`;
  }
  return `- ${left} ${right}`;
}

visitMulDivExpr(ctx: MulDivExprContext) {
  const left = this.visit(ctx.expr(0));
  const right = this.visit(ctx.expr(1));
  const op = ctx._op;

  if (op.type === ExprParser.MUL) {
    return `* ${left} ${right}`;
  }
  return `/ ${left} ${right}`;
}

由于括号在前缀表达式中是不必须的,所以的ParenExpr的访问,只需要去处括号即可:

visitParenExpr(ctx: ParenExprContext) {
  const val = this.visit(ctx.expr());
  return val;
}

对于其他的节点,不需要更多的处理,只需要返回节点对应的标记的文本即可:

visitIdExpr(ctx: IdExprContext) {
  const parent = ctx.parent;
  const id = ctx.ID().text;
  return id;
}

visitIntExpr(ctx: IntExprContext) {
  const parent = ctx.parent;
  const val = ctx.INT().text;
  return val;
}

执行代码的前缀翻译

至此,我们代码前缀翻译的 Visitor 就准备好了,同样,执行过程也很简单,对输入的代码,解析生成得到语法树,使用ExprTranVisitor反问prog根节点,即可返回翻译后的代码:

function execute(code: string): string {
  const input = new ANTLRInputStream(code);
  const lexer = new ExprLexer(input);
  const tokens = new CommonTokenStream(lexer);
  const parser = new ExprParser(tokens);
  const visitor = new ExprTranVisitor();

  const prog = parser.prog();
  const result = visitor.visit(prog);

  return result;
}

对输入代码:

A * B + C / D ;
A * (B + C) / D ;
A * (B + C / D)	;
(5 - 6) * 7 ;

执行输出为:

+ * A B / C D;
/ * A + B C D;
* A + B / C D;
* - 5 6 7;

七、总结

通过上述的 Expr 语言执行器,相信你已经看到了利用 ANTLR v4,前端工程师也可以在浏览器段做很多语法解析相关的事情。