Re: LL vs LR, strengths and weaknesses (Jon Mauney)
Wed, 13 May 1992 17:35:52 GMT

          From comp.compilers

Related articles
LL vs LR, no jihad initiation, but... (1992-05-11)
Re: LL vs LR, strengths and weaknesses (1992-05-11)
Re: LL vs LR, no jihad initiation, but... (1992-05-12)
Re: LL vs LR, strengths and weaknesses (1992-05-13)
Re: LL vs LR, strengths and weaknesses (1992-05-13)
Re: LL vs LR, strengths and weaknesses (1992-05-14)
Re: LL vs LR, strengths and weaknesses (1992-05-14)
LL(1) Questions (Re: LL vs LR, strengths and weaknesses) (1992-05-15)
Re: LL vs LR, strengths and weaknesses (1992-05-15)
Re: LL vs LR, strengths and weaknesses (1992-05-19)
Re: LL vs LR, strengths and weaknesses (1992-05-16)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Jon Mauney)
Keywords: LL(1), LR(1), parse
Organization: North Carolina State University
References: 92-05-059 92-05-072
Date: Wed, 13 May 1992 17:35:52 GMT (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
> 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

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. 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 (919) 828-8053

Post a followup to this message

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