Re: [boost] Re: [ANN] Spirit C++ parser framework.

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.