Large Language Models are powerful tools for program synthesis and advanced
auto-completion, but come with no guarantee that their output code is
syntactically correct. This paper contributes an incremental parser that allows
early rejection of syntactically incorrect code, as well as efficient detection
of complete programs for fill-in-the-middle (FItM) tasks. We develop
Earley-style parsers that operate over left and right quotients of arbitrary
context-free grammars, and we extend our incremental parsing and quotient
operations to several context-sensitive features present in the grammars of
many common programming languages. The result of these contributions is an
efficient, general, and well-grounded method for left and right quotient
parsing.
To validate our theoretical contributions -- and the practical effectiveness
of certain design decisions -- we evaluate our method on the particularly
difficult case of FItM completion for Python 3. Our results demonstrate that
constrained generation can significantly reduce the incidence of syntax errors
in recommended code.

本文介绍了一种增量解析器，该解析器能够早期拒绝语法错误的代码，并高效地检测符合填充中间任务的完整程序。我们开发了一种基于任意无上下文文法的左右商的 Earley 风格解析器，并将增量解析和商操作扩展到许多常见编程语言文法中的若干上下文敏感特性。这些方法的结果是一种高效、通用且可靠的左右商解析方法。为了验证我们的理论和特定设计决策的实际有效性，我们在 Python 3 的填充中间完成任务的特别困难情况下进行了方法评估。结果表明，受限生成可以极大地减少推荐代码中的语法错误的发生。

通过上下文敏感语法的高效左右商运算对编码语言模型进行约束解码

Constrained Decoding for Code Language Models via Efficient Left and  Right Quotienting of Context-Sensitive Grammars

Syntax is fundamental to our thinking about language. Failing to capture the
structure of input language could lead to generalization problems and
over-parametrization. In the present work, we propose a new syntax-aware
language model: Syntactic Ordered Memory (SOM). The model explicitly models the
structure with an incremental parser and maintains the conditional probability
setting of a standard language model (left-to-right). To train the incremental
parser and avoid exposure bias, we also propose a novel dynamic oracle, so that
SOM is more robust to wrong parsing decisions. Experiments show that SOM can
achieve strong results in language modeling, incremental parsing and syntactic
generalization tests, while using fewer parameters than other models.

该研究提出了一种新的语法感知语言模型：Syntactic Ordered Memory (SOM)，它通过一个增量式解析器显式地建模了结构，并保持了标准语言模型 (从左到右) 的条件概率设置。实验证明，该模型在语言建模、增量解析和语法泛化测试方面均能取得强大的结果，同时使用的参数比其他模型更少。

使用增量解析和动态预测来明确建模语言模型中的语法

Explicitly Modeling Syntax in Language Models with Incremental Parsing  and a Dynamic Oracle

Natural, spontaneous dialogue proceeds incrementally on a word-by-word basis;
and it contains many sorts of disfluency such as mid-utterance/sentence
hesitations, interruptions, and self-corrections. But training data for machine
learning approaches to dialogue processing is often either cleaned-up or wholly
synthetic in order to avoid such phenomena. The question then arises of how
well systems trained on such clean data generalise to real spontaneous
dialogue, or indeed whether they are trainable at all on naturally occurring
dialogue data. To answer this question, we created a new corpus called bAbI+ by
systematically adding natural spontaneous incremental dialogue phenomena such
as restarts and self-corrections to the Facebook AI Research's bAbI dialogues
dataset. We then explore the performance of a state-of-the-art retrieval model,
MemN2N, on this more natural dataset. Results show that the semantic accuracy
of the MemN2N model drops drastically; and that although it is in principle
able to learn to process the constructions in bAbI+, it needs an impractical
amount of training data to do so. Finally, we go on to show that an
incremental, semantic parser -- DyLan -- shows 100% semantic accuracy on both
bAbI and bAbI+, highlighting the generalisation properties of linguistically
informed dialogue models.

研究了机器学习方法处理自然语言对话中语言现象的可行性，针对此问题，研究者将实际自然语言现象加入到 Facebook AI Research 的 bAbI 对话数据集中，发现目前的一种检索模型 MemN2N 在这种自然语言数据集合上表现急剧下降，但使用增量语义解析器 DyLan 能够在此数据集合上实现 100％的语义准确性。