2016-07-10 21 views
2

は、例えばを解析ANTL4のパフォーマンスにいくつかの議論がありました:ANTLR4パフォーマンスの問題

とオープンバグレポートがあります:

ANTLR4のパフォーマンスを向上させるために2段階戦略を使用することが求められています。これを行うには、最初にSLLモードでパーサーを呼び出し、遅いLLモードが使用された場合にのみ失敗します。

これが問題に994で使用されているような小さな文法のためにうまく動作:

grammar expr; 

expr: ID 
    | 'not' expr 
    | expr 'and' expr 
    | expr 'or' expr 
    | expr 'between' expr 'and' expr 
    ; 

ID: [a-zA-Z_][a-zA-Z_0-9]*; 
WS: [ \t\n\r\f]+ -> skip; 
ERROR: .; 

が、文法が少し複雑かつ曖昧取得する場合:2つの段階戦略を使用して

/** 
* see https://github.com/antlr/antlr4/issues/994 
*/ 
grammar numexpr; 

numexpr: if_statement EOF; 

if_statement: 
    if_part (else_part) ? 'endif'; 

if_part: 
    'if' expr statement_list| 
    'if' expr; 

else_part: 
    'else' statement_list | 
    'else'; 

statement_list: 
    statement +; 


statement: if_statement; 

expr: ID 
    | VALUE 
    | 'not' expr 
    | expr '=' expr 
    | expr 'and' expr 
    | expr 'or' expr 
    | expr 'between' expr 'and' expr 
    ; 

VALUE: [0-9]+; 
ID: [a-zA-Z_][a-zA-Z_0-9]*; 
WS: [ \t\n\r\f]+ -> skip; 
ERROR: .; 

は」doesnのもう仕事はありません。 タイミング結果は:

2 27 msecs 0,2 
    3 95 msecs 3,5 
    4 99 msecs 1,0 
    5 64 msecs 0,6 
    6 87 msecs 1,4 
    7 181 msecs 2,1 
    8 350 msecs 1,9 
    9 822 msecs 2,3 
10 2912 msecs 3,5 
11 7134 msecs 2,4 
12 21420 msecs 3,0 
ratio: 2,01 

上のいくつかの作業が必要である入力

if Value=0 and not Value0=0 and not Value1=1 endif. 

始まるそれは追加される各「とvaluex = X」という表現部分の倍以上の時間を要しますSLLに適合する文法。

これはどのように行われますか?

関連の質問をします。だから私は

if (mode.equals(PredictionMode.LL_EXACT_AMBIG_DETECTION)) { 
    parserHolder.parser.addErrorListener(new DiagnosticErrorListener()); 
} 

を追加しにdoTestParserラインを変更した場合:

doTestParser(parserHolder, PredictionMode.LL_EXACT_AMBIG_DETECTION, PredictionMode.LL); 

私はまた、任意のあいまいさのラインを取得するだけではありません:

if Value=0 and not Value0=0 and not Value1=1 endif 
line 1:20 reportAttemptingFullContext d=6 (expr), input='andnotValue0' 
line 1:12 reportContextSensitivity d=6 (expr), input='and' 
line 1:37 reportAttemptingFullContext d=6 (expr), input='andnotValue1' 
line 1:29 reportContextSensitivity d=6 (expr), input='and' 

