[antlr-interest] Re: Bounded Left Recursion

lgcraymer lgc at mail1.jpl.nasa.gov
Fri Mar 21 11:33:26 PST 2003


I would suggest taking a look at some of the ANTLR example grammars, 
particularly the one for the exprAST example and java.g (or Monty's C 
grammar).  ANTLR handles operator precedence in the same way that you 
probably learned it (at least, it's the way I learned it)--additive 
expressions operate on atomic numbers, multiplicative expressions, or 
parenthesized expressions; multiplicative expressions operate on 
atomic numbers or parenthesized expressions, and so on.

The biggest problem with using semantic predicates (besides the the 
ones you have already encountered) to try to shortcut the 
identification process is that you then have to jump through hoops to 
structure your abstract syntax trees.


--- In antlr-interest at yahoogroups.com, mzukowski at y... wrote:
> Very interesting post.  Two main problems:
> 1. PCCTS hoisted those sem preds.  ANTLR doesn't.  So if you have 
1+2, after
> you match the 1, as you enter infixOperator[6] it will fail.  In 
> would not have even been entered because the predicates would have 
> hoisted into the ()? subrule and level==6 & LA(1)==PLUS would have 
> ANTLR doesn't know about the level when deciding when to enter
> infixOperator[level], so it will call it for level==6 and it will 
> because it will try to match STAR | SLASH.
> 2. It is infinite recursion there, and antlr's analysis won't allow 
> You're stuck with that one, I think.
> I agree it would be nice to have such a compact representation of 
> rules.  I can't think of an easy way to do that in antlr currently, 
and it's
> really not too difficult to do it the standard LL way.
> Monty
> -----Original Message-----
> From: Brian Smith [mailto:brian-l-smith at u...]
> Sent: Thursday, March 20, 2003 10:40 PM
> To: antlr-interest at yahoogroups.com
> Subject: [antlr-interest] Bounded Left Recursion
> Hi, I have a grammar like the one below. Basically, I am trying to 
> semantic predicates to handle precedence of infix operators. I can 
> that ANTLR is unhappy with the left recursion in infixExpCS. I know 
> _unconstrained_ left recursion is not allowed in LL grammars because 
> results in infinite recursion. However, in this example, the 
> will never go more than seven levels deep. So, is there any way to 
> this trick to work? It is actualy adapted from a very old posting 
> Terence made on comp.compilers on the topic of implementing 
> rules via predicates. Perhaps, I am not using the predicate feature 
> correctly?
> Terence's posting (from 1994): 
> I would also like to read the paper cited as [MiF79]. Does anybody 
> what paper he is referring to?
> Thanks,
> Brian
> class simple extends Parser;
> infixExpCS[int level]
>                  :   {level==7}? prefixExpCS
>                  |   infixExpCS[level+1]
>                      (infixOperator[level]
>                      infixExpCS[level])?
>                  ;
> infixOperator[int level]
>                  : {level==1}? (IMPLIES)
>                  | {level==2}? (AND    | OR | XOR)
>                  | {level==3}? (EQUALS | NOT_EQUALS)
>                  | {level==4}? (LESS_THAN | LESS_EQUAL
>                                |GREATER_THAN | GREATER_EQUAL)
>                  | {level==5}? (PLUS|MINUS)
>                  | {level==6}? (STAR | SLASH)
>                  ;
> prefixExpCS:    NOT prefixExpCS
>              |   INTEGER_LITERAL
>              ;
> [antlr] 5:21: infinite recursion to rule infixExpCS from rule 
> [antlr] 5:21: infinite recursion to rule infixExpCS from rule 
> [antlr] 5:41: warning: nondeterminism upon
>                     PLUS,MINUS,STAR,SLASH
> [antlr] 5:41: between alts 1 and 2 of block
> [antlr] Exiting due to errors.
> Your use of Yahoo! Groups is subject to 


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

More information about the antlr-interest mailing list