Re: [boost] [proto] grammar matching issue

From: Eric Niebler (eric_at_[hidden])
Date: 2007-06-14 14:42:52

Larry Evans wrote:
> I think the nullary expression concept is good.  I've been trying to
> see how proto relates to algebra's and their transforms (or homo 
> morphisms), and algebra's have nullary expressions (true and false
> are nullaries in bool algebra) and the transform
> from one algebra to another map the nullaries of the source
> algebra to nullaries of target algebra.  Now one particular
> algebra relevant to proto and spirit and deterministic parsing
> is what I'll call the "derives_empty" algebra.  Expressions in
> this target algebra are created by a transform from a source
> algebra which is the algebra of grammar expressions.  In that
> transform (call it gram_to_empty), the transforms are:
> 
>    gram_to_empty(terminal) :-> empty_not
>    gram_to_empty(epsilon)  :-> empty_yes
>    gram_to_empty(non_terminal) :-> empty_unknown
>    gram_to_empty(E0 | E1 | ... | En) :->
>        gram_to_empty(E0)
>      + gram_to_empty(E1)
>      + ...
>      + gram_to_empty(En)
>    gram_to_empty(E0 >> E1 >> ... >> En) :->
>        gram_to_empty(E0)
>      * gram_to_empty(E1)
>      * ...
>      * gram_to_empty(En)
> 

<snip>

The presence or absence of terminals as nullary expressions in Proto 
doesn't affect your ability to implement this transform in Proto. The 
transform would be pretty straightforward, I think. I think it would 
make a terrific example, actually. I've been working on the docs for 
Proto's transforms. You can find the latest here:

http://boost-sandbox.sourceforge.net/libs/proto/doc/html/boost_proto/user_s_guide/tree_transformations.html

Check out the examples for fold<>, fold_tree<> and applyN<>. I think 
they would be the most useful ones for this problem.

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com