Re: Parser Recognition Strength

Martin Hellspong wrote:
    [somewhat contrived non LL(k)/LR(k) grammar example]
> * Question: Is anyone aware of another parser/algorithm that can
> handle grammars like that?


Any algorithm that uses backtracking will have little difficulty with
such a grammar. For a version of yacc (LR(1)) + backtracking, take a
look at <http://www.siber.com/btyacc/>


> We ARE aware that there are algorithms, (we know of CYK and Earley),
> that can handle any context-free grammar, but we have not found any
> examples of grammars parseable with CKY that we cannot parse. Please
> do hit us with a serious CKY-only CFG!


Well, if you look at real languages, these kind of contrived grammars
don't really occur. What DOES occur is AMBIGUOUS grammars, with
random rules expressed in english as to how the ambiguities should be
resolved. No parser scheme can really deal with such things directly,
so it mostly comes down to what extra tools your parser-generator
provides for resolving these ambiguities. Backtracking is pretty good
for dealing with real languages, since you can generally specify an
order in which to try things and take the first one that works. An
example here is C++, which has several ambiguities that need to be
resolved in this way.


Of course, you can in general always rewrite the grammars to remove
the ambiguities, but doing so is non-trivial and often results in an
exponential growth of the grammar.


Chris Dodd
chrisd@collins.com
--

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