Re: LL vs LR languages (not grammars)

>A Johnstone wrote:
>| We're looking at top down vs bottom up parsers with infinite
>| lookahead. [...] are there any _languages_ which are
>| inherently LR and not LL(oo)? (LL with infinite lookahead [...])


>Jerry Leichter <leichter@smarts.com> writes:
>>I'm not sure what L(oo) would be.


Fergus Henderson <fjh@mundook.cs.mu.OZ.AU> wrote:
>Judging by the crossposting, I suspect A Johnstone was talking about LL
>parsers with backtracking, as is supported by PCCTS. An LL(1) parser with
>backtracking would not have any difficulty with your example language


>> L = { x^{2n}y^{2n} e, x^{2n+1}y^{2n+1} o}


>because it could try the first (even) alternative, and then if that
>failed it could backtrack and try the other (odd) one.




Some care is needed in defining precisely what exactly
      constitutes backtracking.


It would seem that backtracking allows one to recognize
      non-CFLs like {a^n b^n c^n}; after checking that # of b's =
      # of c's, the machine backtracks and checks a's versus b's...


Lookahead for a fixed number of symbols can be simulated
      in a PDA's finite control; here, however, we have something
      different -- as far as I can tell.


I have not worked with PCCTS and am not familiar with it;
      if there is an answer implicit there, I hope someone will kindly
      post it!


Ilias
--

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