F# 解析抽象语法树
使用 F# 解析 AST 来构建解释器的最佳方法是什么？有很多关于简单语法（基本算术运算）的 F# 示例，但我似乎无法找到具有更大范围功能的语言的任何内容。
受歧视的工会看起来非常有用，但你会如何构建一个具有大量选项的工会呢？是否最好在其他地方定义类型（例如加法、减法、条件、控制流）并将它们作为联合中的预定义类型组合在一起？
或者我是否错过了一些更有效的编写解释器的方法？为每种类型提供一个 eval 函数更有效，还是使用 monad 更有效？
提前致谢
What is the best way to use F# to parse an AST to build an interpreter? There are plenty of F# examples for trivial syntax (basic arithmatical operations) but I can't seem to find anything for languages with much larger ranges of features.
Discriminated unions look to be incrediably useful but how would you go about constructing one with large number of options? Is it better to define the types (say addition, subtraction, conditionals, control flow) elsewhere and just bring them together as predefined types in the union?
Or have I missed some far more effective means of writing interpreters? Is having an eval function for each type more effective, or perhaps using monads?
Thanks in advance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我不确定你在这里问什么；即使有大量选项，DU 仍然很容易定义。请参阅此博客条目了解小型语言的 DU 结构（如以及关于编写树变换的更一般性讨论）。拥有一个具有更多情况的 DU 很好，并且在编译器/解释器中很常见使用这种表示形式。
至于解析，我更喜欢单子解析器组合器；查看 FParsec 或参阅 这个旧博客条目。在使用了这样的解析器组合器之后，我再也无法回到像 lex/yacc/ANTLR 这样的东西了——相比之下，外部 DSL 看起来是如此原始。
（编辑：您发现的“微小算术示例”可能也能很好地代表较大的解决方案。“玩具”示例通常会展示正确的架构。）
I am not sure what you are asking here; even with a large number of options, DUs still are simple to define. See e.g. this blog entry for a tiny language's DU structure (as well as a more general discussion about writing tree transforms). It's fine to have a DU with many more cases, and common in compilers/interpreters to use such a representation.
As for parsing, I prefer monadic parser combinators; check out FParsec or see this old blog entry. After using such parser combinators, I can never go back to anything like lex/yacc/ANTLR - external DSLs seem so primitive in comparison.
(EDIT: The 'tiny arithmetic examples' you have found are probably pretty much representative of what larger solutions looks like as well. The 'toy' examples usually show off the right architecture.)
您应该拿一本 Robert Pickering 的“Beginning F#”。
第 13 章“解析文本”包含一个使用 FsLex 和 FsYacc 的示例，如 Noldorin 所建议。
除此之外，在同一本书的第 12 章中，作者解释了如何为他提出的算术语言构建一个实际的简单编译器。非常有启发性。最重要的部分是您正在寻找的内容：AST 解析器。
祝你好运。
You should take a copy of Robert Pickering's "Beginning F#".
The chapter 13, "Parsing Text", contains an example with FsLex and FsYacc, as suggested by Noldorin.
Other than that, in the same book, chapter 12, the author explains how to build an actual simple compiler for an arithmetic language he proposes. Very enlightening. The most important part is what you are looking for: the AST parser.
Good luck.
我赞同 Brian 的建议，看看 FParsec。如果您有兴趣使用 FsLex 和 FsYacc 以传统方式执行操作，那么可以从 F# 源代码本身来了解如何解析一门重要的语言。请参阅发行版中的
source\fsharp\FSharp.Compiler目录。I second Brian's suggestion to take a look at FParsec. If you're interested in doing things the old-school way with FsLex and FsYacc, one place to look for how to parse a non-trivial language is the F# source itself. See the
source\fsharp\FSharp.Compilerdirectory in the distribution.您可能有兴趣查看 F# WikiBook 的词法分析和解析部分。 F# PowerPack 库 包含FsLex 和 FsYacc 工具，这对此有很大帮助。 WikiBook 指南是一个很好的入门方法。
除此之外，您还需要考虑如何实际执行 AST 形式的代码，这在编译器和解释器的设计中都很常见。然而，这通常被认为是更容易的部分，并且编译器/解释器上有很多通用资源应该提供这方面的信息。
You may be interesting in checking out the Lexing and Parsing section of the F# WikiBook. The F# PowerPack library contains the FsLex and FsYacc tools, which asssist greatly with this. The WikiBook guide is a good way to get started with this.
Beyond that, you will need to think about how you actually want to execute the code from the AST form, which is common the design of both compilers and interpreters. This is generally considered the easier part however, and there are lots of general resources on compilers/interpreter out there that should provide information on this.
我自己没有做过翻译。希望以下内容有所帮助：）
这里是耶鲁大学使用机器学习教授的编译器课程，您可以使用该课程可能会觉得有用。讲义非常简洁（简短）且内容丰富。您可以遵循前几个讲义和作业。正如您所了解的 F#，您在阅读 ML 程序时不会遇到问题。
顺便说一句，这位教授是 A. Appel 的学生，A. Appel 是 SML 实现的创建者。因此，从这些注释中，您还可以获得使用 ML 系列语言编写编译器/解释器的最自然方式。
I haven't done an interpreter myself. Hope the following helps:)
Here's a compiler course taught at Yale using ML, which you might find useful. The lecture notes are very concise (short) and informative. You can follow the first few lecture notes and the assignments. As you know F#, you won't have problem reading ML programs.
Btw, the professor was a student of A. Appel, who is the creator of SML implementation. So from these notes, you also get the most natural way to write a compiler/interpreter in ML family language.
这是使用 F# 和 FParsec 实现完整 Small Basic 的绝佳示例。它甚至包括 IL 编译器。整个代码非常易于访问，并附有作者在 http://trelford.com/blog 上发表的一系列博客文章/
This is an excellent example of a complete Small Basic implementation with F# and FParsec. It includes even IL compiler. The whole code is very accessible and is accompanied by a series of blog post from the author at http://trelford.com/blog/