利用依赖图消除上下文无关文法中的不可达符号

前言

上下文无关文法中一个符号无用有两个原因，其一是无法从开始符号到达它，其二是无法从其推导出一个终结字符串。本文重点介绍一种用来消除第一种无用符号的简便方法——依赖图。

正文

在介绍消除方法之前，先介绍一下依赖图的概念。

• 依赖图

对于上下文无关文法中的依赖图，其中的顶点表示符号，而从顶点 $C$C 到 $D$D 之间存在边当且仅当存在如下形式的生成式$C\rightarrow xDy$C→xDy

• 判断方法

如果一个符号是有用的，仅当在依赖图中存在一条路径，它从以 $S$S 为标记的顶点出发能够到达以该符号标记的顶点。

示例
设文法 $G=\{ N,T,P,S\}$G={N,T,P,S}，$N=\{ S,A,B\}$N={S,A,B}，$T=\{ a\}$T={a}。生成式 $P$P 如下：$S\rightarrow aS|A\\A\rightarrow a\\B\rightarrow aa$S→aS∣AA→aB→aa消除其不可达符号。
解答
做出依赖图：

可知符号 $B$B 不可达，故删去。此时生成式 $P$P 如下：$S\rightarrow aS|A\\A\rightarrow a$S→aS∣AA→a