语法解析器 (Parser) 语法解析器通常作为编译器或解释器出现。它的作用是进行语法检查,并构建由输入单词(Token)组成的数据结构(即抽象语法树)。语法解析器通常使用词法分析器(Lexer)从输入字符流中分离出一个个的单词(Token),并将单词(Token)流作为其输入。实际开发中,语法解析器可以手工编写,也可以使用工具自动生成。
词法分析器 (Lexer) 词法分析是指在计算机科学中,将字符序列转换为单词(Token)的过程。执行词法分析的程序便称为词法分析
antlr4
ANTLR(另一种语言识别工具)是一种强大的解析器生成器,用于读取,处理,执行或翻译结构化文本或二进制文件。它被广泛用于构建语言,工具和框架。ANTLR 从语法上生成了一个解析器,可以构建和遍历解析树。” ANTLR 支持许多语言作为目标,这意味着它可以生成 Java,C#和其他语言的解析器。对于这个项目,可以使用 ANTLR4TS,它是 ANTLR 的 Node.js 版本,可以在 TypeScript 中生成一个词法分析器和解析器。
安装
- 安装Java 1.7及以上
- 下载
$ cd /usr/local/lib
$ curl -O https://www.antlr.org/download/antlr-4.9-complete.jar
或者用链接https://www.antlr.org/download.html 下载到 /usr/local/lib.
- 添加 antlr-4.9-complete.jar 到CLASSPATH:
$ export CLASSPATH=".:/usr/local/lib/antlr-4.9-complete.jar:$CLASSPATH"
也可以加到 .bash_profile 或者启动脚本里。
- 创建ANTLR Tool, 和 TestRig的别名
$ alias antlr4='java -Xmx500M -cp "/usr/local/lib/antlr-4.9-complete.jar:$CLASSPATH" org.antlr.v4.Tool'
$ alias grun='java -Xmx500M -cp "/usr/local/lib/antlr-4.9-complete.jar:$CLASSPATH" org.antlr.v4.gui.TestRig'
使用
编写语法规则
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];
ANTLR4 的语法规则分为词法(Lexer)规则和语法(Parser)规则,词法规则定义了怎么将代码字符串序列转换成标记序列;语法规则定义怎么将标记序列转换成语法树。通常,词法规则的规则名以大写字母命名,而语法规则的规则名以小写字母开始。主流语言的 ANTLR4 语法定义可以到语法仓库中找到。
生成相关文件
// Java中使用
$ antlr4 Expr.g4
$ javac Expr*.java
// javascript
antlr4 -Dlanguage=JavaScript Expr.g4
运行一下
$ grun Expr prog -tree -gui
(Now enter something like the string below)
a = 1;
b = a + 1;
b;
(now,do:)
^D
- 使用 ANTLR 4 生成目标编程语言代码的词法分析器(Lexer)和语法分析器(Parser),支持的编程语言有:Java、JavaScript、Python、C 和 C++ 等;
- 遍历 AST(Abstract Syntax Tree 抽象语法树),ANTLR 4 支持两种模式:访问者模式(Visitor)和监听器模式(Listener)
遍历模式
- Listener (观察者模式,通过结点监听,触发处理方法)
1) Listener模式会由ANTLR提供的walker对象自动调用;在遇到不同的节点中,会调用提供的listener的不同方法
2)Listener模式没有返回值,只能用一些变量来存储中间值
3)Listener模式是对整棵树的遍历
- Visitor (访问者模式,主动遍历)
1)visitor需要自己来指定访问特定类型的节点,在使用过程中,只需要对感兴趣的节点实现visit方法即可
2)visitor模式可以自定义返回值
3)visitor模式是对指定节点的访问
使用antlr4默认生成的是listener模式的解析器,如果要生成visitor类型的,需要加-vistor参数
在js中的使用
;
import Lexer from './ExprLexer.js');
import Parser from './ExprParser.js';
import Listener from './ExprListener.js';
const input = `
a = 1;
b = a + 1;
b;
`
const chars = new antlr4.InputStream(input);
const lexer = new Lexer(chars);
const tokens = new antlr4.CommonTokenStream(lexer);
const parser = new
使用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语言
至此,我们的Visitor
ExprEvalVisitor
已经准备好了,我们只需要在对指定的输入代码,使用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`;
}
下面看具体如何翻译各种表达式。对于
AddSubExpr
和
MulDivExpr
的翻译,是整个翻译器的逻辑,即将操作符前置:
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;
tree-sitter
Tree-sitter是一个解析器生成器工具,也是一个增量解析库。它可以为源文件构建一个具体的语法树,并在编辑源文件时有效地更新语法树。
Tree-sitter目标是:
- 足以解析任何编程语言
- 速度足以解析文本编辑器中的每一次击键
- 足够健壮,即使出现语法错误也能提供有用的结果
- 无依赖性,这样运行时库(用纯C编写)就可以嵌入到任何应用程序中
使用
npm install tree-sitter
npm install tree-sitter-javascript
const Parser = require('tree-sitter');const JavaScript = require('tree-sitter-javascript');const parser = new Parser();parser.setLanguage(JavaScript);
const sourceCode = 'let x = 1; console.log(x);';const tree = parser.parse(sourceCode);
console.log(tree.rootNode.toString());
// (program
// (lexical_declaration
// (variable_declarator (identifier) (number)))
// (expression_statement
// (call_expression
// (member_expression (identifier) (property_identifier))
// (arguments (identifier)))))
const callExpression = tree.rootNode.child(1).firstChild;
console.log(callExpression);
// { type: 'call_expression',
// startPosition: {row: 0, column: 16},
// endPosition: {row: 0, column: 30},
// startIndex: 0,
// endIndex: 30 }
参考
https://zhuanlan.zhihu.com/p/31748014
http://codeinchinese.com/%E5%9C%883/%E5%9C%883.html
https://tree-sitter.github.io/tree-sitter/
https://github.com/tree-sitter/node-tree-sitter