[antlr-interest] NoViableAltException in optional alternative

Brent Yates brent.yates at gmail.com
Sat May 24 11:04:54 PDT 2008


If the prediction DFA for an alternative fails but the alternative is
optional, should the rule throw a NoViableAltException?  It seems to me that
it should not, but the code generated by Antlr 3.1b1 does throw the
exception.  Here is a short silly grammar that shows the problem.  If you
runs this in AntlrWorks and test just the numbers rule with an input of '5',
you will get NoViableAltExceptions.

grammar Bug;

options
    {
    language= Java;
    }

start
    :    declarations EOF
    ;

declarations
    :    numbers ';'
    ;

numbers
    :    '5'
        (
            '.'
        |    '&' '%' '%'
        |    '&' '%' '^'
        |    '%' '$'
        |    '%' '^'
        )?
    ;

If one calls the '*numbers*' rule in isolation (for example during unit
testing or if you are building an interpreter) and feeds a single '*5*' to
it followed by EOF (or anything other than semicolon), the alternative
prediction DFA inside the numbers function fails and a NoViableAltException
is thrown.  I belive this is incorrect as the numbers rule should have
succeeded since the final alternative is optional.  The extra input should
be passed up the chain for other rules to verify.

Antlr is also not consistent in this behavior.  Making minor changes to the
grammar will sometimes cause the generated code to NOT use a DFA for the
alternative check and in this case no exception is thrown when the
alternative does not match - reguardless of the reason for not matching
(i.e., extra input that is not in the follow set).

The inconsistency makes it hard to craft gUnit tests as the rule tests work
sometimes and then later fail (due to NoViableAltExceptions) after unrelated
changes to the grammar.  I also think this could cause problems for
applications where the rules need to be called independently.

Thanks,

Brent Yates
brent.yates at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20080524/2f5d2f6a/attachment.html 


More information about the antlr-interest mailing list