Re: Crenshaw's Tutorial

Rearranged a bit for readability.




On 10 Feb 2000 01:16:03 -0500, "Joachim Durchholz"
<joachim.durchholz@halstenbach.com.or.de> wrote:


>Jack Crenshaw <jcrens@earthlink.net> schrieb:
>>
>> One big advantage of an LALR parse is that it can handle syntax
>> constructs that LL (recursive-descent) parsers cannot. That is true.
>> But these constructs rarely show up in practice, and there is at least
>> a reasonable argument that if you're designing a programming language,
>> you would be better off to choose one that _IS_ easily parsed.
>


C, C++, Java, ADA, SQL and Fortran are not LL(1) [Fortran is LL(k)
with a large k]. I agree with your comment about language design, but
it seems that the languages most people use don't adhere to it.




>Two remarks are in order here.
>
>1) I'm not aware of any consensus about which form of grammar is more
>"natural" or "easily parsed". For example, the LL paradigma is "give
>me the first symbol and I'll know what comes", while LR says "give me
>the left context and I know what comes".


LR actually says "give me the left context and the next symbol(s) and
I'll see if I can transition to a new left context". If a transition
isn't possible because of ambiguity, LR can buffer additional symbols
outside the context in anticipation (not prediction) of an eventual
successful transition to a new context.


LR explicitly looks at the context, any buffered symbols and the
lookahead symbol(s) when deciding what to do. In LL, the context is
implicit and decisions are based solely on the lookahead symbol(s).




>... Which of these is easier to read for a human is something that I'd
>really like to know.


>2) Non-LL languages may be rare (I don't really know) ...


Human languages are ambiguous and we tend to process language in an
LR-like way: we construct a context, look at the next symbol and try
to make a coherent adjustment to the context. If the new context
would be ambiguous, we accumulate and buffer new symbols until the
context plus the buffer is coherent [to the tolerance of the reader]
or until we decide that the sentence is gibberish and give up.


Because LR(k) is more powerful than LL(k) for any k, it follows that
humans should read a sentence in either form equally well.






BTW: it could also be argued that humans use predicated LL and
parallel alternative evaluation, but I don't think that is actually
true. Studies have shown that conscious thought tends to work
serially and short term memory can hold only a limited number of
symbols (about 10) at any one time. I do believe that we employ
parallelism in resolving the symbols to ideas - but not in
linguistically parsing the symbols.






George Neuner
Dynamic Resolutions, Inc.

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