8

在 J. Barkley Rosser 的“数学家的逻辑”中，他使用符号来避免过多的括号。虽然我不知道逻辑学家什么时候开始使用这种符号，但我知道那本书于 1957 年首次出版，以及JGP Nicod 的论文于 1916 年发表的论文也使用了这种符号。所以很明显它有相当长的历史，尽管现在这不受现代逻辑学家的青睐。

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

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

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

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 页。但在一般情况下（也很短），.运算符之前或之后的点代表“分隔符”，将两侧推开。冒号:是更强的分隔符，三个点.:或:.更强，但小于::，依此类推。

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

4

3 回答 3

11

点符号最着名的是罗素和怀特黑德在数学原理（1910-1913）中使用，但该符号是从Guiseppe Peano借来的。它也被 Alonzo Church、Willard Van Orman Quine 和其他有影响力的逻辑学家使用（参见斯坦福哲学百科全书中的这个条目）。

通过一些练习，阅读点符号的公式并不难，但它并不像最初出现的那样优雅。首先，Russell 和 Whitehead 仍然发现在否定运算符中使用括号很有用~：

*3·01. p.q .=. ~(~p v ~q)

如上例所示，点既可用作连词运算符，也可表示优先级。因此，更强的连词可能写为:or even :.。

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

说了这么多，使用调车码算法的变体来解析点符号并不难。不幸的是，它不能用上下文无关的语法来解析，这使得它对使用自动化工具生成的语法不太有用。甚至 GLR 解析器也仅限于 CFG。（点符号不是上下文无关的事实可以用泵引理证明；它比通常的泵引理应用程序更有趣，至少恕我直言。）

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

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

于 2013-08-29T15:22:48.423 回答
3

这是一个有趣的应用程序。Perl6允许您扩展语言，添加新的运算符并定义它们相对于现有运算符的优先级。下面的代码示例定义了运算符*. .*等。下面的测试通过了。

use v6;
use Test;

sub infix:<*.>  ($a, $b) is looser(&infix:<+>)  { $a * $b }
sub infix:<.*>  ($a, $b) is looser(&infix:<+>)  { $a * $b }
sub infix:<*:>  ($a, $b) is looser(&infix:<*.>) { $a * $b }
sub infix:<:*>  ($a, $b) is looser(&infix:<.*>) { $a * $b }

sub infix:<+.>  ($a, $b) is looser(&infix:<*.>) { $a + $b }
sub infix:<.+>  ($a, $b) is looser(&infix:<.*>) { $a + $b }
sub infix:<+:>  ($a, $b) is looser(&infix:<*:>) { $a + $b }
sub infix:<:+>  ($a, $b) is looser(&infix:<:*>) { $a + $b }

# Tests

is 1 + 3 .* 2,
    (1 + 3) * 2;

is 1 *. 3 + 2,
    1 * (3 + 2);

is 1 *. 2 +. 2,
    (1 * 2) + 2;

is 2 *: 2 + 3 .* 4,
    2 * ((2 + 3) * 4);
于 2013-09-06T07:42:36.840 回答
-1

ISO 核心标准 Prolog 不允许直接解析旧的 Logicians 点表示法。虽然它可以形成包括点在内的符号，但突出的符号是 univ 运算符

(=..)/2. 不同的符号用作运算符，导致解析项中的函子不同。为了缓解这个问题，我介绍了sys_alias/1运营商

我的 Prolog 系统中的属性。这是一个示例定义：

:- op(750, xfx, .=.).
:- set_oper_property(infix(.=.), sys_alias(=)).

在上面我们使用(=)/2. 通常(=)/2有 operator level 700，第二个变体有更高的 operator level 750，导致所需的括号。

这是一个运行示例：

Jekejeke Prolog 4, Runtime Library 1.4.5

?- write(p = q .=. q = p), nl.
(p = q) = (q = p)
Yes

可能有助于解析这个野兽：

关于原型的单一公理。二、
博莱斯瓦夫的索博辛斯基 - 1961 年
https://projecteuclid.org/euclid.ndjfl/1093956834

于 2020-08-09T00:11:46.980 回答