Re: LL vs LR, strengths and weaknesses

eifrig@blaze.cs.jhu.edu (Jonathan Eifrig) writes:
>Ahhh, here's an interesting topic: LL(k) vs. LR(1).


Given an LR(1) grammar, to which one now must add semantic
actions/attribute functions, one may wind up with the following two
apparently unrelated productions:


      foo -> A B {action1} C D
      bar -> A B {action2} C E


But since the LR construction puts the productions into the same state,
there is a conflict in the actions. The translator-writer must revise the
action to handle both situations. With an LL(1) grammar, the
common-prefix will already have been factored; once the grammar is LL,
actions can be added without further trouble. It's all a matter of when
you go through the pain.


> A "hack" you say? Well, a hack is in the eye of the, er, hacker.
Push this thought on the stack for later retrieval.


>>The disadvantage really only lies in the fact that you have more constraints
>>when writing LL(k) grammars--no left-recursion and no common prefixes of
>>tokens >= k tokens in length.


> But this is no small restriction! Consider the common expression
>grammar:
> E -> E + T | E - T | T
> This grammar is not LL(k) for any k
>But this is the natural grammar for this language. Sure, I
>can change it to LL(1) by changing the associativity of the operators,


> I don't see any good solution to this, other than LR parsing. How
>_do_ you parse expressions in an LL(k) parser?


a) Natural is in the eye of the naturalist. Having taught grammars and
parsing to undergraduates, I have to recognize that many people won't find
the LR grammar very natural either. A left-recursive grammar does not
supprt the abstract view of expressions as a list of operands separated by
operators, a view which is suggested by this grammar:


      E -> T <more Ts>
      <more Ts> -> + T <more Ts>
      <more Ts> -> empty


In practice there are a few LL idioms, and once you get used to them,
writing LL grammars is easy. You can then make an informed trade-off
between the BNF and the semantic actions.


b) You parse expressions LL(1) by adjusting where you put the semantic
actions. The above LL grammar produces a right-leaning parse tree, but
does not put an obvious associativity on the operator, since all the
operands are at different levels of the tree. Pass the expression-so-far
as an inherited attribute, and do the important evaluation after seeing
the second operand:
      <more Ts> -> + T {eval expr-so-far} <more Ts>


You may prefer to have all of the associations explicit in the parse tree,
but I find it to be no hackier than passing inherited attributes during a
bottom-up parse.


>Real moral of the story: Different tools for different people.


De gustibus non est deterministum.


> Finally, it's important to distinguish between the _tool_ and the
>_technique_: *** YACC IS NOT THE FINAL WORD IN BOTTOM-UP PARSING! ***.


Amen brother! Many people seem to think that there are only two ways to
build a parser: yacc, and hand-constructed recursive descent. But there
are other bottom-up parser generators, and there are a variety of top-down
generators.


dww@inf.fu-berlin.de writes:
>Perhaps I've missed something, but it would seem to me that LL parsers
>need a lot of memory for all the pending production procedure calls, i.e
>you can't reduce <prog> ::= <decl> <stmts> until the very last token has
>been read in. You would normally have as many pending calls as the depth
>of the parse tree at the moment. This could be a problem for some systems.


Recursive-descent parsers commonly convert the tail-recursive productions
into iteration in the parsing procedure, so there is no stack growth.
This is especially easy if the parser generator accepts an extended BNF.
With table-driven parsers, symbols are popped off the stack when expanded
and again there is no serious stack growth.


>An then there would be the if-then-else problem. If you have a grammar like
> ...


The dangling-else is an important theoretical limitation of LL(1) parsing.
You just can't do it. Fortunately the kludge to get around them problem
is simple and painless; you instruct the parser generator to choose in
favor of matching the else -- its a lot like the precedence rules in yacc.


--
Jon Mauney, parsing partisan
Mauney Computer Consulting
mauney@csc.ncsu.edu (919) 828-8053
--

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