如何为专有语言构建AST？

Question

我想了解如何为专有语言构建AST。我需要构建一个AST，这样我就可以提供我的规则和准则，以检查源代码中可能出现的错误。

如何构建AST？有没有任何书籍，文章可以帮助我开始。龙书上的编译器会有帮助吗？

请注意我来自非CS背景。

谢谢

Answer 1

这是一个相当大的问题。我确实感到你的痛苦，因为我也从非CS背景中解决了这个问题。这让我很欣赏CS。

您可能会在您的研究中看到很多东西的一个方面是Extended Backus-Naur Form（EBNF）。这基本上是一种描述你的语言的方式。为你的语言创建一个EBNF将帮助你解决计算机需要解析的东西，这将有所帮助。

回到当前的问题：您可能会使用词法分析器/解析器来构建树。

用来做这件事的传统工具是lex和yacc，或者他们更现代的表兄弟flex和野牛。

较新的方法是Antlr。它被强烈推荐，但是在我的头上。

我发现的第三种方法是Python的pyparsing库。由于我对Python的熟悉程度以及它描述你需要解析什么的可读方式，所以我最终选择了它。

还有plenty of examples可用于pyparsing，这有帮助。我发现建立我的解析器最有帮助的是SimpleCalc。然而，它基于pyparsing的一个相当老的版本，并且比它需要用于稍后实现的pyparsing的一些强大操作更复杂。 SimpleArith是一个相似，但更新的版本。

我还没有用pyparsing实际处理过的一件事是正确分析语法错误。但是，它似乎为您提供了必要的工具。

无论如何，这不是一个真正的完整答案你的问题，但我希望它至少指出你在几个地方开始。为复杂语言构建解析器并不容易！

Answer 2

代码分析引擎通常需要相当多的复杂性，而不仅仅是构建AST。

要做任何严肃的代码分析，您需要知道代码中标识符的含义以及它们在何处/如何定义（“符号表”），并且您经常需要知道信息如何在程序中传播（控制和数据流分析）。您需要机器来支持所有这些，然后您需要将该机器绑定到您的专有语言。

我认为攀登珠穆朗玛峰是一个比喻。获得ASTs就像进入10,000英尺的大本营。任何土块都可以通过使用基本技术（登山靴）爬上山坡来实现。攀登最后17,000英尺需要一种完全不同的技术，承诺和计划，而大多数人在走过第一个10,000英尺时，对于旅程的其余部分毫无准备。 （我在这里有一些经验，检查我的生物）。

这些都是非常详细的主题，你缺少CS背景将会为你打开一条路，可能会非常艰难。 （但是，我们都从某个地方开始，所以这确实是一个雄心壮志的问题）。龙书是一个很好的资源，可以帮助你理解所有这些机器的功能，以及你为什么需要它。存在许多其他优秀的编译器书籍，并且通常也是如此。但你需要准备好认真阅读。

找到曲线的一种方法是使用一种工具，其中许多这种机器已经被大量计算机科学家在构建这样的工具方面经验丰富的人想到并实施。那么你的问题就会大大减少：你只需要学习如何使用他们提供的东西，而不是试图弄清楚你需要什么（大多数人从来没有通过AST阶段），并实施所有必要的支持机制。

ANTLR（已经提到过，由一位非常好的CS教授完成）是一种排序方式，它提供了解析功能，使您能够定义AST如何构建以及如何在程序上爬过结果AST。但它没有提供任何你需要的任务。

我们的DMS Software Reengineering Toolkit提供了我在第一段中提到的所有设施，然后是一些。你会注意到与DMS合作的第一个区别是你只需要提供语法;它会在没有任何进一步帮助的情况下构建AST。

你可以得到一个什么与DMS工作的味道是这样的，在这个example of DMS applied to high school algebra and calculus。特别是，它展示了如何简单地定义代数/演算的简单语法，然后可以操作该语言的“程序”。此应用程序是“转换”代码而不是分析它的应用程序，但基本相同。

分析您专有语言的“真实”DMS应用程序将会相当复杂。