Disambiguating Context-Free Grammars by Selecting the Minimum-Cost Parse Tree
本文提出了一种通过将解析树选择视为最小代价优化问题来消除任意上下文无关文法歧义的方法，其中利用动态规划，在保持原语言不变的前提下，基于惩罚性消歧模式来寻找唯一的最佳解析树。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
语言是一个由规则组成的系统，它允许我们从简单的部分构建复杂的思想。在计算机世界中，这些规则被称为语法，它们告诉机器如何理解一段代码或一个句子。理想情况下，一组规则应该能让任何给定的输入都只产生一种可能的含义。然而，许多用于描述编程语言的语法是存在歧义的，这意味着一段文本字符串可以有多种相互冲突的解释方式。一个经典的例子是包含两个运算（如加法和乘法）的句子。如果没有明确的指令，计算机就不知道应该先进行加法再进行乘法，还是先进行乘法再进行加法。同样，在由一系列“if”语句组成的链条中，计算机可能不知道一个“else”指令属于哪一个条件。为了让计算机正常运行，它必须选择且仅选择一种解释，但规则本身往往无法提供一个明确的胜出者。
几十年来，处理这种混乱的标准方法是通过手动重写规则，或者添加特殊的声明来强制规则变得不再歧义，从而告诉计算机在陷入困境时该走哪条路径。这些方法对于特定类型的问题效果很好，但它们需要人工干预，并且有时会破坏语言的原始结构。由 Mina Hematikarimkhani 提出的一种新方法，并不将这个问题视为一个通过重写规则来解决的谜题，而是将其视为一个优化挑战。这种方法不是试图删除错误的答案，而是要求计算机评估每一种可能的解释，并根据一套特定的标准选择其中“成本最低”的一个。
其核心思想是为计算机用来理解文本的每一种可能的树状结构分配一个成本。在这个系统中，一棵树代表了理解句子的其中一种方式。成本并非货币价值，而是基于三个因素的评分。首先，系统会计算该树违反用户偏好模式（例如关于哪些运算应该优先进行的规则）的次数。其次，它会统计树中的节点数量，这有助于防止计算机陷入死循环。最后，如果两棵树的得分相同，则使用一个唯一的标识符来打破僵局，以确保计算机始终选择完全相同的结果。计算机随后保留总分最低的那棵树。由于该系统是通过惩罚错误选择而非直接禁止它们来实现目标的，因此它保证了语言中的每个有效句子都会得到恰好一种解释，即使这种解释涉及某些规则违规。
为了找到这棵最优的树，研究人员使用了一种称为动态规划的方法，这是一种通过将复杂问题分解为更小的、重叠的部分来解决问题的方法。想象一下，计算机正在观察一个句子，并试图弄清楚理解其每一个微小部分的最佳方式，然后将这些小块组合起来以理解整体。对于简单的案例，比如决定运算顺序，计算机只需要观察相邻的部分。然而，对于更复杂的情况，例如“悬空 else”（dangling else）问题——即一个“else”子句可能属于附近的“if”也可能属于较远的“if”——计算机需要观察更深层的结构。为了处理这种情况，研究人员引入了一个名为“剖面”（profile）的概念。当计算机构建一个小型的树结构时，它同时也会创建一个简短的摘要，即“剖面”，它会告诉父级结构其下方存在什么内容，例如一个分支是否以特定类型的规则结束。这使得计算机能够在不每次都从头重建整个树的情况下，对句子的远端部分做出明智的决策。
该方法适用于任何规则集，包括那些包含空步骤或会导致其他系统产生困惑的循环引用的规则。在测试中，研究人员将此技术应用于各种示例，包括具有混合运算符的数学表达式和嵌套的条件语句。在每种情况下，系统都成功识别出了最合适的单一树结构。例如，当面对一个包含加法和乘法的字符串时，系统正确地选择了尊重标准数学优先级运算的树，并为违反该规则的树分配了更高的成本。在面对嵌套的“if”语句时，它正确地将“else”连接到了最近的“if”，这符合编程中的标准惯例。当没有提供特定规则时，系统也能处理，默认根据树的结构做出一致且确定性的选择。
尽管该方法功能强大，但作者也明确指出了其局限性。随着输入规模的增大，算法运行所需的时间会显著增长，这使得它无法满足现代生产编译器每秒处理数百万行代码的高速需求。相反，研究人员建议这种方法更适合于需要处理任意用户定义语法的工具，例如语言编辑器、静态分析工具或教育软件，在这些领域，可复现性和处理复杂、混乱规则的能力比原始速度更重要。结果的质量完全取决于用户提供的模式；如果规则不完整或存在矛盾，系统仍然会返回一个结果，但那可能并不是人类想要的结果。该方法并没有解决判断一个语法是否具有歧义性的根本数学问题，但它提供了一种在遇到歧义时进行可靠导航的方法。
这项工作代表了我们看待语言处理方式的一种转变。它不再试图在计算机看到语言之前就强迫语言的规则变得完美，而是允许计算机探索所有可能性，并根据一个清晰、可衡量的标准选择最佳方案。它承认歧义是自然语言和人工语言的特征之一，并提供了一种无需改变语言原始结构即可管理歧义的方法。通过将歧义消除视为寻找最小成本的过程，研究人员创造了一种灵活、稳健且能够应对复杂语法中混乱现实的工具，确保对于每一个有效的句子，总有一个清晰且可复现的答案。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。