将令牌从词法分析器传递给解析器

Question

我正在使用C++编写手工Lexer和Parser。我已经按照以下方式编写了Lexer：如果它发现例如 ;，它会打印"SEMICOLON"，如果它发现while，它会打印"KEYWORD"，如果它发现hello，它会打印"IDENTIFIER"等等。然而，现在我需要将这些标记传递给解析器。例如如何使用列表完成此操作？我发现需要存储令牌类型和令牌值。

- user3599420

---

你能展示一下你的努力吗？ - tod

我已经编写了整个词法分析器并且输出结果良好...... 我只需要知道如何将标记传递给解析器。 - user3599420

通常情况下，您希望设计事物以便解析器从词法分析器中提取数据。例如，这可以通过在词法分析器对象上调用get_next_token()方法来实现。 - j_random_hacker

@j_random_hacker get_next_token(Token * tok)，类似这样的吗？我的意思是这个函数将填充传递的Token对象的所有字段，包括令牌类型（也称为令牌种类），令牌值，例如标识符的字符串。 - ollydbg23

@ollydbg23：当然，那看起来对我来说是个实际的方法。 - j_random_hacker

Answer 1

你显然没有使用传统方法，即解析器调用扫描器以获取下一个标记。通常使用拉取解析器。意味着解析器通过调用相应的函数从扫描器（词法分析器）中拉取标记。最常见的扫描器/解析器生成器Lex/Yacc或Flex/Bison使用这种方法。因此，解析器会调用类似getNextToken的函数，然后扫描器从输入流中读取字节，直到找到标记。它将在标记（或错误）被检测到之前不会返回。

也有推送解析器。这里解析器或其他东西（例如套接字）读取输入流，然后将其填入扫描器中，直到可以识别出标记，然后返回该标记。这有点复杂，因为扫描器需要维护状态。最新的Bison版本支持这种方法。

两者共同点是使用一个类或结构体（POD）"Token"。这个类通常包含标记类型和一个或多个属性，例如值。还有许多经常重载的设置器和getter。这通常是解析器和扫描器之间的主要接口。

据我理解你的方法，你首先运行扫描器，消耗整个输入并收集所有令牌。这也是可能的。然后你将把所有令牌（如上所述）存储在std::vector（或其他stl::容器）中。然后解析器将访问向量。

为了进行通信，你可以使用中介者模式，或者将容器嵌入到“上下文”类中，并在扫描器和解析器之间进行交换。

你还可以向扫描器类添加成员函数（getToken），该函数返回你的令牌容器的一个元素。为此，你需要维护状态。为扫描器添加一个迭代器，基本上调用底层容器的迭代器，也是一个好建议。这样，你可以轻松遍历你的令牌，并实现（可能）必要的操作，例如读取前瞻符号或“unget”某些内容。

以上基本上回答了你的问题。

对于简单的语法，这将起作用。但对于更复杂的语法，我建议采用经典方法。可能需要上下文相关的扫描。例如，相同的关键字可能会产生不同的标记。你的方法无法处理这种情况。

我建议阅读有关Lex和Yacc的内容，不是因为您应该使用它，而是为了更深入地了解。或者，当然，阅读《编译器设计》之类的书籍或“使用C编写编译器”等内容。

您还可以查看2个编译器示例 here 希望我能帮到您一点。

- A M

---

你能否通过简单的例子来编辑你的答案？这样我就可以更好地理解当解析器从词法分析器请求标记时的情况。 - Prasanna

请提供Lex和Yacc的最佳资源。 - Prasanna

我无法将整个源代码放入答案中。太多了……请按照答案中的链接查看可工作的示例代码。Lex/Yacc/Flex/Bison文档可以在此处找到：http://dinosaur.compilertools.net/ - A M

感谢您的帮助。 - Prasanna

Answer 2

使用 std::map 的方式如下：

std::map<string, string> my_map = {
    { ";", "SEMICOLON" },
    { "while", "KEYWORD" },
    ...
 };

- muaz