[antlr-interest] Re: Nondeterminism in a simple expression grammar

[Dave Bailey]

--- In antlr-interest at yahoogroups.com, jbb at a... wrote:
> On Fri, 07 May 2004 21:02:15 +0000, Dave Bailey <dave at d...> wrote:
[...]
> >test : (expr SEMI!)+ EOF! ;
> >expr : uexp | bexp ;
> >uexp : U^ expr ;
> >bexp : ID (B^ (uexp | ID))* ;
[...]
> instead of 
> 
> 	bexp : ID (B^ (uexp | ID))* ;
> 
> maybe try
> 
> 	bexp : ID (B^ exp)? ;

Thanks, that fixed it!  I have a slightly more complicated case that
I'm working on and I'm wondering if I can implement it without
syntactic predicates.  The (simplified) grammar has three
left-associative binary operators and three unary operators.  Each
operator has a different precedence, and they are (in order, from
lowest to highest precedence):

U0, B1, U2, B3, B4, U5

where operators starting with "U" are unary, and operators starting
with "B" are binary.  The number after the U or B indicates that
operator's precedence level, with 0 being the lowest and 5 being the
highest.  Here is the expression grammar that I have right now:

test   : (expr SEMI!)+ EOF! ;
expr   : u0 | b1 ;
u0     : U0^ (u0|b1) ;
b1     : ((u2|b3) B1 (b1|u0)) => (u2|b3) B1^ (b1|u0) | (u2|b3) ;
u2     : U2^ (u2|u0|b3) ;
b3     : (b4 B3 (u0|u2|b3)) => b4 B3^ (u0|u2|b3) | b4;
b4     : (u5|ID) (B4^ (u0|u2|b4))? ;
u5     : U5^ (u5|ID) ;

I think that this grammar works correctly, in that it parses all
possible expressions using the six operators I've specified, and gets
the precedences right.  But I have to use a couple of syntactic
predicates, and I'm not sure they're necessary.  Is there a way to
refactor the grammar to eliminate the syntactic predicates?  In the
"real world" application that I'm working on, there are a lot more of
these operators, and many more precedence levels, and I'm worried that
my parser will turn out to be unnecessarily large/slow as a result of
my poor grammar.

The general problem I'm trying to solve is, how do I write a clean
expression grammar for a given set of unary and binary operators with
a given set of precedence levels?  In most expression grammars that
I've seen, the unary operators always have the highest precedences, so
you don't run into the situation I'm describing above.

Thanks again for your help,
-dave











 
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/