0

语言 TLA+ 使用范围作为其运算符优先级(参见指定系统[ PDF ]一书中第 271 页的表格)。引用:

如果两个运算符的范围重叠,则它们的相对优先级是未指定的。

例如,$运算符(优先级 9-13)与+运算符(优先级 10-10)冲突,但与<运算符(优先级 5-5)不冲突。

运算符优先级范围是正式语言中常用的甚至是预先存在的概念吗?我通过一些搜索在网上找不到任何关于此的信息。是否有用于解析这种优先方案或将该方案转换为标准单值优先方案的算法?是否有任何解析器生成器处理运算符优先级范围?与单值优先级相比,通过这种方法可以获得什么?

4

2 回答 2

2

运算符优先级范围是正式语言中常用的甚至是预先存在的概念吗?

不。

事实上,运算符优先级(没有范围)在正式语言中是一个被严重误解的概念。(当我写完这篇论文时,你可以在下面看到这个声明的更长版本。)

是否有用于解析这种优先方案或将该方案转换为标准单值优先方案的算法?

只需使用更复杂的优先级比较,您就可以很容易地调整标准的调车场算法。在标准算法中,比较可以有三种可能的结果:小于(推入符号)、大于(减少左边的表达式)和等于(组合括号或其他括号标记)。(最后一个结果在大多数在线资源中都没有得到很好的描述,并且经常通过添加额外的关联性测试而变得模糊不清。再次,见下文。)

通过范围比较,您将有四种可能的结果。对于小于,您可以将左侧范围的结尾与右侧范围的开头进行比较,对于大于,您将比较左侧范围的开头与右侧范围的结尾。如果这些都不适用,您将有重叠的范围,并且您必须以某种方式将括号标记与错误情况区分开来。

是否有任何解析器生成器处理运算符优先级范围?

如今,只有少数解析器生成器使用运算符优先级表,尽管调车场算法(或其等效算法)的手写实现非常普遍。像 yacc/bison 这样的解析器生成器在解析器构建时使用优先级声明,通过消除一些可能的解析动作来解决冲突;解析器本身不知道优先级,并且严格按照状态转换表进行操作。

ANTLR 是解析器生成器,它在解析过程中最接近使用优先级。它根据语法描述中的产生顺序计算自己的优先级数(分别为每个非终结符)。这些计算的优先级被翻译成语义谓词,这些谓词在解析时执行,以便在不同的解析预测之间进行选择。由于没有明确的优先级声明,您将无法声明范围,但您可以自己编写语义谓词,而不是让 ANTLR 为您生成它们(如果您有明确的谓词,它不会尝试插入冲突分辨率代码)。这将允许您使用与我上面概述的相同的策略,但我认为它不会完全令人满意。

与单值优先级相比,通过这种方法可以获得什么?

在我看来,没什么。就像大多数其他优先级解析一样,这是一个 hack。如果它适用于特定的语法,那很酷,但它会遇到与广义运算符优先级解析相同的问题:你并不真正知道你正在解析什么语言,因为整个装置更像是一种启发式而不是正式的框架。作为证明,很难找到一个手写的基于优先级的解析器,它在某些时候没有一些(希望有注释的)代码来处理优先级比较未正确处理的异常,就像很难找到一个现实生活中使用优先声明的语法,除了最普通的风格之外,在某些地方没有很长的注释来解释一个原本神秘的声明。

于 2021-03-29T22:14:49.737 回答
0

我想你可能已经“埋下了头”。

在该部分之后,它说“如果两个运算符的应用顺序未确定,因为它们的优先级范围重叠并且它们不是关联中缀运算符的两个实例,则表达式是非法的(语法格式不正确)。”

我读到“未指定为“随心所欲”,这表示它无效

ANTLR 是我选择的解析器,我不知道如何让解析器在语法上拒绝它(在解析阶段)。我可以看到您将在哪里应用一组优先级,然后,一旦您有了 ParseTree,您就可以使用在解析树中查找重叠优先级规则的代码来处理它,并在上面抛出错误。我不知道这有不利的一面。您仍然会将其标记为错误。只是 ANTLR 会以您指定的优先级将树的解释交给您。

我可能会用一些 ANTLR 监听器代码(Java 中)来扩展这个想法。

老实说,我有点难以理解这种优先方案的打包版本。这很奇怪。

于 2021-03-29T20:18:35.443 回答