Writing an interpreter, need help representing this data

Question

Hello, I am writing a small interpreter to show an example of Backus-Naur form and i would like to ask for help representing some data.

<statement> : <assignment> | HALT | PRINT(<variable>)
<assignment> : <variable> = <expression>
<expression> : <term> | <term><operator><expression>
<term> : <number> | <variable>
<variable> : x | y | z
<operator> : + | -
<number> : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

As you can see everything is encapsulated in a statement. An then there assignments and expression. An expression encapsulates a term, which encapsulate a number and a variable. An assignment encapsulates a variable and a expression. My question is what data structure do i use to represent all of this? I am thinking it should be a set, but then that raises the question should i have nested sets?

Answer 1

I would use an OO approach:

public class State { /* ... */ }
public abstract class Statement {
  // ...
  public abstract void evaluate(State state);
  // ...
}

public class AssignmentStatement extends Statement {
  // ...
  private Variable var;
  private Expression expr;
  // ...
}

public class HaltStatement extends Statement { /* ... */}

public class PrintStatement extends Statement {
  private Variable var;
}

and so on. Depending on how much information you need to associate with variables (perhaps where they were declared, what line and column this occurrence appeared, and so on), you could possibly get away with using Strings as your variable type and ints as your number type.

Answer 2

This looks like a simple expression parser with a few added commands (PRINT and HALT). Probably the easiest way to parse such a thing is with a recursive descent parser. If you're building an interpreter, you can then either interpret the expression while parsing, or build a postfix (or prefix) representation of the expression for later interpretation.