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

正文

请到「今天看啥」查看全文

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.g4 中定义的语法规则或词法规则，有一点需要注意的是，语法树中所有的叶子节点都对应到词法规则或者字符常量，这也是我们在设计 Expr.g4 中自顶向下的设计方法一样的。

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

使用Visitor来访问语法树

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

请到「今天看啥」查看全文