Ear*_*ine 5 grammar parsing language-design
在J. Barkley Rosser的" 数学家的逻辑 "中,他用一种符号来避免括起来太多.虽然我不知道逻辑学家什么时候开始使用这种符号,但我知道这本书于1957年首次出版,而JGP Nicod在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页.但是在genaral(和short)中,.操作符之前或之后的一个点代表一个"分隔符",将两边推开.冒号:是一个更强的分隔符,三个点.:或:.甚至更强,但更少::,等等.
我想知道如何为上述语言编写语法然后解析它？虽然这个符号已被淘汰,但我发现程序员的眼睛看起来非常清楚.那它的优点和缺点是什么呢？
Dot符号最为着名的是Russell和Whitehead在Principia Mathematica(1910-1913)中的使用,但这个符号是从Guiseppe Peano那里借来的.它也使用了邱奇,威拉德·冯·奥曼·蒯因,以及其他有影响力的逻辑学家(见该条目在斯坦福哲学百科全书).
通过一些练习,用点符号读取公式并不困难,但它并不像第一次出现那么优雅.首先,Russell和Whitehead仍然发现使用带括号运算符的括号是有用的~:
*3·01. p.q .=. ~(~p v ~q)
如上例所示,点既用作连词运算符又用于表示优先级.因此,更强大的结合可能被写成:甚至是:..
最后,为了减少视觉混乱(我想),Russell和Whitehead也使用优先关系,其中运算符集被划分为三个优先级组,使得优先级较高的运算符的点占据相同数量的点对于优先级较低的运营商.在具有相同优先级的运算符之间,点数相等是不合法的,但是Russell和Whitehead也定义了一些三元运算符,例如p v q v r为了能够避免必须指定不重要的优先级.(据我所知,这些表达式的精确解析规则从未正式说明,但定义出现在PM中.)
说了这么多,使用分流码算法的变体解析点符号并不是非常困难.不幸的是,它无法使用无上下文语法进行解析,这使得它对使用自动化工具生成的语法不太有用.甚至GLR解析器也仅限于CFG.(点符号不是无上下文的事实可以通过泵浦引理证明;它比通常的泵浦引理应用程序更有趣,至少是imho.)
如果允许CFG具有无限数量的(点)符号和相应的无限数量的规则,那么编写语法(或者更确切地说,语法模板)是非常简单的,因为大多数规则都是通过点参数化的-计数).因此,理论上您可以通过首先扫描来解析点表达式,以找到所使用的最大点数,然后从模板生成相应的有限CFG.(只要为每个点序列定义一个单独的终端,结果就是LALR(1).)实际上,这可以通过在CFG中使用谓词来完成,因此你可以创建一个带有解析器生成器的解析器,它允许谓词(例如,ANTLR,但我个人使用自下而上的生成器来避免摆弄左递归消除.)
值得注意的是,点符号有自己的"冗余括号"变体,因为至少在理论上你可以使用比必要更多的点.当我在使用上面的(理论上但不是真正有用的)算法 - 自动生成CFG时 - 我发现更容易要求点最小化,因为否则你最终会创建更多的单位规则.我无法找到机器可读的PM副本进行测试,但在我做的所有搜索中,我从未发现过一个不是最小点的表达式.我不知道这是强迫整洁的结果还是只有点极小表达才合法的想法.