Re: LR(1) Parsing : Error Handling & Recovery

On Wed, 16 Jul 2014 16:39:09 -0400 (EDT), Ivan Godard
<ivan@ootbcomp.com> wrote:


>As a practical matter, natural languages are pretty much LL1 (German
>verbs excepted)


Obviously you haven't read any legal briefs lately 8-)


Natural languages are contextual. Neither LL(1) nor (LA|S)LR(1) can
parse a contextual language - both are limited to context-free
languages.


GLR and PEG theoretically can parse contextual languages. It is
thought that LL(*) - LL with unlimited lookahead - may be able to as
well, but AFAIK, there has been no formal proof offered for this.




>so people are reasonably familiar to quasi-linear parsing.


Studies have shown that human parsing of language is both top-town and
bottom-up simultaneously.




>Nearly all languages yield to LL1 techniques (the formal proofs
>that a language is not LL1 are irrelevant) ...


Yes ... most useful context free languages can be contorted into
LL(1). But it's a lot easier just to use an LL(k) tool.


In theory, any LL(k) language can be refactored to be LL(1), but
refactoring a "greater than small k" language is usually impractical
due to explosive growth of the resulting LL(1) grammar.


George

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