Re: spirit grammar graphs

Hi Joel -

On Apr 1, 2011, at 7:33 AM, Joel de Guzman wrote:
> Just a quick note for now: FYI, classic Spirit had subrules and has been
> ported to Spirit2 recently. Anyway, see:
> 
> http://www.boost.org/doc/libs/1_41_0/libs/spirit/classic/doc/subrules.html

Thanks for the informative link!  Very cool to know that this was working in the full Spirit at some point, and is returning.

BTW, what is the meaning behind the name "subrule" - is it this curious grouping syntax?  Or is that they are always put under a regular type-erased rule?  Looks powerful.  Seems like it could be used to optimize critical parts of large grammars too.

> There's a long history in there and in fact, this predates fusion and
> also became a motivation for fusion. Why is it not a full fledged citizen in Spirit2 yet? That's another long story. I'll keep this short for now.

I hope to hear it sometime.

My motivation, again, is threefold:
* to understand Spirit's usage of tying-by-type to talk about it as an example of ad-hoc compile-time graphs
* to learn from the code to implement an EDSL for compile-time and "fusion" graphs
* to see if a compile-time graph ADT can help Spirit

Is the main difficulty the size of expressions?  I am imagining a way to paste together trees to form graphs, so at least it wouldn't all have to be in one expression.  I guess it requires auto, or type unerasure (impossible right?).

As I think you mentioned in one of the Spirit talks, having a complete compile-time view would allow things like spotting left-recursion & some forms of epsilon-star.  Probably some other validations/optimizations.  And of course, implementing LR (although even I in my meta-fanaticism admit that's kind of ridiculous).

(A graph metadata structure might or might not help.)

Cheers,
Gordon

P.S. Thanks Larry!


------------------------------------------------------------------------------
Create and publish websites with WebMatrix
Use the most popular FREE web apps or write code yourself; 
WebMatrix provides all the features you need to develop and 
publish your website. http://p.sf.net/sfu/ms-webmatrix-sf