0

据我了解，大多数语言都是上下文无关的，但也有一些例外。例如，在 C++ 中a * b可能代表或乘法。type * pointer_declaration哪个发生取决于上下文，第一个标识符的含义。另一个例子是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 也值得显示文件内容。但是，如果语法是上下文相关的（假设这f是一个函数，在另一个文件中定义，但后来用户将其重新限定为枚举文字或未定义），则 AST 无效。在这种情况下，AST 会发生变化。每当您更改依赖项时，AST 都会更改。我要求评估并让我知道如何制作的另一种选择是构建一个模棱两可的 AST。

据我所知，解析器组合器是PEG 类型的。他们通过返回第一个匹配的产品来隐藏歧义，并且f会匹配一个函数调用，因为它是我语法中的第一个替代方案。我要求一个组合器，它不会退回到第一次成功，而是继续下一个替代方案。最后，它会返回给我一个所有匹配选项的列表。它会让我感到模棱两可。

我不知道您将如何向用户显示不明确的文件内容树，但它会消除重新解析依赖文件的需要。我也很高兴知道现代语言设计如何解决这个问题。

一旦解析了不明确的节点并返回了不明确的结果，我希望解析器收敛，因为我想继续解析，name并且我不想在每个歧义之后解析到文件末尾。这种情况因诸如 之类的情况而变得复杂f(10)，它可以是带有单个参数的函数调用，也可以是返回一个数组的空函数调用，该数组随后被索引。因此，f(10) 可以通过两种方式匹配名称，func_call直接匹配或递归匹配arr_indexing -> name ~ (expr)。因此，它不会像几个并行规则那样模棱两可，例如fcall | literal. 在重新收敛之前，某些分支可能比 1 个解析器长，例如fcall ~ (expr) | fcall.

你将如何解决它？是否可以将歧义组合器添加到 PEG？

4

1 回答 1

2

首先，您声称“大多数语言都是上下文无关的，但有一些例外”，这并不完全正确。在设计一种计算机语言时，我们大多尽量保持它与上下文无关，因为 CFG 是事实上的标准。它会减轻很多工作。然而，这并不总是可行的，并且很多[?]语言依赖于语义分析阶段来消除任何可能的歧义。

解析器组合器通常不使用正式模型；另一方面，PEG 是语法的一种形式，CFG 也是如此。在过去的十年中，由于两个事实，一些人决定使用 PEG 而不是 CFG：PEG 在设计上是明确的，并且它们可能总是在线性时间内被解析。解析器组合库可能使用 PEG 作为底层形式，但也可能使用 CFG 甚至不使用。

PEG 对设计计算机语言很有吸引力，因为我们通常不想处理歧义，这在使用 CFG 时很难（甚至不可能）避免。并且，正因为如此，它们可能会通过使用动态编程（所谓的 Packrat 解析器）来解析 O(n) 时间。出于几个原因，“给它们添加歧义”并不简单，最重要的是因为它们识别的语言取决于选项是确定性的这一事实，例如在检查前瞻时使用。它并不像“只选择第一选择”那么简单。例如，您可以定义一个 PEG：

S = "a" S "a" / "aa"

仅解析N "a" 的序列，其中 N 是 2 的幂。因此它可以识别 2、4、8、16、32、64 等字母“a”的序列。通过添加歧义，就像 CFG 那样，那么您将识别任何偶数个“a”（2、4、6、8、10 等），这是一种不同的语言。

要回答你的问题，

你将如何解决它？是否可以将歧义组合器添加到 PEG？

首先我必须说这可能不是一个好主意。如果您希望在 AST 上保持歧义，您可能应该改用 CFG 解析器。

例如，可以为 PEG 制作一个解析器，它类似于布尔语法的解析器，但是通过在保持相同语言的同时保持所有备选方案有效，我们的渐近解析时间将从 O(n) 增长到 O(n 3 ) . 我们实际上同时失去了关于 PEG 的两个优点。

另一种方法是将 Packrat 解析器保留在内存中，并横向处理其表以处理来自 AST 的语义。也不是一个好主意，因为这意味着很大的内存占用。

理想情况下，应该通过更改语法结构来构建一个已经包含有关可能歧义的信息的 AST。虽然这需要手动工作，而且通常并不简单，但您不必返回一个阶段再次检查语法。

于 2016-09-10T01:31:29.220 回答