1 Jul 1996 10:20:07 -0400

Related articles |
---|

LL vs LR languages (not grammars) platon!adrian@uunet.uu.net (1996-06-24) |

Re: LL vs LR languages (not grammars) leichter@smarts.com (Jerry Leichter) (1996-06-26) |

Re: LL vs LR languages (not grammars) ikastan@alumnae.caltech.edu (1996-06-30) |

Re: LL vs LR languages (not grammars) fjh@mundook.cs.mu.OZ.AU (1996-06-30) |

Re: LL vs LR languages (not grammars) schoebel@minnie.informatik.uni-stuttgart.de (1996-07-01) |

Re: LL vs LR languages (not grammars) ikastan@alumnae.caltech.edu (1996-07-01) |

Re: LL vs LR languages (not grammars) ikastan@alumnae.caltech.edu (1996-07-02) |

Re: LL vs LR languages (not grammars) schoebel@minnie.informatik.uni-stuttgart.de (1996-07-05) |

From: | schoebel@minnie.informatik.uni-stuttgart.de (Thomas Schoebel-Theuer) |

Newsgroups: | comp.compilers,comp.compilers.tools.pccts |

Date: | 1 Jul 1996 10:20:07 -0400 |

Organization: | Department of Computer Science, University of Stuttgart, Germany |

References: | 96-06-103 96-06-109 |

Keywords: | parse |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.