[antlr-interest] Syntactic predicates and loops

[Noel F Bryson]

On Tue, 2004-05-04 at 11:12, Noel F Bryson wrote:
> 
> 
> 
> 
> On Fri, 2004-04-30 at 17:57, Monty Zukowski wrote:
> > On Apr 30, 2004, at 9:18 AM, Noel F Bryson wrote:
> > 
> > > I'm trying to build a grammar which includes something like the
> > > following rules, which are intended to parse declaration-lists e.g. T1
> > > a,b,c,T2 d,e,f,T3 g,h (where T1,T2 are types and a-h are variables).
> > >
> > > type: identifier;
> > > variable: identifier;
> > >
> > > list_of_variables: variable (COMMA variable)*;
> > >
> > > declaration_list: type list_of_variables
> > >                       ( COMMA type list_of_variables)*;
> > >
> > >
> > > I have simplified the rules to illustrate my problem - which is that
> > > I get an ambiguity in list_of_variables:
> > >
> > > sand2.g:35: warning:nondeterminism upon
> > > sand2.g:35:     k==1:COMMA
> > > sand2.g:35:     k==2:identifier
> > > sand2.g:35:     k==3:EOF
> > > sand2.g:35:     between alt 1 and exit branch of block
> > >
> > > This occurs because ANTLR sees that, when it meets a COMMA, it can
> > > either match using the loop in list_of_variables, or exit and match
> > > using the loop in list_of_declarations. hence it can't tell if T2 is a
> > > variable name or a type name.
> > >
> > > Since 'type' and 'variable' are actually more complex than I have shown
> > > here, and themselves involve loops at the end, I don't think I can
> > > resolve this be factoring or increasing the look-ahead.
> > >
> > >
> > > I'd like to be able to resolve this by getting list_of_variables to use
> > > a syntactic predicate to lookahead through the identifier to see if
> > > there is a COMMA (or EOF) after it. I'm new to this field, and would be
> > > grateful if someone could show me how to do this - ANTLR ignores my
> > > feeble efforts e.g.
> > >
> > > list_of_variables: variable ((COMMA identifier COMMA identifier
> > > identifier) => COMMA variable)*;
> > >
> > What goes wrong with this attempt?  It looks like it should work, 
> > though ANTLR will complain of a superflous syntactic predicate since 
> > there is only one alternative in the ()* closure.
> > 
> > Monty Zukowski
> > 
> > ANTLR & Java Consultant -- http://www.codetransform.com
> > ANSI C/GCC transformation toolkit -- 
> > http://www.codetransform.com/gcc.html
> > Embrace the Decay -- http://www.codetransform.com/EmbraceDecay.html
> > 
> > 
> 
> It gives:
> 
> ANTLR Parser Generator   Version 2.7.3 (20040325-1)   1989-2004 jGuru.com
> sand2.g:18: warning:nondeterminism upon
> sand2.g:18:     k==1:COMMA
> sand2.g:18:     k==2:Identifier
> sand2.g:18:     between alt 1 and exit branch of block
> sand2.g:19: warning:Syntactic predicate superfluous for single alternative
> 
> However, after a week-end hill-walking and drinking beer, I got this example to work with:
> 
> list_of_variables: variable list_tail;
>                                                                                                                                                              
> list_tail:
>     (COMMA Identifier) => ((COMMA type variable) => empty | COMMA variable list_tail)
>     | empty
>     ;
>                                                                                                                                                              
> empty: ();
> 
> Now I'll go back to the real problem !
> 

Now I try to use these rules in my declaration-list grammar:

list_of_declarations: declaration (COMMA declaration)*;

declaration: type list_of_variables;

list_of_variables: variable list_of_variables_tail;
                                                                                                                                                         list_of_variables_tail:
    (COMMA Identifier ) => ((COMMA type variable) => empty 
                             | COMMA variable list_of_variables_tail)
    | empty
    ;

                                                                                                                                                                                                                                                                                    type: Identifier;
variable: Identifier;
empty: ();

This doesn't report any ambiguities from the command-line, but the
diagnostic file has "Error: This rule is non-deterministic" at the
top-level in list_of_variables_tail, and "Warning: This alternative
block is non-deterministic" at the start of the code for the first
alternative  (i.e. the one with the predicates).

Questions:

Why am I getting an error ?
Why am I getting a warning ?
Why don't I get an error report from the command-line ?





 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
     http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
     antlr-interest-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
     http://docs.yahoo.com/info/terms/