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

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
          parsing.


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
--

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