1

我已经实现了解析器组合器，它可以解析可能包含歧义的语法。当语法不明确时会出现错误，但事实证明朝另一个方向前进会更加困难。问题是如何用最少的括号将抽象语法树漂亮地打印成可能不明确的语法。使用运算符优先级会有所帮助，但不是万能的。在相同的优先级内，问题仍然存在。

确切的运算符直到运行时才知道，并且在用户引入新运算符时可以在执行期间更改。我支持前缀、后缀和中缀（左、右和非关联）运算符。中缀左和后缀运算符同时在优先级上混合。这同样适用于中缀右和前缀运算符。运算符还可以嵌入完整的表达式，因此 if-then-else 和 if-then 都可以实现为前缀运算符。（尽管这可能不是明智之举。）

这是一个使用提到的 if-then-else 和 if-then 运算符的示例，这里假定它们处于相同的优先级。显然，该表达式if a then if b then c else d是模棱两可的，因为它可以解释为if a then (if b then c) else dor if a then (if b then c else d)。在漂亮打印期间，即使两个运算符处于相同的优先级并且具有兼容的关联性（右侧），算法也应该知道使用括号。

一个警示性示例：添加另一个前缀运算符 say inc，其优先级与 if-then-else 和 if-then 相同。现在假设一个任意集合P ⊂ H x O，其中H是算子孔O集，是算子集。该集合是一种关系，它告诉何时需要添加括号。检查表达式if a then inc b else c和if a then (inc if b then c) else d。第一个要求(if-then-else.2, inc)不参加P，第二个要求相反。这与问题可以通过某种关系或顺序解决的假设相矛盾。可以尝试(inc.1, if-then)在P做后一个表达式时说 let is if a then inc (if b then c) else d，但随后inc if a then b变成inc (if a then b)了有太多括号的。

据我所知，语法是上下文无关的。不过，我对定义有点摇摆不定。

解析器松散地基于此处的一篇论文。我正在使用 Haskell。

更新：正如 NieDzejkob 所证明的，这个问题通常是无法解决的。我愿意接受可能失败的算法。如果这还不足以使事情变得实用，那么一个好的启发式方法就可以了。

4

2 回答 2

1

您可以根据定义的实际关联性和优先级在所有运算符之间构建排序的偏序关系。

因为运算符的优先级取决于递归发生在规则中的哪个位置（最左边、中间或最右边），所以关系应该包括优先级所在的父节点的哪个位置。

说关系有 type rel[Operator parent, int pos, Operator child]。

假设您可以在运行时应用优先级和关联性声明来生成此关系，那么在漂亮打印期间使用此关系添加括号很容易。如果元组 [parent, pos, child] 在关系中，则打印括号，否则不打印（反之亦然，如果关系反转）。

如何得到这个关系？这里有 Rascal 的语法形式的示例代码，它从运算符之间的相对优先级生成它：https ://github.com/usethesource/rascal/blob/master/src/org/rascalmpl/library/lang/rascal/grammar/definition/优先级.rsc

它从以下规则开始：

E = left E "*" E  
  > left E "+" E
  ;

并产生类似的东西：

{<"*", 0, "+">, <"*", 2, "+"> // priority between * and + 
,<"+", 2, "+">, <"*", 2, "*"> // left associativity of * and +
}

此表说明了哪些位置的哪些嵌套需要额外的括号，因此如果 a+嵌套在*第 0 个位置的 a 下，则需要打印括号

假设你有一个优先表，而不是说：

0 * left
1 + left

或徒劳的东西，然后可以构建类似的关系。i, j我们必须为表中的每个级别生成一个元组i < j。当然，您必须查找每个操作员的规则以找出正确的位置。

对于这些表和 Rascal 中的相对优先级，传递关闭关系很重要，但是如果您不想在漂亮的打印时生成太多括号，则不能添加一些元组。

也就是说，如果父规则是最右递归的，而子规则是最左递归的，那么括号是必要的。反之亦然。但否则不会。考虑这个例子：

E = "if" E "then "E"
  > E "+" E
  ;

在这种情况下，我们确实希望在最右边的孔中使用括号，但不在“if”和“then”之间的保护孔中。索引规则的类似示例，例如E "[" E "]"等。

为了确保这有效，您可以首先计算哪些规则是最右边的，哪些规则是最左边的递归，然后从传递闭包中过滤出没有歧义的元组，因为它们没有处于歧义的位置。

所以对于上面的例子，我们会生成这个：

{<"if", 3, "+">, // and not <"if", 1, "+"> because the 1 position is not left-most recursive, even though the "+" is right-most recursive.
}

关于这个主题的论文，但它们使用相同的关系进行解析而不是反解析：

于 2018-05-20T08:13:26.793 回答
1

总的来说，这是不可能的。考虑运算符A_B, _C_, A_C_B. 表达式A_C_B 1 2(ie A 1 C 2 B) 不可能用括号括起来，因此它不能被解析为A (1 C 2) B。

于 2021-02-24T23:23:18.717 回答