[antlr-interest] Bounded Left Recursion
Brian Smith
brian-l-smith at uiowa.edu
Thu Mar 20 22:40:08 PST 2003
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/
More information about the antlr-interest
mailing list