Parser Combinators，分离语法和 AST 构造
Parser Combinators, separating grammar and AST construction
我正在使用解析器组合器库在 Scala 中编写一种简单的函数式编程语言。
此处指定语法：https://github.com/hejfelix/Frase/blob/master/src/main/scala/it/vigtig/lambda/ParserLike.scala
有一件事我无法通过实现解决：如何将语法定义与转换为 AST 节点分开？
直接在解析器源代码中使用接近人类可读的语法真的很棒，特别是考虑到我是 ATM 项目的唯一程序员并且它可以用作文档。
如何分离语法和特定于 AST 的代码？
嗯，原则上，你所有的 AST 转换都有一个特定的类型。您可以在其他地方定义它们并从您的语法定义中使用它们。它会稍微澄清一些事情。或者，您可以将语法定义定义为 "pass by name" 调用时计算的函数，然后在转换中使用它们。
基本上任何语言都允许您通过在某处定义事物并在其他任何地方引用它们来打破复杂性。由于 scala 允许您将函数作为值，这就更容易了。
这是一个很好的问题，在提出一个我认为对我来说非常有效的解决方案之前，我一直在努力解决这个问题。
构建解析器时，我使用了两种不同的语法树：
具体语法树，或 CST：这是文本的树形式，与文本有 1:1 对应关系。文本中出现的所有内容也将出现在 CST 中。
抽象语法树，或 AST：这不一定与文本有 1:1 对应关系，因为不必要的文本细节（例如大括号、标点符号等）具有已被删除，不会出现在 AST 中。
因此，从输入文本到AST有两个步骤：第一步是将输入字符串解析为CST；第二步是将 CST 转换为 AST，丢弃不必要的细节。
String -> CST 这是我使用解析器组合器的地方。 在此阶段我不对树结构进行任何操作。CST 的结构完全由使用的组合器决定。每个组合器都会产生一个特定形状的子树，我在这个阶段从未改变过。没有任何操作附加到组合器，因此语法定义是干净的，没有任何 AST 信息。
CST -> AST 这是我处理解析树的地方，提取重要内容，忽略其余部分。这也是我经常执行上下文相关检查的地方（例如：检查函数定义是否有重复的参数名称），将这些细节保留在实际解析阶段之外。
示例：这是我使用此方法构建的 JSON 解析器：
Would be really cool to have a close-to-human-readable grammar directly "building" the parser source...
我想知道“接近人类可读的语法”是什么？
How do I separate grammar definition from the transformation into AST nodes?
您拥有的是一个手写的 Packrat 解析器。
我可能是错的，但我将这个问题理解为请求使用独立的语法定义来构建解析器。然后使用该解析器获取解析源的语法树。
那么，语法可以是 EBNF 或 PEG 或 CFG 或“您自己的”语法，对吗？
总之...
让我们从“单独的语法定义”开始，例如EBNF.
然后你需要一个语法分析器，例如一个 EBNFParser.
使用该解析器结果解析语法是该语法的内部结构：语法树。
给定一个有效语法的语法树，您可以 return 一个包含键（作为元标识符）的关联列表并将语法规则附加到它们。
foreach grammar key add matching grammar rule
这意味着您需要选择由 RuleName 标识的语法规则并将其规则添加到“构造的解析器”。
最后：您有一个由各个“语法规则”组装而成的“构造解析器”，能够解析由给定语法定义的源代码。
解析源代码，为您提供源代码的语法树。
通过 1
Grammar -> GrammarParser -> GrammarTree -> GrammarRules -> ConstructedParserForGrammar
第 2 关
Source -> ConstructedParserForGrammar -> Syntax Tree -> Transformations...
换句话说：从 BNF 到自动构建的 Packrat 解析器是一个难题。
自此提交后
https://github.com/scala/scala-parser-combinators/commit/33792d3380791ddafb41760604857d2fc43e54e1
解析器组合器链接到 post，它准确地解决了我的问题。恕我直言，这是对我的问题最准确的回答。
这里的posthttps://enear.github.io/2016/03/31/parser-combinators/先词法化成一个具体的语法树（lexing），然后生成一个AST。
我把它留在这里是因为它为已接受的答案添加了一个示例。
我正在使用解析器组合器库在 Scala 中编写一种简单的函数式编程语言。
此处指定语法：https://github.com/hejfelix/Frase/blob/master/src/main/scala/it/vigtig/lambda/ParserLike.scala
有一件事我无法通过实现解决：如何将语法定义与转换为 AST 节点分开？
直接在解析器源代码中使用接近人类可读的语法真的很棒，特别是考虑到我是 ATM 项目的唯一程序员并且它可以用作文档。
如何分离语法和特定于 AST 的代码？
嗯，原则上，你所有的 AST 转换都有一个特定的类型。您可以在其他地方定义它们并从您的语法定义中使用它们。它会稍微澄清一些事情。或者，您可以将语法定义定义为 "pass by name" 调用时计算的函数，然后在转换中使用它们。
基本上任何语言都允许您通过在某处定义事物并在其他任何地方引用它们来打破复杂性。由于 scala 允许您将函数作为值，这就更容易了。
这是一个很好的问题，在提出一个我认为对我来说非常有效的解决方案之前，我一直在努力解决这个问题。
构建解析器时，我使用了两种不同的语法树：
具体语法树，或 CST：这是文本的树形式，与文本有 1:1 对应关系。文本中出现的所有内容也将出现在 CST 中。
抽象语法树，或 AST：这不一定与文本有 1:1 对应关系，因为不必要的文本细节（例如大括号、标点符号等）具有已被删除，不会出现在 AST 中。
因此，从输入文本到AST有两个步骤：第一步是将输入字符串解析为CST；第二步是将 CST 转换为 AST，丢弃不必要的细节。
String -> CST这是我使用解析器组合器的地方。 在此阶段我不对树结构进行任何操作。CST 的结构完全由使用的组合器决定。每个组合器都会产生一个特定形状的子树，我在这个阶段从未改变过。没有任何操作附加到组合器，因此语法定义是干净的，没有任何 AST 信息。CST -> AST这是我处理解析树的地方，提取重要内容，忽略其余部分。这也是我经常执行上下文相关检查的地方（例如：检查函数定义是否有重复的参数名称），将这些细节保留在实际解析阶段之外。
示例：这是我使用此方法构建的 JSON 解析器：
Would be really cool to have a close-to-human-readable grammar directly "building" the parser source...
我想知道“接近人类可读的语法”是什么？
How do I separate grammar definition from the transformation into AST nodes?
您拥有的是一个手写的 Packrat 解析器。
我可能是错的，但我将这个问题理解为请求使用独立的语法定义来构建解析器。然后使用该解析器获取解析源的语法树。
那么，语法可以是 EBNF 或 PEG 或 CFG 或“您自己的”语法，对吗？
总之...
让我们从“单独的语法定义”开始，例如EBNF.
然后你需要一个语法分析器，例如一个
EBNFParser.使用该解析器结果解析语法是该语法的内部结构：语法树。
给定一个有效语法的语法树，您可以 return 一个包含键（作为元标识符）的关联列表并将语法规则附加到它们。
foreach grammar key add matching grammar rule这意味着您需要选择由 RuleName 标识的语法规则并将其规则添加到“构造的解析器”。
最后：您有一个由各个“语法规则”组装而成的“构造解析器”，能够解析由给定语法定义的源代码。
解析源代码，为您提供源代码的语法树。
通过 1
Grammar -> GrammarParser -> GrammarTree -> GrammarRules -> ConstructedParserForGrammar
第 2 关
Source -> ConstructedParserForGrammar -> Syntax Tree -> Transformations...
换句话说：从 BNF 到自动构建的 Packrat 解析器是一个难题。
自此提交后
https://github.com/scala/scala-parser-combinators/commit/33792d3380791ddafb41760604857d2fc43e54e1
解析器组合器链接到 post，它准确地解决了我的问题。恕我直言，这是对我的问题最准确的回答。
这里的posthttps://enear.github.io/2016/03/31/parser-combinators/先词法化成一个具体的语法树（lexing），然后生成一个AST。
我把它留在这里是因为它为已接受的答案添加了一个示例。