をすることをJUnitのテストの下に見つけてください。問題を示しています。それは、2つのクラスから構成 -

  • https://github.com/antlr/antlr4/issues/1232
  • JUnitのテストケース

    package com.bitplan.ruleparser; 
    
    import java.io.IOException; 
    
    import org.antlr.v4.runtime.ANTLRInputStream; 
    import org.antlr.v4.runtime.CommonTokenStream; 
    import org.antlr.v4.runtime.Lexer; 
    import org.antlr.v4.runtime.ParserRuleContext; 
    import org.junit.Test; 
    
    import com.bitplan.expr.exprLexer; 
    import com.bitplan.expr.exprParser; 
    import com.bitplan.numexpr.numexprLexer; 
    import com.bitplan.numexpr.numexprParser; 
    
    /** 
    * Test the Issue 994 performance 
    * 
    * @author wf 
    * 
    */ 
    public class TestIssue994 extends TestTwoPhaseParser { 
    
        public static class ExprParserHolderFactory extends ParserHolderFactory { 
    
        @Override 
        ParserHolder getParserHolder(int index) throws Exception { 
         return new ExprParserHolder(index); 
        } 
    
        } 
    
        /** 
        * 
        * @author wf 
        * 
        */ 
        public static class ExprParserHolder extends ParserHolder { 
    
        public ExprParserHolder(int index) throws IOException { 
         super(index); 
        } 
    
        private exprParser mParser; 
    
        @Override 
        protected org.antlr.v4.runtime.Parser getParser(CommonTokenStream tokens) { 
         mParser = new exprParser(tokens); 
         return mParser; 
        } 
    
        @Override 
        protected Lexer getLexer(ANTLRInputStream in) { 
         return new exprLexer(in); 
        } 
    
        @Override 
        protected ParserRuleContext parse() { 
         return mParser.expr(); 
        } 
    
        @Override 
        protected String getInput(int index) { 
         String andClause = "not X0"; 
         for (int i = 0; i <= index; i++) { 
         if (i % 4 == 1) { 
          andClause += " or X" + i; 
         } else { 
          andClause += " and not X" + i; 
         } 
         } 
         return andClause; 
        } 
        } 
    
        public static class NumExprParserHolderFactory extends ParserHolderFactory { 
    
        @Override 
        ParserHolder getParserHolder(int index) throws Exception { 
         return new NumExprParserHolder(index); 
        } 
    
        } 
    
        /** 
        * 
        * @author wf 
        * 
        */ 
        public static class NumExprParserHolder extends ParserHolder { 
    
        public NumExprParserHolder(int index) throws IOException { 
         super(index); 
        } 
    
        private numexprParser mParser; 
    
        @Override 
        protected org.antlr.v4.runtime.Parser getParser(CommonTokenStream tokens) { 
         mParser = new numexprParser(tokens); 
         return mParser; 
        } 
    
        @Override 
        protected Lexer getLexer(ANTLRInputStream in) { 
         return new numexprLexer(in); 
        } 
    
        @Override 
        protected ParserRuleContext parse() { 
         return mParser.numexpr(); 
        } 
    
        @Override 
        protected String getInput(int index) { 
         String andClause = "if Value=0 "; 
         for (int i = 0; i <= index; i++) { 
          andClause += " and not Value" + i+"="+i; 
         } 
         andClause+=" endif"; 
         return andClause; 
        } 
        } 
    
    
        /** 
        * see https://github.com/antlr/antlr4/issues/994 
        * 
        * @throws Exception 
        */ 
        @Test 
        public void testIssue994() throws Exception { 
        super.testDuration(new ExprParserHolderFactory(),60); 
        } 
    
        /** 
        * see https://github.com/antlr/antlr4/issues/994 
        * 
        * @throws Exception 
        */ 
        @Test 
        public void testIssue994NumExpr() throws Exception { 
        debug=true; 
        super.testDuration(new NumExprParserHolderFactory(),12); 
        } 
    
    } 
    

    • https://github.com/antlr/antlr4/issues/994
    • とタイミングの問題を示す抽象基底クラスとテストクラスを 基底クラス

      package com.bitplan.ruleparser; 
      
      import static org.junit.Assert.assertTrue; 
      
      import java.io.ByteArrayInputStream; 
      import java.io.IOException; 
      import java.io.InputStream; 
      import java.nio.charset.StandardCharsets; 
      
      import org.antlr.v4.runtime.ANTLRInputStream; 
      import org.antlr.v4.runtime.BailErrorStrategy; 
      import org.antlr.v4.runtime.CommonTokenStream; 
      import org.antlr.v4.runtime.Lexer; 
      import org.antlr.v4.runtime.ParserRuleContext; 
      import org.antlr.v4.runtime.RecognitionException; 
      import org.antlr.v4.runtime.atn.PredictionMode; 
      import org.antlr.v4.runtime.misc.ParseCancellationException; 
      import org.antlr.v4.runtime.Parser; 
      
      /** 
      * 
      * @author wf 
      *   see https://github.com/antlr/antlr4/issues/994 
      */ 
      public abstract class TestTwoPhaseParser { 
          static boolean debug = false; 
      
          public static abstract class ParserHolderFactory { 
          abstract ParserHolder getParserHolder(int index) throws Exception; 
          } 
      
          /** 
          * hold a parser and some input; 
          */ 
          public static abstract class ParserHolder { 
          ANTLRInputStream in; 
          CommonTokenStream tokens; 
          Parser parser; 
          private Lexer lexer; 
          private String input; 
      
          /** 
          * create a parser Holder for the given index 
          * 
          * @param index 
          * @throws IOException 
          */ 
          public ParserHolder(int index) throws IOException { 
           input = getInput(index); 
           init(input); 
          } 
      
          /** 
          * create a parser holder for the given input 
          * 
          * @param input 
          * @throws IOException 
          */ 
          public void init(String input) throws IOException { 
           if (debug) 
           System.out.println(input); 
           in = streamForText(input); 
           lexer = getLexer(in); 
           CommonTokenStream tokens = new CommonTokenStream(lexer); 
           parser = getParser(tokens); 
          } 
      
          /** 
          * get an input of the given index/size 
          * 
          * @param index 
          * @return a string to be tested 
          */ 
          protected abstract String getInput(int index); 
      
          protected abstract Parser getParser(CommonTokenStream tokens); 
      
          protected abstract Lexer getLexer(ANTLRInputStream in); 
      
          protected abstract ParserRuleContext parse(); 
      
          /** 
          * get the ANTLRInputStream for the given text 
          * 
          * @param text 
          * @return 
          * @throws IOException 
          */ 
          public static ANTLRInputStream streamForText(String text) 
           throws IOException { 
           InputStream stream = new ByteArrayInputStream(
            text.getBytes(StandardCharsets.UTF_8)); 
           ANTLRInputStream in = new ANTLRInputStream(stream); 
           return in; 
          } 
          } 
      
          /** 
          * test how long the parsing takes 
          * 
          * @param parserHolderFactory 
          * @throws Exception 
          */ 
          public void testDuration(ParserHolderFactory parserHolderFactory, int max) 
           throws Exception { 
          long prevduration = 0; 
          double ratiosum = 0; 
          int ratiocount = 0; 
          for (int i = 1; i <= max; i++) { 
           long start = System.currentTimeMillis(); 
           ParserHolder parserHolder = parserHolderFactory.getParserHolder(i); 
           doTestParser(parserHolder, PredictionMode.SLL, PredictionMode.LL); 
           long stop = System.currentTimeMillis(); 
           long duration = stop - start; 
           if (duration < 1) 
           duration = 1; 
           if (i >= 2) { 
           double ratio = duration * 1.0/(prevduration * 1.0); 
           System.out.println(String.format("%3d %5d msecs %5.1f", i, duration, 
            ratio)); 
           ratiosum += ratio; 
           ratiocount++; 
           } 
           prevduration = duration; 
          } 
          double averageRatio = ratiosum/ratiocount; 
          System.out.println(String.format("ratio: %3.2f", averageRatio)); 
          assertTrue("Performance issue https://github.com/antlr/antlr4/issues/994", 
           averageRatio < 1.2); 
      
          } 
      
          /** 
          * tes the parser 
          * 
          * @param parserHolder 
          * @param mode 
          * @param fallBackMode 
          * @return 
          * @throws IOException 
          */ 
          protected ParserRuleContext doTestParser(ParserHolder parserHolder, 
           PredictionMode mode, PredictionMode fallBackMode) throws IOException { 
          ParserRuleContext result; 
          try { 
           BailErrorStrategy errorHandler = new BailErrorStrategy(); 
           parserHolder.parser.setErrorHandler(errorHandler); 
           // set PredictionMode 
           parserHolder.parser.getInterpreter().setPredictionMode(mode); 
           result = parserHolder.parse(); 
          } catch (Throwable th) { 
           if (th instanceof ParseCancellationException) { 
           ParseCancellationException pce = (ParseCancellationException) th; 
           if (pce.getCause() instanceof RecognitionException) { 
            RecognitionException re = (RecognitionException) pce.getCause(); 
            ParserRuleContext context = (ParserRuleContext) re.getCtx(); 
            throw context.exception; 
           } 
           } 
           if (fallBackMode != null) { 
           parserHolder.tokens.reset(); 
           parserHolder.parser.reset(); 
           parserHolder.parser.getInterpreter().setPredictionMode(fallBackMode); 
           result = parserHolder.parse(); 
           } else { 
           throw th; 
           } 
          } 
          if (debug) { 
           System.out.println(result.toStringTree()); 
          } 
          return result; 
          } 
      
      } 
      

      デバッグ出力

      if Value=0 and not Value0=0 and not Value1=1 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] Value) = ([52 12 12 28 17 14] 0)) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value0)) = ([52 55 12 28 17 14] 0))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value1)) = ([52 55 28 17 14] 1)))) endif) <EOF>) 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] Value) = ([52 12 12 12 28 17 14] 0)) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value0)) = ([52 55 12 12 28 17 14] 0))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value1)) = ([52 55 12 28 17 14] 1))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value2)) = ([52 55 28 17 14] 2)))) endif) <EOF>) 
          2 27 msecs 0,2 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] ([12 12 12 12 12 28 17 14] Value) = ([52 12 12 12 12 28 17 14] 0)) and ([55 12 12 12 28 17 14] ([12 55 12 12 12 28 17 14] not ([47 12 55 12 12 12 28 17 14] Value0)) = ([52 55 12 12 12 28 17 14] 0))) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value1)) = ([52 55 12 12 28 17 14] 1))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value2)) = ([52 55 12 28 17 14] 2))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value3)) = ([52 55 28 17 14] 3)))) endif) <EOF>) 
          3 96 msecs 3,6 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 and not Value4=4 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] ([12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 28 17 14] Value) = ([52 12 12 12 12 12 28 17 14] 0)) and ([55 12 12 12 12 28 17 14] ([12 55 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 28 17 14] Value0)) = ([52 55 12 12 12 12 28 17 14] 0))) and ([55 12 12 12 28 17 14] ([12 55 12 12 12 28 17 14] not ([47 12 55 12 12 12 28 17 14] Value1)) = ([52 55 12 12 12 28 17 14] 1))) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value2)) = ([52 55 12 12 28 17 14] 2))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value3)) = ([52 55 12 28 17 14] 3))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value4)) = ([52 55 28 17 14] 4)))) endif) <EOF>) 
          4 99 msecs 1,0 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 and not Value4=4 and not Value5=5 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] ([12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 28 17 14] Value) = ([52 12 12 12 12 12 12 28 17 14] 0)) and ([55 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 28 17 14] Value0)) = ([52 55 12 12 12 12 12 28 17 14] 0))) and ([55 12 12 12 12 28 17 14] ([12 55 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 28 17 14] Value1)) = ([52 55 12 12 12 12 28 17 14] 1))) and ([55 12 12 12 28 17 14] ([12 55 12 12 12 28 17 14] not ([47 12 55 12 12 12 28 17 14] Value2)) = ([52 55 12 12 12 28 17 14] 2))) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value3)) = ([52 55 12 12 28 17 14] 3))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value4)) = ([52 55 12 28 17 14] 4))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value5)) = ([52 55 28 17 14] 5)))) endif) <EOF>) 
          5 65 msecs 0,7 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 and not Value4=4 and not Value5=5 and not Value6=6 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] ([12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 28 17 14] Value) = ([52 12 12 12 12 12 12 12 28 17 14] 0)) and ([55 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 28 17 14] Value0)) = ([52 55 12 12 12 12 12 12 28 17 14] 0))) and ([55 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 28 17 14] Value1)) = ([52 55 12 12 12 12 12 28 17 14] 1))) and ([55 12 12 12 12 28 17 14] ([12 55 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 28 17 14] Value2)) = ([52 55 12 12 12 12 28 17 14] 2))) and ([55 12 12 12 28 17 14] ([12 55 12 12 12 28 17 14] not ([47 12 55 12 12 12 28 17 14] Value3)) = ([52 55 12 12 12 28 17 14] 3))) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value4)) = ([52 55 12 12 28 17 14] 4))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value5)) = ([52 55 12 28 17 14] 5))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value6)) = ([52 55 28 17 14] 6)))) endif) <EOF>) 
          6 90 msecs 1,4 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 and not Value4=4 and not Value5=5 and not Value6=6 and not Value7=7 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] ([12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 28 17 14] Value) = ([52 12 12 12 12 12 12 12 12 28 17 14] 0)) and ([55 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 28 17 14] Value0)) = ([52 55 12 12 12 12 12 12 12 28 17 14] 0))) and ([55 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 28 17 14] Value1)) = ([52 55 12 12 12 12 12 12 28 17 14] 1))) and ([55 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 28 17 14] Value2)) = ([52 55 12 12 12 12 12 28 17 14] 2))) and ([55 12 12 12 12 28 17 14] ([12 55 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 28 17 14] Value3)) = ([52 55 12 12 12 12 28 17 14] 3))) and ([55 12 12 12 28 17 14] ([12 55 12 12 12 28 17 14] not ([47 12 55 12 12 12 28 17 14] Value4)) = ([52 55 12 12 12 28 17 14] 4))) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value5)) = ([52 55 12 12 28 17 14] 5))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value6)) = ([52 55 12 28 17 14] 6))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value7)) = ([52 55 28 17 14] 7)))) endif) <EOF>) 
          7 185 msecs 2,1 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 and not Value4=4 and not Value5=5 and not Value6=6 and not Value7=7 and not Value8=8 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] ([12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 12 28 17 14] Value) = ([52 12 12 12 12 12 12 12 12 12 28 17 14] 0)) and ([55 12 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 12 28 17 14] Value0)) = ([52 55 12 12 12 12 12 12 12 12 28 17 14] 0))) and ([55 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 28 17 14] Value1)) = ([52 55 12 12 12 12 12 12 12 28 17 14] 1))) and ([55 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 28 17 14] Value2)) = ([52 55 12 12 12 12 12 12 28 17 14] 2))) and ([55 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 28 17 14] Value3)) = ([52 55 12 12 12 12 12 28 17 14] 3))) and ([55 12 12 12 12 28 17 14] ([12 55 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 28 17 14] Value4)) = ([52 55 12 12 12 12 28 17 14] 4))) and ([55 12 12 12 28 17 14] ([12 55 12 12 12 28 17 14] not ([47 12 55 12 12 12 28 17 14] Value5)) = ([52 55 12 12 12 28 17 14] 5))) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value6)) = ([52 55 12 12 28 17 14] 6))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value7)) = ([52 55 12 28 17 14] 7))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value8)) = ([52 55 28 17 14] 8)))) endif) <EOF>) 
          8 358 msecs 1,9 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 and not Value4=4 and not Value5=5 and not Value6=6 and not Value7=7 and not Value8=8 and not Value9=9 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] ([12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 12 12 28 17 14] Value) = ([52 12 12 12 12 12 12 12 12 12 12 28 17 14] 0)) and ([55 12 12 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 12 12 28 17 14] Value0)) = ([52 55 12 12 12 12 12 12 12 12 12 28 17 14] 0))) and ([55 12 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 12 28 17 14] Value1)) = ([52 55 12 12 12 12 12 12 12 12 28 17 14] 1))) and ([55 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 28 17 14] Value2)) = ([52 55 12 12 12 12 12 12 12 28 17 14] 2))) and ([55 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 28 17 14] Value3)) = ([52 55 12 12 12 12 12 12 28 17 14] 3))) and ([55 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 28 17 14] Value4)) = ([52 55 12 12 12 12 12 28 17 14] 4))) and ([55 12 12 12 12 28 17 14] ([12 55 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 28 17 14] Value5)) = ([52 55 12 12 12 12 28 17 14] 5))) and ([55 12 12 12 28 17 14] ([12 55 12 12 12 28 17 14] not ([47 12 55 12 12 12 28 17 14] Value6)) = ([52 55 12 12 12 28 17 14] 6))) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value7)) = ([52 55 12 12 28 17 14] 7))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value8)) = ([52 55 12 28 17 14] 8))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value9)) = ([52 55 28 17 14] 9)))) endif) <EOF>) 
          9 837 msecs 2,3 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 and not Value4=4 and not Value5=5 and not Value6=6 and not Value7=7 and not Value8=8 and not Value9=9 and not Value10=10 endif 
      ... 
      11 7346 msecs 2,5 
      if Value=0 and not Value0=0 and not Value1=1 and not Value2=2 and not Value3=3 and not Value4=4 and not Value5=5 and not Value6=6 and not Value7=7 and not Value8=8 and not Value9=9 and not Value10=10 and not Value11=11 and not Value12=12 endif 
      ([] ([14] ([17 14] if ([28 17 14] ([12 28 17 14] ([12 12 28 17 14] ([12 12 12 28 17 14] ([12 12 12 12 28 17 14] ([12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 12 12 12 12 28 17 14] ([12 12 12 12 12 12 12 12 12 12 12 12 12 12 28 17 14] Value) = ([52 12 12 12 12 12 12 12 12 12 12 12 12 12 28 17 14] 0)) and ([55 12 12 12 12 12 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 12 12 12 12 12 28 17 14] Value0)) = ([52 55 12 12 12 12 12 12 12 12 12 12 12 12 28 17 14] 0))) and ([55 12 12 12 12 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 12 12 12 12 28 17 14] Value1)) = ([52 55 12 12 12 12 12 12 12 12 12 12 12 28 17 14] 1))) and ([55 12 12 12 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 12 12 12 28 17 14] Value2)) = ([52 55 12 12 12 12 12 12 12 12 12 12 28 17 14] 2))) and ([55 12 12 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 12 12 28 17 14] Value3)) = ([52 55 12 12 12 12 12 12 12 12 12 28 17 14] 3))) and ([55 12 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 12 28 17 14] Value4)) = ([52 55 12 12 12 12 12 12 12 12 28 17 14] 4))) and ([55 12 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 12 28 17 14] Value5)) = ([52 55 12 12 12 12 12 12 12 28 17 14] 5))) and ([55 12 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 12 28 17 14] Value6)) = ([52 55 12 12 12 12 12 12 28 17 14] 6))) and ([55 12 12 12 12 12 28 17 14] ([12 55 12 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 12 28 17 14] Value7)) = ([52 55 12 12 12 12 12 28 17 14] 7))) and ([55 12 12 12 12 28 17 14] ([12 55 12 12 12 12 28 17 14] not ([47 12 55 12 12 12 12 28 17 14] Value8)) = ([52 55 12 12 12 12 28 17 14] 8))) and ([55 12 12 12 28 17 14] ([12 55 12 12 12 28 17 14] not ([47 12 55 12 12 12 28 17 14] Value9)) = ([52 55 12 12 12 28 17 14] 9))) and ([55 12 12 28 17 14] ([12 55 12 12 28 17 14] not ([47 12 55 12 12 28 17 14] Value10)) = ([52 55 12 12 28 17 14] 10))) and ([55 12 28 17 14] ([12 55 12 28 17 14] not ([47 12 55 12 28 17 14] Value11)) = ([52 55 12 28 17 14] 11))) and ([55 28 17 14] ([12 55 28 17 14] not ([47 12 55 28 17 14] Value12)) = ([52 55 28 17 14] 12)))) endif) <EOF>) 
      12 21790 msecs 3,0 
      ratio: 2,01 
      

    答えて

    1

    それはin my articleを説明しているように非再帰的または原始再帰的なルールを左再帰exprルールを分割する必要があります。

    0

    これは、文法は@KvanTTT

    /** 
    * see https://github.com/antlr/antlr4/issues/994 
    */ 
    grammar primrecexpr; 
    
    primrecexpr: if_statement EOF; 
    
    if_statement: 
        if_part (else_part) ? 'endif'; 
    
    if_part: 
        'if' expr statement_list| 
        'if' expr; 
    
    else_part: 
        'else' statement_list | 
        'else'; 
    
    statement_list: 
        statement +; 
    
    statement: if_statement; 
    
    
    expr: 
        notexpr 
        | expr 'and' expr 
        | expr 'or' expr 
        ;  
    
    notexpr: 
        'not' notexpr 
        | equalexpr; 
    
    equalexpr: 
        atomexpr | 
        equalexpr '=' equalexpr 
        ; 
    
    atomexpr: 
        ID 
        | VALUE; 
    
    VALUE: [0-9]+; 
    ID: [a-zA-Z_][a-zA-Z_0-9]*; 
    WS: [ \t\n\r\f]+ -> skip; 
    ERROR: .; 
    
    によって提案された分割後にどのように見えるかです