动机
一个文法中可能含有永远不会对终结符单词有贡献的符号、仅仅把一个非终结符改名为另一个非终结符的产生式,以及会消失的非终结符。去掉这些特征,能使后续的构造(例如乔姆斯基(Chomsky)范式)更容易理解。但也很容易删得过多:删去全部空产生式会丢失空单词;只在某一个位置删除可空符号,则会遗漏有效的推导。
我们将给出明确的有限构造,并证明两个方向的语言包含关系。这些构造保持的是语言,而不一定保持语法分析树、歧义性或推导长度。它们只是预处理工具,因此其假设条件以及对空单词的特殊处理都至关重要。
定义
定义 2.5.1
(可空非终结符、空产生式与单位产生式)
设 为有限上下文无关文法,其终结符字母表与非终结符字母表不相交。当 时,称非终结符 是可空的(nullable)。右部为 的产生式称为空产生式,形如 (其中 为非终结符)的产生式称为单位产生式。
首先引入一个新的开始符号 ,它不出现在任何旧产生式中。添加 。若 可空,则再添加 。新的开始符号不出现在任何右部中。这个预备文法与旧文法生成相同的语言:第一条新规则把推导交给 ,第二条规则只添加了一个本来就已被生成的空单词。
可空集合按最小不动点求得。先标记每条空产生式的左部。然后反复进行:若 的某个产生式的右部完全由已标记的非终结符构成,则标记 。终结符不是可空的。有限文法只有有限个非终结符,所以标记过程必然终止。
定理
定理 2.5.2
(空产生式的消除)
从带新开始符号的文法出发,可以构造出生成相同语言的文法,其中除了可能有 之外没有空产生式,并且 不出现在任何右部中。
定理 2.5.3
(单位产生式的消除)
从有限文法出发,可以构造出与之等价且没有单位产生式的文法。若其唯一的空产生式是受保护的 ,且 不出现在任何右部中,则该性质得以保持。
证明
计算可空非终结符
证明
(可空标记的正确性)
每个标记都是可靠的:标记规则把右部所有符号已知的空推导组合在一起。反过来,若 能推导出空单词,考虑一棵有限的推导树。其根处的产生式不能含有终结符,而且每个子非终结符都有一棵更小的、推导出空单词的树。对树高作归纳可知,这些子节点最终都会被标记,于是 也会被标记。
这个证明无需猜测就能处理循环。仅有规则 并不会使 被标记:不动点从没有任何无依据的标记开始。若有 、 以及 ,则先标记 ,再标记 。循环依赖需要一个有限的基础推导来确立可空性。
消除空产生式
对每条产生式 ,独立地对每个作为可空非终结符的 的出现选择保留或删除,从而生成一个右部。所有终结符的出现以及不可空的非终结符都必须保留。把每个生成的非空右部都作为 的产生式插入,并去除重复项。删去所有空右部,然后当且仅当原来的开始符号可空时,恢复 。特别要注意,删除某个重复出现的非终结符的一次出现,与删除它的另一次出现是不同的选择,尽管所得的右部可能相同。
证明
(消除空产生式的构造保持语言不变)
为证明每个新推导产生的都是旧单词,把每条生成的产生式替换为它所来自的旧产生式,并对每个被省略的可空出现插入一个空推导。受保护的空产生式是合理的,因为 原本就可空。因此每个新的终结符单词都属于原来的语言。
对于另一方向的包含关系,取一棵生成非空终结符单词的旧推导树。删去每个其终结符产出为空的子树。在每个保留下来的非终结符处,被删去的子节点都是可空的出现,所以它剩下的右部正是所生成的备选右部之一。保留根以及其产出对非空单词有贡献的子节点。这样便得到生成同一单词的新树。若旧单词为空,则由受保护的 产生它。两个方向的包含关系合起来就证明了定理。
证明透视
删除一个符号相当于表示一整个空推导
由新到旧的包含关系较容易;由旧到新的包含关系才带有思想。旧树中的某个可空出现可能位于一棵产出为空的大子树之上,但新文法无法保留一个其子树已经消失的非终结符,所以必须在父节点处把这次出现删去。这就是为什么每个出现都独立地选择删除或保留:旧树逐个出现地决定哪些子节点的产出为空。论证依靠两个假设。标记过程所提供的、通往空单词的有限推导,在由新到旧的方向上把空推导放回去,从而证明删除是合理的。受保护的开始规则则处理唯一无法由任何非空右部表示的单词,即空单词本身。没有这条受保护的规则,构造就会丢失 ,例题中 的情形说明了这一点。
一个含有 个可空出现的右部,在去重之前至多有 种删除选择。这可能使单条产生式的规模发生指数膨胀。证明某个构造会终止,并不自动意味着其输出具有多项式规模的界。
消除单位产生式
在非终结符上建立一个有向图,对每条单位产生式 连一条边 。对每个 ,找出所有经由零条或多条单位边可达的 (包括 本身)。对每条非单位产生式 ,添加 。最后删去所有单位产生式。单位环不构成困难:图的可达性只涉及有限个顶点,并且多次复制同一条产生式没有任何影响。
证明
(消除单位产生式的构造保持语言不变)
就可靠性而言,新添加的 模拟了旧的从 到 的单位路径,随后接上 。就完备性而言,取一棵旧推导树,把每条极大的单位节点链压缩到紧随其后的第一条非单位产生式。相应的图可达性使得该非单位产生式被复制到了链的起始非终结符。每个有限的终结符推导在每条被压缩的链之后都有这样一条产生式,所以得到的树产生同一个单词。
若 不出现在任何右部中,则除 之外没有非终结符含有指向 的单位边。因此只有 能通过单位边到达受保护的 的源头,复制步骤不会引入不受保护的空产生式。这就是新开始符号这一限制有用而非装饰的原因。
单位图中的零长度路径至关重要。它保证 已有的每条非单位产生式都被复制回 ,即使 没有任何出边。若先删除全部产生式再仅沿正长度路径复制,就可能误删普通的生成终结符的规则。另一种实现方式是保留所有已有的非单位产生式,仅显式地沿正长度路径复制;去除重复后,两种描述给出相同的集合。
反例模式
先消除单位产生式,并不能保证它们不再出现
断言:单位产生式一旦消除,再消除空产生式就不会把它们带回来。取 、、。这里没有单位产生式,所以消除单位产生式什么也不改变。只有 可空,从 删去它便加入 ,这是新的单位产生式,而语言仍是 。补救办法就是本节采用的次序:先消除空产生式,再消除单位产生式,此例便把 复制成 。
即使有些非终结符从开始符号不可达,该构造仍保持终结符语言。这些多余的规则可以由随后的有用符号处理步骤去除。把单位消除与可达性分开,可以简化证明:单位图可以对每个非终结符进行处理,而无需先判定它是否参与从开始符号出发的推导。
删除无用符号
若非终结符能推导出某个终结符单词(可以是空单词),则称其为可产生的(productive)。计算可产生的非终结符的方法是:只要 的某条产生式仅含终结符和已标记的可产生非终结符,就标记 。空右部满足这一条件。删除每条含有不可产生非终结符的产生式,并删除不可产生的符号。终结符推导不可能用到这样的符号,因此这不会删去任何终结符单词。
若开始符号是可产生的,则在剩下的文法中计算从它可达的符号:从开始符号出发,沿着左部已被到达的产生式的右部出现进行。删除不可达的产生式和符号。剩下的产生式中的每个符号都是可达的,且剩下的每个非终结符都是可产生的。从开始符号出发的终结符推导从不经过不可达的符号,所以语言不变。
顺序对于“最终文法没有无用非终结符”这一论断是重要的。某个符号可能仅通过后来因含不可产生符号而被丢弃的产生式才可达;在可产生性过滤之后重新计算可达性,便能去掉这个新孤立出来的符号。若开始符号不可产生,则语言为空。用一个没有任何产生式的开始符号单独表示它;此时开始符号必然不可产生,所以不要声称这种空语言的表示中所有非终结符都是可产生的。
反例模式
仅仅可达并不意味着有用
对于 、、,在原文法中 与 都是可达的,但 不能推导出终结符单词。删去 这条产生式后, 变为不可达;化简后的非空语言文法可以直接使用 。
例题详解
例题 2.5.4
(重复出现的可空符号)
设 ,。 与 都是可空的。产生式 生成非空备选 ;删除任一个出现都得到同样的备选 。保留 ,并使用新开始符号来保护空单词。所得语言为 ,与原来完全相同。
例题 2.5.5
(一个单位环)
对于 ,,,单位图使 与 互相可达,并使二者都从 可达。 每个都得到分别生成 和 的两条非单位产生式。删去单位产生式后,开始符号的语言仍为 。
例题 2.5.6
(为什么需要受保护的开始符号)
若 ,不加补偿就删去空规则会丢失 。引入 。可空删除在 之外添加 ,而单位消除把这些非单位备选复制到 。所得的开始符号仍然推导出 中的每个单词,包括空单词,同时没有任何旧的非终结符需要空规则。
例题 2.5.7
(空语言)
对于 ,,两个非终结符都不是可产生的:没有任何有限推导能产生终结符单词。其语言为空。带新开始符号 且没有任何产生式的文法即表示该语言。仅仅发现 是可达的,并不会使它成为可产生的。
常见错误
常见错误
(可空符号的每个出现都是各自独立的选择)
一个非终结符可以在右部中出现多次,并且在修剪后的树中每个出现各自独立地存在或不存在。若只对每个符号名称做一次全局决定,就可能遗漏产生式。例如,若 且 可空,则只保留第一个出现或只保留第二个出现,会产生不同的备选 与 。
常见错误
(单位产生式指的是整条右部)
单位链是由整条产生式 构成的序列,而不是在其他符号之中含有一个非终结符的产生式。规则 不是单位产生式。类似地,仅有单位环并不能生成终结符单词;被复制的是有限链末端的可产生备选。
常见错误
(语言相同并不表示语法分析树相同)
最后,语言等价并不意味着语法分析结构相同。复制和修剪产生式可能把原本不同的推导合并。不要用这一保持语言的证明去推断语法分析树的数量或歧义性得以保持。
总结
可空不动点识别出有限的空推导。删除可空出现的任意组合并保护开始符号,可以保持每个单词,包括空单词。随后,单位可达性用非单位出口取代单位链。先做可产生性过滤再做可达性过滤,便去除了未使用的结构,而空语言另作处理。每一步都有双向的证明,而不是纯粹句法上的论证。
练习
快速检查
(对于 ,,,列出由 生成的非空备选,并说明开始符号是否需要受保护的空产生式。)
独立地删除每个可空的出现,再舍弃空的结果。
解答 · 答案
备选为 、 和 。同时删去两者会得到空右部,该右部在此被省略。由于 与 都可空, 也可空,所以新开始符号必须保留其受保护的空产生式。
快速检查
(对于 ,,,给出一个等价的、无单位产生式的开始产生式。)
沿着从 出发的单位边走。
解答 · 答案
单位图中有一条从 到 的路径。复制非单位产生式 ,得到 。自环 不会带来额外的终结符产生式。
快速检查
(解释为什么文法 ,, 的语言为空,尽管每个非终结符都是可达的。)
哪些产生式可以作为可产生性标记的起点?
解答 · 答案
没有任何含终结符的产生式或空右部可以作为可产生性标记的起点。没有任何非终结符能推导出终结符单词。可达性只说明符号出现在可能的推导中,并不保证推导能以终结符结束。
快速检查
(在 中( 可空),列出通过删除 的出现所生成的所有互不相同的非空备选。)
共有两个出现,所以有四种删除方式。
解答 · 答案
备选为 、、 和 。由于终结符 从不被删除,它们都是非空的。两种只删除一个出现的情形,分别在于被保留的非终结符所处的位置。