12

使用 F# 解析 AST 以构建解释器的最佳方法是什么？有很多用于琐碎语法（基本算术运算）的 F# 示例，但我似乎无法找到具有更大范围功能的语言的任何内容。

有区别的工会看起来非常有用，但是您将如何构建一个具有大量选项的工会？在别处定义类型（例如加法、减法、条件、控制流）并将它们作为预定义类型放在联合中是否更好？

还是我错过了一些更有效的编写口译员的方法？每种类型都有一个 eval 函数更有效，还是使用 monad？

提前致谢

4

6 回答 6

14

有区别的工会看起来非常有用，但是您将如何构建一个具有大量选项的工会？在别处定义类型（例如加法、减法、条件、控制流）并将它们作为预定义类型放在联合中是否更好？

我不确定你在这里问什么；即使有大量的选项，DU 仍然很容易定义。例如，请参阅此博客条目以了解小型语言的 DU 结构（以及有关编写树转换的更一般性的讨论）。拥有更多案例的 DU 很好，并且在编译器/解释器中很常见以使用这种表示。

至于解析，我更喜欢一元解析器组合器；查看FParsec或查看此旧博客条目。在使用了这样的解析器组合器之后，我再也无法回到 lex/yacc/ANTLR 之类的东西——相比之下，外部 DSL 似乎很原始。

（编辑：您发现的“小算术示例”可能也非常代表更大的解决方案。“玩具”示例通常展示了正确的架构。）

于 2010-01-13T16:28:57.970 回答
3

你应该拿一份 Robert Pickering 的“Beginning F#”。

正如 Noldorin 所建议的，第 13 章“解析文本”包含一个FsLex和FsYacc示例。

除此之外，在同一本书的第 12 章中，作者解释了如何为他提出的算术语言构建一个实际的简单编译器。很有启发性。最重要的部分是您正在寻找的东西：AST 解析器。

祝你好运。

于 2010-01-13T16:26:00.237 回答
3

我同意布赖恩的建议，看看 FParsec。如果您对使用 FsLex 和 FsYacc 以老式方式做事感兴趣，那么寻找如何解析非平凡语言的一个地方就是 F# 源代码本身。查看source\fsharp\FSharp.Compiler发行版中的目录。

于 2010-01-13T16:34:11.500 回答
2

我自己没有做过翻译。希望以下内容有所帮助：）

这是耶鲁大学使用 ML 教授的编译器课程，您可能会发现它很有用。讲义非常简洁（简短）且内容丰富。您可以按照前几个讲义和作业进行。如您所知 F#，阅读 ML 程序不会有问题。

顺便说一句，教授是 A. Appel 的学生，他是 SML 实现的创建者。因此，从这些笔记中，您还可以获得使用 ML 家族语言编写编译器/解释器的最自然方式。

于 2010-01-13T16:09:04.780 回答
2

您可能会对F# WikiBook 的 Lexing and Parsing部分感兴趣。F# PowerPack 库包含FsLex和 FsYacc 工具，它们对此有很大帮助。WikiBook 指南是一个很好的入门方法。

除此之外，您还需要考虑您实际上希望如何从 AST 形式执行代码，这在编译器和解释器的设计中都很常见。然而，这通常被认为是更容易的部分，并且有很多关于编译器/解释器的通用资源应该提供这方面的信息。

于 2010-01-13T16:09:26.760 回答
0

这是一个使用 F# 和 FParsec 的完整 Small Basic 实现的极好示例。它甚至包括 IL 编译器。整个代码非常易于访问，并附有作者在http://trelford.com/blog/上的一系列博客文章

于 2015-03-02T16:08:19.753 回答