ANTLR4语法性能非常差

Question

鉴于下面的语法，在解析较长的字符串时，我看到性能很差，大约在几秒钟内。 （在Python和Go实现上都有这个）在这个语法中是否有什么导致了这种情况？

输出示例：

0.000061s LEXING "hello world" 
0.014349s PARSING "hello world" 
0.000052s LEXING 5 + 10 
0.015384s PARSING 5 + 10 
0.000061s LEXING FIRST_WORD(WORD_SLICE(contact.blerg, 2, 4)) 
0.634113s PARSING FIRST_WORD(WORD_SLICE(contact.blerg, 2, 4)) 
0.000095s LEXING (DATEDIF(DATEVALUE("01-01-1970"), date.now, "D") * 24 * 60 * 60) + ((((HOUR(date.now)+7) * 60) + MINUTE(date.now)) * 60)) 
1.552758s PARSING (DATEDIF(DATEVALUE("01-01-1970"), date.now, "D") * 24 * 60 * 60) + ((((HOUR(date.now)+7) * 60) + MINUTE(date.now)) * 60)) 

这是Python的..虽然我不指望炽热的表现我希望亚秒级的任何输入。我究竟做错了什么？

grammar Excellent; 

parse 
    : expr EOF 
    ; 

expr 
    : atom             # expAtom 
    | concatenationExpr          # expConcatenation 
    | equalityExpr           # expEquality 
    | comparisonExpr           # expComparison 
    | additionExpr           # expAddition 
    | multiplicationExpr          # expMultiplication 
    | exponentExpr           # expExponent 
    | unaryExpr            # expUnary 
    ; 

path 
    : NAME (step)* 
    ; 

step 
    : LBRAC expr RBRAC 
    | PATHSEP NAME 
    | PATHSEP NUMBER 
    ; 

parameters 
    : expr (COMMA expr)*          # functionParameters 
    ; 

concatenationExpr 
    : atom (AMP concatenationExpr)?       # concatenation 
    ; 

equalityExpr 
    : comparisonExpr op=(EQ|NE) comparisonExpr    # equality 
    ; 

comparisonExpr 
    : additionExpr (op=(LT|GT|LTE|GTE) additionExpr)?   # comparison 
    ; 

additionExpr 
    : multiplicationExpr (op=(ADD|SUB) multiplicationExpr)* # addition 
    ; 

multiplicationExpr 
    : exponentExpr (op=(MUL|DIV) exponentExpr)*    # multiplication 
    ; 

exponentExpr 
    : unaryExpr (EXP exponentExpr)?       # exponent 
    ; 

unaryExpr 
    : SUB? atom            # negation 
    ; 

funcCall 
    : function=NAME LPAR parameters? RPAR      # functionCall 
    ; 

funcPath 
    : function=funcCall (step)*        # functionPath 
    ; 

atom 
    : path             # contextReference 
    | funcCall            # atomFuncCall 
    | funcPath            # atomFuncPath 
    | LITERAL             # stringLiteral 
    | NUMBER             # decimalLiteral 
    | LPAR expr RPAR           # parentheses 
    | TRUE             # true 
    | FALSE             # false 
    ; 

NUMBER 
    : DIGITS ('.' DIGITS?)? 
    ; 

fragment 
DIGITS 
    : ('0'..'9')+ 
    ; 

TRUE 
    : [Tt][Rr][Uu][Ee] 
    ; 

FALSE 
    : [Ff][Aa][Ll][Ss][Ee] 
    ; 

PATHSEP 
     :'.'; 
LPAR 
     :'('; 
RPAR 
     :')'; 
LBRAC 
     :'['; 
RBRAC 
     :']'; 
SUB 
     :'-'; 
ADD 
     :'+'; 
MUL 
     :'*'; 
DIV 
     :'/'; 
COMMA 
     :','; 
LT 
     :'<'; 
GT 
     :'>'; 
EQ 
     :'='; 
NE 
     :'!='; 
LTE 
     :'<='; 
