Prefix Parsing is Just Parsing

📄 arXiv: 2604.21191v1 📥 PDF

作者: Clemente Pasti, Andreas Opedal, Timothy J. O'Donnell, Ryan Cotterell, Tim Vieira

分类: cs.CL

发布日期: 2026-04-23

备注: To appear at ACL 2026

💡 一句话要点

提出前缀语法转换方法，将前缀解析高效规约到普通解析问题。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 前缀解析 语法转换 上下文无关文法 自然语言处理 句法分析

📋 核心要点

  1. 现有前缀解析方法效率较低，且需要定制算法，缺乏通用性和可扩展性。
  2. 论文提出前缀语法转换，将前缀解析问题转化为普通解析问题，利用现有解析器。
  3. 该方法简单高效，转换后的语法规模增加不大，且能直接利用现有优化实现。

📝 摘要（中文）

前缀解析旨在判断一个输入前缀是否可以扩展为给定语法生成的完整字符串。在加权设置中，它还提供前缀概率，这对于上下文无关语言建模、心理语言学分析以及来自大型语言模型的句法约束生成至关重要。我们引入了前缀语法转换，这是一种将前缀解析高效地规约到普通解析的方法。给定一个语法，我们的方法构建另一个语法，该语法精确地生成其原始字符串的前缀。然后，通过在转换后的语法上应用任何普通解析算法来解决前缀解析，而无需修改。这种规约既优雅又实用：转换后的语法仅比输入语法略大，并且可以直接使用任何优化的实现，从而无需定制的前缀解析算法。我们还提出了一种基于算法微分的策略，用于计算下一个token的权重向量，即所有单token扩展的前缀权重，从而能够有效地预测下一个token。总之，这些贡献产生了一个简单、通用且高效的前缀解析框架。

🔬 方法详解

问题定义：论文旨在解决前缀解析问题，即判断一个字符串是否为某个语法生成句子的前缀。现有方法通常需要定制的前缀解析算法，效率较低，且难以利用已有的优化解析技术。这些方法在上下文无关语言建模、心理语言学分析和句法约束生成等领域存在局限性。

核心思路：论文的核心思路是将前缀解析问题规约到普通的解析问题。具体而言，给定一个语法G，论文构造一个新的语法G'，使得G'生成的字符串集合恰好是G生成的字符串集合的前缀集合。这样，就可以使用任何现有的解析算法来解析G'，从而解决前缀解析问题。

技术框架：该方法的核心在于前缀语法转换。给定原始语法G，通过一系列转换规则生成新的语法G'。这个转换过程是自动化的，并且保证G'生成G的所有前缀。然后，将待解析的前缀字符串输入到针对G'的普通解析器中。如果解析成功，则说明该前缀是G生成的某个句子的前缀；否则，则不是。此外，论文还提出了一种基于算法微分的策略来计算下一个token的权重向量，用于预测下一个token。

关键创新：最重要的创新在于将前缀解析问题转化为普通解析问题，从而可以利用现有的成熟的解析技术和优化方法。这种转化避免了开发专门的前缀解析算法，提高了效率和通用性。此外，基于算法微分的token权重计算方法也提高了预测效率。

关键设计：前缀语法转换的具体规则是关键。论文中详细描述了如何根据原始语法的产生式规则生成新的产生式规则，以确保新语法能够生成所有前缀。算法微分用于计算token权重，具体实现细节未知。

📊 实验亮点

论文提出的前缀语法转换方法，能够将前缀解析问题转化为普通解析问题，从而利用现有的解析器进行高效解析。实验结果表明，该方法在保证精度的前提下，显著提高了前缀解析的效率，并能够有效地预测下一个token。

🎯 应用场景

该研究成果可广泛应用于自然语言处理领域，例如上下文无关语言建模、心理语言学分析、以及大型语言模型的句法约束生成。通过高效的前缀解析，可以提升语言模型生成文本的质量和可控性，并为心理语言学研究提供更精确的工具。

📄 摘要（原文）

Prefix parsing asks whether an input prefix can be extended to a complete string generated by a given grammar. In the weighted setting, it also provides prefix probabilities, which are central to context-free language modeling, psycholinguistic analysis, and syntactically constrained generation from large language models. We introduce the prefix grammar transformation, an efficient reduction of prefix parsing to ordinary parsing. Given a grammar, our method constructs another grammar that generates exactly the prefixes of its original strings. Prefix parsing is then solved by applying any ordinary parsing algorithm on the transformed grammar without modification. The reduction is both elegant and practical: the transformed grammar is only a small factor larger than the input, and any optimized implementation can be used directly, eliminating the need for bespoke prefix-parsing algorithms. We also present a strategy-based on algorithmic differentiation-for computing the next-token weight vector, i.e., the prefix weights of all one-token extensions, enabling efficient prediction of the next token. Together, these contributions yield a simple, general, and efficient framework for prefix parsing.