Re: LL vs LR languages (not grammars)

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

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