|LL vs LR, no jihad initiation, but... firstname.lastname@example.org (1992-05-11)|
|Re: LL vs LR, strengths and weaknesses email@example.com (1992-05-11)|
|Re: LL vs LR, no jihad initiation, but... firstname.lastname@example.org (1992-05-12)|
|Re: LL vs LR, strengths and weaknesses email@example.com (1992-05-13)|
|LL, LR debate firstname.lastname@example.org (1992-05-13)|
|Re: LL vs LR, strengths and weaknesses email@example.com (1992-05-13)|
|Re: LL vs LR, strengths and weaknesses firstname.lastname@example.org (1992-05-14)|
|[10 later articles]|
|From:||email@example.com (Terence J Parr)|
|Keywords:||LL(1), LR(1), parse|
|Date:||Mon, 11 May 1992 02:44:23 GMT|
firstname.lastname@example.org (Mike Tiller) writes:
> Is there anything to be cautious of when using LL? I looked in
> Principles of Compiler Design, but I couldn't decipher exactly what
> the pros and cons were.
There is no strict ordering between LL(k) and LALR(1); that is, I know of
one grammar that is LL(k), but not LALR(1). HOWEVER, LALR(1) has stronger
recognition strength in practice. yacc's advantage in this area has
narrowed due to PCCTS's full LL(k>1) parsing (only k=1 was commonly
available before). Strength is not the end of the story because one
rarely wants to merely recognize --> we TRANSLATE. Here, LL parsers are
the clear winner. A few highlights:
o Actions cannot introduce ambiguities into your LL grammar. All yacc
programmers say "arrgggghhh!" here.
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
o If recursive-descent compilers are generated, then local, stack-based
variables are trivial to implement. Bottom-up folks have no
*convenient* way. Local variables are useful because you get a
new one at each rule invocation; e.g. a new 'scope' variable appears
every time you enter rule 'function'.
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.
> Basically, I just use yacc (bison whatever) to parse some input
> specification files.
If you can do what you need to do with yacc and/or already have grammars
that do what you want, then there is no reason to change.
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.
One other point: The tool's programming interface is also a consideration.
Does the system allow EBNF? Can it build trees for you
automagically? Can you debug the resulting parsers
(tables vs recursive-descent) easily?
Terence Parr, email@example.com
Purdue University Electrical Engineering
Return to the
Search the comp.compilers archives again.