ANTLR4 Grammatik Leistung sehr schlecht

Question

Angesichts der Grammatik unten, sehe ich sehr schlechte Leistung beim Parsen längerer Strings, in der Größenordnung von Sekunden. (Dies gilt sowohl für Python als auch für Go-Implementierungen.) Gibt es etwas in dieser Grammatik, das das verursacht?

Beispiel Ausgabe:

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)) 

Dies ist auf Python .. obwohl ich herausragende Leistung nicht erwarten würde ich für jeden Eingang unter einer Sekunde erwarten. Was mache ich falsch?

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

Sie können immer versuchen, mit SLL(*) ersten und nur zu analysieren, wenn das fehlschlägt Sie es mit LL(*) analysieren müssen (dies ist die Standardeinstellung).

Siehe this Ticket auf ANTLR GitHub für weitere Erläuterungen und here ist eine Implementierung, die diese Strategie verwendet.

Diese Methode spart Ihnen (viel) Zeit beim syntaktischen Korrigieren der Eingabe.

Answer 2

Scheint wie diese Leistung aufgrund der linken Rekursion in der Addition/Multiplikation usw. Operatoren verwendet wird. Das Umschreiben dieser zu binären Regeln führt stattdessen zu einer sofortigen Leistung. (siehe unten)

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 
      ;