[antlr-interest] Bug report: Unexplainable "no viable alternative"

[David-Sarah Hopwood]

alex.marin at amiq.ro wrote:
> Hello,
> 
> We have trouble understanding why we get a "no viable alternative" when
> running the attached parser grammar on the following input:
> 
> bit bitstream [];
> 
> The output is:
> 
> line 1:15 no viable alternative at input ']'
> 
> However, we have found two (very strange) workarounds for the issue:
> 1. Commenting out the 'real' option in the data_type rule
> 2. Using associative_dimension_2 rule instead of associative_dimension_1
> (although the two are equivalent)
> 
> What is the explanation for this behavior?

The problem is the k=1 option. If that is deleted, and neither workaround
is needed. Also delete the redundant syntactic predicate in
<variable_dimension>.

The grammar is not LL(1), because a two-token lookahead is needed to
distinguish between <associative_dimension> and (the first of a sequence of)
<sized_or_unsized_dimension>.

The reason why you didn't get a warning about the too-small k value is
that the use of a syntactic predicate in <variable_dimension> caused the
warning to be suppressed. The syntactic predicate is not necessary because
<associative_dimension> and <sized_or_unsized_dimension> are not mutually
ambiguous.

Removing the predicate (still with k=1) would have given the warning:

  [21:36:45] warning(200): Example.g:43:1: Decision can match input such
  as "LBRACK" using multiple alternatives: 1, 2
  As a result, alternative(s) 2 were disabled for that input

which is correct since one-token lookahead is not sufficient in rule
<variable_dimension>.

> Is there a rigorous solution to avoid such behavior?

In general, the k option is rarely if ever necessary. When k is too small,
it can often be the case that apparently equivalent rules cause different
behaviour. This is because ANTLR uses different strategies for lookahead
based on considerations that are fairly unpredictable, and the k value
has different effects on these strategies. (IMHO this should be made
clearer in the documentation; arguably, the statements that k simply causes
ANTLR to use LL(k) parsing are misleadingly incomplete.)

You should also avoid redundant predicates, since they often suppress
useful warnings.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20091104/6124f14e/attachment.bin