[antlr-interest] Re: nondeterminism question

[Klaas Hofstra]

On Thursday 01 September 2005 21:51, Bill Canfield wrote:
> Hi Klaas:
>
> I haven't looked at your grammar in detail, but be aware that ANTLR uses
> "linear approximate" lookahead.  In a nutshell, you might have an
> unambiguous grammar that looks ambiguous to ANTLR because it took a
> shortcut in calculating the rule.  Higher values of k tend to produce
> more of these false ambiguities.
>
> Here's a note on it in the ANTLR docs:
>
> http://www.antlr.org/doc/options.html#_bb4
>
> When I've had a situation like this, I just factor the rule until I get
> ANTLR to behave :-).
>
> Bill

Bill, thanks for your answer. 

In order to check whether I had a problem with "linear approximate" lookahead, 
I first simplified the typeSpec by replacing 'range' by 'INT DOTDOT INT'. 
(this does not get rid of the warning about LPAREN).

typeDef
    : "signed"
    | "unsigned"
    | "float"
    | ("integer" ( LPAREN! INT DOTDOT! INT RPAREN! )? )      <= warning
    ;

I found that I don't get a warning when I remove typeSpec from the 'cast' line 
in unarayExpression (which renders grammar unusable) 

unaryExpression
    : postFixExpression
    | PLUS^ unaryExpression
    | MINUS^ unaryExpression
    | NOT^ unaryExpression
    | "cast"! (typeSpec | ID) unaryExpression
    ;

I don't understand why this solves the LPAREN warning. Below I posted the 
generated code (Python) for unaryExpression in edited form. 

For the cast branch the choice between 'typeSpec' and 'ID' is also 
unambiguous, so why does removing typeSpec help?

Are there tools that can help me find the problem in the grammar?

Cheers,
Klaas

------------------------------------------------

def unaryExpression(self): 
    la1 = self.LA(1)
    if la1 and la1 in [ID,LPAREN,INT,REAL,STRING]:
        self.postFixExpression()
    elif la1 and la1 in [PLUS]:
        self.match(PLUS)
        self.unaryExpression()
    elif la1 and la1 in [MINUS]:
        self.match(MINUS)
        self.unaryExpression()
    elif la1 and la1 in [NOT]:
        self.match(NOT)
        self.unaryExpression()
    elif la1 and la1 in [LITERAL_cast]:
        self.match(LITERAL_cast)
        la1 = self.LA(1)
        if la1 and la1 in [LITERAL_signed, LITERAL_unsigned, LITERAL_real, 
LITERAL_integer, LITERAL_enum]:
            self.typeSpec()
        elif la1 and la1 in [ID]:
            self.match(ID)
            
        self.unaryExpression()

------------------------------------------------