Testing grammar for ambiguities

5
votes

I'm writing a grammar for a formal language. Ideally I'd want that grammar to be unambiguous, but that might not be possible. In either case, I want to know about all possible ambiguities while developing the grammar. How can I do that?

So far, most of the time when I developed a language, I'd turn to Bison, write a LR(1) grammar for it, run Bison in verbose mode and have a look at all the shift-reduce and reduce-reduce conflicts it tells me about. Make sure that I agree with its choice in each case.

But now I'm in a project where Bison doesn't have a code generator for one of the required target languages, and where ANTLR is already being used. Plus the language isn't LR(1), and rewriting it as LR(1) would entail additional syntax checks after the parser is done, thus reducing the expressiveness of the grammar as a tool to describe the language.

So I'm now working with ANTLR, fed it my grammar, and all seems to be working well. But ANTLR doesn't seem to check for ambiguities at compile time. For example, the following grammar is ambiguous:

grammar test;
lst: '(' ')'      {System.out.println("a");}
   | '(' elts ')' {System.out.println("b");} ;
elts: elt (',' elt)* ;
elt: 'x' | /* empty */ ;

The input () could be interpreted as the empty list, or it could be interpreted as a list consisting of a single empty element. The generated parser chooses the former interpretation, but I'd like to be able to manually verify that choice.

  • Is there command line switch I can use to get ANTLR to tell me about ambiguities?
  • Or perhaps an option I can set in the grammar file?
  • Or should I use some other tool to check the grammar for ambiguities?
  • If so, is there one which can already read ANTLR syntax, or do I have to strip out all the actions and boil this down to BNF myself?

The ANTLRErrorListener.reportAmbiguity method suggests that ANTLR might be able to perform some ambiguity testing at runtime. But I guess that's only going to tell you whether the parsing of a given input is ambiguous. Is there some strategy how I could leverage this to detect all ambiguities, using a carefully selected set of inputs?

1
parsingantlrgrammarantlr4context-free-grammar
Yes, attaching a DiagnosticErrorListener to your parser will cause DiagnosticErrorListener#reportAmbiguity(...) being called. In that method, the information is available that the alternatives 1 and 2 from your production lst are ambiguous. – Bart Kiers

1 Answers

5
votes

Well, as far as I know, ANTLR has no real option to check for ambiguity, other than the errors it produced IF you write an ambiguous grammar and feed an input that triggers the ambiguity. I do, however know a few tools which can check for ambiguity. They all have different syntax, and I don't know any tool which uses ANTLR grammar.

  1. A software called AtoCC has a tool called KfG which can check for ambiguity.
  2. ACLA (Ambiguity Checking with Language Approximations).
  3. Context Free Grammar Tool.

Personally, I find tool 3 easiest to use, but is the most limited as well. It is important, however to note that none of the tools can be 100% sure; if the tools says you're grammar is ambiguous, it is ambiguous, however if they say you're grammar is unambiguous, they might still be ambiguous, as they have no way of testing an infinite number of ways, that your language can be written.

Hope this helps.