Java：了解递归下降解析器实现

Question

假设我们有一个简单的语法：

程序 ::= 表达式
表达式 ::= 数字
::= - ( 表达式 , 表达式 )

用这个表达式：-(-(8,3)4)
返回 1.

我的令牌流（我拼接了括号和逗号）看起来像这样
(负 -)
(负 -)
（整数 8）
（整数 3）
（整数 4）

所以 AST 看起来像这样
. . -
. - 。 4
8..3

我的问题是关于语法的递归性质。给定差异表达式有 2 个求值表达式，java 示例将如何工作。

我试过像这样将表达式传递给 class 构造函数：

public class DiffExp implements LetLangExp {
  LetLangExp left, right;

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

这只适用于 -(number,number) 的差异表达式，但递归地它不起作用，因为我似乎无法理解解析的递归性质。我坚持这个例子，我在网上看过，但我似乎无法将这种类型的语法与我所见过的任何东西模棱两可。

基本上我如何实现递归处理的差异表达式，它可以将差异表达式作为操作数并相应地计算？

编辑：根据 Markspace 的要求，我正在尝试为解析树构建一个节点结构。这是我现在拥有的 class。

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

您应该为语法中的每个规则创建方法，例如：

parseProgram(String program) {
  return parseExpression(program)
}

parseExpression(String expression) {

  if ( isNumber(expression) ) {
    return parseNumber(expression);
  } else 
  if ( isSignedExpression(expression) ) {
    String left = getLeftExpression(expression);
    String right = getRightExpression(expression);

    return parseExpression(left) - parseExpression(right);
  } 

}

parseNumber(String number) {
  parsedNumber = ...
  return parsedNumber;
}

Answer 2

看起来不错，但您需要将树构建和评估分开：

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。解析应该大致如下：

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);
}

Java：了解递归下降解析器实现

Java: Understanding a Recursive Descent Parser Implementation

java

recursion

parsing

recursive-descent