动机
CYK 算法之所以可行,是因为每棵非空语法分析树的根都具有特别简单的形式:它要么产生一个终结符,要么把词分成两个非空的部分。任意的上下文无关文法未必具有这种结构:它可能含有很长的右部、终结符与非终结符混杂的右部、重命名规则以及空产生式。要把 CYK 应用到这样的文法上,我们需要一种转换,并且其证明要说明:为什么每个原有的词仍然有分析树,又为什么不会出现新的词。
范式是关于语言的陈述,而不是关于保持原有推导的陈述。化简可能把若干条原有推导合并为同一条规则。如果目标是计算分析树的数目或证明歧义性,仅有语言等价并不能提供足够的信息。因此我们将精确地记录这一构造究竟保证了什么。
定义
定义 2.6.1
(带保护起始符的乔姆斯基范式)
上下文无关文法由有限且互不相交的变元集与终结符集、有限的产生式集 以及一个起始变元组成。我们采用带保护起始符的乔姆斯基(Chomsky)范式:每条产生式都具有下列形式之一
其中 是变元, 是终结符,最后一种规则是可选的。新的起始符 不出现在任何右部中,特别地,它不能作为二元规则的子节点。除此之外没有其他空规则,也没有变元到变元的单位产生式。产生式集允许为空,此时文法生成空语言。
配套的“文法化简”单元证明了一个可有效实现的预处理定理:对任意有限的上下文无关文法,可以得到一个与之语言等价的文法,它带有受保护的新起始符,除可能的 外没有空产生式,也没有单位产生式。我们在此使用该定理,并在其后明确说明转换过程。删除无用变元对于范式而言是可选的,语言等价的论证并不需要它。
定理
定理 2.6.2
(每个上下文无关语言都具有这种范式)
对每个有限的上下文无关文法 ,存在一个可有效构造的、具有上述带保护起始符范式的文法 ,满足 ;当空串属于该语言时,空串同样包含在内。
定理 2.6.3
(非空范式分析树的形状)
在带保护起始符的范式文法中,长度为 的非空串的每棵分析树恰有 个终结符产生式节点和 个二元产生式节点。当 时,其根是一个终结符产生式;当 时,其根是一个二元产生式,且两个子节点的产出串均非空。
证明
证明:分离终结符并将链二叉化
证明
(终结符代理与右链保持语言不变)
从预处理后的文法出发。每个非空右部的长度至少为一。长度为一的右部必然是终结符,因为单个变元会是单位产生式。受保护的空规则(若存在)本来就是允许的,保持不变。
对于出现在长度至少为二的右部中的每个终结符 ,创建一个新变元 ,其唯一的产生式为 。在每个这样的长右部中,把 的每次出现替换为 。已有的单终结符规则保持不变。这样得到的非空规则,其右部要么是一个终结符,要么是至少两个变元组成的序列。替换是同时进行的,并且没有任何 被用作起始符。
为什么这保持语言不变?在旧的分析树中,把兄弟节点之间出现的每个终结符叶子替换为一个 节点及其子节点 。反之,新分析树中的每个 节点恰有这一个终结符子节点,把它收缩即可。这些变换都保持从左到右的叶子词不变。由于这些新变元没有其他产生式,反向变换不会引入旧规则中原本不存在的选择。
现在考虑每条长度 的规则
其中每个 都是变元。引入专属于该规则的新变元 ,并把它替换为链
当 时,这恰好是 与 。已有的长度为二的规则保持不变。这条链中的每个新变元恰好只有所列出的那一条产生式,且没有其他旧规则使用它。因此,展开这条链必然按顺序强制出原来的序列 。反过来,使用原规则的节点可以展开成这条链,而不改变其子节点的产出串。这就得到两个方向上的语言包含关系。
转换之前,受保护的起始符不可能出现在任何右部中。该过程只插入新的代理变元与链变元,所以之后它仍然不可能出现在右部中。该过程也不引入空规则或单位产生式。因此所得文法恰好具有所要求的形式,并且语言相同;当且仅当其受保护的空规则存在时,它才包含 。这就证明了第一个定理。
证明透视
为何新变元使收缩精确成立
必须同时成立两件事:新文法不多生成任何东西,也没有遗漏任何东西。“不多生成”用到新变元的唯一性。链变元 恰好出现在一条规则的右部,并且只有一条产生式,所以它的任何使用都展开为原序列 ,把完成的链收缩就得到旧规则的一次合法使用。若 被两条规则共用,收缩就可能把一条规则的前段接到另一条规则的后段,这正是下面“一条规则中的四个变元”例题所展示的失败。“没有遗漏”是较容易的方向:把每个旧规则节点展开为它的链。不显然的一步属于簿记:选取专属于该规则及位置的名称;论证之所以封闭,是因为收缩由叶子向上、逐个完成的子树进行。
证明:二叉树的内部节点比叶子少一个
证明
(计算满二叉树的节点数)
对于一个非空的被推导词,可选的 不可能出现在根以下,因为 不出现在任何右部中;它也不可能用在非空产出串的根上。因此每个节点要么是二元的,要么恰有一个终结符子节点。该词有 个终结符叶子,因此有 个终结符产生式节点。
把每个终结符产生式节点与其终结符子节点收缩为一个叶子。剩下的有根树是满二叉树。设它有 个二元内部节点,数其边数得 ,故 。特别地,二元规则的子节点不可能推导出空串:除受保护的起始符外,没有变元具有空推导。这恰好就是 CYK 所用的“非空划分”假设。
概念视角组合
把范式分析树看作词的括号化
非空分割性质说明,每个二元节点都把词的一个区间分成左右两个区间,且两者都非空。因此,长度为 的词的范式分析树,就是对其 个字母的满二叉括号化,并以变元作标记;它的 个二元节点正是作出分割的 个位置。这恰好是 CYK 表所索引的区间结构:一个区间所对应的格,由它两个部分的格两两配对填入。
例题详解
例题 2.6.4
(混合产生式)
设预处理得到 与 ,其中受保护的起始符为 。引入 与 ,得到临时规则 。再引入新变元 使之二叉化:
两个文法恰好都只生成 。位于 之下的那个 使用 ;最后一个 使用代理 。它们碰巧有相同的终结符产出,但在分析树中的角色并不相同。
例题 2.6.5
(空串与单个字母)
文法 生成 。一个有效的带保护起始符的范式文法为
根 从不出现在右部中。规则 给出长度为一的情形;二元规则每次在前面添加一个 。若省去 ,恰好会丢失空串。
例题 2.6.6
(一条规则中的四个变元)
对于 ,使用新变元 以及三条规则 、、。若 分别生成 ,则新的树按相同顺序产出 。如果从某个无关的产生式中重用 ,就会给它增加额外的选择,从而生成原规则不允许的词。
例题 2.6.7
(空语言)
如果原文法为 ,则不能推导出任何终结符词。带有新起始符且没有任何产生式的文法已经符合我们的范式,并且生成同样的空语言。我们不必仅仅为了让文法看起来非空而人为制造一条终结符产生式。
常见错误
反例模式
重命名不是范式规则
一个诱人的捷径是把 当作范式规则,并原封不动地运行 CYK。取起始符为 的 、,它生成词 。只使用 与 两种形式规则的 CYK 表,会在 的长度为一的格中只填入 ,因为只有 的右部是终结符。起始符 从不进入表中,所以 被拒绝,尽管 。直接删去单位产生式也不是补救办法,因为这样就什么也生成不了;已证明的预处理步骤会把它替换为 。
常见错误
(在去除空规则与单位产生式之前先二元化)
对于本文所采用的叙述方式,操作顺序是重要的。先对规则二叉化也是可行的,但之后消去空规则可能产生单位产生式,这些单位产生式同样必须被去除。这里我们先引用化简定理,然后才添加被强制要求的终结符规则与二元规则。该证明并不声称这些步骤的任意重新排列无需进一步清理就都能奏效。
常见错误
(分析树的数目不被保持)
它也不声称转换保持分析树的数目。例如,、、 对于 有两棵分析树;当产生式被视为集合时,消去单位产生式可能只给出单一的产生式 。语言保持不变,但新文法上的 CYK 计数表所数的是新文法的树,而不是旧文法的树。若要传递歧义性信息,就需要额外的来源记录和单独的证明。
把构造读作算法
含有 个变元的规则被替换为 条二元规则与 个新的链变元。因此,在应用预处理定理之后,终结符分离与二叉化相对于预处理后文法的总长度只增加线性数量的符号与产生式。这一计算并不意味着具体的预处理过程是线性的或多项式的:展开所有可空位置的选择,其规模可能相对于原规则长度呈指数增长。采用不同的顺序并共享中间变元可以改进规模,但对此的分析不属于本定理的内容。
实现该构造时,应系统地使用新名字,并保留一个映射,记录每个人为添加的变元由哪条产生式的哪个位置创建。这个映射支持证明中所述的收缩,也帮助学生重建原语言中的见证词。它无法恢复在化简过程中已被合并的重数。在任何分析器的接口处,都应当清楚区分见证词、一棵分析树以及全部原有分析树。
跟踪一条已转换的推导,有一种有用的方法:在每个人为添加的节点处记录其产出串。终结符代理恰好贡献它所命名的字母;链变元贡献分配给它的原产生式的连续后缀。这些局部断言使我们能够自叶子向上、逐棵完成的子树地收缩这些人为节点。当原有的子节点本身有许多种可能的推导时,这一点很有用:它们内部的选择在收缩中保持不变。该论证既不要求文法无歧义,也不要求其所有变元都是可产出的。不可产出的子节点只是没有可供收缩的、完整的终结符产出树。
对第二个定理还有一个简单的边界检查。长度为一的非空串有 ,因此没有二元节点。对于两个字母的词,恰好有一个二元节点,它的两个子节点各产生一个终结符。这些计数是完整范式分析树的性质,并不说明推导中途的任意句型恰好含有 个变元。
另一种范式使每个推导步骤都产生一个字母,代价是需要另一种构造。
通往推广的路径
若每条规则都必须以终结符开头,会怎样?
另一种范式使每个推导步骤都产生一个字母,代价是需要另一种构造。
Greibach 范式只允许形如 的规则,其中 是终结符, 是(可以为空的)变元串。每个不含空串的上下文无关语言都有这样的文法。由于每一步都产生一个字母,长度为 的字符串,其最左推导恰好用 步。所需的构造比上面的更复杂。
总结
首先去除空产生式与单位产生式,同时保护起始符及其可能的空串。把长规则中的终结符替换为新的终结符代理,再把长变元序列展开为新的二元链。树的展开与收缩证明了语言相等。所得的二叉树形状提供了 CYK 所需的非空划分,但并不自动保持歧义性或分析树的数目。
练习
练习 2.6.8
(把已化简的文法 、、 转换为带保护起始符的范式,并指出它的语言。)
基础
解答(3)
- 1
分离长规则中的终结符
加入 ,把 改写为 。
- 2
把三个变元的序列二元化
引入新变元 ,使用 、。保留 、 与 。
依据: 这条规则的长度为 ,所以需要一个新的链变元。
- 3
读出语言
离开 的唯一方式是 ,之后 。语言为 。
快速检查
(一棵范式分析树有七个终结符叶子。它含有多少个二元产生式节点?为什么它的非起始变元都不能推导出空串?)
利用非空串的节点个数公式。
解答 · 答案
它有六个二元节点。任何非起始节点只由二元规则或终结符规则展开。在有限的分析树中,这些规则不可能产生空的终结符产出,而唯一允许的空规则属于受保护的起始符,它不可能作为子节点出现。
快速检查
(设 、、。给出同一语言的范式文法,并解释为什么它的分析树数目不同。)
单元消去对两个根 和 做了什么?
解答 · 答案
单规则文法 生成同一个单元素语言。原文法有以 和 为中间根的两棵不同的树,而新文法只有一棵。语言相等并不意味着单元消去前后的分析树之间有一一对应。
练习 2.6.9
(预处理后的文法有 ,且 各有一条单终结符产生式。所述的右链构造需要多少个新的链变元?写出这些二元规则。)
核心
解答(2)
- 1
数出链变元
长度为五,因此引入三个变元 。
依据: 长度为 的规则需要 个新变元。
- 2
写出链
规则为 、、 与 。每个引入的变元恰好只有所显示的那条规则。