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

# 1. LL parsers cannot handle left recursion, whereas LR parsers cannot
# handle right recursion.


A left recursive grammar is not an LL(k) grammar, but the grammar can
be mechanically transformed to rid it of left recursion. The resulting
grammar might still not be LL(k).


LR(k) can handle any deterministic grammar. Left recursive productions
only need one production on the stack; right recursion piles up the
entire recursive nest on the stack and then reduces all of them at
once: right recursion requires a deeper stack.


# 2. Most languages are ambiguous at the syntax level, so that implicit
# disambiguation (longest match...) or explicit semantical constraints
# must be introduced. (see: dangling else...).


Only poorly designed programming languages are ambiguous. (Natural
languages are ambiguous and don't use deterministic language theory.)


Many programming language grammars are ambiguous because the people
writing the grammars are lazy and/or uneducated in these matters. The
dangling else nonproblem was solved some 40 years ago. Anyone who
thinks this is still a problem is just too lazy to write a well known
solution.


# 3. Only LL(1) recursive descent parsers are readable, that's why no
# LL(k) parser generators exist, in contrast to LR(k) parser generators.


Recursive descent is not LL(k). Recursive descent is an implementation
technique not a language class. There are recursive ascent parsers for
LR(k) grammars. LR(k) parsers can be written as recursive finite state
transducers, with right recursion and embedding requiring recursion
and left recursion merely looping; if a language uses left recursion
only (type iii), the LR(k) state diagram is easily convertible to a
finite transducer for the language.


# 4. When at least one terminal must be consumed, before a recursive
# invocation of a rule, no infinite recursion can occur. (every loop will
# terminate after all terminals in the input stream have been consumed)


Confusing implementation with language class. Any grammar that
includes a rule such as A -> A | empty is ambiguous therefore
nondeterministic therefore not LR(k) therefore not LL(k). There are
many other things that keep a grammar or language from being LL(k);
LL(k) does not include all deterministic languages.


# Ad (1+2): We should keep grammars apart from languages. Most languages
# require recursive grammars, but allow for both left or right recursive
# grammars.


A language definition that does not depend on vague handwaving (one or
two such definitions actually exist) bases the semantics on the parse
tree. Since right and left recursion build different parse trees, this
issue is very important in definitions with riguous semantics.


# Languages with "expr '+' expr" or "list ',' list" can be parsed in
# multiple ways. Unless there exist additional (semantical) restrictions,
# correct and equivalent left or right recursive grammars can be
# constructed for such languages.


Or just write an unambiguous production. It's not any harder to do it
right than to do it lazy and wrong.


If the semantics of a subtract production are the value of the right
subtree is subtracted from the value of left subtree, then
3 - 2 - 1
with left recursion is
= (3 - 2) - 1 = 1 - 1 = 0
with right recursion is
= 3 - (2 - 1) = 3 - 1 = 2


Rather different answers but unless your software is controlling a
satellite to Venus, I guess sloppiness can be repaired in the next
patch release.


Algol-60 used left recursion except exponentiation so that the value
could be determined from the parse tree without a lot misreadable
prose.


# And when a human is allowed to disambiguate a grammar for such a
# language himself, a parser generator should be allowed to do the same ;-)


hy bother inserting ambiguity and then remove it again with obscure
rules? Eschew ambiguity from the onset.


--
SM Ryan http://www.rawbw.com/~wyrmwif/
You face forward, or you face the possibility of shock and damage.

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