动机
同一个单词在上下文无关文法中可能有许多不同的推导,朴素的推导搜索可能反复回答相同的问题。换一个思路:询问哪些变元能够推导出输入的每一个连续子串。当文法的产生式具有受限的形式时,每棵非平凡的语法分析树都会分解为两棵更小的子树。以子串为索引的表可以复用这些较小的答案,从而无需枚举全部推导即可判定成员关系。
下面的算法通常称为 CYK 算法。它的输入是一个满足指定范式的文法和一个单词;范式转换是配套笔记中另行给出的构造。成员判定的答案只针对这个文法和这个单词,并不涉及两个任意上下文无关文法是否等价的问题。
定义
设 为有限上下文无关文法。假设每个产生式都具有如下形式之一:,其中 为变元;或 ,其中 为终结符。可以另外允许 ,但此时 不得出现在任何产生式的右侧。这就是本文采用的范式约定。对于非空单词 ,令 表示能够推导出子串 的变元集合,其中 。
表按子串长度递增的顺序计算。令 。对于 ,当且仅当存在 满足 ,以及产生式 使得 且 时,把 放入 。对于非空单词,当且仅当 时接受。对于空单词,当且仅当存在例外产生式 时接受。
定理
定理 2.3.1
(子串成员关系的正确性)
对于每个非空输入以及所有 ,计算所得的集合 恰好由满足 的变元 组成。因此该算法能够判定文法是否生成该输入。
定理 2.3.2
(资源界)
对于 ,逐一检查每个划分和每个二元产生式的直接实现使用 次基本的产生式检查,以及 个布尔表项。对成功的表项保存回溯指针后,当输入被接受时可以重构出一棵语法分析树。
证明思路或证明
证明
(对长度的归纳与资源计数)
对子串长度进行归纳。长度为一时,变元只能通过终结符产生式推导出单个终结符:二元产生式会产生两棵非空的变元子树,而在所述范式下两者都不能推导出空单词。因此初始化是精确的。
对于更长的子串,任何语法分析树的根变元都必须使用二元产生式 。它的两个子节点产生所得产物的两个非空且相邻的部分,由此得到某个划分 。由归纳假设, 和 出现在对应的较短子串的集合中,所以表中包含 。反过来,若表利用 和某个划分插入了 ,则归纳假设给出两部分的推导;先应用该产生式,再应用这两个推导,就得到整个子串的推导。这就证明了两个方向的包含关系。例外的空起始规则绝不会出现在非空子树中,因为起始变元不出现在任何右侧。
共有 个子串,每个子串至多有 个划分位置。在每个划分处检查全部二元产生式,共得到 次检查;终结符的初始化在这个界之内,至多相差通常的读入输入以及常数规模的边界项。布尔表对每个变元和每个子串各有一个表项。对于每个被插入的变元,保存其终结符产生式,或保存一个成功的产生式及其划分。所记录的子节点的产物都更短,所以递归地沿指针前进必然终止,并给出一棵语法分析树。每个表项一个指针只足以重构一棵树,并不足以表示所有可能的分析。
证明透视
范式的每个假设用在哪里
归纳是对长度 的强归纳,并要求每个划分都产生两个严格更短的非空区间。三个假设共同保证这一点。形式 使长度为一的树的根必为终结符规则、较长的树的根必为二元规则,无需处理第三种形状。没有单位产生式,也没有除 以外的 规则,意味着二元规则的子节点不可能推导出空单词,因此两个区间都非空,也都短于 。起始变元不得出现在右侧,则使 不会出现在任何非空的树中。唯一不显然的一步是反向包含:表项是一份证书,每个被插入的变元都带有两份更短的证书。只要去掉其中任何一个假设,表中就可能漏掉分析树放在该处的变元(见“常见错误”中的单位产生式例子)。
例题详解
例题 2.3.3
(两个符号的单词)
设产生式为 、、,输入 得到 和 。唯一的划分把 插入 。因此 被接受,根产生式为 ,并带有两个终结符子节点。
例题 2.3.4
(较长的嵌套推导)
使用 、、、。对于 ,中间的两个符号 使 进入 。随后子串 经由 使 进入 。最后,开头的 与该 使 进入 。所得语法分析树的产物为 。
例题 2.3.5
(空的表项)
对于第一个文法和输入 ,每个长度为一的集合都含有 。没有任何产生式带有两个 子节点,所以 为空, 不在其中。算法拒绝该输入;这一结论来自整个表的构造,而不是仅仅因为没有找到某一个特定的推导。
常见错误
反例模式
只检验第一个划分
断言:要填 ,只需检验划分 ,因为能推导出 的变元必定通过第一个划分推导。取 、、、、,输入 。该单词确实被生成:。只用划分 时,得到 和 ,而且不存在形如 的规则,故 ,输入被错误地拒绝。划分 则给出 (由 )和 ,所以 。修正后的说法就是递推式本身: 是对所有满足 的 取并集。
常见错误
(对含单位产生式的文法直接用表算法)
取 、,输入 。该单词确实被生成(),但初始化只给出 ,因为 不是产生式,而递推式不会回头处理长度为一的情形。于是 ,单词被错误地拒绝。表算法只对已处于所述范式的文法才是精确的;要先消去单位产生式(这里把 改为 )。
常见错误
(把一棵保存下来的分析树当作无歧义的证明)
取 和 。此时 ,且 同时来自 和 ,即两棵不同的树 与 。只保存一个回溯指针只会重构其中一棵。表给出的树说明单词属于该语言,却不能说明不存在其他的树。
一个表项可以包含多个变元,一个变元也可以有多个有效的回溯指针。只保存第一个成功的指针,可以保持成员判定的结果以及一棵分析树,但会丢失关于其他分析的信息。例外的空单词必须单独处理:所示的表中没有对应长度为零的子串的单元格。
执行表算法
直接实现可以为每个三元组 保存一个布尔标志。首先把所有标志初始化为假。对每个输入位置扫描终结符产生式,并设置相应的长度为一的标志。然后对长度 ,考虑每个满足 的 、每个划分 以及每个产生式 。如果 和 的标志都为真,就把 的标志置为真,并可选地把该产生式和划分保存为见证。
处理长度 时,任一划分处的两个子串长度都小于 。因此更新所读取的全部标志都已取得最终值。同一长度的各单元格之间的顺序无关紧要。把标志置为真是单调的:一旦找到了推导,之后失败的划分就不得把它重置为假。等价地说,数学上的更新是对所有成功组合取并集,而不是依据最后检查的那个组合进行赋值。
例题 2.3.6
(同一单元格的不同划分)
考虑产生式 、、、、、、。对于输入 ,根 可以使用 并在第一个字符之后划分: 推导出 , 推导出 。它也可以使用 并在第二个字符之后划分: 推导出 , 推导出 。两者都把同一个变元插入 。一个回溯指针只给出一棵分析树;若两个都保留,则能保留根节点两种分解方式的选择。
文法中可能含有不能推导出任何终结符串的符号、重复的产生式,或从 不可达的变元。这些符号可以出现在文法的表示中,但不会使归纳论证失效。只有当某个变元得到终结符产生式或一对经过验证的较短表项的支持时,表项中才包含它。删去不可达或不产生终结符串的符号可以改进实现,但它并不是本表算法正确性的前提。
回溯指针与歧义性
长度为一的表项的回溯指针记录产生式 。对于更长的表项,它记录产生式 、划分 ,以及两个子表项。要重构以 为根、覆盖 的树,创建一个标记为 的节点,沿着它的指针前进,并在各自指定的区间上递归地构造两个子节点。在每个内部节点处,两个区间都非空、互不相交且相邻;它们的并集就是父节点的区间。因此从左到右读出的叶子标记恰好还原输入单词。
这张表在两个方向上都是成员关系的证书。如果 出现在最后的单元格中,则指针给出一棵可以局部检验的语法分析树:每个内部节点都使用文法中的一个产生式,每个叶子都与输入匹配。如果 不出现,则正确性证明表明不存在任何语法分析树。单独一条失败的搜索路径不能给出这样的否定结论,但在范式假设下,表已经考虑了所有可能的划分位置和产生式。
歧义文法可以为一个单词给出多于一棵语法分析树。仅凭成员关系无法判定歧义性,而一棵重构出的树也不能说明不存在其他的树。如果保留每个成功的回溯指针,所得的共享结构可以表示多种分析,但把它们显式列出所需的空间可能远大于布尔表。若要断言枚举所有分析的代价,就需要计算输出的规模,并仔细处理共享的子结构。
范式的作用
带有单位产生式 的文法不适用所示的递推式。例如,若 且 ,则对于输入 ,初始化会插入 ,却不会插入 。同样,二元推导内部的空产生式可能使某个子节点的产物为空,而这无法用分成两个非空区间的划分来表示。把算法原封不动地用于这样的文法可能产生假的否定结果。要么先用经过证明的保持语言的方法把文法转换为规定的形式,要么改用显式处理这些规则的另一种算法。
范式转换即使保持语言不变,也可能改变文法及其语法分析树。回溯指针所给出的树是转换后文法的树。如果应用需要原文法中的树,转换过程还必须保留足够的对应关系,以便把该树翻译回去;仅有所生成的语言相等,本身并不能确定这样的翻译。配套的构造证明了语言层面的转换,而本单元证明的是对已处于所需形式的文法的成员判定。
空单词的约定之所以单独处理,是因为没有可填入表中的非空子串。在受保护的起始规则之下, 是起始变元推导出空单词的唯一方式。如果另一种范式约定允许其他空产生式,则特殊检验必须相应调整。对于非空单词, 可以出现在根处,但它不得出现在右侧这一禁止条件,阻止了例外的空规则被用作子节点。
理解复杂度的陈述
长度循环中,长度为 的单元格有 个,每个单元格有 个候选划分。因此单元格与划分的配对数为 。在每个配对处至多扫描 个二元产生式,就得到所述的三次上界。这个界计算的是一种简单的实现;按子节点符号为产生式建立索引可能有用,但其数据结构和预处理必须在另外的分析中计入。
空间界计算的是布尔成员标志。直接的稠密表为 个非空区间中的每一个分配 个标志。回溯指针需要下标和产生式编号,其位长取决于输入的表示方式;说有 个表项,并不自动等同于有这么多个比特。稀疏表示在某些输入上可以节省空间,但其最坏情形的表现和查找代价取决于所选的数据结构。
对于已处于范式的文法,复杂度关于文法规模和输入长度是多项式的。若从另一种文法出发,则总量中要计入转换的时间和规模。该定理并没有说可能的语法分析树的数目是多项式的:一张紧凑的表可以共享大量部分推导,而完整的树的数目则可能大得多。
总结
范式把非空单词的分析归结为单个终结符,或归结为分成两个非空子串的二元划分。归纳法使表是精确的;整个单词的单元格中是否含有起始变元决定成员关系,而保存的见证可以重构出一棵语法分析树。
练习
快速检查
(对于 、、,计算单词 的表,并判定其是否属于该语言。)
先填两个长度为一的单元格。
解答 · 答案
单字符单元格为 和 。没有任何二元产生式的子节点依次为 ,所以 ,, 被拒绝。
快速检查
(对于例题中较长的那个文法,找出一个使 进入子串 所对应单元格的划分。)
取输入 和单元格 。
解答 · 答案
把 划分为 和 。前一部分由 推导(故 ),后一部分由 推导(故 ),所以可以应用 。
快速检查
(如果在所述范式下不含 ,空单词会被接受吗?)
哪些产生式可能产生空的产物?
解答 · 答案
不会。其他所有产生式的产物都非空,而可选的例外规则是唯一的空产生式。
快速检查
(若只要求一棵分析树,为什么每个变元和单元格只保存一个成功的回溯指针是安全的?)
想想一个指针证明了什么。
解答 · 答案
每个保存的指针都证明了对应变元在该子串上的一个推导。沿着更短子串的指针递归地前进,就构造出一棵完整的分析树;对于这个输出而言,其他推导是不必要的。