Ambiguity in grammar not reported by ANTLR

Question

Can anyone help me understand what makes ANTLR not report an issue with the ambiguity in this grammar?

https://github.com/NASA-SW-VnV/fret/blob/master/fret-electron/support/NuSMVParser/NuSMV.g4#L61-L78

The rules in simpleExpr and ltlExpr are duplicated in such a way that there are always two alternative paths to build anything with an and, or, xor, implies, equiv, not operator applied to it, or some parenthesized expressions.

When I run ANTLR on it, I would expect to see a warning but I get nothing (meaning a parser and a lexer are produced).

score 2 · Answer 1 · answered Nov 08 '21 at 18:45

Since ANTLR matches parser rule in a first-come-first-serve manner, the first rule that matches "wins" (the parser doesn't care that certain input can be parsed in multiple ways).

To display the ambiguity, you could attach a custom error listener and override its reportAmbiguity method and set the prediction mode to PredictionMode.LL_EXACT_AMBIG_DETECTION.

Take the following grammar where the print_statement_1 and print_statement_2 alternatives from statement are ambiguous:

grammar T;

parse
 : statement* EOF
 ;

statement
 : print_statement_1
 | print_statement_2
 ;

print_statement_1
 : 'print' expr
 ;

print_statement_2
 : 'print' expr
 ;

expr
 : INT
 ;

INT
 : [0-9]+
 ;

SPACE
 : [ \t\r\n] -> skip
 ;

ANY
 : .
 ;

and if you run the following code:

public static void main(String[] args) {
    
  String source= "print 42";
  TLexer lexer = new TLexer(CharStreams.fromString(source));
  TParser parser = new TParser(new CommonTokenStream(lexer));

  parser.getInterpreter().setPredictionMode(PredictionMode.LL_EXACT_AMBIG_DETECTION);

  parser.addErrorListener(new BaseErrorListener() {
    // The code below is from org.antlr.v4.runtime.DiagnosticErrorListener
    @Override
    public void reportAmbiguity(Parser recognizer, DFA dfa, int startIndex, int stopIndex, boolean exact, BitSet ambigAlts, ATNConfigSet configs) {
      if (exact) {
        String format = "reportAmbiguity d=%s: ambigAlts=%s, input='%s'";
        String decision = this.getDecisionDescription(recognizer, dfa);
        BitSet conflictingAlts = this.getConflictingAlts(ambigAlts, configs);
        String text = recognizer.getTokenStream().getText(Interval.of(startIndex, stopIndex));
        String message = String.format(format, decision, conflictingAlts, text);
        recognizer.notifyErrorListeners(message);
      }
    }

    protected String getDecisionDescription(Parser recognizer, DFA dfa) {
      int decision = dfa.decision;
      int ruleIndex = dfa.atnStartState.ruleIndex;
      String[] ruleNames = recognizer.getRuleNames();
      if (ruleIndex >= 0 && ruleIndex < ruleNames.length) {
        String ruleName = ruleNames[ruleIndex];
        return ruleName != null && !ruleName.isEmpty() ? String.format("%d (%s)", decision, ruleName) : String.valueOf(decision);
      } else {
        return String.valueOf(decision);
      }
    }

    protected BitSet getConflictingAlts(BitSet reportedAlts, ATNConfigSet configs) {
      if (reportedAlts != null) {
        return reportedAlts;
      } else {
        BitSet result = new BitSet();
        Iterator i$ = configs.iterator();

        while(i$.hasNext()) {
          ATNConfig config = (ATNConfig)i$.next();
          result.set(config.alt);
        }

        return result;
      }
    }
  });

  ParseTree root = parser.parse();
}

the following will be printed:

line 1:8 reportAmbiguity d=1 (statement): ambigAlts={1, 2}, input='print42'

Ambiguity in grammar not reported by ANTLR

1 Answers1

Linked