尝试理解解析器

Question

我正在尝试使用 JavaCC 构建一个简单的命令行计算器，可以处理各种表达式。虽然有很多关于如何编写语法的教程，但到目前为止我所看到的都没有解释随后发生的事情。

我现在的理解是，将字符串传递到解析器后，它会被分割成标记并变成解析树。接下来会发生什么？我是否遍历解析树，对每个节点的内容进行一系列 if-else 字符串比较，然后执行适当的函数？

Answer 1

我强烈建议您观看 Scott Stanchfield 的 ANTLR 3.x 教程。即使您最终没有使用 ANTLR（这对您的项目来说可能有点大材小用，但我对此表示怀疑），通过观察他的思考过程，您也会学到很多东西。

一般来说，这个过程是......

1. 构建一个词法分析器来理解您的标记
2. 构建一个解析器，可以验证和理解输入并将输入组织到抽象语法树（AST）中，该抽象语法树应该表示简化/易于使用的版本您的语法
3. 基于 AST 运行任何计算

Answer 2

您需要根据需要实际编译或解释它。

对于计算器，您只需要递归访问树并评估解析的树，而使用更复杂的语言，您必须将其翻译为汇编语言-类似，但保留了底层架构的抽象。

当然，您可以开发自己的简单虚拟机，该虚拟机能够执行一组在您的语言中进行编译的指令，但在您的情况下这会有点过分……只需访问解析树即可。就像这样：

enum Operation {
  PLUS, MINUS
}

interface TreeNode {
  float eval();
}

class TreeFloat implements TreeNode {
  float val;
  float eval() { return val; }
}

class TreeBinaryOp implements TreeNode {
  TreeNode first;
  TreeNode second;
  Operation op;

  float eval() {
    if (op == PLUS)
      return first.eval()+second.eval();
}

然后你只需在树的根上调用 eval 函数即可。可能需要进行语义检查（如果您计划使用变量或其他内容，则还需要构建符号表）。

Answer 3

我是否遍历解析树，对每个节点的内容进行一系列 if-else 字符串比较，然后执行适当的函数？

不，不需要构建解析树来实现计算器。在创建新节点对象的代码部分中，只需进行计算并返回一个数字即可。

JavaCC 允许您为产生式选择任何返回类型，因此只需提供您的返回号即可。

Answer 4

某些解析器生成器（例如 YACC）允许您将操作放入语法中，因此当您应用某个产生式时，您还可以在该产生式期间应用定义的操作。

例如，在 YACC 中：

E: NUM + NUM     {$ = $1.value + $2.value};

会将 NUM 的值相加并将结果返回到 E 非终结符。

不确定 JavaCC 可以让您做什么。