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)

Composite+Builder class diagram

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?

score 11 · Accepted Answer · answered Aug 20 '12 at 17:00

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.

That's basically what I thought from the start, but maybe I should stop trusting people that are giving advices without knowing of what they're talking about! — StepTNT, Aug 21 '12 at 11:03

score 3 · Answer 2 · answered Aug 18 '12 at 12:04

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 | ...

. . .

kothvandir · Answer 3 · 2012-08-21T10:04:05.113

The interpreter provides you a way to define an expression of your language based on terminal and not terminal objects. An interpreter is a composite pattern itself so i think it is already applied.

Maybe you don't need to create one class per notTerminal and terminal element, use attributes like (operatorType, expressionType) in NonTerminal/Terminal clases to differ from your grammar symbols.

Given and expression generated with your grammar like [ A = 0 ], the objects tree formed with interpreter's pattern classes will look like this (please forgive for the bad quality and the UML sintax errors but i dont have now a suitable UML editor):

enter image description here

This object tree should be constructed by an expression analyzer. Once you have this tree, use the Recursive Descendent Parser to walk over this tree evaluating each tree node.

So evaluation of the expression is made by the parser, and the interpreter provides you a data structure to represent your grammar expressions.

Hope this help.

Using Interpreter pattern on a Composite structure

3 Answers3