解析器组合器、语法分离和AST构造

Question

我正在使用解析器-组合器库用Scala编写一个简单的函数式编程语言。

语法在这里指定：https://github.com/hejfelix/Frase/blob/master/src/main/scala/it/vigtig/lambda/ParserLike.scala

有一件事我无法用实现来解决:如何将语法定义从转换到AST节点中分离出来？

如果有一个接近人类可读的语法直接作为解析器的来源，那就太酷了，特别是考虑到我是ATM项目中唯一的程序员，而且它可以作为文档。

如何将语法和AST特定的代码分开？

Answer 1

这是一个很好的问题，在我想出一个对我来说很好的解决方案之前，我一直在努力解决这个问题。

在构建解析器时，我使用两种不同的语法树：

• 具体语法树，或CST:这是文本的树形式，与文本有1:1的对应关系。案文中的所有内容也将出现在科技委中。
• 摘要语法树，或AST:这不一定与文本有1:1的对应，作为不必要的文本细节(如大括号、标点符号等)。已经被移除并且没有出现在AST中。

因此，从输入文本到AST有两个步骤:第一步是将输入字符串解析为CST；第二步是将CST转换为AST，丢弃不必要的细节。

1. String -> CST --这是我使用解析器组合子的地方。我在这个阶段不对树结构做任何操作，，CST的结构完全由所使用的组合子决定。每个组合器产生一个特定形状的子树，在这个阶段我从未改变过。没有任何动作附加到组合器，所以语法定义是干净的，没有任何AST信息。
2. CST -> AST --这是我按摩解析树的地方，提取重要的内容，忽略其余的内容。这也是我经常执行上下文敏感检查的地方(例如:检查函数定义没有重复的参数名称)，使这些细节远离实际的解析阶段。

示例:下面是我使用此方法构建的JSON解析器：

• 通用解析器组合器
• 构建CST节点的组合器
• 构建CST的实际JSON解析器

Answer 2

原则上，所有AST转换都有一个特定的类型。您可以在其他地方定义它们，并从语法定义中使用它们。这会让事情变得更清晰。或者，您可以将语法定义定义为“按名称传递”函数，这些函数在调用时进行评估，然后从转换中使用它们。

基本上，任何语言都允许您通过在某个地方定义事物并在其他任何地方引用它们来打破复杂性。既然scala允许您将函数作为值使用，这就更容易了。

Answer 3

如果有一个接近人类可读的语法，直接“构建”解析器源，那就太酷了.

我想知道“接近人类可读的语法”是什么？

如何将语法定义从转换到AST节点中分离出来？

你有一个手写的Packrat Parser。

我可能错了，但我把这个问题理解为请求使用独立的语法定义来构建解析器。然后使用该解析器获取解析源的语法树。

所以，语法可以是EBNF，PEG，CFG或者“你自己的”语法，对吗？

不管怎样..。

• 让我们从“单独的语法定义”开始，例如EBNF。
• 然后，您需要语法解析器，例如EBNFParser。
• 使用解析器结果解析语法是该语法的内部结构:语法树。
• 给定有效语法的语法树，您可以返回带有键(作为元标识符)的关联列表，并将语法规则附加到它们。 foreach grammar key add matching grammar rule
• 这意味着您需要选择由RuleName标识的语法规则，并将其规则添加到“构造解析器”中。
• 最后:您有一个“构造解析器”，由单个“语法规则”组装而成，能够解析给定语法定义的源。
• 解析Source，为源提供一个语法树。

通行证1

Grammar -> GrammarParser -> GrammarTree -> GrammarRules -> ConstructedParserForGrammar

通行证2

Source -> ConstructedParserForGrammar -> Syntax Tree -> Transformations...

换句话说，从BNF到自动构造的Packrat解析器是一个相当大的难题。