GTE 
     :'>='; 
QUOT 
     :'"'; 
EXP 
     : '^'; 
AMP 
     : '&'; 

LITERAL 
    : '"' ~'"'* '"' 
    ; 

Whitespace 
    : (' '|'\t'|'\n'|'\r')+ ->skip 
    ; 

NAME 
    : NAME_START_CHARS NAME_CHARS* 
    ; 

fragment 
NAME_START_CHARS 
    : 'A'..'Z' 
    | '_' 
    | 'a'..'z' 
    | '\u00C0'..'\u00D6' 
    | '\u00D8'..'\u00F6' 
    | '\u00F8'..'\u02FF' 
    | '\u0370'..'\u037D' 
    | '\u037F'..'\u1FFF' 
    | '\u200C'..'\u200D' 
    | '\u2070'..'\u218F' 
    | '\u2C00'..'\u2FEF' 
    | '\u3001'..'\uD7FF' 
    | '\uF900'..'\uFDCF' 
    | '\uFDF0'..'\uFFFD' 
    ; 

fragment 
NAME_CHARS 
    : NAME_START_CHARS 
    | '0'..'9' 
    | '\u00B7' | '\u0300'..'\u036F' 
    | '\u203F'..'\u2040' 
    ; 

ERRROR_CHAR 
    : . 
    ; 

Answer 1

你可以总是试图用SLL(*)第一解析和仅如果失败，你需要LL(*)解析它（这是默认值）。

请参阅this ANTLR的GitHub上的票证作进一步解释，here是使用此策略的实施。

此方法将为您节省（大量）时间解析语法上的输入。

Answer 2

看起来像这样的性能是由于在运算符的加法/乘法等中使用了左递归。将这些重写为二进制规则会产生即时性能。 （见下文）

grammar Excellent; 

COMMA  : ','; 
LPAREN  : '('; 
RPAREN  : ')'; 
LBRACK  : '['; 
RBRACK  : ']'; 

DOT  : '.'; 

PLUS  : '+'; 
MINUS  : '-'; 
TIMES  : '*'; 
DIVIDE  : '/'; 
EXPONENT : '^'; 

EQ   : '='; 
NEQ  : '!='; 

LTE  : '<='; 
LT   : '<'; 
GTE  : '>='; 
GT   : '>'; 

AMPERSAND : '&'; 

DECIMAL : [0-9]+('.'[0-9]+)?; 
STRING  : '"' (~["] | '""')* '"'; 

TRUE  : [Tt][Rr][Uu][Ee]; 
FALSE  : [Ff][Aa][Ll][Ss][Ee]; 

NAME  : [a-zA-Z][a-zA-Z0-9_.]*; // variable names, e.g. contact.name or function names, e.g. SUM 

WS   : [ \t\n\r]+ -> skip;  // ignore whitespace 

ERROR  : . ; 

parse  : expression EOF; 

atom  : fnname LPAREN parameters? RPAREN    # functionCall 
      | atom DOT atom        # dotLookup 
      | atom LBRACK expression RBRACK    # arrayLookup 
      | NAME           # contextReference 
      | STRING          # stringLiteral 
      | DECIMAL          # decimalLiteral 
      | TRUE           # true 
      | FALSE          # false 
      ; 

expression : atom           # atomReference 
      | MINUS expression        # negation 
      | expression EXPONENT expression    # exponentExpression 
      | expression (TIMES | DIVIDE) expression  # multiplicationOrDivisionExpression 
      | expression (PLUS | MINUS) expression   # additionOrSubtractionExpression 
      | expression (LTE | LT | GTE | GT) expression # comparisonExpression 
      | expression (EQ | NEQ) expression    # equalityExpression 
      | expression AMPERSAND expression    # concatenation 
      | LPAREN expression RPAREN      # parentheses 
      ; 

fnname  : NAME 
      | TRUE 
      | FALSE 
      ; 

parameters : expression (COMMA expression)*    # functionParameters 
      ;