大型语言模型的高效引导生成：迭代解析的扩展

链接表

• 摘要和简介
• LLM 抽样和指导生成
• 迭代 FSM 处理和索引
• 迭代解析的扩展
• 讨论、参考文献和致谢

4. 迭代解析的扩展

在本节中，我们将重点转移到通用的解析器引导生成，并从对作为 CFG 提供的类似 Python 的语法进行简单演练开始。

考虑一个由“d”和“ef”之类的字符串组成的词汇表，这些字符串可以根据隐式 CFG 组合起来产生类似 Python 的语法，并假设这些字符串按照类似算法 1 的过程按顺序采样和连接。

此外，考虑 CFG 中的终结符 DEF，它对应于字符串“def”，由简单正则表达式 def 给出。另外，考虑由正则表达式 [^\W\d]\w* 给出的 NAME 符号（例如 Python 标识符）。我们希望以符合 Python 语法的方式按顺序解析从上述词汇表中采样的字符串。

例如，以下可能是一个这样的序列：[“d”, “ef”, “ f”, “oo(”, “):”, “ “, “pass”]。序列中的所有元素都是词汇表的定义元素。连接该序列会产生“def foo(): pass”，这是定义函数的有效标记序列。在我们正在考虑的情况下，我们将观察到直到某个点的所有标记，但对该点之后的标记一无所知。

例如，在示例序列中的第三个观察点处，我们有连接字符串“def f”。如果我们要对这个字符串进行 lex/parse，传统方法将返回符号序列 DEF NAME，这会将“f”错误地识别为完整的 NAME 标记。从序列的其余部分可以看出，正确的 NAME 标记将是“foo”。

一般来说，可以从词汇表中抽取的下一个有效字符串是

1. 继续扩展/推进当前以“f”开头的 NAME（如我们示例中的完整序列一样），和/或

   
   

2. 以“(”开头的任何内容 - 即带有正则表达式 ( - 的 LPAR 符号，并继续指定有效的参数签名。

在第一种情况下，“f”可以看作是 Python 中部分匹配的 NAME 符号，并且——回想一下它的正则表达式是 [^\W\d]\w*——我们可以说它匹配正则表达式中的两个子模式（即 [^\W\d] 和 \w*）。我们使用 FSM 通过 FSM 的状态形式化子模式的概念。在这种情况下，NAME 的正则表达式可以用 FSM M 表示，它有三个状态：0（即初始状态 q0）、1（即 [^\W\d]）和 2（即 \w*），其中 1、2 ∈ F。

使用算法 3，我们将获得“f”的 FSM 状态序列 (0, 1)、(1, 2)、(2, 2) 以及与 NAME 符号对应的 FSM M。这些“f”的 FSM 序列告诉我们，对于这个词汇字符串，匹配可以从状态 0、1 或 2 开始，也可以在状态 1 或 2 结束。

根据上述情况 1，解析可以继续进行（针对 NAME 符号），此前解析已结束于状态 1 或 2。根据情况 2，下一个字符串也可以以 LPAR 开头或包含 LPAR，这意味着 M 将终止，这是可以的，因为 1 和 2 是 M 中的最终状态，解析将在读取“f”后停止。M 终止还表示 NAME 符号已完成，并且语法允许转换到接受 LPAR 的状态。

在此示例中，下一个有效词汇字符串至少为“d”、“ef”、“pass”、“”、“oo(”，因为所有这些字符串都会扩展部分匹配的 NAME，最后一个字符串也会将解析状态推进到读取 LPAR 的状态。我们考虑的词汇子集中的剩余字符串“:”将导致具有无效语法的序列。

相对于 FSM 索引方法，这意味着算法 4 会将 FSM 状态 0、1 和 2 映射到符号 NAME 及其 FSM M 的子集“d”、“ef”、“pass”、“”、“oo(”。

此图省略了确定允许哪些语法符号和转换的底层解析器状态。我们使用下推自动机 (PDA) 作为扩展 FSM 方法并解决其余细节的手段。

4.1 下推自动机公式

我们使用以下 6 元组表示来定义下推自动机[Sipser，1996，定义 2.13]：

为了为 PDA 驱动的解析器构建索引方法，我们需要使用 CFG 符号（通过相应的 PDA 字母表）与产生 PDA 读取的符号的词法分析和扫描步骤之间的连接。

更具体地说，解析器由词法分析器和扫描器支持，它们从字符输入序列中识别符号，正如我们在第 4 节中隐式说明的那样。可以根据每个状态中的映射 δ 允许的符号和堆栈转换，为每个解析/PDA 状态构建有序的终结符列表。这意味着我们可以为每个解析状态构建一个 FSM，它是与状态读取的终结符相对应的每个 FSM 的并集。

然后，扫描步骤将识别出一组可能的终结符 V ⊂ Σ，这些终结符是自解析过程中最后一个完全识别的符号以来读取的字符。例如，在第 4 节中 Pythonlike CFG 的 PDA 的初始状态 q0 中，扫描和词法分析字符串“de”将导致 V = {DEF, NAME}：即，对于完成字符串“def”的任何词汇字符串，其结果为 DEF（后跟 NAME FSM 未读取的字符串（例如“def”）），对于其 FSM 读取的任何其他字符串（例如“default”）。请注意，扫描器的步骤和 LLM 的采样步骤最终将减少集合 V，直到确定单个终结符 v ∈ V。

通过将算法 3 应用于 V 中的每个字符串，使用每个解析状态的组合 FSM，我们可以确定由 PDA 状态、相应的 FSM 状态和潜在终端符号组成的解析器配置。

通过与算法 3 中的步骤类比，我们可以使用 PDA 转换图的原像来确定 PDA 堆栈值，这些值将读取解析器配置的 PDA 状态 q ∈ Q 和终端符号集 V：

此映射提供的堆栈值是需要通过 PDA 找到路径（如果有的话），这些路径允许从可能的解析器配置开始成功、完整地解析 V 中的每个字符串。对于与 LALR(1) 解析器的 REDUCE 操作相对应的解析器状态和终端组合，这些解析器配置将不仅仅包含 Γ 中的栈顶值；它们将由与词汇字符串所需的 REDUCE 操作的所有有效前缀相对应的子堆栈组成。最终，每个允许完整解析词汇字符串的解析器配置都会作为 PDA 索引中的条目添加，在这种情况下，索引将需要是 trie 数据结构，以便允许查询解析器的堆栈值。