Re: [boost] [proto] grammar matching issue

From: Larry Evans (cppljevans_at_[hidden])
Date: 2007-06-14 13:51:09

On 06/14/2007 11:57 AM, Eric Niebler wrote:
> Maurizio Vitale wrote:
>> if you could find a way to completely hide the fact that a terminal is
>> a unary_expr from the user I think it would be much cleaner for
>> a boost::proto release.
> 
> I'll give the issue some thought. One possibility is shoehorn into proto 
> the concept of a nullary expression, which is what terminals should 
> rightly be. Of course, what is there already works, so IMO there are 
> bigger fish to fry first.
> 

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)

where + and * is a binary operators in the target algebra.  Their
definition are defined for empty_not and empty_yes in
the obvious way.  e.g.

    empty_not | X == X
    empty_yes | X == empty_yes
    empty_not * X == empty_not
    empty_yes * X == X

and a grammar's productions can be transformed into a set
of equations in the derives_empty algebra whose solution
define the empty attribute for each grammar expression.
This is, in essence, what the statement:

   this->attr_fixed_point<attr_empty >(maxit);

on line 1348 of:

http://svn.boost.org/trac/boost/browser/sandbox/boost/grammar_pipeline/eff/productions.hpp

does.  I've been struggling with doing the same in proto, but haven't
been successful yet.  Maybe transforming proto to a more "algebraic
orientation" would ease the solution.  However, without actually doing
this transform (which would be a lot of work, I guess), that's just
guessing; however, it is something to consider.

-regards,
Larry