Re: Trouble understanding LL(k) vs. LALR(k) etc.

Just an answer to one of your questions:


> Statements = <Statement> | <Statements> <Statement>


This is LEFT recursion. See, how Statements is on the left end of the
second alternative (i.e. <Statements> <Statement>) and it is also the
thing being defined. That is the definition of left recursion, the
thing being deined appears on the left end of one of the definitions.
In right recursion, you write the alternative in the other order
(i.e. <Statement> <Statements>). You must use right recursion if you
want your grammar to be LL(1).


There is, as you appear to know, a simple transform from a right
recursive grammar to a set of recursive routines that parse the
language. This is the essence of recursive descent parsing. If you
naively apply the transformation to a left recursive grammar, you can
still get code out, but the code doesn't work, because the program
stack overflows while trying to execute the left recursive procedure.


A recursive descent parser generator like ANTLR or JavaCC makes the
checks to see that grammar is well-formed as it does the
transformation, assuring you that you will have a working parser when
you get done.


From a "learning" perspective, I would write a tiny (say five rule)
grammar that I translated by hand into its recursive descent solution.
I would then take the same grammar and feed it to an LL parser
generator and see the code the tool generated, and use that to
understand the tools output. After that, I would not generate another
recursive descent parser by hand.


I WOULD NOT do my entire BASIC parser by hand. There is little to be
learned by doing a grammar of that size (that can't be seen in a small
example).


Note, tools like Yacc and Bison implement LR parsing which allows left
recursion, but generate a model that is more removed from the simple
recursive descent approach. Some people don't like these tools
because they cannot fathom how the generated output implements the
parser the same way that simple recursive descent tools do.


If you want to learn the LR approach also, which I would personally
recommend that you do, I would suffer through reading a testbook on
it. Again, one can learn the technique quite adequately from a 5 rule
grammar. Note, if you find the testbook tough sledding, enroll in a
course. The LR method is well understood and someone will be able to
explain the points you are caught up on.


Finally, it isn't generally hard to write a LL grammar for most
programming languages if one simply uses right recursion. The only
tricky part is describing the "expression" part of a grammar which
gets the precendence and associativity right. That's because
expression grammars are "naturally" both left-and-right recursive and
one associates the precedence and associative rules with the operator
in the middle. Translating these rules into the hierarchy of term,
factor, etc. takes some thought until one gets confortable with it
(although it is an emminently learnable skill and many people can
write such rules without conscious thought). The rest of us simply
find an LL grammar that someone else has written and "borrow" the
expression rules from it (or use one of the yacc-derived tools that
allow the "natural" expression rules to be applied).


In any case, if you use an LL generator and instinctively avoid right
recursion, you will almost naturally write an LL grammar (and the tool
will tell you when you have failed)--the LL grammar you are likely to
write will also certainly be an LALR grammar also (and, in fact, most
LL grammars are LALR grammars, while the reverse is not true). The
only thing that will be hard to deal with is if you introduce
left-recursion indirectly and that's not likely unless you have
mutually recursive concepts like a statement is a declaration and a
declaration is also a statement. You're not likely to do that in a
BASIC grammar.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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