Re: Newbie Question re: Transforming a domain specific language.

[Hans Aberg]

On 2004/11/22 21:21, Matt Friedman at address@hidden wrote:

> I'm quite the newbie here.

Pleasemake sure to cc replies to Help-Bison -- a lot of newbies here forget
that. :-)

>I'm an experienced programmer but have
> recently found a need to implement a small domain specific language.
> Not only do I need to implement the language but I need to transform
> it into something a little more friendly for another group to
> interpret.  If this is the wrong list or a bad topic perhaps you can
> let me know and steer me in the right direction.
> 
> Here is the basic idea of the language. I need the user to be able to
> specify sets of things as such:
> 
> Set1 UNION Set2 INTERSECTION Set3 UNION !Set4

In order to get this, you can merely take the calculator (mfcalc) example
from the Bison manual, and change
  "+" -> UNION
  "*" -> INTERSECTION
  unary "-" -> COMPLEMENT.

> So finally, to my question: is this a job for a language
> generator/parser and if not, has anyone been faced with this challenge
> and how might I approach it? Any pointers would be greatly
> appreciated.

In addition, the tokenization is conveniently done using Flex:
  Help-flex mailing list
  address@hidden
  http://mail.gnu.org/mailman/listinfo/help-flex

> In particular, I need to be able to produce an equivalent expression
> without the brackets. To demonstrate I can show that:
> 
> Set3 INTERSECTION (Set1 UNION Set2)
> 
> is the same as:
> 
> Set3 INTERSECTION Set1 UNION Set3 INTERSECTION Set2
> 
> This can be applied to any arbitrarily complicated expression that
> uses brackets such that the resulting expression yields the same
> result but has no brackets. The non-bracket version can be executed
> step-wise, whereas the version with brackets has a hierarchical
> structure. For legacy reasons, the group I am passing this onto wants
> to be able to execute a series of steps in a linear fashion without
> having to worry about the hierarchical part.

The above takes care of the parsing problem. One can then define parsing
actions which either produces the computations immediately, or more often,
some other object that can be activated at a suitable point in time. This
can be some kind of runtime closure, or some output code to be executed in
another language.

It is not clear if you merely want to compute those sets, or if you want to
be able to compare those expressions abstractly, to check if they are equal.
For the latter question, there is a theorem in propositional calculus that
perhaps can be used in some form: It says that two logical expressions are
equal exactly when the corresponding truth functions are equal. So in your
example, one might form the truth expressions corresponding to the set
formula:
   f(x, y, z) := x and (y or z)
   g(x, y, z) := (x and y) or (x and z)
Then merely check for the the 2^3 truth value tuples of (x, y, z) to checkl
that these agree.

  Hans Aberg