[antlr-interest] Bounded Left Recursion

[mzukowski at yci.com]

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 uiowa.edu]
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/