Compiler/Interpreter 设计：内置方法应该有自己的节点还是应该使用查找 table？

Question

我正在设计一个使用递归下降的解释器，我已经到了开始实现内置方法的地步。

我正在实施的方法的一个示例是输出到控制台的 print() 方法，就像 python 的 print() 方法和 Java' s System.out.println().

然而，我注意到有多种方法可以实现这些内置方法。我敢肯定还有更多，但我已经确定了实现此目标的 2 种可行方法，并且我正在尝试确定哪种方法是最佳实践。下面的上下文是我在我的解释器中使用的不同层，它松散地基于 https://www.geeksforgeeks.org/introduction-of-compiler-design/ 和我遇到的其他教程。

词法分析器
解析器
语义分析器
解释器/代码生成器

1.为每个内置方法创建一个 AST 节点。

此方法需要对解析器进行编程，以便为每个单独的方法生成一个节点。这意味着每个方法都将存在一个唯一的节点。例如：

当在词法分析器中找到 TPRINT 标记时，解析器将寻找生成节点的方法。

print : TPRINT TLPAREN expr TRPAREN {$$ = new Print();}
      ;

这就是印刷品 class 的样子。

class Print : public Node {
public:
    virtual VariableValue visit_Semantic(SemanticAnalyzer* analyzer) override;
    virtual VariableValue visit_Interpreter(Interpreter* interpreter) override;
    Node* value;
    Print(Node* cvalue) {
        value = cvalue;
    }
}

从那里我定义了 visit_Semantic 和 visit_interpreter 方法，并从顶级节点使用递归访问它们。

我能想到几个 advantages/disadvantages 来使用这个方法：

优势

当代码生成器遍历树并访问 Print 节点的 visit_interpreter 方法时，它可以直接执行响应，因为它被编程到它的访问方法中。

缺点

我将不得不写很多复制粘贴代码。我必须为每个单独的方法创建一个节点并定义它的解析器语法。

2。为方法调用节点创建一个通用 AST 节点，然后使用查找 table 来确定正在调用的方法。

这涉及创建一个通用节点 MethodCall 和语法以确定是否调用了一个方法，使用一些唯一的 标识符 例如方法的字符串指的是。然后，当调用 MethodCall 的 visit_Interpreter 或 visit_Semantic 方法时，它会在 table 中查找要执行的代码。

methcall : TIDENTIFIER TLPAREN call_params TRPAREN {$$ = new MethodCall(->c_str(), );}
         ;

MethodCall节点。这里的唯一标识符是 std::string methodName:

class MethodCall : public Node {
public:
    virtual VariableValue visit_Semantic(SemanticAnalyzer* analyzer) override;
    virtual VariableValue visit_Interpreter(Interpreter* interpreter) override;
    std::string methodName;
    ExprList *params;
    MethodCall(std::string cmethodName, ExprList *cparams) {
        params = cparams;
        methodName = cmethodName;
    }
};

优点：

一个通用 grammar/node 用于所有方法调用。这使它更具可读性

缺点：

在某些时候，必须在查找 table 中比较唯一标识符 std::string methodName 以确定对其的响应。这不如在响应节点访问方法时直接编程有效。

哪种做法是在 compiler/interpreter 中处理方法的最佳方式？是否有更好的不同做法，或者是否还有其他 disadvantages/advantages 我想念的？

我对 compiler/interpreter 设计还很陌生，所以如果我的术语有误，请让我澄清一下。

Answer 1

您绝对应该使用 table 查找。它使您的事情变得容易得多。另外，想想用户定义的功能！那你肯定需要一个 table.

Answer 2

据我所知，您必须在某处将事物拆分为方法。问题是，您是要将其作为解析器定义的一部分来实现（解决方案 1），还是要在 C++ 端实现（解决方案 2）。

就个人而言，我更愿意保持解析器定义简单并将此逻辑移至 C++ 端，即解决方案 2。

从解决方案 2 的运行时间角度来看，我不会太担心。但最终，这取决于调用该方法的频率以及您拥有多少标识符。只有几个标识符不同于以 "else if" 方式比较数百个字符串。

您可以首先以简单直接的方式实现它，即以 "else if" 方式匹配字符串标识符，然后查看您是否运行陷入运行时间问题。

如果您遇到运行时间问题，您可以使用散列函数。 "hardcore" 方法是自己实现一个最优散列函数并离线检查散列函数的最优性，因为你知道字符串标识符集。但是对于你的应用程序来说，这可能有点矫枉过正或出于学术目的，我建议只使用来自 STL 的 unordered_map（它在底层使用哈希，另请参见）来映射你的索引号的字符串标识符，以便您可以通过对这些索引号进行有效的 switch 操作来实现跳转 table。

Compiler/Interpreter 设计：内置方法应该有自己的节点还是应该使用查找 table？

Compiler/Interpreter design: should built in methods have their own Node or should a lookup table be used?

compiler-construction

lookup

methods

interpreter

abstract-syntax-tree