Is pyparsing really a recursive descent parser?

[Chris Mellon]

On Nov 7, 2007 5:15 PM, Just Another Victim of the Ambient Morality
<ihatespam at hotmail.com> wrote:
>
> "Chris Mellon" <arkanes at gmail.com> wrote in message
> news:mailman.945.1194471797.13605.python-list at python.org...
> > On Nov 7, 2007 3:15 PM, Just Another Victim of the Ambient Morality
> > <ihatespam at hotmail.com> wrote:
> >
> >> > In short, it hasn't really evovled into a user-friendly package
> >> > yet.
> >>
> >>     Thank you.
> >>     How is it that I seem to be the only one in the market for a correct
> >> parser?  Earley has a runtine of O(n^3) in the worst case and O(n^2)
> >> typically.  I have trouble believing that everyone else in the world has
> >> such intense run-time requirements that they're willing to forego
> >> correctness.  Why can't I find a pyparsing-esque library with this
> >> implementation?  I'm tempted to roll my own except that it's a fairly
> >> complicated algorithm and I don't really understand how it's any more
> >> efficient than the naive approach...
> >
> > You have an unusual definition of correctness. Many people would say
> > that an ambiguous grammar is a bug, not something to support.
>
>     I don't think I do.

There are an enormous variety of parsing tools, and it's the subject
of much research. And in all those tools, not one meets your
definition of correctness? You don't think that might make it unusual?


> Besides, you assume too much...
>     First off, we've already established that there are unambiguous grammars
> for which pyparsing will fail to parse.  One might consider that a bug in
> pyparsing...

You might. Or you might not, since it's well known that there are lots
of types of parsers that can't parse all possible grammars, but that
doesn't make those parsers useless.


>     Secondly, I get the impression you want to consider ambiguous grammars,
> in some sense, "wrong."  They are not.

Sure they are, at least in many contexts. I understand that you want
support for them, but it's by far more common to want one and only one
set of results from parsing a particular document.

>Even if they were, if you are
> parsing something for which you are not the creator and that something
> employs an ambiguous grammar, what choice do you have?

You either disambiguate, or you don't accept ambiguous input. The
third option seems to be what you want, which is to find all possible
solutions and return all of them (and wouldn't this be NP-hard in the
general case?) but that's not a satisfactory result in most
applications.

> Furthermore, given a
> set of possible parsings, you might be able to decide which one you favour
> given the context of what was parsed!  There's a plethora of applications
> for parsing ambiguous grammars yet there are no tools for doing so?
>

If you can do this, isn't this really a sign that your grammar is
context sensitive?

>
> > In fact, I often use pyparsing precisely in order to disambiguate
> > (according to specific rules, which are embodied by the parser)
> > ambiguous input, like bizarre hand-entered datetime value.
>
>     What do you mean?  How do you use pyparsing to disambiguate:
>
>
>     01-01-08

The same way a human would - given an ambiguous date such as this, I
(arbitrarily) decided what it would mean. The alternative is to refuse
the input.