暂无图片
暂无图片
暂无图片
暂无图片
暂无图片

ISOGQL 的 Antlr4 使用及优化

TuGraph 2023-08-10
1732

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 ExprLexer
        from 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






              END


              往期回顾
              → 权威报告:蚂蚁集团TuGraph跻身中国图数据库市场“领导者”象限
              → 蚂蚁图计算平台开源业内首个工业级流图计算引擎
              → 洪春涛:图数据库厂商的新机遇在深海中等待


              ▼ 关注蚂蚁图计算技术,了解最新资讯


              文章转载自TuGraph,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

              评论