Re: Parser Recognition Strength

cathy hynson <>
23 Sep 1997 23:29:32 -0400

          From comp.compilers

Related articles
Parser Recognition Strength (Martin Hellspong) (1997-09-12)
Parser Recognition Strength (1997-09-15)
Re: Parser Recognition Strength (cathy hynson) (1997-09-23)
Re: Parser Recognition Strength (Bostjan Slivnik) (1997-09-23)
| List of all articles for this month |

From: cathy hynson <>
Newsgroups: comp.compilers
Date: 23 Sep 1997 23:29:32 -0400
Organization: Equator Technology Consulting
References: 97-09-041
Keywords: parse

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

> 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

Post a followup to this message

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