Re: Boolean sets

[Tim Van Holder]

Nicholas Crosbie wrote:
> I would like to set a a Bison project which processes
> a an expresssion of the form
> 
> gate = r3 AND r5 NOT (r5 OR r7)
> 
> i.e. a Boolean expression of arbitrary
> length/complexity, where r3, r5 etc. are
> variables containing integer data (e.g. an array, or
> stored as a set or list).
> My prefered option would is to have Bison do the
> parsing and call Objective
> C or C++ code for set intersection, set union, set
> minus.  Alternatively, I could
> have Bison call C functions for set intersection etc. 
> 
> 
> Does anyone have any experience with such a
> task.....can point me to example
> code?

Unless the grammar is exceedingly simple, I typically
construct a parse tree, and have C/C++ code process that.
This restricts the parser's role to that of a parser,
instead of making it a full interpreter.
You can mix it a bit though, if needed by constructing
parse trees on a per-expression basis and then executing
them as soon as they're done.

mockup:

%union {
  struct parse_node* node;
  int                integer;
}

%start expressions

%%

expressions
: /* empty */
| expressions expression
  {
    process_expression ($2);
    free_parse_tree ($2);
  }
;

expression
: identifier '=' set_expression /* assignment expression */
  {
    append_child ($2, $1);
    append_child ($2, $3);
    $$ = $2;
  }
| ... /* other forms of statement/expression as needed */
;

set_expression
: identifier
| '(' set_expression ')'
  {
    combine_parens ($1, $3); /* create a single "()" node instead */
    append_child ($1, $2);
    $$ = $1;
  }
| set_expression "AND" set_expression
  {
    append_child ($2, $1);
    append_child ($2, $3);
    $$ = $2;
  }
| set_expression "OR" set_expression
  {
    append_child ($2, $1);
    append_child ($2, $3);
    $$ = $2;
  }
| "NOT" set_expression
  {
    append_child ($1, $2);
    $$ = $1;
  }
;