Re: Parser Recognition Strength

Martin Hellspong wrote:
>
> 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. :-)


First, LL parsing is precisely defined and works only with unambiguous
grammars. I guess that you have either expanded LL parser or used
the term LL parser instead of top-down parser. I am interested in the way
your algorithm handels ambiguous grammars.


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


It is very difficult if not impossible to construct a grammar not
parsable with an algorithm which is not specified.


If you consider the grammar


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


and a word ABD^nBCD^mC, for any n and m, the decision on whether to
use mid ::= pre or mid ::= pre suf cannot be made until entire word is
read. My conclusion would be: if your parser can parse this grammar,
it must postpone the decision on which production expanding the symbol
mid is to be used, until it reaches the end of the input. So you can
use modified LL(k) or LR(k) parsing which builds a tree of all possible
runs on the input word.


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


See a few lines above.


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


In any case, I am very interested in your work. Please inform me when
it will be ready for presentation.


Hope to hear from you soon, Bo"stjan




----------------------------------------------------------------------
    o o Bostjan Slivnik phone +386 61 177 3430
o o Jozef Stefan Institute fax +386 61 219 385
o o Dept. of Dig. Comm. and Networks sliva@acm.org
    o Jamova 39, 1000 Ljubljana, Slovenia http://parcae.ijs.si/~sliva
--

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