动机
有限自动机无法匹配任意深度的嵌套,因为匹配需要不受限制的计数。上下文无关文法直接描述嵌套结构:像 这样的规则表示,一个平衡块是一个左括号、一个平衡块、一个右括号,再接一个平衡块。下推自动机是与之对应的机器,即带有后进先出栈的有限控制器。本节证明二者在一个方向上的精确联系——从文法到栈机器——然后证明一个为该语言类划定边界的泵引理。
泵引理显式使用乔姆斯基(Chomsky)范式作为前提;配套笔记范式与栈计算中隐藏的文法给出该前提及 NPDA 到文法的完整证明。本节从文法到机器的证明不依赖反向构造。
定义
定义 2.4.1
(上下文无关文法与推导)
上下文无关文法(CFG)是 ,其中 是有限的变元集, 是与 不相交的有限字母表, 是有限的规则集,记作 , 是起始变元。若 由 把某个变元出现 按规则 替换为 而得,记作 ; 是其自反传递闭包。语言为 ,若一个语言等于某个 CFG 的 ,则称它是上下文无关语言。若每一步都替换最左边的变元,则该推导称为最左推导。
定义 2.4.2
(语法分析树、产出与歧义)
语法分析树以起始变元为根,每个内部节点标记为一个变元,其子节点依次拼出某条规则的右部,叶子标记为终结符或 ;其产出是沿叶子读出的字。 的每个字都是某棵语法分析树的产出;每一步展开最左边尚未展开的变元,每棵分析树就给出一个最左推导。若某个字有两棵不同的分析树(等价地,两个不同的最左推导),则称该文法是有歧义的。
定义 2.4.3
(非确定型下推自动机(空栈接受))
NPDA 是 ,其中 是有限集, 是初始栈符号, 的有限子集。格局是 :状态、尚未读入的输入,以及栈内容(栈顶在左)。若 ,,则 。若对某个 有 ,则机器以空栈接受 。
这一约定是一种选择。按终态接受是另一种常见约定;二者等价是标准定理,此处不予证明,因此下面所有关于 NPDA 的陈述都指空栈接受。
定理
定理 2.4.4
(两个基本文法)
(a) 文法 恰好生成 。(b) 称 上的字平衡,如果其左括号与右括号个数相等,且每个前缀中左括号不少于右括号。文法 恰好生成全部平衡字,并且每个平衡字恰有一棵分析树。
定理 2.4.5
(从文法到栈机器)
设 是 CFG。定义 :只有一个状态 ,栈字母表为 ,初始栈符号为 ,转移为:对 ,;对 ,;再无其他转移。则 以空栈接受的恰好是 。
定理 2.4.6
(上下文无关语言对并、连接与星号封闭)
若 是上下文无关语言,则 、 与 也是。
定理 2.4.7
(上下文无关语言的泵引理)
假设范式定理成立:每个上下文无关语言 都有一个乔姆斯基范式的文法(每条规则形如 或 ),它生成 。在此假设下,若 是上下文无关语言,则存在 ,使每个满足 的 都可写成 ,其中 ,,且对每个 有 。
证明思路
证明
(基本文法:对推导的归纳)
基本文法。 (a) 对推导长度归纳:从 推出的终结符字要么立即使用 ,要么以 开始,其余推导从 产出 ,所以该字为 。反之, 由 次使用 再使用 得到。
(b) 可靠性对推导长度归纳: 的产出是一个括号、一个平衡字、一个括号和一个平衡字,这些构造保持前缀条件。完备性对长度归纳。设 非空且平衡;它以左括号开头。令 为使前缀的两种括号个数相等的最小正长度,由于 本身个数相等,它存在。对小于 的正前缀长度,左括号个数严格多于右括号,所以第 个符号是右括号,且长度为 的前缀的多出量恰为一。于是 ,其中 (第 至第 位)两种括号个数相等且每个前缀多出量非负,而 平衡,因为 之后的前缀多出量非负,而长度为 的前缀多出量为零。 与 都更短,故应用归纳假设。唯一性:非空 的任何分析树根处必用 ,而分解 ( 平衡)被迫取为第一次回到零的位置,因为平衡的 后接一个右括号恰在该处首次回到零。对长度归纳即得各子树唯一。
证明
(从文法到 NPDA:两个包含方向)
从文法到 NPDA。 的每个字都被接受。 取最左推导 ,写 ,其中 为终结符串, 为空或以变元开头。最左推导从不修改终结符前缀,所以 (某个 )。我们断言对每个 有 。 时显然。归纳步骤中,,所用规则为 。规则转移把栈上的 替换为 ,然后写 ( 为终结符串, 以变元开头或为空),转移 把 的符号与输入逐个匹配弹出,这是可行的,因为 。当 时,栈为空且输入已读完。
每个被接受的字都属于 。 我们证明:若 ,,且 ,则 。对 作强归纳。若 为终结符,唯一可用的转移是用输入符号 弹出 ,所以 。若 为变元,第一步是规则转移到 ,其中 。若 ,栈已为空,。否则,每一步只检查并替换栈顶符号,恰好移除一个符号并压入若干符号,所以栈的高度每步至多下降一。令 为栈首次等于 的时刻。在 到 的这段时间里,高度始终高于 ,所以 从未被触及,这一段是从 到 的计算,其中 是这一段读入的输入。于是 ,每段都短于 ,由归纳假设 。故 。对 应用即得结论。
证明
(对并集、连接与星号的封闭性)
封闭性。 重命名后设变元集不相交,起始变元分别为 。取新的 ,并并入规则:并用 ,连接用 ,星号用 。由于变元集不相交,从 与 出发的两个子推导互相独立地演化。这分别给出 、 与 ,最后一个对 的使用次数归纳。
证明
(由语法分析树的高度推出泵引理)
泵引理。 设 是 的范式文法,有 个变元,令 。在分析树中,每个内部节点要么有两个变元子节点,要么有一个终结符子节点。因此对高度 (最长根到叶路径上的边数)归纳可知,高度为 的树至多有 个叶子。取 的 及其分析树。它的高度满足 ,所以最长路径上至少含 个变元节点。在这条路径最低的 个变元节点中,由鸽巢原理有两个带有同一变元 ;设为 (在上)与 (在下)。 处的子树高度至多为 ,所以其产出 ( 为 子树的产出)满足 。由于 有两个子节点,其中一个指向 ,另一个子节点的产出非空(此完整分析树的旁支均有非空终结字作为产出),且落在 或 内,所以 。把 处的子树换成 处子树的副本,得 ;把 处的子树反复换成 处子树的副本,得 。
证明透视
上下文无关泵引理中的依赖关系
证明建立在三个支撑上。第一,范式假设使树成为二叉的,从而把高度界转化为叶子数界,并保证有一个旁支贡献非空产出;没有它,像 或 这样的规则可能使 为空。第二,鸽巢原理作用于同一条最长路径上的变元,这决定了 。第三,同一变元 出现在两个节点,意味着下方节点的子树可以替换上方节点的子树,或被其替换,而结果仍是合法的分析树。论证以读出各部分产出作结。
反例模式
上下文无关语言对交与补不封闭
断言(错误):若 与 是上下文无关的,则 也是。取 与 ,可由 、、 及其镜像生成。二者都是上下文无关的,但 ,由泵引理它不是上下文无关的(见关于 的例题)。补也不封闭:若该类对补封闭,又因它对并封闭,则 将是上下文无关的。修正:对并、连接与星号封闭是成立的;与正则语言求交也封闭,但此处不证明。
概念视角结构
栈作为最左句型中尚未展开的部分
在模拟过程中,最左句型 被分成已消耗的终结符前缀 与放在栈上的待处理部分 。因此栈恰好包含推导仍需展开或与输入匹配的内容。规则转移就是推导的展开,弹出转移则是把终结符与输入核对。这就是该构造只需一个状态的原因:全部控制信息都在栈内容里。
例题
例题 2.4.8
((())() 的最左推导与分析结构)
用 :。根处的规则把该字分解为 ,其中 ,; 的子推导是第二到第四步, 的子推导是最后三步。由第一个定理的唯一性部分,不存在其他分析树。
例题 2.4.9
(表达式文法的歧义)
对 ,字 有两个最左推导: 把它分组为 ,而 把它分组为 。两棵不同的树给出不同的解读,这对求值很重要。下面的构造通过把和、积与原子分层来修复这种歧义。我们既要证明终结符字的集合不变,又要证明每个字只剩一棵树。歧义属于文法:同一个语言也可能有无歧义的文法。
保持表达式语言不变,修复文法歧义
一句“先乘后加”并没有改变原文法的产生式;它的两棵分析树仍然存在。要让文法本身规定这个约定,可用三个变元,以 为起始变元:
这里 表示表达式, 表示项, 表示因子。终结符字母表仍是 。这些规则不含括号、一元运算符或空表达式。记
所以 、 和 属于 ,而 、 和 不属于。 的情形就是单独的字 。
定理 2.4.10
(相同的表达式语言,唯一的分析树)
原来的单变元表达式文法与分层文法都恰好生成 。分层文法无歧义:它把乘法安排在项的内部,并使连续的加法及连续的乘法均向左结合。
证明
(分层文法生成相同的单词)
语言相等。 对原文法,按分析树归纳可知每个产出都在 中:叶子产生式给出 ,而用任一运算符连接两个 中的字,所得仍在 中。反过来,对 中一个字的运算符个数归纳。没有运算符时,该字为 。对于更长的字,切出最后一个运算符及最后一个 ,写成 。按照 选择 或 ,对左边的 用归纳假设,右边推出 。这就证明了原文法语言的两个包含方向。
对分层文法, 只生成 ,而 恰好生成非空的乘积 :每用一次 ,就加上最后一个因子; 则结束递归。这里 指把“一个字面上的乘法符号后接 ”这个双符号块重复 次;括号只是记号,不是终结符。 的分析树则对应一个由 分隔的非空项序列,因为 每次加上最后一项。每个 中的字都有这种分解:在所有 处切开,再把余下的各块读成乘积。这给出它的分层推导。反之,这些产生式只会生成以 开头和结尾、操作数与运算符交替出现的字。因此,分层文法的语言也恰好是 。
修复后的文法为什么只有一棵分析树
证明
(分层文法的语法分析树唯一)
对于 ,产出 的树是唯一确定的。对于一个 字,按乘法符号的个数归纳证明唯一性。没有乘法时,只能取 。至少有一个乘法时,根处必用 。由于右侧 恰好产出一个 ,根处的乘法符号必是字中最后一个 。于是左侧子串被唯一确定,且比原字少一个乘法符号。由归纳假设,它有唯一的 树;右侧的 树也唯一确定。
接着按一个 字中加法符号的个数归纳。没有加法时,根处不可能用 ,所以只能用 ,而 树的唯一性已经证明。有加法时,根处不可能用 ,因为项不含 。因此必用 ;其中的 必须是最右边的加法符号,因为右侧的项不能再含 。这同时确定了左右两个子串。左边少了一个加法符号,由归纳假设有唯一的 树;右边根据前一段有唯一的 树。因此每个字至多有一棵树。语言相等的证明已经保证至少有一棵,无歧义性得证。
证明透视
根处的切分必须被迫唯一,而不只是可行
语言相等的论证告诉我们怎样构造一棵树,但这本身不能排除另一棵。唯一性依赖右侧子节点的限制:因子只是一个 ,项则不能含加法。这些限制迫使项的根乘法位于最后一个乘法符号,表达式的根加法位于最后一个加法符号。随后归纳处理被唯一确定的较小部分。证明没有预先假设所希望的优先级约定,而是从产生式推出该约定。
例题 2.4.11
(先确定根处的切分,再展开树)
对于 ,最右边的 迫使根处切成 。在左侧表达式中,剩下的 迫使切分为 。乘积 只有一棵 树。所以最终分组为 ;这里展示的括号用来描述树,不是额外加入的终结符。若每个 都取值 ,该树给出 。 对应的树会给出 ,但它被排除,因为 子树不能生成 。
同样, 在根处切成 ,而 作为项切成 。这些都是左结合的树。虽然普通加法与乘法满足结合律,这些特定的重新分组会给出相同数值,但数值相同并不使两棵树成为同一棵树。文法规定语法结构,并不依赖这种代数上的巧合。
什么差异才真正说明有歧义?
反例模式
两种推导顺序可能描述同一棵树
对于 、、,推导 与 确实不同。它们只是以不同顺序展开互不依赖的兄弟节点,描述的却是同一棵树:根为 ,子节点为 ,终结符叶子为 。只有第一个推导是最左推导。这个文法无歧义。要证明歧义,必须给同一个字找出两棵不同的树,或者两个不同的最左推导;仅有两个任意展开顺序还不够。
左递归也是另一回事。 是左递归规则,但上面的证明已经建立无歧义性。若某个朴素分析过程总是优先展开这个递归选项,它可能尚未读取输入就永远运行下去。这是该分析过程的问题,并没有给出第二棵树。反过来,直接删除这个选项会丢失所有含 的表达式,也就不能保持语言不变。
快速检查
((a) 写出 被迫采用的分组。(b) 保留 ,但把项的规则替换为 ,文法是否仍无歧义?)
解答 · 答案
(a) 先在最后一个 处切开,再在剩下的 处切开,最后处理各项内的乘法。分组为 。(b) 否。字 有一棵左子树产出 的 树,也有一棵右子树产出 的 树。把任一棵接在 下方,就得到两棵表达式树。修复所需的是 右侧只能是因子,而不能是任意项;只给层次起不同名字,却不落实限制,并不足以消除歧义。
例题 2.4.12
(用 M_G 处理 aabb)
对 :。第一、三、五步展开 ,其余各步弹出一个匹配的终结符,第五步使用 。在恰当的时刻选择 由非确定性完成;错误的选择,例如过早地用 展开 ,会使栈已空而输入尚未读完,这不是接受格局。
例题 2.4.13
( 不是上下文无关的)
假设 有泵长度 ,取 。由于 ,因子 不可能同时含有 与 ,因为二者之间隔着 个 。所以三种字母中至少有一种不在 中出现,而 表明至少有一种字母出现。于是 中出现在 里的某字母个数增加,而未出现的字母个数不变,三个个数不相等,该字不在 中,与引理矛盾。
常见错误
常见错误
(歧义属于文法,而不属于语言)
常见错误之一是把歧义当作语言的性质。它是文法的性质;“固有歧义”才是针对语言的另一个概念。同样,“上下文无关”并不意味着文法无歧义,也不意味着机器是确定的。一般而言这里需要非确定性;本节不讨论确定型下推自动机。
常见错误
(空栈接受要同时满足两个条件)
本节的 NPDA 以空栈接受:接受格局要求输入耗尽且栈同时为空。输入已全部读完但栈中仍有符号的运行不是接受。
常见错误
(要检查被泵部分的每一种位置)
在对 的泵论证中,长度界 表示 或者落在同一段相同字母之内,或者跨越两段相邻的字母块。完整的论证要处理每一种位置:在每一种位置上, 都没有触及某个字母,该字母的个数仍是 ;而泵送至少改变 中出现的某个字母的个数(因为 ),所以三个个数不再相等。只检查某一种方便的位置并不能证明什么。此外,泵引理只能证明一个语言不是上下文无关的,而不能证明它是。
总结
上下文无关文法生成嵌套结构,推导对应于分析树。分层表达式文法保持终结符语言不变,同时规定唯一的树,使乘法优先、连续运算向左结合。单状态栈机器模拟最左推导,并以空栈接受恰好是该文法的语言;逆向命题见配套范式笔记。上下文无关语言对并、连接与星号封闭,但对交与补不封闭。在范式假设下,泵引理给出 的形式,并表明 在该类之外。
练习
快速检查
(给出 的文法,并证明两个包含方向。)
解答 · 答案
用 。从 可达且含变元的句型都形如 ,,因为 增加一个 和一个 , 增加一个 ;最后一步 给出 的 。反之,对 ,先恰好应用 次 ,再恰好应用 次 ,最后应用 。
快速检查
(证明 不是上下文无关的。)
解答 · 答案
设 为泵长度,。因为 ,它不能同时触及 和 ,所以四种字母中至少有一种不在 中,且至少有一种在其中。取 泵送会使某一个个数增加而另一个不变,四个个数不再相等,该字不在语言中,矛盾。
快速检查
(对 CFG ,把每条规则的右部反转得到 。证明 。)
解答 · 答案
对推导长度归纳,证明对每个变元 和终结符字 , 当且仅当 。长度为一时即规则的定义。对更长的推导, 中的第一条规则 ( 为终结符串)给出 ,其中 ;在 中该规则是反转后的串,由归纳假设,它产出 ,且每个 由 推出。逆向对称。
快速检查
(对 ,列出 接受 的格局序列。)
解答 · 答案
。各步在展开与弹出之间交替,展开 共用了三次。