LL vs LR, no jihad initiation, but...

parrt@ecn.purdue.edu (Terence J Parr)
Mon, 11 May 1992 02:44:23 GMT

          From comp.compilers

Related articles
LL vs LR, no jihad initiation, but... parrt@ecn.purdue.edu (1992-05-11)
Re: LL vs LR, strengths and weaknesses eifrig@blaze.cs.jhu.edu (1992-05-11)
Re: LL vs LR, no jihad initiation, but... dww@inf.fu-berlin.de (1992-05-12)
Re: LL vs LR, strengths and weaknesses reid@csgrad.cs.vt.edu (1992-05-13)
LL, LR debate scott@cs.rochester.edu (1992-05-13)
Re: LL vs LR, strengths and weaknesses mauney@adm.csc.ncsu.edu (1992-05-13)
Re: LL vs LR, strengths and weaknesses ressler@cs.cornell.edu (1992-05-14)
[10 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: parrt@ecn.purdue.edu (Terence J Parr)
Keywords: LL(1), LR(1), parse
Organization: Compilers Central
Date: Mon, 11 May 1992 02:44:23 GMT

tiller@solace.me.uiuc.edu (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, parrt@ecn.purdue.edu
Purdue University Electrical Engineering

Post a followup to this message

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