Cyclic operator precedence grammars for parallel parsing

Michele Chiari

doi:10.1016/j.ic.2025.105363

2025-10-01

Michele Chiari *

Dino Mandrioli

Matteo Pradella

DOI：10.1016/j.ic.2025.105363

原文链接

查看原文

摘要

En 中文

算符优先语言（OPLs）具有局部可解析性这一性质，这意味着由充当括号作用的一对标记所包围的代码片段，可以在不了解其外部上下文的情况下进行解析。这一性质已被用于构建针对以OPL形式化的语言的并行解析器。然而，观察到当句子的语法树具有线性子结构时，解析必须按顺序进行，这使得将此类子树分割成并行处理的块变得无效。这种不便源于等价优先关系不能是循环的这一假设，迄今为止，大多数关于OPLs的文献都做出了这一假设。这一假设源于保持数学符号尽可能简单的需求，尽管它导致了算符优先文法与定义OPLs的其他形式化（如算符优先自动机、单子二阶逻辑和算符优先表达式）的表达能力之间存在差异，后者并未假设无循环性。我们提出了一种算符优先文法的扩展版本，称为循环算符优先文法，它允许文法规则右部使用简化的正则表达式。对于这类算符优先文法，等价优先关系的无循环性假设不再需要，以保障生成语言的代数性质。循环文法的表达能力现在完全等同于定义OPLs的其他形式化的表达能力。因此，循环算符优先文法产生无层级的语法树和具有平坦无界子结构的句子，这些子结构可以自然地划分为适合并行解析的块。(c) 2025 The Author(s)。由Elsevier Inc.出版。这是一篇开放获取文章，采用CC BY许可（http://creativecommons.org/licenses/by/4.0/）。

Keyword:

Operator precedence languages

Cyclic precedence relations

Parallel parsing