Re: LL vs LR languages (not grammars)

|> We're looking at top down vs bottom up parsers with infinite
|> lookahead. Everybody knows that LL(1) grammars are more restrictive
|> than LR(1) grammars, but are there any _languages_ which are
|> inherently LR and not LL(oo)? (LL with infinite lookahead, ie LL(k)
|> with k = oo.)


No.


LL(oo) means to always detect the right alternative corresponding to a
*uniquely determined* subtree of *the* syntax tree, if there is exactly one.
In other words, if the grammar is unambiguous (or more precisely if the
input word has exactly one parse), you will always choose the right
alternatives corresponding to this one tree *in advance*, because you have
infinite lookahead to detect this. Conversely, if there is more than one
tree, you will always get a lookahead conflict.


So LL(oo) is a parsing method which works (at least) for all unambiguous
grammars. Since LR(k) (for fixed k) ist always unambiguous, any LR(k)
grammar is also a LL(oo) grammar. You can even extend this to LR(oo),
but to see LL(oo)==LR(oo) you probably need some theory from my forthcoming
dissertation.


Now for your question regarding _languages_: It is known that any
deterministic PDA can be simulated by an LR(1) grammar, and conversely.
Hence the deterministic context free languages can can be recognized by
LL(oo). However, I suspect the converse (that LL(oo) could be simulated by a
deterministic PDA) is not true in general. This should be due to the
undecidability of ambiguity. LL(oo) can decide ambiguity at *runtime*, but
not *statically*. If LL(oo) membership were statically decidable, you could
effectively decide ambiguity, which is known to be undecidable. So you
cannot decide for an arbitrary grammar whether it's LL(oo) (in contrast to
whether it's LR(k) for fixed k), all you can do is start parsing and watch
for runtime conflicts. Note that undecidability of LL(oo) membership
parallels the undecidability of LR(oo), resp. the undecidability of finding
a k for LR(k).


In other words, since LL(oo) comprises the class of unambiguous grammars,
it is strongly more powerful than deterministic methods.


An example: First look at the language L = { a^n b^n c^m } U { a^n b^m c^m },
which is the classical example for an inherent ambiguous language. You cannot
parse this language with a deterministic PDA, because you have to either
compare the number of b's with the a's or c's, but you cannot do both
with one single stack, because you cannot move back the input like in
2-way automata.
Now we modify the language by appending a single letter in both
cases: L' = { a^n b^n c^m d } U { a^n b^m c^m e }.
This makes the language unambiguous, because the trailing d or e gives
a unique criterion. But it remains impossible to parse L' with a
*deterministic* PDA, as was the case with L (and can be seen with the
same arguments): you would need infinite lookahead to see the trailing d or e.
So you again have to decide the right alternative *in advance* if you have
only one deterministic stack. Although a deterministic PDA cannot do this,
LL(oo) can do it.


|> Note that I am assuming (1) that infinite lookahead is
|> available, so that LL problems associated with left factorisation are
|> done away with, and that algorithms to remove (2) epsilon productions
|> and (3) left recursion are also applied to the grammar. Under these
|> assumptions, is top down as powerful as bottom up?


Yes.
However, the terms "top down" and "bottom up" should not be used as
a property of LL versus LR methods, as has been done in the past
and in many text books. Both LL and and LR have top-down and bottom-up
components, and both do even (nearly) the same under a nondeterministic
point of view. Some details can be found in


@proceedings{ASMICS94,
    title = {1st ASMICS Workshop on Parsing Theory},
    organization = {Dipartimento di Scienze dell'Informazione, Universita' degli Studi di Milano},
    month = {12--14 October},
    year = {1994}
}


@misc{Sch94,
    author = {Thomas Sch\"obel-Theuer},
    title = {Towards a Unified Theory of Context-Free Parsing},
    howpublished = {1st ASMICS Workshop on Parsing Theory, Dipartimento di Scienze dell'Informazione, Universita' degli Studi di Milano},
    month = {13 October},
    year = {1994}
}


a reprint is available under
http://lite.ncstrl.org:3803/Dienst/UI/2.0/Describe/ncstrl.ustuttgart_fi%2fTR-1996-06?abstract=


-- Thomas
--

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