parsing - 如何编写文本转换器？

Question

假设我有一个可以轻松解析的文本。它由文本和特殊标识符组成。解析后，我得到一个与文本和文本中的特殊标识符相对应的标记列表。

我遇到的问题是如何将它从这个令牌列表转换为其他形式？

我不明白如何解决这个问题。

我试图构建一个解析树，但我不明白下一步该做什么。

请就这个解析的一般问题提出建议。

Answer 1

一旦你有了一个标记流，你可以通过使用解析器生成器并指定你的语言的语法将它转换成一个解析树。

根据您想使用的编程语言，您可能需要查看以下解析器生成器：

C/C++ -雅克

Java - ANTLR（还有 JavaCC、SableCC）

Python - PLY (Python Lex / Yacc)

OCaml - ocamlyacc

如果您不了解语法，那么您选择的解析器生成器的文档应该足以让您继续学习。

当您的解析器完成后，它将获取令牌流并使用中间表示构造一棵树 - 您定义的类型代表您的语言的各个部分（例如您提到的文本和特殊标识符）。然后，您可以随意操作树。

编辑：针对您的评论-我不太确定要给您什么级别的答案，因为我无法确切说明您遇到了什么问题。首先，您熟悉树数据结构吗？如果是这样，您是否知道如何编写一个简单的递归算法来查找树的高度，或者运行深度优先搜索？请记住，树只是一种组织信息的方式——这完全取决于您如何处理这些信息。

将算法应用于异构树（即节点属于不同类型的树）的常见设计模式是访问者模式。如果您已经熟悉树，可以查找您喜欢的语言的访问者模式示例；但是，如果这个概念对您来说是新概念，我强烈建议您从更简单的算法开始练习。