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

# > Only poorly designed programming languages are ambiguous. (Natural
# > languages are ambiguous and don't use deterministic language theory.)
#
# Counterexample:
# The argument list of a subroutine is nothing but a list, which can be
# expressed using either left or right recursion in a grammar.


This is not about syntax ambuigity, but operator associativity. The
language definition can define
a@b@c = (a@b)@c = a@(b@c)
for some binary operator @. The syntax should still be unambiguous,
but the language lets the compiler reorder operations.


It's important to keep associativity distinct from syntax. Some
operators are associative, some are ant-associative, and some are
not associative in any form. For example integer adds are usually
associative, but real adds are not. The precise order the operands
are summed can be critical in the stability of real arithmetic.


# The dangling else problem can be solved by adding implicit general rules
# to the interpretation of a language (or grammar?). Of course there exist
# ways to prevent the occurence of such problems, just in the language
# specification. But AFAIR it's impossible to prove, in the general case,
# that a language is inambigous.


LR(1) parser generation can only succeed for an unambiguous grammar,
in which case the language is proven unambiguous. If you avoid bison
shortcuts and resolve all reduce conflicts, you will have an unambiguous
LALR grammar and your language is unambiguous.


The dangling else was solved shortly after it was discovered by defining
open and closed statements. The solution is simple.


# > Recursive descent is not LL(k). Recursive descent is an implementation
# > technique not a language class.
#
# Okay, but what's the relationship between leftmost/rightmost derivation
# and a language?


None. It's the order in which you replace nonterminals in string
derivation. You end up with the same parse tree for the same grammar
in either case.


# I'm not sure what you want to tell me. AFAIR LR(k) (languages?
# grammars?) can be transformed into LR(1), for which a finite state
# machine can be constructed easily. I assume that a transformation from
# LL(k) into LL(1) would be possible as well, using essentially the same
# transformation algorithms.


No. LL(k+1) includes languages which cannot be LL(k). Also I don't think
there's mechanical process to convert LR(k) into LR(1), merely that it
is possible.


# My point is that table driven parsers are unreadable, due to the lost
# relationship between the parser code and the implemented language or
# grammar. Do there exist LR parsers or parser generators at all, which
# preserve the relationship between the parser code and the grammar?


Any parser can be considerred table driven with the CPU interpretting
object code. I don't concern myself with the code the parser generator
creates. I concern myself with the grammar representation I give the
parser generator.


# With regards to programming languages, there exist many constructs that
# do not impose or require the construction of an specific (unique) parse


And many that do. The language definition can declare some operators
commute or associate and some do not; that if a program's evaluation
changes when converted into what the language definition says is
equivalent, then it is the program that is at fault. Thus the
unambiguous parse trees can be transformed in a number ways by the
compiler.


--
SM Ryan http://www.rawbw.com/~wyrmwif/
GERBILS
GERBILS
GERBILS

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