2 Jul 1996 12:35:01 -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: | ikastan@alumnae.caltech.edu (Ilias Kastanas) |

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

Date: | 2 Jul 1996 12:35:01 -0400 |

Organization: | Caltech Alumni Association |

Expires: | July 13, 1996 |

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

Keywords: | parse |

Thomas Schoebel-Theuer <schoebel@minnie.informatik.uni-stuttgart.de> wrote:

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

With this definition, LL(oo) seems to be indulging in what one might

call 'focused nondeterminism'. It is possible to simply posit the defi-

nition and work with it... but since it is somewhat conclusory, an attempt

at PDA implementation is: allow nondeterminism, say using the backtracking

model, but make it exhaustive. That is, continue exploring choices even

after a successful computation, instead of announcing it. If it proves to

be the only one, then and only then accept.

The case of the perfectionist backtracker.

It is clearer under the replicant model, the PDA spawning clones at

every instance of a choice. Each clone reaches a conclusion (assuming

Greibach normal form, maybe) and the presence of two or more "accept"s

blows a fuse.

Ignoring the details of LL or LR, does this properly describe

infinite lookahead?

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

In a prior posting I suggested a simpler kind of lookahead -- and

weaker than the one above. Rephrasing it: the PDA enters a special state

and places a marker under the reading head (or: unconsumed input carries

a special starting symbol %). From then on it can read input without

consuming it, and can make transitions into subspecial states, but cannot

use the stack. There is a special state for returning to normal mode,

upon reading the marker (or the %) and with more than one transition (to

"report" the outcome of this foray). In short, 2-way FA operation. We

could call this LLL, lookie-loo lookahead.

It can carry out some lookahead tasks beyond fixed k. I don't know

whether it corresponds to something known.

*>An example: First look at the language L = { a^n b^n c^m } U { a^n b^m c^m },*

[ . . . ]

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

LLL can do it, too, obviously enough. It only needs to look -- go

out and see the 'd' or the 'e'.

But LLL is less than LL(oo): one can change the example and foil

lookie-loos. Replace 'd' by f^i g^i, and 'e' by f^i g^(i+1), say.

Now it takes work to 'read' the criterion.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.