如何将 PEG 解析器转换为不明确的解析器？
How do I convert PEG parser into ambiguous one?
据我所知，除了一些例外，大多数语言都是上下文无关的。例如，a * b 可能代表 type * pointer_declaration 或 C++ 中的乘法。发生哪一个取决于上下文，即第一个标识符的含义。另一个例子是 name VHDL 中的生产
enum_literal ::= char_literal | identifer
physical_literal ::= [num] unit_identifier
func_call ::= func_identifier [parenthized_args]
array_indexing ::= arr_name (index_expr)
name ::= func_call | physical_literal | enum_litral | array_indexing
你看句法形式不一样但是如果省略可选参数也能匹配，比如f，是不是代表func_call，physical_literal，比如1米带可选隐含数量 1，或 enum_literal。
与 Scala 插件设计者交谈后，我了解到构建 AST 是为了在依赖项发生变化时重新评估它。如果您有 AST，则无需重新解析文件。 AST 也值得显示文件内容。但是，如果语法是上下文相关的，则 AST 无效（假设 f 是一个函数，在另一个文件中定义，但后来用户将其重新限定为枚举文字或未定义）。在这种情况下 AST 发生了变化。每当您更改依赖项时，AST 都会更改。我要求评估并让我知道如何制作的另一种选择是构建一个模棱两可的 AST。
据我所知，解析器组合子 PEG kind. They hide the ambiguity by returning you the first matched production 和 f 将匹配函数调用，因为它是我语法中的第一个替代项。我要求的是一个组合器，它不会返回到第一个成功，而是继续进行下一个选择。最后，它会 return 我列出所有匹配的备选方案。这会让我 return 模棱两可。
我不知道您将如何向用户显示不明确的文件内容树，但它会消除重新解析相关文件的需要。我也很高兴知道现代语言设计如何解决这个问题。
一旦解析了不明确的节点并且结果的歧义被 returned，我希望解析器收敛，因为我想在 name 之后继续解析并且我不想解析每次歧义后到文件末尾。这种情况因 f(10) 之类的情况而变得复杂，它可以是具有单个参数的函数调用或空函数调用，其中 return 是一个数组，之后会对其进行索引。因此，f(10) 可以通过两种方式匹配名称，直接作为 func_call 或递归地作为 arr_indexing -> name ~ (expr)。所以，它不会像fcall | literal这样的几个并行规则那样出现歧义。某些分支在重新收敛之前可能比 1 个解析器长，例如 fcall ~ (expr) | fcall.
你会如何解决它？是否可以向 PEG 添加歧义组合器？
首先你声称“除了一些例外大多数语言都是上下文无关的”，这并不完全正确。在设计计算机语言时，我们主要尝试尽可能使其与上下文无关，因为 CFG 是该语言的实际标准。它会减轻很多工作。不过，这并不总是可行的，许多[?] 语言依赖于语义分析阶段来消除任何可能的歧义。
解析器组合器通常不使用正式模型；另一方面，PEG 是语法的一种形式主义，CFG 也是如此。在过去的十年中，由于两个事实，一些人决定使用 PEG 而不是 CFG：PEG 在设计上是明确的，并且它们可能总是在线性时间内被解析。解析器组合器库 可能 使用 PEG 作为基础形式，但也可以使用 CFG 甚至 none.
PEG 对于设计计算机语言很有吸引力，因为我们通常不想处理歧义，而使用 CFG 时很难（甚至不可能）避免歧义。并且，正因为如此，它们可能会通过使用动态编程（所谓的 Packrat 解析器）来解析 O(n) 时间。 It's not simple to "add ambiguities to them" for a few reasons, most importantly because the language they recognize depend on the fact that the options are deterministic, which is used for example when checking for lookahead。它不像"just picking the first choice"那么简单。例如，您可以定义一个 PEG：
S = "a" S "a" / "aa"
仅解析 N "a" 的 序列，其中 N 是 2 的幂。所以它识别的序列是 2、4、8、16、32、64 等，字母 "a"。通过添加歧义，正如 CFG 所具有的那样，您将识别任意偶数的 "a"（2、4、6、8、10 等）， 这是一种不同的语言.
为了回答你的问题，
How would you go about solving it? Is it possible to add ambiguating combinator to PEG?
首先我必须说这可能不是一个好主意。如果您希望在 AST 上保持歧义，您可能应该改用 CFG 解析器。
例如，可以为 PEG 制作一个类似于 boolean grammars 的解析器的解析器，但是我们的渐近解析时间将从 O(n) 增长到 O(n3) 通过在保持相同语言的同时保持所有替代方案。我们实际上同时失去了 PEG 的两个优点。
另一种方法是将 Packrat 解析器保留在内存中，并横向处理其 table 以处理来自 AST 的语义。这也不是一个好主意，因为这意味着占用大量内存。
理想情况下，应该构建一个 AST，它已经通过更改语法结构获得了关于可能的歧义的信息。虽然这需要手动操作，而且通常并不简单，但您不必返回一个阶段再次检查语法。
据我所知，除了一些例外，大多数语言都是上下文无关的。例如，a * b 可能代表 type * pointer_declaration 或 C++ 中的乘法。发生哪一个取决于上下文，即第一个标识符的含义。另一个例子是 name VHDL 中的生产
enum_literal ::= char_literal | identifer
physical_literal ::= [num] unit_identifier
func_call ::= func_identifier [parenthized_args]
array_indexing ::= arr_name (index_expr)
name ::= func_call | physical_literal | enum_litral | array_indexing
你看句法形式不一样但是如果省略可选参数也能匹配，比如f，是不是代表func_call，physical_literal，比如1米带可选隐含数量 1，或 enum_literal。
与 Scala 插件设计者交谈后，我了解到构建 AST 是为了在依赖项发生变化时重新评估它。如果您有 AST，则无需重新解析文件。 AST 也值得显示文件内容。但是，如果语法是上下文相关的，则 AST 无效（假设 f 是一个函数，在另一个文件中定义，但后来用户将其重新限定为枚举文字或未定义）。在这种情况下 AST 发生了变化。每当您更改依赖项时，AST 都会更改。我要求评估并让我知道如何制作的另一种选择是构建一个模棱两可的 AST。
据我所知，解析器组合子 PEG kind. They hide the ambiguity by returning you the first matched production 和 f 将匹配函数调用，因为它是我语法中的第一个替代项。我要求的是一个组合器，它不会返回到第一个成功，而是继续进行下一个选择。最后，它会 return 我列出所有匹配的备选方案。这会让我 return 模棱两可。
我不知道您将如何向用户显示不明确的文件内容树，但它会消除重新解析相关文件的需要。我也很高兴知道现代语言设计如何解决这个问题。
一旦解析了不明确的节点并且结果的歧义被 returned，我希望解析器收敛，因为我想在 name 之后继续解析并且我不想解析每次歧义后到文件末尾。这种情况因 f(10) 之类的情况而变得复杂，它可以是具有单个参数的函数调用或空函数调用，其中 return 是一个数组，之后会对其进行索引。因此，f(10) 可以通过两种方式匹配名称，直接作为 func_call 或递归地作为 arr_indexing -> name ~ (expr)。所以，它不会像fcall | literal这样的几个并行规则那样出现歧义。某些分支在重新收敛之前可能比 1 个解析器长，例如 fcall ~ (expr) | fcall.
你会如何解决它？是否可以向 PEG 添加歧义组合器？
首先你声称“除了一些例外大多数语言都是上下文无关的”，这并不完全正确。在设计计算机语言时，我们主要尝试尽可能使其与上下文无关，因为 CFG 是该语言的实际标准。它会减轻很多工作。不过，这并不总是可行的，许多[?] 语言依赖于语义分析阶段来消除任何可能的歧义。
解析器组合器通常不使用正式模型；另一方面，PEG 是语法的一种形式主义，CFG 也是如此。在过去的十年中，由于两个事实，一些人决定使用 PEG 而不是 CFG：PEG 在设计上是明确的，并且它们可能总是在线性时间内被解析。解析器组合器库 可能 使用 PEG 作为基础形式，但也可以使用 CFG 甚至 none.
PEG 对于设计计算机语言很有吸引力，因为我们通常不想处理歧义，而使用 CFG 时很难（甚至不可能）避免歧义。并且，正因为如此，它们可能会通过使用动态编程（所谓的 Packrat 解析器）来解析 O(n) 时间。 It's not simple to "add ambiguities to them" for a few reasons, most importantly because the language they recognize depend on the fact that the options are deterministic, which is used for example when checking for lookahead。它不像"just picking the first choice"那么简单。例如，您可以定义一个 PEG：
S = "a" S "a" / "aa"
仅解析 N "a" 的 序列，其中 N 是 2 的幂。所以它识别的序列是 2、4、8、16、32、64 等，字母 "a"。通过添加歧义，正如 CFG 所具有的那样，您将识别任意偶数的 "a"（2、4、6、8、10 等）， 这是一种不同的语言.
为了回答你的问题，
How would you go about solving it? Is it possible to add ambiguating combinator to PEG?
首先我必须说这可能不是一个好主意。如果您希望在 AST 上保持歧义，您可能应该改用 CFG 解析器。
例如，可以为 PEG 制作一个类似于 boolean grammars 的解析器的解析器，但是我们的渐近解析时间将从 O(n) 增长到 O(n3) 通过在保持相同语言的同时保持所有替代方案。我们实际上同时失去了 PEG 的两个优点。
另一种方法是将 Packrat 解析器保留在内存中，并横向处理其 table 以处理来自 AST 的语义。这也不是一个好主意，因为这意味着占用大量内存。
理想情况下，应该构建一个 AST，它已经通过更改语法结构获得了关于可能的歧义的信息。虽然这需要手动操作，而且通常并不简单，但您不必返回一个阶段再次检查语法。