Using Interpreter pattern on a Composite structure

Question

I've been asked to make an expression evaluator using Composite, Recursive Descendent Parser and Interpreter.

Here's the grammar :

<cond> → <termb> [OR <termb>]*
<termb>→<factb>[AND <factb>]*
<factb>→<expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → [PLUS | MINUS] <term> [(PLUS <term>) | (MINUS <term>)]*
<term> → <termp> [(MULT <termp>) | (DIV <termp>) | (REM <termp>)]*
<termp> → <fact> [POWER <fact>]*
<fact> → ID | NUM | OPAR1 <expr> CPAR1
----TERMINALS----
ID → ("A" | ... | "Z" | "a" | ...| "z") [("A"| ... | "Z" | "a" | ...| "z" | "0" | ... | "9")]*
NUM → ("0" | ... | "9") [("0" | ... | "9")]*
OPAR → "("
CPAR → ")"
OPAR1 → "["
CPAR1 → "]"
RELOP → EQ | NEQ | GT | GE | LT | LE
EQ → "= ="
NEQ → "!="
GT → ">"
GE → ">="
LT → "<"
LE → "<="
POWER → "^"
DIV → "/"
REM → "%"
MULT → "*"
MINUS → "−"
PLUS → "+"
AND → “and” or “&&”
OR → “or” or “||”
NOT → “not” or “!”

The assignment is:

The goal of the project, based on Composite, Recursive Builder and Interpreter, is to get a conditional expression, do a syntax analysis and build its composite tree. Starting from the tree, you've got to evaluate the result of the condition, based on an external context (read from a properties file) that contains the value of the internal variables

Now, the first thing that I noticed is that Interpreter uses a Composite structure, so it seemed a good idea to extend my Composite structure with an evaluate(:Context) method.

I've asked around, but I've been told that this is not the way to do the assignment. Seems like I've got build the Interpreter tree, starting from the Composite one (which is quite nonsens for me, as I've already got a tree to work with!).

So I've built my tree using Composite + Recursive Builder, it recognizes the input and it build the tree without any kind of problem.

But the question is : how do I apply Interpreter to my structure?

Here's my class diagram (something is Italian but it's quite understandable)

If I got it right, Interpreter uses a class for each grammar rule, so I've got to make a cond class, then a termb and so on.

But ho do I link them to my composite?

Answer 1

Not sure why you were told not to use the same tree structure. I think I would add an evaluate() method to my expression interface. It makes sense to me. An expression should know how to evaluate itself.

I would say that your current expression interface exposes too much (such as operands). As a client of expression, I should only need to 1) invoke it and 2) read the result and I guess maybe 3) have it print. Actually, i would prefer using toString() over directly printing.

You probably already noticed but not all expressions take 2 operands (such as NOT or NEGATE). This already creates a sort of discrepancy with your interface. I would simplify it to:

 public interface Expression {
   int evaluate();
 }

Then each one of your operations and terminals knows how to evaluate itself (and convert itself to a string).

So I could have concrete operations like:

 public class Terminal implements Expression {
   private final int value;

   public Terminal(int value) { this.value = value; }

   public int evaluate() { return value; }

   public String toString() { return String.valueOf(value); }
 }

 public class Add implements Expression {
   private final Expression left;
   private final Expression right;

   public Add(Expression left, Expression right) {
     this.left = left;
     this.right = right;
   }

   public String toString() {
     return left.toString() + " + " + right.toString();
   }

   // leave the rest for you
 }

Now I can build the tree pretty easily

Expression expr = new Add(new Terminal(1), new Subtract(new Terminal(2), new Terminal(3)));

int result = expr.evaluate();
System.out.print(expr.toString() + " = " + result);

And I don't even need direct access to individual operands.

Answer 2

If I understand correctly your problem I would say that every concrete class should by a subclass of your main composite structure.

If Expression is you main composite then:

Expression : Term Expression : OperandTerm

Condition: Term BinOperand Expression Condition: UnaryOperand Expression

Term: Int | Foat | ...

. . .