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

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2001-06-02 10:46:58

Ed Brey wrote:

> From: "joel de guzman" <isis-tech_at_[hidden]>
> >
> > I tried for example to find logic behind my dislike for +
> > for concatenation. Addition is *not* concatenation, I
> > asserted. Addition implies a + b = b + a. Commutative.
> > I opted for a non-commutative operator. That was one
> > of the reason for Spirit's use of >>, after all I believe
> > arrows clearly denote sequencing.
>
> Commutatively is a property of the semantics of an operation.  Since grammar
> is not related to math and doesn't have a concept of addition, there is no
> reason to expect + to follow addition's commutative semantic.  Contrarily,
> std::string has the concept of concatenation, which is represented by a
> non-commutative +.  Since a grammar uses the same concept of concatenation
> as std::string, it is logical to use the same operator.

I believe * and + should instead be used for concatenation and alternation.
The main reason is, as I think Colvin mentioned, it "fits" better with regular
grammars.  For example, a RE language can be expressed as a set of
linear equations and solved for the start symbol with, at least some,
linear equation solvers.  For example:

     X = 'a' * X + 'b'

In math,  X is solved for by:

     (1 - 'a')*X = 'b'
     X = 'b'/(1-'a')

where, 'b'/(1-'a') in BNF is a*b.  So if * and + are used, we might could
use a boost templated linear equation solver to find solutions.  OTOH, this
solution method is probably not be practical because there are more efficient
solution methods.  But it would make boost linear equation solvers more
reusable if someone is only interested in a result and not so much
in the speed.