Java: Understanding a Recursive Descent Parser Implementation

Question

Let's say we have a simple grammar:

1. Program ::= Expression
2. Expression ::= Number
3. ::= - ( Expression , Expression )

With this expression: -(-(8,3)4)
Returning 1.

My token stream(I splice parens and commas out) looks like this
(MINUS -)
(MINUS -)
(INTEGER 8)
(INTEGER 3)
(INTEGER 4)

So the AST would look like so
. . -
. - . 4
8..3

My question is, regarding the recursive nature of the grammar. How would a java example work given the difference expression has 2 evaluated expressions.

I've tried passing in expressions to a class constructor like so:

public class DiffExp implements LetLangExp {
  LetLangExp left, right;

  public DiffExp(LetLangExp l, LetLangExp r) {
    left = l;
    right = r;
    eval();
  }
}

This works for just a difference expression of -(number,number) but recursively it doesn't, because I can't seem to wrap head around the recursive nature of parsing it seems. I'm stuck on this example and i've looked online but i can't seem to equivocate this type of grammar to anything i've seen.

Essentially how do I implement a Difference Expression that is handled recursively that can take a difference expression as an operand and calculate that accordingly?

Edit: Per Markspace's request, i'm attempting to build a node structure for the parse tree. Here is the class I have right now.

class ExprNode{
String c;
static String operator;
static ExprNode operand1;
static ExprNode operand2;

public ExprNode(String num){
    c = num;
    operand1 = operand2 = null;
}

public static void Expr(String op, ExprNode e1, ExprNode e2){
    operator = op;
    operand1 = e1;
    operand2 = e2;
}
}

Answer 1

Looks good but you'll want to separate tree building and evaluation:

public class DiffExp implements LetLangExp {
  LetLangExp left, right;

  public DiffExp(LetLangExp l, LetLangExp r) {
    left = l;
    right = r;
  }

  public double eval() {
    return left.eval() - right.eval();
  }
}

p.s. Parsing should be roughly as follows:

LetLangExpr parseProgram(LinkedList<String> tokens) {
  return parseExpression(tokens);
}

LetLangExpr parseExpression(LinkedList<String> tokens) {
  if ("-".equals(tokenStream.peekFirst())) {
    return parseDiff(tokens);
  } else {
    return parseNumber(tokens);
  }
}

LetLangExpr parseDiff(LinkedList<String> tokens) {
  tokens.pollFirst();  // Consume "-"
  LetLangExpr left = parseExpression(tokens);
  LetLangExpr right = parseExpression(tokens);
  return new DiffExpr(left, right);
}

LetLangExpr parseNumber(LinkedList<String> tokens) {
  String numberStr = tokens.pollFirs();
  double number = Double.parseDouble(numberStr);
  return new NumberExpr(number);
}