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

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?




> 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"?








> Those are my main points. Following are nitpicks.
>
>> 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?
>
> Again, you seem to confuse human-centered subjective terms like
> "preserve the relationship" with measurable terms. Obviously there is
> /some/ kind of special relationship between a yacc-generated parser
> and its target language --- something that makes it parse C and not
> Java or pig Latin. You're complaining that the relationship isn't
> close enough to the surface for humans to see --- but why is that
> important?


Consider that typically you want to add actions to a grammar. Then you
must know about the context (stack contents...), in which your code will
execute.


Finally you may want to debug your grammar and your code. In case of an
recursive descent parser, the call stack contains much information about
the parser state, whereas debugging the state transitions of an
automaton requires additional debugging features.




> After all, the point of table-driven parsers is that humans never
> /need/ to see the generated code. It "just works."


I found some yacc clones, which all just do *not* work. Now tell me how
somebody should figure out, what makes these tools misbehave :-(


DoDi

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