漂亮的打印歧义语法
Pretty printing ambiguous grammar
我已经实现了解析器组合器，它可以解析可能包含歧义的语法。当语法有歧义时会给出错误，但事实证明，朝另一个方向前进会更加困难。问题是如何用最少的括号将抽象语法树漂亮地打印成可能有歧义的语法。使用运算符优先级有帮助，但不是万灵药。在同一个优先级内，问题依旧。
直到运行时才知道确切的运算符，并且可以在用户引入新运算符时在执行期间更改。我支持前缀、后缀和中缀（左、右和非关联）运算符。中缀左运算符和后缀运算符同时在优先级混合。这同样适用于中缀右和前缀运算符。运算符还可以嵌入完整表达式，因此 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 d 或 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 中使后一个表达式 if a then inc (if b then c) else d，但随后 inc if a then b 变成 inc (if a then b)，括号太多。
据我所知，语法是上下文无关的。不过我对这个定义有点犹豫。
解析器大致基于论文 here。
我正在使用 Haskell.
更新：正如NieDzejkob所证明的那样，这个问题一般来说是无法解决的。我愿意接受一个可能会失败的算法。如果这还不足以使事情变得实用，那么好的启发式方法就可以了。
您可以根据所定义的实际结合性和优先级在所有运算符之间构建排序的偏序关系。
因为运算符的优先级取决于递归发生在规则中的哪个位置（最左边、中间或最右边），所以关系应该包括优先级适用于父节点的哪个位置。
假设关系的类型为 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/Priorities.rsc
它从这样的规则开始：
E = left E "*" E
> left E "+" E
;
并生成如下内容：
{<"*", 0, "+">, <"*", 2, "+"> // priority between * and +
,<"+", 2, "+">, <"*", 2, "*"> // left associativity of * and +
}
这个table解释了哪些嵌套在哪些位置需要额外的括号，所以如果
a + 嵌套在 a * 下的第 0 个位置，您需要打印括号
假设您有一个优先级 table 而不是：
0 * left
1 + left
什么的，那么就可以构造出类似的关系。我们必须为 table 中的每个 i, j 级别生成一个元组，其中 i < j。当然，您必须查找每个操作员的规则才能找出正确的位置。
对于这些 tables 和 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.
}
有关此主题的论文，但它们使用相同的关系进行解析而不是反解析：
总的来说，这是不可能的。考虑运算符 A_B、_C_、A_C_B。表达式 A_C_B 1 2（即 A 1 C 2 B）无法加括号，因此无法解析为 A (1 C 2) B.
我已经实现了解析器组合器，它可以解析可能包含歧义的语法。当语法有歧义时会给出错误，但事实证明，朝另一个方向前进会更加困难。问题是如何用最少的括号将抽象语法树漂亮地打印成可能有歧义的语法。使用运算符优先级有帮助，但不是万灵药。在同一个优先级内，问题依旧。
直到运行时才知道确切的运算符，并且可以在用户引入新运算符时在执行期间更改。我支持前缀、后缀和中缀（左、右和非关联）运算符。中缀左运算符和后缀运算符同时在优先级混合。这同样适用于中缀右和前缀运算符。运算符还可以嵌入完整表达式，因此 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 d 或 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 中使后一个表达式 if a then inc (if b then c) else d，但随后 inc if a then b 变成 inc (if a then b)，括号太多。
据我所知，语法是上下文无关的。不过我对这个定义有点犹豫。
解析器大致基于论文 here。 我正在使用 Haskell.
更新：正如NieDzejkob所证明的那样，这个问题一般来说是无法解决的。我愿意接受一个可能会失败的算法。如果这还不足以使事情变得实用，那么好的启发式方法就可以了。
您可以根据所定义的实际结合性和优先级在所有运算符之间构建排序的偏序关系。
因为运算符的优先级取决于递归发生在规则中的哪个位置（最左边、中间或最右边），所以关系应该包括优先级适用于父节点的哪个位置。
假设关系的类型为 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/Priorities.rsc
它从这样的规则开始：
E = left E "*" E
> left E "+" E
;
并生成如下内容：
{<"*", 0, "+">, <"*", 2, "+"> // priority between * and +
,<"+", 2, "+">, <"*", 2, "*"> // left associativity of * and +
}
这个table解释了哪些嵌套在哪些位置需要额外的括号，所以如果
a + 嵌套在 a * 下的第 0 个位置，您需要打印括号
假设您有一个优先级 table 而不是：
0 * left
1 + left
什么的，那么就可以构造出类似的关系。我们必须为 table 中的每个 i, j 级别生成一个元组，其中 i < j。当然，您必须查找每个操作员的规则才能找出正确的位置。
对于这些 tables 和 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.
}
有关此主题的论文，但它们使用相同的关系进行解析而不是反解析：
总的来说，这是不可能的。考虑运算符 A_B、_C_、A_C_B。表达式 A_C_B 1 2（即 A 1 C 2 B）无法加括号，因此无法解析为 A (1 C 2) B.