logo标签列表

F# 解析抽象语法树

f#language-designabstract-syntax-tree
14
什么是使用 F# 解析 AST 并构建解释器的最佳方法？有许多 F# 的示例适用于简单的语法（基本算术操作），但我似乎找不到适用于具有更大范围特性的语言的示例。
区分联合看起来非常有用，但如果选项很多，应该如何构造它？是在其他地方定义类型（例如加法、减法、条件语句、控制流）并将它们作为预定义类型引入联合中更好呢？
或者我错过了编写解释器的其他更有效的方法？对于每种类型使用一个 eval 函数是否更有效，或者也许使用单子？
提前感谢您。
6个回答
14
“Discriminated unions”看起来非常有用，但如何构建具有大量选项的联合类型？是在其他地方定义类型（例如加法、减法、条件语句、控制流），然后将它们作为预定义类型组合到联合中更好呢？我不确定你在这里问什么问题；即使有很多选项，DUs 仍然很容易定义。例如，请参见此博客条目，其中介绍了一个小语言的 DU 结构（以及关于编写树转换的更一般讨论）。拥有许多更多情况的 DU 是可以的，并且在编译器/解释器中使用这种表示方式很常见。
至于解析，我喜欢单子解析器组合器；请查看FParsec或参见此旧博客条目。在使用这样的解析器组合器之后，我再也无法回到类似 lex/yacc/ANTLR 的任何东西——相比之下，外部 DSLs 看起来如此原始。
（编辑：你找到的“小算术示例”可能基本上代表了更大解决方案的情况。通常，“玩具”示例展示了正确的架构。）
旧博客文章的链接似乎已经失效。 - Dmitry G.
4
你应该获取Robert Pickering的“Beginning F#”一书的副本。
第13章“解析文本”包含一个示例，其中使用了FsLex和FsYacc，正如Noldorin所建议的那样。
除此之外，在同一本书的第12章中，作者解释了如何为他提出的算术语言构建一个实际的简单编译器。非常有启发性。最重要的部分是你正在寻找的：AST解析器。
祝你好运。
3
很高兴看到人们已经开始阅读《Beginning F#》了 :). 我应该指出，第12章还涵盖了FParsec (http://www.quanttec.com/fparsec/)，这是一个单子解析器。这可能是我现在更喜欢在F#中创建解析器的方法，因为它意味着您不必使用外部工具和代码生成。 - Robert
3

我赞同Brian的建议，看一下FParsec。如果你有兴趣用FsLex和FsYacc以老派的方式完成工作，可以查看F#自身源代码来了解如何解析一个复杂的语言。请参阅分发中的fsharp\FSharp.Compiler目录。

2
我没有亲自做过解释器。希望以下内容能帮到您：）这里是耶鲁大学教授的编译器课程，使用ML语言，您可能会发现它很有用。讲义非常简洁（短）且富有启发性。您可以跟随前几节课的笔记和作业，因为您了解F＃，所以阅读ML程序时不会有问题。顺便说一下，这位教授曾是A. Appel的学生，后者是SML实现的创造者。因此，从这些笔记中，您还可以获得在ML系列语言中编写编译器/解释器最自然的方式。
2
您可能会对查看 F# WikiBook 中的 词法分析和语法分析 部分感兴趣。F# PowerPack 库 包含了 FsLex 和 FsYacc 工具，这些工具在此方面有很大帮助。WikiBook 指南是入门的好方式。
除此之外，您需要考虑如何从 AST 形式执行代码，这是编译器和解释器的共同设计。然而，这通常被认为是更容易的部分，并且有很多关于编译器/解释器的通用资源可以提供相关信息。
0

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

小型基础实现的链接已经失效。我认为现在它在 https://github.com/ptrelford/smallbasiccompiler 上。 - GrumpyRodriguez
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接