[antlr-interest] Bug in lookahead DFA?

Harmon Nine hnine at isis.vanderbilt.edu
Tue Dec 11 15:32:08 PST 2007


When is 3.1 to be released (ballpark)?

 

Thanks.

-- Harmon

 

________________________________

From: antlr-interest-bounces at antlr.org
[mailto:antlr-interest-bounces at antlr.org] On Behalf Of Terence Parr
Sent: Tuesday, December 11, 2007 4:33 PM
To: antlr-interest at antlr.org
Subject: Re: [antlr-interest] Bug in lookahead DFA?

 

Harmon, this is indeed a bug. worse, in 3.1beta it disappears and builds
bad DFA!  Yikes.  I've seen this before; added to my existing bug:

 

http://www.antlr.org:8888/browse/ANTLR-178

 

I'll fix for 3.1

 

Ter

On Nov 14, 2007, at 9:36 AM, Harmon Nine wrote:





Hi.

 

I'm trying to write a parser for MatLab (without objects, classes, or
structs) and am coming across some peculiar behavior.  A portion of this
grammar that results in this behavior is at the end of this message.

 

In this grammar, I'm using a syntactic predicate to differentiate
between an assignment and expression-evaluation statements (see the
"statement" rule below).  Antlr accepts the parser definition without
error.

 

The problem occurs when the parser attempts to parse a rather simple
file:

y(1) = 0

y(1)

 

That is, it gives the error

 

line 1:5 no viable alternative at input '='

 

Perhaps there is an error in the parser definition, but the peculiar
thing is that when, on the "statement" rule, I reduce "k" to 2, i.e.

 

statement:

options {

  k=2;

}

            : ...

 

The parser works correctly.

 

I also tried k at various other values.  When it is set at a value of
10, I get the following message:

 

ANTLR Parser Generator  Version 3.0.1 (August 13, 2007)  1989-2007

warning(205): DFABug.g:37:2: ANTLR could not analyze this decision in
rule statement; often this is because of recursive rule references
visible from the left edge of alternatives.  ANTLR will re-analyze the
decision with a fixed lookahead of k=1.  Consider using "options {k=1;}"
for that decision and possibly adding a syntactic predicate.

 

The warning message isn't really applicable, as the rule is not
recursive and already has a syntactic predicate.

 

Is this normal behavior?   I.e. when using syntactic predicates, is it
normal to have to give "k" a small finite value to get the lookahead to
work properly, rather than simply to enhance efficiency?

 

If not, how does one submit a bug report?

 

 

Here's the grammar:

parser grammar DFABug;

 

options {

//  language=C++;

  tokenVocab=DFABugTokens;

  output=AST;

}

 

delimiter

        :       null_lines empty_lines?

        |       empty_lines

        ;

 

null_lines

        :       null_line+

        ;

 

null_line

        :       empty_lines? ( COMMA | SEMI )!

        ;

 

empty_lines

        :       line+

        ;

 

line    :       ( COMMENT | NEWLINES )!

        ;

 

statement_list

        :       statement ( delimiter statement )* delimiter?

        ;

 

statement

options {

  k=2;

}

      :     (reference ASSIGN)=> reference ASSIGN^ expr

        |       expr

      ;

 

expr  :     reference

      |     INTEGER

      |     DOUBLE

      |     IMAGINARY

      |     TEXT

      ;

 

reference

      :       IDENTIFIER^ LPAREN! argument_list RPAREN!

        ;

 

argument_list

        :       expr ( COMMA! expr )*

        ;

 

 

 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20071211/49f4e602/attachment-0001.html 


More information about the antlr-interest mailing list