[antlr-interest] Bounded Left Recursion

[Brian Smith]

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/