Re: LL vs LR, strengths and weaknesses

ressler@cs.cornell.edu (Gene Ressler) writes:
>I've been surprised that no one has mentioned the inherent problem that LL
>has with many precedence levels, i.e. to parse ((x*x)+(y*y)) in C
>requires perhaps 70 recursive descent calls (or stack pushes in a
>table-driven LL parser) with the stack up to 30 deep...


If this proves to be a real problem and you're willing to put some work
into it, you can revise the "grammar" (most serious LL people use some
form of extended BNF, not strict LL(1) BNF) to fast-track the common
cases. (Bear in mind that the above is really quite a complicated
expression, and is well beyond the typical case, which is something like
`x' or `5'.) For example, revise `expr' in


expr = term { "+" term }
term = atom { "*" atom }


to


expr = atom [ "*" term ] { "+" term }


which will deal with the (common) single-atom exprs without the dreaded
"recursive plunge". Doing this for a messy zillion-level expression
grammar is a lot of work, and the semantics stuff may need adjustments if
you really care about associativity, but it can be done.


Credit Where Due Dept: I first saw this trick in the SP/k PL/I-subset
compiler done by the Computer Systems Research Group here at U of T, in
project-internal documentation that I read in late 1977. I'm not sure it
ever got written up anywhere more accessible. I don't remember exactly
whose name was on it, although I'd guess the idea came from Ric Holt or
possibly Jim Cordy.
--
Henry Spencer @ U of Toronto Zoology, henry@zoo.toronto.edu utzoo!henry
--

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