10

我被要求使用Composite、Recursive Descendent Parser和Interpreter制作表达式评估器。

这是语法：

<cond> → <termb> [OR <termb>]*
<termb>→&lt;factb>[AND <factb>]*
<factb>→&lt;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 “&amp;&”
OR → “or” or “||”
NOT → “not” or “!”

任务是：

该项目的目标是基于 Composite、Recursive Builder 和 Interpreter，获得条件表达式，进行语法分析并构建其复合树。从树开始，您必须根据包含内部变量值的外部上下文（从属性文件中读取）来评估条件的结果

现在，我注意到的第一件事是Interpreter使用了Composite结构，因此使用evaluate(:Context)方法扩展我的Composite结构似乎是个好主意。

我四处询问，但有人告诉我这不是完成任务的方法。似乎我已经构建了解释器树，从复合树开始（这对我来说是非常荒谬的，因为我已经有了一棵树可以使用！）。

所以我使用Composite + Recursive Builder构建了我的树，它识别输入并构建树而没有任何问题。

但问题是：如何将解释器应用于我的结构？

这是我的类图（有些是意大利语，但很容易理解）

Composite+Builder类图

如果我做对了，Interpreter会为每个语法规则使用一个类，所以我必须创建一个cond类，然后是一个termb，等等。

但是我如何将它们链接到我的复合材料？

4

3 回答 3

11

不知道为什么你被告知不要使用相同的树结构。我想我会在我的表达式接口中添加一个 evaluate() 方法。对于我，这说得通。表达式应该知道如何评估自己。

我会说您当前的表达式接口暴露了太多（例如操作数）。作为表达式的客户，我只需要 1) 调用它并 2) 读取结果，我猜也许 3) 让它打印。实际上，我更喜欢使用 toString() 而不是直接打印。

您可能已经注意到，但并非所有表达式都采用 2 个操作数（例如 NOT 或 NEGATE）。这已经与您的界面产生了某种差异。我会将其简化为：

 public interface Expression {
   int evaluate();
 }

然后，您的每个操作和终端都知道如何评估自己（并将自己转换为字符串）。

所以我可以有具体的操作，比如：

 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
 }

现在我可以很容易地构建树

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

而且我什至不需要直接访问单个操作数。

于 2012-08-20T17:00:41.773 回答
3

如果我正确理解您的问题，我会说每个具体类都应该由您的主要复合结构的子类组成。

如果 Expression 是您的主要复合材料，那么：

表达式：项 表达式：OperandTerm

条件：Term BinOperand 表达式条件：UnaryOperand 表达式

术语：诠释 | 脚 | ...

. . .

于 2012-08-18T12:04:06.673 回答
2

解释器为您提供了一种基于终端而不是终端对象定义语言表达式的方法。解释器本身就是一种复合模式，所以我认为它已经被应用了。

也许您不需要为每个 notTerminal 和终端元素创建一个类，在 NonTerminal/Terminal 类中使用 (operatorType, expressionType) 之类的属性来与您的语法符号不同。

给定和使用您的语法生成的表达式，如 [ A = 0 ]，由解释器的模式类形成的对象树将如下所示（请原谅质量差和 UML sintax 错误，但我现在没有合适的 UML 编辑器）：

在此处输入图像描述

此对象树应由表达式分析器构建。一旦你有了这棵树，使用递归下降解析器遍历这棵树，评估每个树节点。

因此，解析器对表达式进行评估，解释器为您提供一个数据结构来表示您的语法表达式。

希望这有帮助。

于 2012-08-20T10:36:48.227 回答