语法树解析中观察者模式的使用

Question

我已经详细说明了问题的规格，原因在我最后提出问题后就会变得清楚。我正在构建的程序是 Java 中的解析器，用于具有以下语法的语言（尽管这与问题不太相关）：

<expr> ::= [<op> <expr> <expr>] | <symbol> | <value>
<symbol> ::= [a-zA-Z]+
<value> ::= [0-9]+
<op> ::= '+' | '*' | '==' | ‘<’
<assignment> ::= [= <symbol> <expr>]
<prog> ::= <assignment> |
           [; <prog> <prog>] |
           [if <expr> <prog> <prog>] |
           [for <assignment> <expr> <assignment> <prog>] |
           [assert <expr>] |
           [return <expr>]`

这是该语言的代码示例：

[; [= x 0] [; [if [== x 5] [= x 7] [= x [+ x 1]]] [return x]]]

相当于：

x = 0;
if (x == 5)
    x = 7;
else
    x = x + 1;
return x;`

代码保证语法正确；给定代码的不正确性仅通过具有：
来定义 a) 以前未声明的已用变量（符号）（声明的意思是指派给它的东西），即使该变量用在 if 的分支或程序执行过程中从未到达的其他地方；
b) 在程序可能采取的每条路径上都有一个 "return" 指令，这意味着程序不能在不返回它可能采取的任何执行路径的情况下结束。要求是程序要解析代码。

我的解析器必须：
a) 检查所说的正确性；
b) 解析代码并计算返回值。

我对此的看法是：
1) 将给出的代码解析成一棵指令和表达式树；
2) 通过遍历树并查看变量在使用前是否在上层作用域中声明来检查正确性；
3) 通过遍历树并查看是否有任何执行分支以 "return" 指令结束来检查正确性；
4) 如果前面的所有条件都成立，通过遍历树并记住 HashMap 或其他存储中所有变量的值来评估代码的返回值。

现在，我的问题 是我必须使用 Visitor 和 Observer[=58= 来实现解析器] 设计模式。这是项目的关键要求。我对设计模式比较陌生，对这两个只有基本的了解。

我的问题是：should/can 我在我的解析器中使用 Observer 设计模式的地方？

在步骤 2、3 和 4 中使用 Visitor 访问树的节点是有意义的。不过，我无法弄清楚必须在何处使用观察者模式。
在我的实施中有什么地方可以使用它吗？根据我的理解，Observer 模式负责处理可以被许多人读取和修改的数据 "observers"，其中心思想是修改数据的对象将通知可能受修改影响的其他对象。

在我的程序中修改的主要数据是 tree 和 HashMap，我在其中存储变量的值。两者都以线性方式访问，只有一件事。树一次构建一个节点，就此而言，没有其他节点或对象关心节点的添加或修改。在评估阶段，访问每个节点并在散列table中添加或修改变量，但除了当前节点的当前访问者之外没有其他对象关心这个。我想我可以让每个节点成为一个观察者，在观察到变化时什么都不做，或者类似的东西，强制观察者模式，但这并不是很有用。

那么，是否有一个明显的答案是我完全想念的？有没有一个不那么明显，但仍然提供有用的 Observer 实现的？我可以在我的算法中的某个地方使用半有用的稍微强制的观察者模式，还是完全强制的，完全无用的方式是实现它的唯一方法？是否有一种完全不同的方法来解决这个问题，让我可以使用访问者模式，更重要的是，使用观察者模式？

备注：
我还没有用 Visitor 对树进行评估（步骤 2、3 和 4）；我只是想过我应该怎么做。明天我会实现它，看看有没有办法在某个地方使用Observer，但是我想了几个小时如何使用它，我仍然没有想法。不过，我希望有一种方法，虽然我没能发现，但在写完那部分后就会变得清晰。
我很抱歉写了这么多。我不能更好地总结它，并且仍然可以更好地提供有关情况的详细信息。
另外，如果我的解释不清楚，我深表歉意。已经很晚了，我想了几个小时，累了，我不能说我对这些概念有完美的理解。如果有任何不清楚的地方或想了解有关某些问题的更多详细信息，请随时提出。另外，请不要犹豫，指出我对问题的判断中的任何错误或错误路径。

Answer 1

这里有一些想法，您可以如何使用众所周知的模式和概念为您的语言构建解释器：

开始处理输入流，将其拆分为标记 ([;、=、x、0、]， ETC。）。第一个组件（a.k.a。词法分析器、扫描器、分词器）去除不相关的细节，例如空格并生成分词。

您可以将其实现为一个简单的状态机，一次输入一个字符。因此它可以实现为输入字符序列的观察者。
在下一阶段（a.k.a.解析）中，您将根据生成的标记构建抽象语法树 (AST)。

解析器是标记器的观察器，即它会收到标记器生成的任何新标记的通知。^(*) 它一次被喂一个令牌。在语法相当简单的情况下，扫描器本身也可以是一些基于堆栈的状态机。（例如，如果它需要匹配左括号和右括号，它需要能够记住它在括号外的上下文/状态，因此它可能会使用某种堆栈来进行上下文管理。）
一旦解析器构建了 AST，也许几乎所有后续步骤都可以使用 访问者模式 来实现。遍历 AST、定位特定节点或子树或转换（部分）AST 的每个算法都可以建模为访问者。一些访问者只会对没有 return 值的操作建模，而另一些访问者会 return 为访问的节点创建新的 AST 节点，以便可以将新的转换后的 AST 放在一起。例如：
- 检查 AST 或其任何子树是否描述了有效的程序片段（访问（子）树，将其简化为布尔值或错误列表）。
- 简化/优化程序（访问（子）树，生成更小或更优的子树，最后从转换后的子树重新组装一棵新树）。
- 执行AST（访问并解释每个节点，根据节点的含义执行一些代码）。

^(*) 将解析器称为扫描器的观察者可能有些不准确。 This Software Engineering SE post 对密切相关的设计模式进行了很好的总结。可能是扫描器实施了策略来处理令牌。

语法树解析中观察者模式的使用

Observer pattern usage in syntax tree parsing

syntax

tree

parsing

design-patterns

observer-pattern