Boost logo

Boost :

From: Greg Colvin (gcolvin_at_[hidden])
Date: 2001-05-24 12:12:38


From: Vladimir Prus <ghost_at_[hidden]>
>
> This is an add-on to my previous message, which was send unfinished by
> mistake.
>
> >>It is therefore necessary to establish which grammars are suitable.
> >>This can be done through experiment only.
>
> Greg Colvin wrote:
> >And by understanding, theoretically, just what kind of parser
> >Spirit is, and what the known performance characteristics of
> >that kind of parser are.
>
> Joel de Guzman wrote:
> >Scope? Well admittedly, the original intent of Spirit is for small to
> >medium sized grammars. Internet protocols, files, html, xml, scripting
> >languages, possibly basic variants, pascal variants, pre-processors,
> >resource description, lexers, and yes I intend to use Spirit as an engine
> >for another parser.
>
> Theoretical study is not likely do give us much. Backtraing parser have
> exponetial complexity in worst case, and "high priests" would find their use
> impossible.

It wasn't clear to me from the documentation that Spirit is a
backtracking parser. If it is then, yes, theory says it will
have exponentional worst case complexity.

It is even less clear to me that Spirit *must* be a backtracking
parser. Some have suggested that an Earley parser would be better.

> Therefore, what I would like in the end, is the statement in documentation in
> the form: "Spirit has been used in practice for such-and-such tasks, has
> shown such-and-such performance and is considered suitable for those tasks".
> Hope that once it works with g++/bcc somebody will try it for his real
> problems.

Again, I think it is well understood what kind of grammars and
inputs lead to worst-case backtracking.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk