解析挑战 : Old logician's dot notation

Question

在 J. Barkley Rosser 的“Logic for Mathematicians”中，他使用了一种符号来避免括号过多。虽然我不知道逻辑学家什么时候开始使用这个符号，但我知道那本书最早出版于 1957 年，而且 J. G. P. Nicod's paper 1916 年出版的也使用了这种表示法。很明显，它有着相当长的历史，尽管现在现代逻辑学家并不喜欢它。

在编程世界中，在类似 LISP 的编程语言中，程序员要跟踪正确(巨大!)数量的括号是一个巨大的挑战。 Haskell 提供了一个操作符 $提供部分功能，但因为你不能说 2 * $ 3 + 4它不像点那么强大(见下面的例子)。 C 语言序列使用传统的操作优先级，但在某些情况下仍然需要深嵌套括号。所以我想知道为什么没有实际的语言使用这种策略？我试过了，但我发现我什至无法为它写一个语法!

让我展示一些只有两个运算符的玩具计算器语言的示例 +和 * ，并且所有项都是整数。

使用此符号，翻译器应通过以下测试用例:

1 + 3 .* 2
= (1 + 3) * 2
1 *. 3 + 2
= 1 * (3 + 2)
1 *. 2 +. 2
= (1 * 2) + 2
2 *: 2 + 3 .* 4
= 2 * ((2 + 3) * 4)

我无法解释这个符号的所有细节，它在 Rosser 的书中花费了将近 5 页。但总的来说(简而言之)，一个点 .操作符之前或之后代表“分隔符”，将两侧推开。冒号 :是更强的分隔符，三个点 .:或 :.甚至更强，但不及 :: ， 等等。

我想知道我们如何为上述语言编写语法然后解析它？此外，虽然这个符号已经过时，但我发现它在程序员的眼中看起来非常清晰。那么它的优缺点是什么呢？

Answer 1

圆点表示法最著名的是罗素和怀特黑德在 Principia Mathematica 中使用的。 (1910-1913) 但符号是从 Guiseppe Peano 借来的.它也被 Alonzo Church、Willard Van Orman Quine 和其他有影响力的逻辑学家使用(参见斯坦福哲学百科全书中的 this entry)。

通过一些练习，阅读点符号中的公式并不难，但它并不像最初出现的那样优雅。首先，Russell 和 Whitehead 仍然发现在否定运算符 ~ 中使用括号很有用。 :
*3·01. p.q .=. ~(~p v ~q)
如上例所示，点既用作连词运算符又用于表示优先级。因此，更强的合取可以写成 :甚至 :. .

最后，为了减少视觉困惑(我想)，Russell 和 Whitehead 还使用了优先关系，其中将运算符集分为三个优先级组，这样优先级较高的运算符的点支配了相同数量的点对于优先级较低的运算符。在同等优先级的运算符之间，点数相等是不合法的，但罗素和怀特黑德也定义了一些三元运算符，例如p v q v r为了能够避免必须指定不重要的优先级。 (据我所知，此类表达式的精确解析规则从未正式阐明，但定义出现在 PM 中。)

话虽如此，使用调车码算法的变体解析点符号并不是非常困难。不幸的是，它无法使用上下文无关文法进行解析，这使得它对于使用自动化工具生成的文法不太有用。甚至 GLR 解析器也仅限于 CFG。 (点符号不是上下文无关的事实可以用泵引理证明；它比通常的泵引理应用程序更有趣，至少恕我直言。)

如果您允许 CFG 具有无限数量的(点)符号和相应的无限数量规则，那么编写文法(或者更准确地说，是文法模板，因为大多数规则都是由点参数化的)是非常简单的-数数)。因此，理论上您可以通过首先扫描找到使用的最大点数来解析点表达式，然后从模板生成相应的有限 CFG。 (结果是 LALR(1)，只要您为每个点序列定义一个单独的终端。)实际上，这将通过在 CFG 中使用谓词来完成，因此您可以创建一个带有解析器生成器的解析器，它允许谓词(例如，ANTLR 确实如此，但我个人会使用自下而上的生成器来避免摆弄左递归消除。)

重要的是要注意点符号有它自己的“冗余括号”变体，因为至少在理论上，您可以使用比必要更多的点。当我玩弄上面的(理论上但不是真正有用的)算法时——自动生成 CFG——我发现需要点最小化更容易，因为否则你最终会创建更多的单位规则。我找不到 PM 的机器可读副本进行测试，但在我所做的所有搜索中，我从未找到不是点最小的表达式。我不知道这是强制性整洁的结果还是只有点最小表达式才是合法的想法。