Suggestions for logical expression syntax?

[rakkar]

I want the user to be able to do something like this

(column1 has changed AND column2 has not changed) OR (column 3 has changed)

A couple of ideas I had to let the user express this:

C Style:
(column1(CHANGED) AND column2(NOT_CHANGED)) OR (column3(CHANGED)

Postfix:

OR, AND, CHANGED, column1, NOT_CHANGED, column2, column 3

Let the user connect nodes in a graph view. Two or more links means OR, one link means AND.

-------- -----------------------
|Start|---->| column1 (Changed |-----> (etc)
______ -------------------------

However, these are a lot of work. I was wondering if anyone had any suggestions. Maybe there is a library or built-in feature for something like this already?

[wysota]

Usually you'd use predicates and either prefix or infix operators:

(column1 has changed AND column2 has not changed) OR (column 3 has changed)

"( changed(column1) AND NOT changed(column2) ) OR changed(column3)"

It's just a couple of minutes of work to implement a parser and interpreter for such a language. You may use parser generators (like qlalr for Qt) if you want but if you haven't used one before, it'll be faster to implement the parser manually.

Just for completeness a full grammar of the language in EBNF:

Expression ::== LogicalValue | OrExpression | AndExpression | NotExpression | ParenthesisExpression ;
OrExpression ::== Expression 'OR' Expression ;
AndExpression ::== Expression 'AND' Expression ;
NotExpression ::== 'NOT' Expression ;
ParenthesisExpression ::== '(' Expression ')' ;
LogicalValue :: == 'TRUE' | 'FALSE' | Predicate ;
Predicate ::== AlNumString '(' AlNumString ')' ;
AlNumString ::== (A..Z|a..z)(A..Z|a..z|0..9)* ;

Expression ::== LogicalValue | OrExpression | AndExpression | NotExpression | ParenthesisExpression ;
OrExpression ::== Expression 'OR' Expression ;
AndExpression ::== Expression 'AND' Expression ;
NotExpression ::== 'NOT' Expression ;
ParenthesisExpression ::== '(' Expression ')' ;
LogicalValue :: == 'TRUE' | 'FALSE' | Predicate ;
Predicate ::== AlNumString '(' AlNumString ')' ;
AlNumString ::== (A..Z|a..z)(A..Z|a..z|0..9)* ;

To copy to clipboard, switch view to plain text mode 

And a skeletal implementation for OrExpression:

class Node { 
public:
  virtual bool Interprete() = 0;
};
class OrNode : public Node {
public:
  OrNode(Node *left, Node *right){ m_left = left; m_right = right; }
  bool Interprete() { return (left->Interprete() || right->Interprete()); }
private:
  Node *m_left, *m_right;
};

class Node { 
public:
  virtual bool Interprete() = 0;
};
class OrNode : public Node {
public:
  OrNode(Node *left, Node *right){ m_left = left; m_right = right; }
  bool Interprete() { return (left->Interprete() || right->Interprete()); }
private:
  Node *m_left, *m_right;
};

To copy to clipboard, switch view to plain text mode 

The parsing code has to first do a lexical analysis by dividing the input into tokens and then start matching tokens to ones you expect. For instance at top level you can either encounter one of the following tokens: TRUE, FALSE, AlNumString, NOT, '('. First three correspond to LogicalValue, the fourth one to a NotExpression and the last one to ParenthesisExpression. Then you can call an appropriate subroutine that will return a node and information about where it stopped parsing. If you encounter an OR token, you call a subroutine to parse the right part (the left one is already parsed) and then you create an OrNode and assign the two obtained nodes to it. At some point you'll either encounter a parse error (unexpected token) or end of input. At that point the last node will be the root of your abstract syntax tree. You can call Interprete() on it to get the boolean value of the whole expression.

This is really simple and not as much work as you'd think.

Node *parseExpression(QList<Token> &tokens){
  Token t = tokens.first();
  if(t.type == T_TRUE || t.type == T_FALSE || t.type == T_IDENT) return parseLogicalValue(tokens);
  else if(t.type == T_NOT) return parseNotExpression(tokens);
  else if(t.type == T_LPAREN) return parseParenthesisExpression(tokens);
  else return 0; // parse error
}
 
Node *parseNotExpression(QList<Token> &tokens){
  Token t = tokens.first();
  if(t.type != T_NOT) return 0; // parse error
  tokens.takeFirst(); // removes T_NOT from input
  Node *subNode = parseExpression(tokens);
  if(!subNode) return 0; // propagate parse error
  return new NotNode(subNode);
}

Node *parseExpression(QList<Token> &tokens){
  Token t = tokens.first();
  if(t.type == T_TRUE || t.type == T_FALSE || t.type == T_IDENT) return parseLogicalValue(tokens);
  else if(t.type == T_NOT) return parseNotExpression(tokens);
  else if(t.type == T_LPAREN) return parseParenthesisExpression(tokens);
  else return 0; // parse error
}

Node *parseNotExpression(QList<Token> &tokens){
  Token t = tokens.first();
  if(t.type != T_NOT) return 0; // parse error
  tokens.takeFirst(); // removes T_NOT from input
  Node *subNode = parseExpression(tokens);
  if(!subNode) return 0; // propagate parse error
  return new NotNode(subNode);
}

To copy to clipboard, switch view to plain text mode 

etc.