methods - 编译器/解释器设计 : should built in methods have their own Node or should a lookup table be used?

Question

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

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

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

1. 词法分析器
2. 解析器
3. 语义分析器
4. 解释器/代码生成器

<强>1。为每个单独的内置方法创建一个 AST 节点。

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

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

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

这就是打印类的样子。

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 方法，并使用来自顶级节点的递归访问它们。

我可以想到使用这种方法的一些优点/缺点:

优点

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

缺点

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

<强>2。为方法调用节点创建通用 AST 节点，然后使用查找表来确定正在调用的方法。

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

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

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

优点:

• 所有方法调用的通用语法/节点。这使它更具可读性

缺点:

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

哪种做法是在编译器/解释器中处理方法的最佳方式？是否有更好的不同做法，或者是否有我遗漏的任何其他缺点/优点？

我是编译器/解释器设计的新手，所以请让我澄清我是否有一些术语错误。

Answer 1

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

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

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

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

如果遇到运行时问题，可以使用哈希函数。 “硬核”方法是自己实现一个最佳哈希函数并离线检查哈希函数的最优性，因为您知道字符串标识符集。但是对于您的应用程序来说，这可能有点矫枉过正或出于学术目的，我建议只使用 STL 中的 unordered_map(它在底层使用散列，另请参见 How std::unordered_map is implemented)来映射您的字符串标识符到索引号，这样您就可以通过对这些索引号进行高效的 switch 操作来实现您的跳转表。