Antlr4是一款备受欢迎的语法分析器生成工具,能够根据语法规则快速生成自定义解析器。其支持LL(*)解析,拥有更强大的错误处理能力和更快的解析速度。不仅如此,Antlr4还支持Java、Python、C++、JavaScript、Go等10种目标语言,广泛应用于多种开发语言生态中。简单易用的API和文档使得开发人员能够快速上手。无论是编程语言、数据格式、编译器还是解释器等领域,Antlr4都发挥着重要作用。著名的开源项目如Apache Spark、Eclipse IDE和MongoDB等都使用了Antlr4进行语法分析。
Antlr4 示例
下面是一个基本的示例,展示如何使用ANTLR4来解析一个简单的表达式。
首先我们定义一个ANTLR4的语法文件,用于定义输入的语法规则。文件定义了一个简单的表达式语法规则。表达式由一个或多个项组成,每个项之间使用操作符连接,项可以是整数或者一个带括号的表达式。
grammar Expr;// 定义表达式的语法规则expr: term (op term)* ;term: INT | '(' expr ')' ;op: '+' | '-' | '*' | '/' ;// 定义整数类型INT: [0-9]+ ;WS: [ \t\n\r]+ -> skip ;
然后我们可以使用ANTLR4命令行工具生成相应语言的解析器,例如可以使用下述命令生成一个Python3版本的解析器代码。
antlr4 -Dlanguage=Python3 Expr.g4
此时,我们就可以在Python中使用生成的解析器处理表达式。例如下述Python程序,可以输出[2, '*', 3, '+', 4],表示"2 * (3 + 4)"被解析后的表达式树。
from antlr4 import *from ExprLexer import ExprLexerfrom ExprParser import ExprParser# 定义一个Visitor,用于处理表达式class ExprVisitor(ParseTreeVisitor):# 处理表达式def visitExpr(self, ctx: ExprParser.ExprContext):return self.visitChildren(ctx)# 处理项def visitTerm(self, ctx: ExprParser.TermContext):if ctx.INT():return int(ctx.INT().getText())else:return self.visit(ctx.expr())# 处理操作符def visitOp(self, ctx: ExprParser.OpContext):return ctx.getText()# 处理子元素def visitChildren(self, node):results = []for child in node.getChildren():result = self.visit(child)if result is not None:results.append(result)return results# 输入表达式input_expr = "2 * (3 + 4)"# 创建词法解析器和语法解析器lexer = ExprLexer(InputStream(input_expr))tokens = CommonTokenStream(lexer)parser = ExprParser(tokens)# 解析表达式tree = parser.expr()# 处理表达式visitor = ExprVisitor()result = visitor.visit(tree)print(result)
这个示例只是展示了ANTLR4的简单用法,ANTLR4还可以处理更复杂的语法规则,并且可以使用Listener或者Visitor模式来处理解析树。如果想要了解更多关于ANTLR4的使用,可以参考官方文档和示例。
我们做了哪些优化工作
目前已有的一些 ISO GQL 语法文件(譬如 https://github.com/damianw27/gql/blob/main/grammar/src/versions/latest/antlr/GqlParser.g4)直接从 ISO GQL 语法规范手册中拷贝BNF语法至相应的语法文件中,虽然这类方法可以保证在语法层面上和规范一致,但是在实际使用中,存在 Antlr4 语法树层级过深等问题,严重影响解析性能。因此,TuGraph 团队在语法规范手册的基础上,结合 Antlr4 的特点,对部分语法规则进行了重构,通过减少语法树层级、减少解析过程中“二义性”出现的次数等优化手段,大幅提升了解析速度。
出于使语法更清晰的目的,语法手册的范围通常都非常广泛,这意味着其中的语法可能存在歧义,能够以多种方式匹配相同的输入文本。譬如在表达式中可能会存在很多“二义性”的结构,一条表达式可能多种“正确”的解析路径,从而导致 Antlr4 解析速度大幅下降,影响整体性能。
因此,在这版本的语法文件中,在保证表达式语法表达能力不下降的前提下,我们在 Antlr4 语法文件中对表达式的语法定义结构进行了大量的重构工作,从而尽量避免表达式解析过程的歧义问题,提高了 Antlr4 解析 ISO GQL 语句的性能。在内部业务场景下,平均可以提升解析速度数十倍,在一些复杂查询语句场景下,甚至可以提升至上百倍。
以下述查询语句为例:
MATCH (p:Person)-[r:IS_FRIENDS_WITH]->(friend:Person)WHERE EXISTS (MATCH (p)-[:WORKS_FOR]->(:Company {name: "GQL, Inc."}))RETURN p, r, friend
下面的代码片段为直接按照BNF格式语法生成的Antlr4语法文件中表达式的部分定义。
valueExpr: commonValueExpr | booleanValueExpr;commonValueExpr:numericValueExpr| stringValueExpr| dateTimeValueExpr| durationValueExpr| listValueExpr| recordValueExpr| pathValueExpr| refValueExpr| commonValuePropertiesGroup;numericValueExpr:term| term PLUS numericValueExpr| term MINUS numericValueExpr;term: factor | factor ASTERISK term | factor SOLIDUS term;factor: SIGN? numericPrimary;numericPrimary: valueExprPrimary | numericValueFunction;stringValueExpr: charStringValueExpr | byteStringValueExpr;charStringFactor: charStringPrimary;charStringPrimary: valueExprPrimary | stringValueFunction;valueExprPrimary:parenthesizedValueExpr| nonParenthesizedValueExprPrimary;
对于查询语句中的"GQL, Inc."部分,上述定义可能存在多种可能的匹配路径:
valueExpr-commonValueExpr-numericValueExpr-term-factor-numericPrimary-valueExprPrimary-nonParenthesizedValueExprPrimary- ... ... - characterStringLiteral
valueExpr-commonValueExpr-stringValueExpr-charStringValueExpr-charStringFactor-charStringPrimary-valueExprPrimary-nonParenthesizedValueExprPrimary- ... ... - characterStringLiteral
valueExpr-commonValueExpr-dateTimeValueExpr- ... ...
多种可能匹配路径的存在,会给Antlr4在解析过程中带来额外的开销,从而导致解析速度下降。此外从语义的角度来看,第一种的匹配路径本身也不应该存在,毕竟"GQL, Inc."不应该被认为是一个数值量。上述这类问题,也会影响到RETURN p, r, friend中的变量名的解析,最终导致整个语句解析缓慢。
而在改写之后的语法文件中,相应的语法定义如下:
expression: NOT expression| lhs = expression AND rhs = expression| lhs = expression XOR rhs = expression| lhs = expression OR rhs = expression| expressionPredicate;expressionPredicate: expressionPredicate IS NOT? truthValue| lhs = expressionPredicate compOp rhs = expressionPredicate| ...| expressionAtom;expressionAtom: LEFT_PAREN expression RIGHT_PAREN| ...| unsignedLiteral| ...;
我们通过重构语法结构,尽可能降低语法树的层级和减少表达式解析过程的歧义问题。对于查询语句中的"GQL, Inc."部分,最终有且仅有一种匹配路径:expression - expressionPredicate -expressionAtom - unsignedLiteral - generalLiteral - characterStringLiteral。最终z对于该查询语句,Antlr4解析耗时从 ~6000ms 降低至 ~90ms(Python3 runtime),性能大幅提升。
👉 GitHub代码仓库:https://github.com/TuGraph-family/gql-grammar

欢迎关注 TuGraph 代码仓库
https://github.com/tugraph-family/tugraph-db
https://github.com/tugraph-family/tugraph-analytics




