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 <pt93mhe@student.hk-r.se>
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

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