Parser Recognition Strength

Martin Hellspong <pt93mhe@student.hk-r.se>12 Sep 1997 21:27:08 -0400

From comp.compilers

Related articles
Parser Recognition Strength pt93mhe@student.hk-r.se (Martin Hellspong) (1997-09-12)
Parser Recognition Strength clark@quarry.zk3.dec.com (1997-09-15)
Re: Parser Recognition Strength chrisd@etcons.com (cathy hynson) (1997-09-23)
Re: Parser Recognition Strength Bostjan.Slivnik@ijs.si (Bostjan Slivnik) (1997-09-23)
| List of all articles for this month |

 From: Martin Hellspong Newsgroups: comp.compilers Date: 12 Sep 1997 21:27:08 -0400 Organization: Compilers Central Keywords: parse, LL(1), question

I am involved in writing my software engineering master thesis
together with a classmate, and we have developed a quite powerful (in
our own opinion, anyway) LL parser, and we want to compare
it to other parsers and algorithms available, with your help...

Therefore we have one challenge and one question for you all:

* Challenge: We think our parser can handle *any* context-free grammar
correctly, so we challenge everybody to present us with a really
difficult grammar (in terms of parsing complexity, not size) that
you think our parser cannot handle. The grand prize is to make us
really disappointed that our algorithm was not as smart as we
thought, however we are confident you will not be able to find such a
grammar. :-)

In order for you to know something about the power of our algorithm,
we present a grammar that we can parse, but that we have not found
any other (see below) parser that can:

top ::= A mid suf
mid ::= pre suf | pre
pre ::= B
suf ::= C

For instance, any LL(k) or LR(k) grammar will fail if you make "pre"
or "suf" contain more than k tokens.

* Question: Is anyone aware of another parser/algorithm that can
handle grammars like that?

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!

We are also aware that it is possible to rewrite the grammar so that it
becomes "easier" to parse, but since our parser can handle this
grammar without rewriting it, we would be very interested in knowing
if any other parser can handle the grammar *without* rewriting it.

Thank you...
--
Martin Hellspong - pt93mhe@student.hk-r.se
Software Engineering, Master Year.
University of Karlskrona/Ronneby, Sweden
W3page: http://www.student.hk-r.se/~pt93mhe
Thesis: http://www.student.hk-r.se/~epidemic
--

Post a followup to this message