Re: Problem with infinite left-recursion...

Casper Stoel (cbs@ascinc.com:
> I have a problem with left-recursion in my grammar. I am wondering if
> there is a 'standard' way of breaking the recursion? Is there an easy
> way of breaking up the rule into multiple rules?


There is! Let's say you have a grammar rule: E -> E + T and E -> T
Standard way to get rid of the leftrecursion (so as to be able to write
a topdown recursive descent parser for instance) is:
    E -> T X with X a new nonterminal with productions
    X -> + T X
    X ->
Sometimes (topdown) parsergenerators can handle the following construct,
thereby avoiding the above introduction of a new nonterminal:
    E -> T ( + T ) SEQUENCE OPTION
meaning, an E is a T, followed by zero or more occurrences of +T.


--
Jan Jongejan email: jjan@cs.rug.nl
Dept. Comp.Sci.,
Univ. of Groningen, 8-{)
Netherlands.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.