static-analysis - 如何为专有语言构建 AST？

Question

我试图了解如何为专有语言构建 AST。我需要构建一个 AST，以便我可以输入我的规则和指南，以检查源代码中可能存在的错误。

如何构建 AST？是否有任何书籍、文章可以帮助我入门。关于编译器的龙书有帮助吗？

请注意，我来自非 CS 背景。

谢谢

Answer 1

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

您在研究中可能会经常看到的一件事是扩展巴科斯-诺尔形式 (EBNF)。它基本上是描述您的语言的一种方式。为你的语言创建一个 EBNF 将帮助你理解计算机需要做什么来解析它，它会有所帮助。

回到手头的问题:您可能会使用词法分析器/解析器来构建树。

用于执行此操作的传统工具是 lex 和 yacc，或者它们更现代的表亲 flex 和 bison。

较新的方法是 Antlr .强烈推荐它，但超出了我的头脑。

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

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

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

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