RE: Why LL(1) Parsers do not support left recursion?

Chris noted:


> Quinn's grammar into Andru's, and these hueristics are commonly
> applied by LR parser generators and camoflague the fact that Quinn's
> grammar is actually ambiguous.


Whoops. Yes. I knew it was also ambiguous, but was only looking at the left
recursive aspect of it. That's what I get for running off half-loaded with
my example. A better example might have been:


list ::= list COMMA item | item;
item ::= NUMBER | STRING_LITERAL;


Or some such. This could be expressed right recursively by changing list to:


list ::= item COMMA list | item;


The left recursive form might be the preferred form for a LR parser, since
it could, in theory, parse a very long list without producing a horrendously
deep stack in the process, whereas the right recursive form will tend to
produce a deep stack. The left recursive form precludes parsing by LL
methods, the right form is acceptable to LL (and still results in a very
deep stack with very long lists). A typical work around in the LL world is
extended BNF like this:


list ::= (item COMMA)+ | item


Sometimes written


list ::= {item COMMA} | item


This produces an iterative parser that doesn't build a deep stack, and is
also not recursive. (There's nothing to stop an LR parser generator author
from using those extensions to do the same thing, but since the left
recursive form does the same thing, there's no perceived need for such
extensions, perhaps.)


Now, in a similar tone to "heuristics are commonly applied ... to camouflage
the fact...", Dodi said (in another message in this thread):


> It's not a matter of the parser, but instead of the parser generator. I
> see no reason why a parser generator should be able to create an LR
> parser for the original grammer, but not an LL parser. And, for
> completeness, a parser generator IMO should reject the grammar anyhow.


It's easy to catch (either direct or indirect) left recursion in an LL
generator and then generate a build error. This, IMO, is the preferred
method.


Although in some cases, it's also possible to generate a left-factored
version of the rule and quietly generate an equivalent grammar that doesn't
contain the left-recursion, I've always been against invisible fixes of what
are fundamental grammar construction issues. (Such modifications can produce
inexplicably deep parse trees that contain nodes that were manufactured by
the generator to bypass the issue, for example, and I prefer nodes to come
from explicitly stated rules rather than something the generator dreamed
up.)


Adaptive grammars that use an LL algorithm to effect a parse come up with
another problem with left recursion. It may not be knowable until run time
(in the middle of a parse) whether or not a grammar is left-recursive:


x ::= (y|z) COLON list
y ::= /* something that sets foo to non-lambda */
z ::= /* something that sets foo to lambda */
list ::= foo list COMMA item | item;


x follows the z path, list is left-recursive at run time. Although it is
technically possible to strictly detect this at grammar-compile time "in the
simple case", one cannot do it "in the general case" because of Turing
Power, and foolproof predetermination that foo cannot/can be empty implies a
solution to the Halting problem. The adaptive(k) algorithm allows list but
fails at run-time if foo is lambda. (It does this by using a sanity check on
stack depth when list is entered; if foo is empty, that sanity check will
fail when the stack quickly hits the upper limit).


(Please note that I wrote this email in haste -- all blunders my own.)


--
Quinn Tyler Jackson


http://press.ChevalierEditions.com

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