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

Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:
# Arthur J. O'Dwyer schrieb:
#
# >>> # 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.)
# >> 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.
# >
# > That's a true statement, but I don't see what it's a "counterexample"
# > to.
#
# With regards to "poorly designed programming languages".
#
# After all I agree, that a language with a stricter definition leaves
# less room for different opinions about the implementation. Okay?


If the grammar is ambiguous then you don't have a guarentee what a
construct means. The compiler is allowed to translate your program
into different object programs. In a few rare cases, the different
object programs produce the same results; in these cases the ambiguity
is acceptable.


If your expression syntax is ambiguous 3-2-1 has two very different
meanings, (3-2)-1 and 3-(2-1) which produce very different results.
Because it is trivial to avoid this kind ambiguity, there is no good
reason to make the syntax ambiguous. (In fact people who do this
kind of doofus syntax are not intending to write ambiguous code: rather
they are depending on bison is straighten things out for them, thus
locking themselves into one out of date tool, becoming lazy in the
process.)


# > In the same way, it's possible to create many different "parse trees"
# > for a C-language "sentence", indicated here with indentation levels:
# >
# > if (x) if (x) if (x)
# > if (y) if (y) if (y)
# > foo(); foo(); foo();
# > else else else
# > bar(); bar(); bar();
# >
# > Only the leftmost parse tree is useful in understanding the semantics
# > of the C program; therefore, we call it "correct", and design our
# > grammars to create this parse tree in preference to the other two.
#
# How will you determine, in this special case or in general, which
# grammars or parse trees are "correct"?


This issue was solved a long time ago. Apparently the solution
has been forgotten.


<statement> ::= <closed statement> | <open statement>
<closed statement> ::= <assignment> | <block> | <closed if> | <closed while>
<open statement> ::= <open if> | <open while>
<open if> ::=
if <predicate> then <statement>
| if <predicate> then <closed statement> else <open statement>
<open while> ::= while <predicate> do <open statement>
<closed if> ::= if <predicate> then <closed statement> else <closed statement>
<closed while> ::= while <predicate> do <closed statement>


--
SM Ryan http://www.rawbw.com/~wyrmwif/
Raining down sulphur is like an endurance trial, man. Genocide is the
most exhausting activity one can engage in. Next to soccer.

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