Re: LL vs LR, strengths and weaknesses

Ahhh, here's an interesting topic: LL(k) vs. LR(1). Again, let's not
start a religious conflict, but I think a few words from the other side of
the aisle might be in order. I'll place myself firmly in the LR(1) side,
whereas Terence is clearly of the LL(k) camp:


parrt@ecn.purdue.edu (Terence J Parr) writes:
>Strength is not the end of the story because one rarely wants to merely
>recognize --> we TRANSLATE.


This is a good point. We want don't so much want to recognize a
_language_ so much as generate a parse tree of the input for a particular
grammar. The _grammar_ itself is important; if one has to contort the
"natural" grammar (i.e., the one that matches the semantic grouping) of
language in order to accomodate our parsing scheme, this is a serious dis-
advantage. This is why, for example, we don't just convert our ambiguous
grammars into Chomsky normal form and apply the obvious dynamic
programming parsing scheme. We'll see in a minute that both LL(k) and
LR(1) parsing schemes suffer from this problem.


>Here, LL parsers are the clear winner. A few highlights:
>
>o LL rules may inherit attributes; i.e. you can pass stuff to them just
> like in a programming language. For example, you can pass a scope to
> your rule that recognizes declarations. Future versions of PCCTS
> will even let you pass productions to rules-->context-sensitive
> parsing.


People often make the mistakes that (1) yacc <=> LALR parsing and
(2) yacc is limited to synthesized attributes. If you think about what is
actually happening during parsing, you will realize that the left-context
of each production is available, albeit in a somewhat disguised form: the
left context of currect production is the contents of the entire parsing
stack. Accessing the left context of a production is no more painful than
accessing the attributes of the rhs of a production. The problem is that
we've been spoiled by yacc's convenient use of the $n constructs.


Considering your example, where expressions are parsed in a
context that containing declarations, we can do the following: Suppose our
grammar is:


exp -> LET decls IN exp | atexp
                                exp -> exp + exp | ....
decls -> ...


Then I can access the attribute of the "decls" by the following:


exp : exp '+' exp1 {$$ = parse_in_context($1,$3,$<decls>-1);


since the stack at the time of the reduction of exp '+' exp -> exp looks
like:


------------------------------
| exp | <attribute of exp> | = "$3"
------------------------------
| '+' | <attribute of '+'> | = "$2"
------------------------------
| exp | <attribute of exp> | = "$1"
------------------------------
| IN | <attribute of IN> | = "$0"
------------------------------
| decls | <attribute of decls> | = "$-1"
------------------------------
| LET | <attribute of LET> | = "$-2"
------------------------------


A "hack" you say? Well, a hack is in the eye of the, er, hacker.
Clearly, accessing the synthesized attributes is, by the nature of yacc's
facilities, somewhat easier than accessing the left context. But that is
a feature of yacc, not LR parsing. All I need to do general L-attributed
grammars is an attribute stack, and I would be happy if yacc only allowed
action functions that took a single argument: the top of the attribute
stack. It's possible to write a compiler that uses no variables other
than the attribute stack (along with some locals of action functions).
You keep the symbol table in the attribute stack; this makes exiting
declaration scopes painless.


>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
                                T -> T * N | T / N | N
                                N -> (E) | 1 | 2 | ...


This grammar is not LL(k) for any k (since I can pump with the
parentheses.) But this is the natural grammar for this language. Sure, I
can change it to LL(1) by changing the associativity of the operators, but
that produces a parse tree that doesn't reflect the intended semantics of
the language, and will cause me headaches later on.


I don't see any good solution to this, other than LR parsing. How
_do_ you parse expressions in an LL(k) parser? Sure, I can write a parser
that, when trying to consume an E when looking ahead at a "(", recursively
calls itself, but that isn't an LL(k) parser.


>Moral of story: Most languages can be described easily with LL(k);
> the semantic flexibility of LL(k) makes any fancy
> footwork regarding the grammar worth the effort for me.


Moral of _my_ story: Most languages can be described easily with LR(1);
                                    the grammatical flexibility of LR(1) makes any fancy
                                    footwork regarding the semantics worth the effort for me.


:-) :-) :-) :-) :-) :-) :-) :-) :-)


Real moral of the story: Different tools for different people. Finally,
it's important to distinguish between the _tool_ and the _technique_:
*** YACC IS NOT THE FINAL WORD IN BOTTOM-UP PARSING! ***.


BTW, if anyone wants to see a _really_ slick parser and parser-generator
tool, check out the parser in the SML/NJ compiler, generated by ML-yacc.
A very nice piece of code!
--
Jack Eifrig (eifrig@cs.jhu.edu) The Johns Hopkins University, C.S. Dept.
--

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