|  | reg parser for interpretor pattern | | |
| | | sunil |  |
|  Posted: Thu Jun 12, 2008 2:51 pm Post subject: reg parser for interpretor pattern |  |
| |  | |
Hello,
I am working on a problem where I will have a boolean expression with
upto four variables: A,B,C,D and connected by basic operator &&,||and
may be XOR and NOT in future AND has higher precedence than OR and ()
(parenthesis) takes utmost precedence... I wrote a sample code that
uses interpretor pattern that uses composition pattern to repeatedly
call the evaluate() function, this works properly, however I need to
construct the expression object properly, I hardcoded this (as shown
in the sample code attached below) but would assume I should some kind
of parsing technique to generate the proper top level expression
object, I have no background in Computer Science (am an electrical
enginner  ) so would need some help here, how to build this parser, I
GOGled quite a bit and found some info but nothing simple/straight
forward to understand, any pointers on simple layman tuorials/sample
code for this problem would be highly appreciated:
My other question is: is it an overkill to even think of using the
interpretor pattern for problem I am trying to solve, if its OK, is it
overkill to try building parser is it enough to hardcode the
generation of expression object...
Thanks,
Sunil
P.S.: My interpretor pattern below doesnt need to pass around the
"context" as the object Variable is already updated externally...
Sample code:
//Variable: smallest thing that can be part of expression.
class Variable {
public:
Variable(bool value,string name):_value(value),_name(name) {
}
bool getValue() {
return _value;
}
void setValue(bool value) {
_value=value;
}
string getName() {
return _name;
}
private:
bool _value;
std::string _name;
};
enum
OperatorType{OPERATOR_NONE,AND_OPERATOR,OR_OPERATOR,NOT_OPERATOR};
//Expression is built using variables and symbols and it can be
recursive i.e.
//an expression can be having expression in itself. It can have 1 or
two
//operands but only one operator
class Expression {
public:
Expression(string exprName,OperatorType
operatorType) :_exprName(exprName),_operator(operatorType) {}
~Expression(){}
string getName() {
return _exprName;
}
virtual bool evaluate()=0;
protected:
string _exprName;
OperatorType _operator;
};
//Various basic expressions allowed: AND,OR
//AND
class AndExpression: public Expression {
public:
AndExpression(Expression* exp1,Expression* exp2,string exprName):
Expression(exprName,AND_OPERATOR),_exp1(exp1),_exp2(exp2) {
}
bool evaluate() {
bool retVal;
cout << "Evaluating variable AND expr: name=" << _exprName <<
endl;
retVal = (_exp1->evaluate() && _exp2->evaluate());
cout << "Result of AND expr:" << _exprName << "is:" <<retVal <<
endl;
return retVal;
}
private:
Expression * _exp1;
Expression * _exp2;
};
//OR
class ORExpression: public Expression {
public:
ORExpression(Expression* exp1,Expression *exp2,string exprName):
Expression(exprName,OR_OPERATOR),_exp1(exp1),_exp2(exp2) {
}
bool evaluate() {
bool retVal,exp1Val;
cout << "Evaluating variable OR expr: name=" << _exprName << endl;
retVal=(_exp1->evaluate() || _exp2->evaluate());
cout << "Result of OR expr:" << _exprName << " is:" << retVal <<
endl;
return retVal;
}
private:
Expression* _exp1;
Expression* _exp2;
};
//NOT
class NOTExpression: public Expression {
public:
NOTExpression(Expression* exp,string exprName):
Expression(exprName,NOT_OPERATOR),_exp(exp) {
}
bool evaluate() {
bool retVal;
cout << "Evaluating variable NOT expr: name=" << _exprName <<
endl;
retVal = !(_exp->evaluate());
cout << "Result of NOT expr:" << _exprName << " is " << retVal;
return retVal;
}
private:
Expression* _exp;
};
//VariableExpression: expression with variable.
class VariableExpression: public Expression {
public:
VariableExpression(Variable* var): Expression(var->getName()
+"expr",OPERATOR_NONE),_var(var) {
}
bool evaluate() {
cout << "Evaluating variable expr: name=" << _exprName
<< "value= "
<< _var->getValue() <<endl;
return _var->getValue();
}
private:
Variable* _var;
};
int main() {
Variable var1(false,"var1");
Variable var2(true,"var2");
Variable var3(true,"var3");
VariableExpression varExp1(&var1);
VariableExpression varExp2(&var2);
VariableExpression varExp3(&var3);
//(varExp1 || varExp2) && varExp3
Expression *exp = new AndExpression(new
ORExpression(&varExp1,&varExp2,"inexp"),&varExp3,"outexp");
cout << "Result of evaluation=" << exp->evaluate() << endl;
var2.setValue(false);
cout << "Result of evaluation=" << exp->evaluate() << endl;
//Advantage of this approach A||B&C factored in when expression
created.
} |
| |
| | | H. S. Lahman | |
| | Posted: Thu Jun 12, 2008 2:51 pm Post subject: Re: reg parser for interpretor pattern | |
| | | |
Responding to sunil...
| Quote: | I am working on a problem where I will have a boolean expression with
upto four variables: A,B,C,D and connected by basic operator &&,||and
may be XOR and NOT in future AND has higher precedence than OR and ()
(parenthesis) takes utmost precedence... I wrote a sample code that
uses interpretor pattern that uses composition pattern to repeatedly
call the evaluate() function, this works properly, however I need to
construct the expression object properly, I hardcoded this (as shown
in the sample code attached below) but would assume I should some kind
of parsing technique to generate the proper top level expression
object, I have no background in Computer Science (am an electrical
enginner ) so would need some help here, how to build this parser, I
GOGled quite a bit and found some info but nothing simple/straight
forward to understand, any pointers on simple layman tuorials/sample
code for this problem would be highly appreciated:
|
Why do you need the evaluator? I ask because if you, as an EE, are
trying to find the minimum sum of products, there is a O(n) algorithm
for doing that (Quine-McCloskey is O(n**2) in the worst case). (But the
setup overhead and cost for each n is large so it is only more efficient
when the expressions are fairly large (e.g., a parity generator).
| Quote: | My other question is: is it an overkill to even think of using the
interpretor pattern for problem I am trying to solve, if its OK, is it
overkill to try building parser is it enough to hardcode the
generation of expression object...
|
Alas, while Interpreter is ideally suited to this the sort of linear
parsing problem implicit in evaluating boolean expressions, I don't
think you have encoded Interpreter at all. B-(
The decisions about which expression operators to invoke and their
sequencing are hard-wired in main() rather than being driven by parsing
some input stream of expression elements. What you have encoded in
Variable and Expression are the mechanics of boolean evaluation, which
is done *after* Interpreter parses the input and travels the correct
path through the syntax table. There is no such parsing here; you
hard-wire Variables in main() and then hardwire the invocation of
Expression::evaluate() in the right order to do the boolean algebra for
that particular expression.
To put it another way, one would use Interpreter to parse an input
stream to instantiate the Variable objects and determine which boolean
operations are required (e.g., assign your OperatorType). If the
expression is nested, Interpreter would use the input parsing to
instantiate relationships among the Variable objects and the right
Expression objects.
Note that if expressions can be nested by parentheses, then one must
defer evaluation until one gets to the innermost pair of variables and
then do the evaluation as one "backs out" from there. That defeats the
linear (no-backtracking) approach of Interpreter. So one needs to create
some sort of structure to describe that nesting tree as the syntax is
parsed and the "walk" it later to actually do the evaluation. Typically
for boolean expression evaluation one would create that structure with
the Interpreter pattern when parsing the input. Then one would do the
actual evaluation via depth-first traversal of that tree *after* the
Interpreter objects had completed the parsing. IOW, the evaluation of
complex boolean expressions would usually be a completely separate
activity from parsing the input to determine what the expression was.
(I know of non-LALR(1) compilers that could do the evaluation as they
parsed complex expression input, but that is well beyond the intended
scope of the Interpreter pattern.)
<aside on mechanics>
One thing I would point out is that you may not need to subclass
Expression. The only thing those subclasses are providing is a
specialized method to do the evaluation. If you have an expressionType
attribute for Expression (your enum) all you need is a jump table to the
various methods indexed on the expression type. Then the methods are
private methods of Expression and Expression::evaluate just selects the
right one to execute from the jump table.
</aside on mechanics>
--
There is nothing wrong with me that could
not be cured by a capful of Drano.
H. S. Lahman
hsl@pathfindermda.com
Pathfinder Solutions
LINK
blog: LINK
"Model-Based Translation: The Next Step in Agile Development". Email
info@pathfindermda.com for your copy.
Pathfinder is hiring:
LINK
(888)OOA-PATH |
| |
| | | Dmitry A. Kazakov | |
| | Posted: Thu Jun 12, 2008 3:39 pm Post subject: Re: reg parser for interpretor pattern | |
| | | |
On Thu, 12 Jun 2008 07:51:53 -0700 (PDT), sunil wrote:
| Quote: | I am working on a problem where I will have a boolean expression with
upto four variables: A,B,C,D and connected by basic operator &&,||and
may be XOR and NOT in future AND has higher precedence than OR
|
A bad idea, BTW. They should better have same precedence, but illegal to
associate with each other. In some languages for example:
x AND y AND z -- OK
x AND y OR z -- Association error, can't mix AND with OR
x AND (y OR z) -- That's fine
| Quote: | and ()
(parenthesis) takes utmost precedence... I wrote a sample code that
uses interpretor pattern that uses composition pattern to repeatedly
call the evaluate() function, this works properly, however I need to
construct the expression object properly,
|
You mean an interpretable code. Usually there should be a pair steps in
between. Except that when the language is very simple.
| Quote: | I hardcoded this (as shown
in the sample code attached below) but would assume I should some kind
of parsing technique to generate the proper top level expression
object, I have no background in Computer Science (am an electrical
enginner )
|
I see, you don't want to learn formal grammars... ()
| Quote: | so would need some help here, how to build this parser, I
GOGled quite a bit and found some info but nothing simple/straight
forward to understand, any pointers on simple layman tuorials/sample
code for this problem would be highly appreciated:
|
You can take a look at
LINK
it contains an implementation of parsers built in an OO way. No grammar
involved. ()
| Quote: | My other question is: is it an overkill to even think of using the
interpretor pattern for problem I am trying to solve, if its OK, is it
overkill to try building parser is it enough to hardcode the
generation of expression object...
|
H.S. has already answered this.
--
Regards,
Dmitry A. Kazakov
LINK |
| |
|
|
