[antlr-interest] Re: Bounded Left Recursion

[lgcraymer]

Brian--

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.

--Loring


--- 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 
PCCTS it
> would not have even been entered because the predicates would have 
been
> hoisted into the ()? subrule and level==6 & LA(1)==PLUS would have 
failed.
> 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 
fail
> because it will try to match STAR | SLASH.
> 
> 2. It is infinite recursion there, and antlr's analysis won't allow 
it.
> You're stuck with that one, I think.
> 
> I agree it would be nice to have such a compact representation of 
expression
> 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 
use 
> semantic predicates to handle precedence of infix operators. I can 
see 
> that ANTLR is unhappy with the left recursion in infixExpCS. I know 
that 
> _unconstrained_ left recursion is not allowed in LL grammars because 
it 
> results in infinite recursion. However, in this example, the 
recursion 
> will never go more than seven levels deep. So, is there any way to 
get 
> this trick to work? It is actualy adapted from a very old posting 
that 
> Terence made on comp.compilers on the topic of implementing 
predecence 
> rules via predicates. Perhaps, I am not using the predicate feature 
> correctly?
> 
> Terence's posting (from 1994): 
http://makeashorterlink.com/?X330167E3
> 
> I would also like to read the paper cited as [MiF79]. Does anybody 
know 
> 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 
infixExpCS
> [antlr] 5:21: infinite recursion to rule infixExpCS from rule 
infixExpCS
> [antlr] 5:41: warning: nondeterminism upon
> [antlr] 5:41: k==1:IMPLIES,AND,OR,XOR,EQUALS,NOT_EQUALS,
>                     LESS_THAN,LESS_EQUAL,GREATER_THAN,GREATER_EQUAL,
>                     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 
http://docs.yahoo.com/info/terms/


 

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