抱歉,标题有点复杂,但是用一句话来解释有点困难。
所以我正在编写一种简单的解释型语言来帮助处理一些我经常做的事情。我设置了一个词法分析器,输入抽象语法树生成器。
抽象语法树吐出表达式。 (我正在使用 unique_ptrs 传递)。有几种类型的表达式派生自该基类,其中包括:
- 数字
- 变量
- 函数调用/原型(prototype)
- 二元运算
等每个派生类都包含该表达式所需的信息,即变量包含其标识符的 std::string,二进制操作包含左侧和右侧的 unique_ptr 以及运算符的字符。
现在它工作得很好,表达式按照它们应该的方式被解析。
This is what an AST would look like for 'x=y*6^(z-4)+5'
+--Assignment (=)--+
| |
Var (x) +--------BinOp (+)----+
| |
5 +------------BinOp (*)---+
| |
+---------BinOp (^)-------+ Var (y)
| |
Num (6) +------BinOp (-)-----+
| |
Var (z) Num (4)
当尝试解耦 AST 与解释器 时会出现问题。我想让它保持解耦,以防将来我想为编译提供支持,或者其他什么。另外,AST 已经变得相当复杂,我不想再添加它了。我只希望 AST 具有有关如何获取标记并将它们以正确的顺序转换为表达式树的信息。
现在,解释器 应该能够遍历这个自上而下的表达式列表,并递归地计算每个子表达式,将定义添加到内存中,计算常量,将定义分配给它们的函数,等等。但是,每个评估必须返回一个值,以便我可以递归地遍历表达式树。
例如,一个二元运算表达式必须递归地计算左侧和右侧,然后对两侧进行加法并返回。
现在,问题是,AST 返回指向基类 Expr 的指针,而不是派生类型。调用 getExpression 返回下一个表达式,而不管它的派生类型,这使我可以轻松地递归地评估二进制操作等。为了让解释器获得有关这些表达式的信息(例如数值或标识符),我会基本上动态地转换每个表达式并检查它是否有效,我必须重复执行此操作。另一种方法是做一些类似于访问者模式的事情——Expr 调用解释器并将 this 传递给它,这允许解释器为每个派生类型有多个定义。但同样,解释器必须返回一个值!
这就是我不能使用访问者模式的原因——我必须返回值,这会将 AST 完全耦合到解释器。
我也不能使用策略模式,因为每种策略都会返回截然不同的东西。例如,解释器策略与 LLVM 策略相差太大。
我完全不知道该做什么。一个非常棘手的解决方案是从字面上将每个表达式类型的枚举作为 expr 基类的成员,解释器可以检查类型,然后进行适当的类型转换。但这很丑陋。真的很丑。
我在这里有哪些选择?谢谢!
最佳答案
通常的答案(与大多数解析器生成器所做的一样)是同时具有标记类型值和关联数据(在讨论此类事物时称为属性)。类型值通常是一个简单的整数,表示“数字”、“字符串”、“二进制操作”等。在决定使用什么生产时,您只检查 token 类型,当您与生产规则匹配时,您就会知道是什么类型 token 输入该规则。
如果你想自己实现这个,请查看解析算法(LALR 和 GLR 是几个例子),或者你可以切换到使用解析器生成器,只需要担心语法正确,然后正确实现产生式而不必担心自己实现解析引擎。
关于c++ - 当算法需要派生类的知识时,将算法与数据解耦,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50243025/