第三章
上下文无关文法与上下文无关语言
? 上下文无关文法的重要性：
? 拥有足够强的表达力来表示大多数程序设计语
言的语法
? 可以构造有效的分析算法来检验一个给定的字
符串是否是由某个上下文无关文法产生 。
? 上下文无关语言在实践中有重要意义：
? 1） 定义程序设计语言,
? BNF（ 巴克斯 -诺尔范式 ） ；
? 2） 描述文档格式,
? XML,HTML；
? 3） 使语法分析概念形式化；
? 4） 简化程序设计语言的翻译,
? 语法分析器的设计；
? 给定文法 G,如果对于 G中的任意产生式 ν→ω,
而 ν只是一个非终结符, 即 A→ω, A∈ V,
ω∈ (∑UV） *,则称文法 G为上下文无关文法 （ 简
称无关文法 ） 。 如果一个语言能由一个无关文法
产生, 则称这个语言是上下文无关语言 （ 简称无
关语言 ） 。
定义 3-1 线性的无关文法
?若无关文法 G=(∑,V,S,P)的
所有产生式都是下列形式之一：
?A→uBv 或 A →w ；
?其中,A,B∈ V； u,v∈ ∑+； w∈ ∑*。
?该文法称为线性的无关文法 。
?注意,u,v可以有一个为空串 ε。
?特别地,
如果 u=ε,称为左线性的 (无关 )文法；
如果 v=ε,称为右线性的 (无关 )文法 。
?从定义可以看出, 线性的无关文法是受
限制的无关文法；本身一定还是无关文
法 。
化简的上下文无关文法
?左线性文法和右线性文法是线性文法中
特殊的两类 。
? 定理 3-2 G=（ ∑,V,S,P） 是一个上下文
无关文法, 产生式的一般形式为 A→w, 其中：
w∈ （ ∑UV） *,
? 则存在另一个等价的线性的无关文法 G1,而
G1中产生式的形式为；
? A→a 或 A→aβb 。
? 其中, A∈ V； a,b∈ ∑U{ε}； β∈ V+。
?证明：
? 读者自己完成 。
? 定理 3-3 G=（ ∑,V,S,P） 是一个上下文
无关文法, 产生式的一般形式为 A→w, 其
中,w∈ （ ∑UV） *,则存在另一个等价的无
关文法 G1,而 G1中产生式的形式为；
? A→a 或 A→aB 或 A→aBC 。
? 其中,A,B,C∈ V； a∈ ∑{ε} 。
?证明,读者自己完成 。
3.1 消除无关文法中的无用非终结符号
? 定义 3-4 文法中的无用符号
?一个无关文法 G,符号 Y∈ V,如果不出
现在任何形如 S=>*uYv=>*uwv的推导
之中, 称 Y为文法 G的无用非终结符 。
?其中,u, w, v ∈ ∑*。
?反之, 一个无关文法 G,符号 Y∈ V,如
果能够出现在某个形如
S=>*uYv=>*uwv的推导之中, 称 Y为
文法 G的有用非终结符 。 其中,u,
w, v ∈ ∑*。
? 从定义可知：有用非终结符, 必须同时满
足两个条件
? (1) 从它开始推导, 能够产生终结符号串；
? (2) 它必须出现在某个句型中；
? 判断某个符号是有用非终结符, 就应该从
这两方面同时进行考虑 。
?有用非终结符的判断算法：
?略。
定义 3-7 无用的产生式
? 如果一个产生式中 （ 产生式的左边或右边 ） 包含
有无用的非终结符, 则该产生式就是无用的产生
式 。 可以将无用的产生式从文法中删除掉 。
? 问题 3-8 文法产生的语言是否为空？
? 一个无关文法 G,产生的语言为 L(G),而 L(G)是
否为空 （ 即空集 Ф）, 是可以判定的 。
? 注意：
? 一个语言包含有空串 ε 或语言本身就是 {ε },它
们都不是空集 Ф。
? 判定方法：
? ① 首先使用空串定理, 消除该无关文法中的所有
空串产生式, 如果还有 S→ ε, 则该文法产生的
语言不为空；
? (2)构造能产生终结符串的非终结符集合 N,如果
S ∈ N,则该文法产生的语言不为空 。 否则, 该
文法产生的语言为空 。
? 定理 3-11 已知产生一个非空语言的上下文无关
文法 G,则对于某个 A ∈ V,总有 A=>*w,且
w∈∑ *。
? 证明：
? 读者自行完成 。
? 定理 3-12 一个无关文法 G=(∑,V,S,P), 产生的语言为
L(G)。 如果 L(G)不为空, 则至少存在一个非终结符 A,而
它的产生式右边仅仅只包含终结符号或空串 ε 。
? 证明提示：
? 考虑产生串的推导过程中最后使用的产生式的特点 。
? 证明：
? 读者自行完成 。
? 定理 3-13 已知产生一个非空语言的上下文无关
文法 G=（ ∑, V,S,P）, 则能够构造一个等价
的无关文法 G1,对于任意 A ∈ V,总有一个推
导,S=>*w1Aw3=>*w1w2w3,且 w1,w2,w3 ∈∑ *。
? 证明：
? 读者自行完成 。
? 定理 3-14 已知产生一个非空语言的上下文无关
文法 G=(∑,V,S,P), 则文法中的每个非终结符都
是有用的；即：若 A∈V, 则 S=>*uAv=>*uwv
? 其中,u, w, v ∈∑ *。
? 证明：
? 读者自行完成。
? 问题 3-15 上下文无关语言 CFL是否有穷是否可
以判定？
? 上下文无关文法 CFG生成无穷个句子的原理是利
用递归的产生式，即
? S=>*uAy=>*uvAxy=>*… =>*uviAxiy=>*uviwxiy
? 根据着一原理可以判定上下文无关语言是否有穷 。
? 定义 3-16 可派生性图的定义
? 上下文无关文法 G=（ ∑, V,S,P）, 文法 G的可
派生性图是满足下列条件的有向图：
? (1)对于终结符或非终结符 X，图中有且仅有一个
标记为 X的顶点。
? (2)如果 A->X1X2… Xn,则图中存在从标记为 A的
顶点分别到标记为 X1,X2,…,Xn的顶点的弧 。
? (3)图中只有满足条件 (1)和 (2)的弧 。
? 可派生性图表示了 G中变量间的派生关系：从 A到
B有一条有向路表示 B出现在 A派生出的某个符号
串中 。
? 3.2 推广的化简上下文无关文法
? 上下文无关文法化简的目的：
限制产生式的格式而不降低文法生成句子的能力,
从而降低文法分析算法的复杂度 。
? 上下文无关文法化简的基本手段：
删除无用符号
删除单一产生式组
? 对于一个上下文无关文法 G,如果：
? ① 没有 A→A 形式的产生式；
? ② 每个非终结符 A都是有用的, 即：
? 有 S=>*α Aβ =>*α wβ ；
? 其中,α, w,β ∈∑ *；
? 则该文法是化简的上下文无关文法 。
? 对于任意的无关文法, 进行
? （ 1） 直接删除没有 A→A 形式的产生式
? 对于 A→A 形式的产生式, 该类产生式是递归的, 可以反
复利用任意多次, 但对于无穷语言的产生, 没有任何作
用 。 可以直接删除即可 。
? （ 2） 消除无关文法中的无用非终结符号
? 消除无关文法中的无用非终结符号后, 无关文法中的所
有非终结符号都是有用的 。
? 得到的文法是化简的上下文无关文法 。
? 定义 3-21 推广的简化上下文无关文法：
? 对于一个上下文无关文法 G,如果该文法中不存
在形如 A → B的产生式 （ A,B ∈ V ）,
? 则该文法是推广的化简上下文无关文法 。
? 定理 3-22 对于一个上下文无关文法 G,能够找
到一个等价的无关文法 G1,而 G1中不存在形如 A
→ B的单产生式 （ A,B ∈ V ） 。
? 证明思路：
? 对于某个推导过程：
S=>*α Aβ =>α Bβ =>α wIβ =>…
? 可简化为,S=>*α Aβ =>α wIβ =>…
? 即省略掉 A => B的推导 。
? 因此, 需要将 A→B 的产生式使用下面产生式进行
替换：
? A →w 1|w2|w3|… |wn
? 而 B →w 1|w2|w3|… |wn 是文法 G中关于 B的所有
产生式 。
?实际上, 就是将推导过程在产
生式中就体现出来 。
? 注意, 对于关于 B的产生式,
B →w 1|w2|w3|… |wn
需要保留, 不能删除 。 因为可能存在
? S=>α 1Bβ 1=>α 1wIβ 1=>…
? 的推导, 即该推导过程没有使用产生式 A → B。
思考：
? 能否将文法中的产生式右边的 A直接替换为 B，
然后将
? A→β 1|β2|β3|… |βm|B
? 替换为
? B→β 1|β2|β3|… |βm
? 这是不行的；因为可能产生多余的串 。
? A →α,而 B → β,如果 B →α,它将 B的功能
扩大了 (能够定义为 α和 β)。
? 例如：
? S → AB S → BB
? A →B|a B →a
? B →b B →b
? L为,{ab,bb} L为,{aa,ab,bb,ba}
3.3 推导树
?对于无关文法 G,如果串 ω能由该文
法产生, 则 ω的产生过程可以用推导
的办法表示, 即用符号, =>”表示,
也可以用推导树的办法表示 。
定义 3-23 推导树（语法分析树）
? 推导树是一棵有向无循环的图 。
? 树的节点是文法中的非终结符或者终结符, 如果
有空串产生式, 则 ε 也可以是树的节点, 树的根
节点是文法的开始符号 S； 如果推导使用了产生
式 A→a 1a2a3… an,其中 A是非终结符, ai是非终
结符或者是终结符；则 a1,a2,a3,…, an都是 A
的直接后继节点 （ A称为父节点, a1,a2,a3,…,
an称为子节点 ） ；
? 一个节点和它的直接后继节点之间用有向边连接
起来；
? 如果节点是终结符, 该节点称为叶子节点；
? 如果节点是非终结符, 该节点称为非叶子节点
（ 或称为分枝节点 ） ；
? 端末节点 (仅有入口, 没有出口的节点 )从左到右
的连接, 是该推导树产生的边缘 。
?注意：推导树是向下生长的。
?定理 3-24 设文法 G为无关文法，那么
S=>*α，当且仅当存在一棵以 α为边
缘的推导树。即文法和推导树都可以
产生串 α。
?证明,
?略。
?结论,端末节点从左到右的连接，就
是该推导树产生的句型。
?注意：
?推导树不仅可以表示句子的产生，也
可以表示句型的产生。
?思考：
?端末节点一定为终结符吗？
? 定义 3-24 直接子孙和子孙的定义：
? 在一个有向无循环的图 (树 )中，称满足下
列条件的节点 n为节点 m的直接子孙：有一
条有向边从节点 m出发进入节点 n。
? 如果有节点的序列,n1,n2,n3… nk，使
得 m=n1,n=nk，以及对于每一个 i,ni+1是
ni的一个直接子孙,则节点 n称为节点 m的子
孙。
?约定：
?每一个节点都是自己的子孙。
?一棵推导树 T中的每个节点
都是根节点 S的一个子孙。
?定义 3-25 推导树的另一个
定义
?无关文法 G=(∑,V,S,P)，若
一棵树满足下列条件，则称
之为文法的推导树：
?每个节点都有一个标记 (是
∑UV的一个符号或者是 ε)；
?根的标记为 S；
?若一个节点有多于 1个的子孙，
该节点标记的符号为非终结符号；
?如果节点 A的所有直接子孙，
从左到右的次序是标记为 A1，
A2,A3,…, Ak的节点，则
?A → A 1A2A3… Ak为文法 G的一
个产生式。
?实际上，存在产生句子的（完
整的）推导树，也存在产生句型的（不完整的）推导树。
?一棵推导树中，仅有一个子孙
的节点称为端末节点（该子孙就是自己）。
?定义 3-26 最左推导和最左推导的定
义
?无关文法 G，有产生式 A →β,对于一
步直接推导 α1Aα2=>α1βα2：
?若 α1∈ ∑*，则称之为一步最左推导；
?若 α2∈ ∑*，则称之为一步最右推导；
?对于文法 G和句型 w：
?如果产生 w的每一步推导都是最左推
导，则称产生 w的推导为最左推导；
?如果产生 w的每一步推导都是最右推
导，则称产生 w的推导为最右推导。
?最右推导还称为规范推导。
?一般，常使用
最左推导。
?例 3-27 文法 S→0B|1A
?A→0|0S|1AA
?B→1|1S|0BB
?对于串 0011的产生过程：
?最左推导：
S=>0B=>00BB=>001B=>0011
?最右推导：
S=>0B=>00BB=>00B1=>0011
? 推导也可以用推导树表示为：
S
0 B
0 B B
1 1
? 实际上，一棵推导树代表了一个句型（或者句子）
的最左推导和最右推导过程以及其他所有的以任
意顺序进行推导的过程。
? 在推导树中，从根节点到一个叶节点（或者端末
节点）叫一条路径，一条路径上的非终结符的个
数，叫做该路径的长度。最大的路径长度叫做该
推导树的高度。
? 定义 3-28 推导树的子树的定义,
? 在一棵推导树 T中，以任意一个非终结符 A为根，连同它
的所有后继节点（直接的节点和非直接的节点，即它的
所有子孙,并且子孙的个数 >1），构成一棵子树，称之
为推导树 T的 A-子树。
? 推导树本身就是树 T最大的一棵子树；即 S-子树。
? 注意：
? 一个非终结符本身不是一棵子树。
对于推导树：
S
0 B
0 B B
1 1
? 共有 4棵子树：除它自身外，还有
B B B
1 1 0 B B
1 1
? 3.4 空串定理
? 定理 3-29 消除空串产生式
? G是一个上下文无关文法，存在一般的空
串产生式 A→ε,若 ε!∈ L(G)，则存在另一
个上下文无关文法 G1，使得：
? ⑴ L(G)=L(G1)；
? ⑵ G1中没有任何空串产生式；
?证明,
?因为 ε!∈ L(G)，对于 C∈ V，考虑它的
所有产生式 C→w （ w不为空串 ε），
如果 w中有非终结符 A1,A2,… Ak，
B1,B2,… Bj，对于 Ai，
? 1≤i≤k有 Ai → ε ；
?首先，将 C→w 改造为 C→w ’，其中 w’
是通过 0步,1步,… k步删除 w中的 Ai
而得到的,w’共有 2k个。
?最后，去掉所有的空串产生式（包括
在改造 w的过程中引入的空串产生式，
如 C→A1,则改造为 C→A1|ε ；引入
了 C→ε ），去掉无用的非终结符就得
到 G1。
?再考虑 G产生串 β的推导树 T，如
果 β的推导中使用了空串产生式，
则树 T中有以 ε为标志的叶节点，
删除树 T中的所有产生 ε的子树，
得到树 T1，而它刚好是文法 G1产
生串 β的推导树，所以，
L(G)=L(G1)。证毕。
? 例如：
? 文法,改造成 G’：
? S→ABCD S→ACD
? C→RS C→S
? B→ε A→a
? A→a D→d
? D→d S→d
? R→ε
? S→d
? 它们产生相同的语言 L。
定理 3-30 空串定理
? G是一个无关文法，存在一般的空串产生式 A→ε,
则存在另一个无关文法 G′使得：
? ⑴ L(G)=L(G′)；
? ⑵ 若 ε!∈ (G)，则 G′中没有任何空串产生式；
? ⑶ 若 ε∈ L(G)，则 G′中有一个空串产生式,S′→ε,
且 S′不出现在 G′的其它任何产生式的右边；（ S′
是 G′开始符号）。
? 证明：
? 如果 ε!∈ L(G)，先消除文法 G中的所有空
串产生式，得到 G’。
? 假设 ε∈ L(G)，则要增加新的开始符号 S’
和两个产生式
? S’→S, S’→ε ；再按上述方法得到 G’。
? 证毕。
?根据文法的定义,G’是一个无
关文法。也是一个相关文法,所
以,任意一个无关语言也是一个
相关语言。
?文法间关系：交叉
?语言间关系：包含
? 3.5 无关语言的泵浦 (pumping)定理
? 推导树有一个性质：
推导树的性质
?假设推导树 T是终结符串 z的推导树,
并且假设在树 T的某个路径上非终结
符 A出现了两次 ；
?（ 该文法是递归的文法 ）
?例如：
推导树的性质一
S
u A y
Av x
w
推导树的性质一
?该推导树产生串 z=uvwxy，由
于文法是上下文无关的文法,
在推导时可以用下面的 A代替
上面的 A，则得到另一棵推导
树：
推导树的性质一
S
u A y
w
推导树的性质一
?它推导出串 uwy=uv0wx0y；
?同样，在推导时可以用上面
的 A代替下面的 A，并做任意
多次后，则得到另一棵推导
树,
推导树的性质一
S
u A y
A
v x
Av x
推导树的性质一
?它推导出串 uvnwxny。
w
A
推导树的性质二
? 定理 3-13 给定上下文无关文法 G，假设文法中
的产生式的右边最多有 m个符号，令 T是串
w∈ L(G)的一棵推导树，如果 T中的没有路径的
长度大于 j，则 |w|≤mj。
? 证明：
? 使用归纳法证明：若对于以任意非终结符为根，
高度 ≤j的推导树 T，结论成立。
? 基础：当 j=1时,T代表单个产生式的使用，所以
串的长度小于等于 m。
? 假设：对于以任意非终结符为根，高度 ≤j的推导树 T，结
论成立；
? 归纳：令 T是以非终结符 A为根，高度为 j+1的树，假定
树根使用的产生式是 A→v,而 v中的每个符号至多产生
一个高度为 j的树，根据假设，每个子树至多产生一个长
度为 mj的串（即 v中的每个符号都是非终结符，且它们
都使用最长的产生式进行推导），由于 |v|≤m，所以，树
T产生的串的长度
? ≤mj+ mj + mj … + mj (共 |v|个 ) ≤m * mj = mj+1 。
?利用推导树的上述两个性质，可以得
到泵浦引理。
? 定理 3-14 泵浦 (pumping)引理（或 uvwxy定理）。
? 给定上下文无关语言 L，则存在两个仅依赖于语言 L的常
数 p和 q；使得：
? 如果 z是语言 L中的串，且 |z|>p；则 z可以写成 uvwxy的形
式，并且满足：
? ⑴ |vwx|≤q；
? ⑵ v和 x至多有一个为空；
? ⑶对所有的 i≥0，串 uviwxiy都属于 L。
? 泵浦引理也可以直接称为泵引理。
? 若 G是产生语言 L的上下文无关文法,m是 G中最长
产生式右边的符号个数,k是文法 G中非终结符的
个数；令 p=mk,如果 z是语言 L中的串，且
|z|>p，根据定理 5，在 z的推导树 T中，一定有某
个路径的长度大于或等于 k+1，而文法 G仅有 k个
非终结符，则在这条路径上至少有一个非终结符
出现两次。令 A是树 T中最低的重复的非终结符，
则 A的下面不再包含重复的非终结符。
? 故以上面的 A为根的树的高度至多为 k+1；这个子
树产生串 vwx,根据定理 3-13,|vwx| ≤m k+1,令
q= mk+1,则 |vwx|≤ q；
? 用下面的 A代替上面的 A,得到串 vwx=uv0wx0y的
推导, 用上面的 A代替下面的 A（ 进行 i次 ）,
得到串 uviwxiy的推导, 所以, 对所有的 i≥ 0，
串 uviwxiy属于 L。
? 下面证明 v和 x至多有一个为空, 即不能同时为空 。
因为若 v=x=ε, 由下面的 A代替上面的 A,仍得到
串 z的推导, 但路径的长度缩短了 。 如果每个有
重复非终结符的路径都如此, 那么推导出串 z的
树的高度可能小于 k+1；这与假设是矛盾的 。 所
以, v和 x不能同时为空 。 证毕 。
? 利用泵浦引理, 可以证明某些语言不是上下文无
关的语言, 即用反证法证明语言不满足泵浦引理 。
? 例 3-33 语言 {anbncn|n>0}不是上下文无关的语言。
? 证明：
? 假设该语言是上下文无关的语言，则存在两个常数 p和 q；
使得泵浦引理成立。考虑串 arbrcr,r>p，且 r>q； 则
|arbrcr|=3r>p；根据泵浦引理，串 arbrcr可以写成 uvwxy，
且 |vwx|≤q；由于 r>q；所以串 vwx只能在
? ① a串中或者 b串中或者 c串中，即 vwx只能包含字母 a或
者 b或者 c；
? ② a,b串中或者 b,c串中，即 vwx只能包含字母 a和 b或
者 b和 c；
? 否则,|vwx|>r>q。
? 也就是说，串 vwx中最多包含两个字母，所以串
uviwxiy（ i>1）中只有最多两个终结符的数目在
增加，而不能使 a,b和 c的数目相等，所以串
uviwxiy （ i>1）不在语言 { anbncn |n>0}中，与
泵浦引理矛盾，所以假设不成立。语言 { anbncn
|n>0}不是上下文无关语言。证毕。
? 3.6 短语
? 定义 3-12 短语的定义
? 如果 αβγ是上下文无关文法 G的一个句型，若有
S=>*αAγ，并且有 A=>+β，则称 β是句型 αβγ关于
非终结符 A的一个短语（或者简称 β是句型 αβγ的
一个短语；特别地，若 A=>β，则 β是句型 αβγ的
一个直接短语。句型最左边的直接短语，就是句
柄。（注意：一个句型或者句子的短语是该句型
或者句子的一个子串）。
? 根据定义，句型 αβγ本身就是 αβγ关于开始符号 S
的一个短语。
? 利用子树的概念，可以方便地理解短语的概念。
在句型 αβγ的推导树中，若 β是 A-子树产生的串，
则 β就是句型 αβγ关于非终结符 A的短语，如果子
树只有父子两代，则 β就是直接短语。最左边的
仅有父子两代的子树产生的直接短语就是句柄。
? 注意：
? 对于文法 G的一个给定的句型（或者句子），可
以有多个短语，多个直接短语，只有一个句柄。
在指明短语（直接短语，句柄）时，一定要指明
它是哪一个句型（或句子）的短语（直接短语，
句柄）。
?定义 3-13 素短语的定义
?素短语是一个短语，至少包含一个终
结符，并且除它自身以外，不再含有
任何更小的素短语。最左素短语是指
句型（或句子）最左边的素短语。
? 例 3-41 文法
? E→E+T
? E→T
? T→T*F
? T→F
? F→ （ E）
? F→2
? 对于句型 F+2*F，
? 短语,F,2,2*F,F+2*F
? 直接短语,F,2
? 句柄,F
? 素短语,2
? 最左素短语,2
? 3.7 形式语言与高级计算机程序设计语言
? 对于某种高级计算机程序设计语言的学习，
首先要了解该语言的字母表，各类单词符
号的形成规定（即词法规则）。
? 程序设计语言的单词符号一般分为 5类：
? 保留字,标识符,运算符,常量,(分 )界符。
?标识符和常量可以有任意多个。
?保留字，运算符和 (分 )界符的个数是
规定好的（对一个具体的高级程序设计语言），是有限的。
?标识符的形成可以使用文法,(字母开
始的字母、数字串 )
?I →L
?I →IL|ID
?L →a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|
s|t|u|v|w|x|y|z
?D →0|1|2|3|4|5||6||7|8||9
?正整型常量的形成可使用文法：
? C →D|EA
? A →AD|D
? E →1|2|3|4|5||6||7|8||9
? D →0|E
?对于某种高级计算机程序设计语言的
学习和介绍，还必须了解该语言的语
法单位（如：表达式，语句，子程序，
程序）的组成规定（即语法规则）。
? 语法规则对于高级程序设计语言的设计者，
实现者和使用者都是十分有用的：
? 语法规则表达了语言设计者的意图和设计
目标；
? 指导语言的使用者写出正确的程序；
? 指导语言的实现者 (编译程序的设计者 )编
写一个语法检查程序来识别所有合法的程
序。
? 语法规则可以用自然语言描述（如汉语，
英语等）；也可以用通用的形式化的方式 -
---文法来进行语法描述（特别是上下文无
关的文法）。而程序中的各个语法单位就
是文法所产生的句子。
? 定义 3-43 二义性文法的定义
? 一个文法 G是二义性的，如果 L(G)中的某个串 x
有两棵不同的推导树，即串 x有两种不同的最左
推导或两种不同的最右推导；否则，文法 G是非
二义的文法。
? 定义 3-44 二义性语言的定义
? 对于一个语言 L，如果产生该语言的所有文法都
是二义性的文法，则 L是二义性的语言。
? 实际上，语言的二义性是不可判定的。二
义性的语言也是没有什么实际意义的。
? 绝大多数的程序设计语言的语法规定可以
用上下文无关文法进行描述。
? 例 基本 PASCAL的语法结构：
? G=(∑, V,C,P)；
? 其中：
? ∑ ={begin,end,pred,succ,,=,<>，
while,do,；, (,),0,x,y}
? V={C,S,S1,S2,A,W,U,T}
? C是开始符号
?
? P={ C→begin S1 end
? S1→SS 2
? S2→ ； S1|ε
? S→A|W|C
? A→V, =T
? T→pred(V)|succ(V)| 0
? W→while V<>V do S
? V→x|y
? }
或
? C→begin S1 end
? S1→S| S ； S1
? S→A|W|C
? A→V, =T
? T→pred(V)|succ(V)| 0
? W→while V<>V do S
? V→x|y
? 该文法产生的一个基本语法单位为：
? begin
? y,=0；
? while x<>y do
? y,=succ(y)
? end
? (文法中没有考虑回车和换行 )
? 3.8 形式语言与自然语言
? 无关文法也可以用来描述自然语言（例如对英
语）。
? 使用下列符号：
? S 代表语句 ;NP代表名词短语 ;VP代表动词短语
? Adj代表形容词； Det代表冠词； N代表名词
? V代表动词； Prep代表介词；
? A代表形容词短语； PP代表介词短语
?可以有下列文法：
?S→NP VP
?NP→Det N|Det A N
?A→Adj A|Adj
?VP→Vbe PP
?PP→Prep NP
?Vbe→am|is|are
?Det→a|an|the
?Prep→on|in|for| ……
? V→play|go| ……
? N →boy|girl| ……
? Adj→small|big|high| ……
?对于语句：
?The big red ball is on the table
?推导树 P52图 3-13。
3.9基本的语法分析方法
? 对给定的上下文无关文法 G=（ ∑,V,S，
P）及符号串 w∈ ∑*，语法分析就是判断
串 w是否是文法 G能产生的合法的句子。
即是否 S=>*w 成立?
?对于计算机程序设计语言和使用
该语言编写的程序而言，语法分
析的任务就是要判断程序中的各
个语句是否是合法的语句，进而
判断整个程序是否合法。这也是
形式语言中要研究的一个重要方
面。
? 基本的语法分析方法有两种：
? ⑴自上（顶）而下法
? 从文法的开始符号（顶）出发，能否找到一个最左推导
序列推导出 w（下），即 S=>+w；或者从根节点 S开始，
是否能向下构造一棵推导树，能产生串 w；
? ⑵ 自下（底）而上法：
? 与自上而下分析法的推导序列相反，从符号串 w(底 )出发
寻找一个归约序列，逐步对可归约串向上进行归约，直
到文法的开始符号 S（顶）。
? 例 3-46 对于算术表达式的文法（ E是开始
符号，文法表示出了运算符的优先级）
? E→E+T|T
? T→T*F|F
? F→(E)|2
? 串 2+2*2是否是文法的合法的句子呢？
? 自上而下法：
? 最左推导：
?
E=>E+T=>T+T=>F+T=>2+T=>2+T*F=>2
+F*F=>2+2*F=>2+2*2
? 最右推导：
? E=>E+T=>E+T*F=>E+T*2=>E+F*2=>E+
2*2=>T+2*2=>F+2*2=>2+2*2
? 对于自下而上的分析法，遇到的最大问题是可归约串的
定义。若每次归约的是句柄，就是 LR分析法，该过程也
称之为最左归约或规范归约，实质上是最右推导的逆过
程（因此，最右推导也被称为规范推导）。若每次归约
的是最左素短语，就是算符优先分析法。
? 自下而上法：
? LR分析法：（画下划线的是该句型的句柄）
? 2+2*2<=F+2*2<=T+2*2<=E+2*2<=E+F*2<=E+T*2<=E
+T*F<=E+T<=E
? 算符优先分析法：（画下划线的是该句型的最左素短语）
? 2+2*2<=F+2*2<=F+F*2<=F+F*F<=F+T<=E
? 可以看出，算符优先分析法比 LR分析法要简明，原因是
它省略了单个符号的产生式（形如 A→B 的产生式）的归
约。其中,A,B∈ V。
? 实际上，算符优先分析法省略了产生式右边全是非终结
符的的产生式（形如 A→W 的产生式）的归约。 其中：
A∈ V,W∈ V+。
? 因为非终结符串不可能是素短语。
? 3.10 消除左递归
?在某些情况下,需要消除一个无关文法
中的左递归。
?递归的好处是产生无穷的语言，消除
左递归，只是将左递归改造为右递归。
?左递归包括直接的和间接的。
?3.10.1 消除直接左递归
?直接左递归的产生式形式为
? A→Av
?其中,A∈ V,v∈ (∑UV)+。
?递归的产生式可以产生串的任意次连
接，可以将左递归转换为右递归。
?假设文法 G的产生式形式为：
? A→Av|w,
?其中,A∈ V,v,w∈ (∑UV)*，
? 且 w不以 A开头，
?对于 A，有 A=>*wv*
?增加一个新的非终结符 B，构造无左
递归文法：
? A→wB|w
? B→vB|v
?它产生的串也为 wv*的形式；
?或者 A→wB
? B→vB|ε
? 实际上，消除了 ε产生式，就得
? A→wB|w
? B→vB|v
? 一般，产生式的形式为：
? A→Av1|Av2| … |Avn|w1|w2|… |wm
? 对于 A，有
? A=>*(w1|w2|… |wm)(v1|v2|… |vn)*
? 增加一个新的非终结符 B，构造无左递归
文法：
? A→w1B|w2B| … |wmB|w1|w2|… |wm
? B→v1B|v2B| … |vnB|v1|v2|… |vn
? 它产生的串也为
? (w1+w2+… wm)( v1+v2+… vn)*的形式；
? 某些文法可能没有直接左递归，但可能会
有间接左递归，
? 例如：文法 S→Aa
? A→Sb|b
? 虽然它的每个产生式都没有直接左递归，
但推导 S=>Aa=>Sba导致了左递归的出现，
这种左递归就称为间接左递归。
?3.10.2 消除间接左递归
?G是一个上下文无关文法，首先使用
空串定理；然后将文法 G中的所有非
终结符按任一顺序排列为 A1，
A2,… An，根据下列算法消除可能
存在的间接左递归。
? for i,=1 to n do
? begin
? for j,=1 to i-1 do
? begin
? 将形如 Ai→Ajw 的产生式改写为：
? Ai→v 1w|v2w|… |vkw ；
? (其中,v1,v2,…, vk是 Aj的侯选式 )
? end
? 消除 Ai产生式的直接左递归；
? end
?最后，删除多余（无用）的产生式，
即在从文法开始符号 S开始的任何推
导中都不会使用的非终结符（即无用
非终结符）对应的产生式；就可以得
到没有间接左递归的文法。
?该算法思想是将推导过程中可能出现
的左递归，在文法的产生式中就体现
出来，产生式的改写实际上是推导的
体现 ---用 Aj的侯选式将 Aj代替掉。
?为方便实现，将上述算法进行改写。
?G是一个上下文无关文法，将文法 G
中的所有非终结符按任一给定的顺序
排列为 A1,A2,… An，那么，文法
的每个产生式是 Ai→Ajw 的形式（对
于 Ai→aw 形式的产生式，不用考虑，
因为它不会导致左递归的出现），而 i
和 j的大小关系只可能有 3种情况：
? Ai→Ajw
? Ai,Aj∈ V
? 而 i和 j的大小关系只可能有 3种情况
? Ai→Ajw
? i<j 称该产生式是向上的，这类产生式不用替
代。
? Ai→Ajw
? i=j 该产生式是直接左递归的；消除直接左递归。
?Ai→Ajw
?i>j 称该产生式是向下的；这类产生
式需要替代，用 Aj的侯选式将 Aj替掉，
若出现了直接左递归，还需要将直接
左递归消除；
? 首先考虑非终结符 A1：
? A1→Ajw
1<j 产生式是向上的
1=j 该产生式是直接左递归的；消除直
接左递归
? 对于非终结符 A2:
? A2→Ajw
2<j 产生式是向上的
2=j 该产生式是直接左递归的；消除直接
左递归
2>j 该产生式是向下的；这类产生式需要
替代，用 Aj的侯选式将 Aj替掉，若出现了
直接左递归，还需要将直接左递归消除；
? …
? 对于非终结符 An：
? An→Ajw
n=j 消除直接左递归；
n>j 该产生式是向下的；这类产生式需要需要
替代，用 Aj的侯选将 Aj替换掉，若出现了直接左
递归，还需要将直接左递归消除；
? 最后，删除多余的产生式，得到的文法就没有了
左递归，包括直接和间接的左递归。
? 例 3-47 消除下列文法的左递归
? S→Qc│c
? Q→Rb│b
? R→Sa│a
? 解 1,按 S,Q,R排列,代入后
? S→Qc│c
? Q→Rb│b
? R→ Rbca│bca│ca│a
? 消除 R中的直接左递归
? R→ bcaR ’│caR’│aR’
? R’→ bcaR ’│?
? 文法产生的语言,(bca|ca|a)(bca)*bc|bc|c
? 解 2：按 R,Q,S排列,代入后
? R→Sa│a
? Q→Sab│ab│b
? S→Sabc│abc │bc│c
? 消除 S中的直接左递归
? S→abcS ’│bcS’│cS’
? S’→abcS ’│?
? 文法产生的语言,(abc|bc|c)(abc)*
? 3.11 上下文无关文法的另一种表示
? 文法的存在另外一种表示方法：
? 使用 {α}表示 α可任意重复 0次至 n次；即闭
包运算 α* ；
? 使用 [α]表示 α的出现可有可无 (等价于 α│ε)
? 左递归的产生式
? A→a|b|Aw
? 改写成：
? p→(a|b){w}
? 右左递归的产生式
? p→a|b|wA
? 改写成：
? p→{w}(a|b)
? 例 3-48 标识符可定义为：
? I→L
? I→IL
? I→ID
?
L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|
w|x|y|z
? D→0|1|2|3|4|5|6|7|8|9
? 也可以定义为：
? I→L{L|D}
? L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|
w|x|y|z
? D→0|1|2|3|4|5|6|7|8|9
? 例 3-49 实数可定义为
? decimal→ [sign]integer.{digit}[exponent]
? exponent→E[sign]integer
? integer→0|digit1{digit2}
? sign→+│ -
? digit1→1|2|3|4|5|6|7|8|9
? digit2→0|digit1
? 其中,decimal,exponent,integer、
sign,digit1和 digit2代表非终结符。
?,,+,-,1,2,3,4,5,6,7,8和 9代
表终结符。
上下文无关文法与上下文无关语言
? 上下文无关文法的重要性：
? 拥有足够强的表达力来表示大多数程序设计语
言的语法
? 可以构造有效的分析算法来检验一个给定的字
符串是否是由某个上下文无关文法产生 。
? 上下文无关语言在实践中有重要意义：
? 1） 定义程序设计语言,
? BNF（ 巴克斯 -诺尔范式 ） ；
? 2） 描述文档格式,
? XML,HTML；
? 3） 使语法分析概念形式化；
? 4） 简化程序设计语言的翻译,
? 语法分析器的设计；
? 给定文法 G,如果对于 G中的任意产生式 ν→ω,
而 ν只是一个非终结符, 即 A→ω, A∈ V,
ω∈ (∑UV） *,则称文法 G为上下文无关文法 （ 简
称无关文法 ） 。 如果一个语言能由一个无关文法
产生, 则称这个语言是上下文无关语言 （ 简称无
关语言 ） 。
定义 3-1 线性的无关文法
?若无关文法 G=(∑,V,S,P)的
所有产生式都是下列形式之一：
?A→uBv 或 A →w ；
?其中,A,B∈ V； u,v∈ ∑+； w∈ ∑*。
?该文法称为线性的无关文法 。
?注意,u,v可以有一个为空串 ε。
?特别地,
如果 u=ε,称为左线性的 (无关 )文法；
如果 v=ε,称为右线性的 (无关 )文法 。
?从定义可以看出, 线性的无关文法是受
限制的无关文法；本身一定还是无关文
法 。
化简的上下文无关文法
?左线性文法和右线性文法是线性文法中
特殊的两类 。
? 定理 3-2 G=（ ∑,V,S,P） 是一个上下文
无关文法, 产生式的一般形式为 A→w, 其中：
w∈ （ ∑UV） *,
? 则存在另一个等价的线性的无关文法 G1,而
G1中产生式的形式为；
? A→a 或 A→aβb 。
? 其中, A∈ V； a,b∈ ∑U{ε}； β∈ V+。
?证明：
? 读者自己完成 。
? 定理 3-3 G=（ ∑,V,S,P） 是一个上下文
无关文法, 产生式的一般形式为 A→w, 其
中,w∈ （ ∑UV） *,则存在另一个等价的无
关文法 G1,而 G1中产生式的形式为；
? A→a 或 A→aB 或 A→aBC 。
? 其中,A,B,C∈ V； a∈ ∑{ε} 。
?证明,读者自己完成 。
3.1 消除无关文法中的无用非终结符号
? 定义 3-4 文法中的无用符号
?一个无关文法 G,符号 Y∈ V,如果不出
现在任何形如 S=>*uYv=>*uwv的推导
之中, 称 Y为文法 G的无用非终结符 。
?其中,u, w, v ∈ ∑*。
?反之, 一个无关文法 G,符号 Y∈ V,如
果能够出现在某个形如
S=>*uYv=>*uwv的推导之中, 称 Y为
文法 G的有用非终结符 。 其中,u,
w, v ∈ ∑*。
? 从定义可知：有用非终结符, 必须同时满
足两个条件
? (1) 从它开始推导, 能够产生终结符号串；
? (2) 它必须出现在某个句型中；
? 判断某个符号是有用非终结符, 就应该从
这两方面同时进行考虑 。
?有用非终结符的判断算法：
?略。
定义 3-7 无用的产生式
? 如果一个产生式中 （ 产生式的左边或右边 ） 包含
有无用的非终结符, 则该产生式就是无用的产生
式 。 可以将无用的产生式从文法中删除掉 。
? 问题 3-8 文法产生的语言是否为空？
? 一个无关文法 G,产生的语言为 L(G),而 L(G)是
否为空 （ 即空集 Ф）, 是可以判定的 。
? 注意：
? 一个语言包含有空串 ε 或语言本身就是 {ε },它
们都不是空集 Ф。
? 判定方法：
? ① 首先使用空串定理, 消除该无关文法中的所有
空串产生式, 如果还有 S→ ε, 则该文法产生的
语言不为空；
? (2)构造能产生终结符串的非终结符集合 N,如果
S ∈ N,则该文法产生的语言不为空 。 否则, 该
文法产生的语言为空 。
? 定理 3-11 已知产生一个非空语言的上下文无关
文法 G,则对于某个 A ∈ V,总有 A=>*w,且
w∈∑ *。
? 证明：
? 读者自行完成 。
? 定理 3-12 一个无关文法 G=(∑,V,S,P), 产生的语言为
L(G)。 如果 L(G)不为空, 则至少存在一个非终结符 A,而
它的产生式右边仅仅只包含终结符号或空串 ε 。
? 证明提示：
? 考虑产生串的推导过程中最后使用的产生式的特点 。
? 证明：
? 读者自行完成 。
? 定理 3-13 已知产生一个非空语言的上下文无关
文法 G=（ ∑, V,S,P）, 则能够构造一个等价
的无关文法 G1,对于任意 A ∈ V,总有一个推
导,S=>*w1Aw3=>*w1w2w3,且 w1,w2,w3 ∈∑ *。
? 证明：
? 读者自行完成 。
? 定理 3-14 已知产生一个非空语言的上下文无关
文法 G=(∑,V,S,P), 则文法中的每个非终结符都
是有用的；即：若 A∈V, 则 S=>*uAv=>*uwv
? 其中,u, w, v ∈∑ *。
? 证明：
? 读者自行完成。
? 问题 3-15 上下文无关语言 CFL是否有穷是否可
以判定？
? 上下文无关文法 CFG生成无穷个句子的原理是利
用递归的产生式，即
? S=>*uAy=>*uvAxy=>*… =>*uviAxiy=>*uviwxiy
? 根据着一原理可以判定上下文无关语言是否有穷 。
? 定义 3-16 可派生性图的定义
? 上下文无关文法 G=（ ∑, V,S,P）, 文法 G的可
派生性图是满足下列条件的有向图：
? (1)对于终结符或非终结符 X，图中有且仅有一个
标记为 X的顶点。
? (2)如果 A->X1X2… Xn,则图中存在从标记为 A的
顶点分别到标记为 X1,X2,…,Xn的顶点的弧 。
? (3)图中只有满足条件 (1)和 (2)的弧 。
? 可派生性图表示了 G中变量间的派生关系：从 A到
B有一条有向路表示 B出现在 A派生出的某个符号
串中 。
? 3.2 推广的化简上下文无关文法
? 上下文无关文法化简的目的：
限制产生式的格式而不降低文法生成句子的能力,
从而降低文法分析算法的复杂度 。
? 上下文无关文法化简的基本手段：
删除无用符号
删除单一产生式组
? 对于一个上下文无关文法 G,如果：
? ① 没有 A→A 形式的产生式；
? ② 每个非终结符 A都是有用的, 即：
? 有 S=>*α Aβ =>*α wβ ；
? 其中,α, w,β ∈∑ *；
? 则该文法是化简的上下文无关文法 。
? 对于任意的无关文法, 进行
? （ 1） 直接删除没有 A→A 形式的产生式
? 对于 A→A 形式的产生式, 该类产生式是递归的, 可以反
复利用任意多次, 但对于无穷语言的产生, 没有任何作
用 。 可以直接删除即可 。
? （ 2） 消除无关文法中的无用非终结符号
? 消除无关文法中的无用非终结符号后, 无关文法中的所
有非终结符号都是有用的 。
? 得到的文法是化简的上下文无关文法 。
? 定义 3-21 推广的简化上下文无关文法：
? 对于一个上下文无关文法 G,如果该文法中不存
在形如 A → B的产生式 （ A,B ∈ V ）,
? 则该文法是推广的化简上下文无关文法 。
? 定理 3-22 对于一个上下文无关文法 G,能够找
到一个等价的无关文法 G1,而 G1中不存在形如 A
→ B的单产生式 （ A,B ∈ V ） 。
? 证明思路：
? 对于某个推导过程：
S=>*α Aβ =>α Bβ =>α wIβ =>…
? 可简化为,S=>*α Aβ =>α wIβ =>…
? 即省略掉 A => B的推导 。
? 因此, 需要将 A→B 的产生式使用下面产生式进行
替换：
? A →w 1|w2|w3|… |wn
? 而 B →w 1|w2|w3|… |wn 是文法 G中关于 B的所有
产生式 。
?实际上, 就是将推导过程在产
生式中就体现出来 。
? 注意, 对于关于 B的产生式,
B →w 1|w2|w3|… |wn
需要保留, 不能删除 。 因为可能存在
? S=>α 1Bβ 1=>α 1wIβ 1=>…
? 的推导, 即该推导过程没有使用产生式 A → B。
思考：
? 能否将文法中的产生式右边的 A直接替换为 B，
然后将
? A→β 1|β2|β3|… |βm|B
? 替换为
? B→β 1|β2|β3|… |βm
? 这是不行的；因为可能产生多余的串 。
? A →α,而 B → β,如果 B →α,它将 B的功能
扩大了 (能够定义为 α和 β)。
? 例如：
? S → AB S → BB
? A →B|a B →a
? B →b B →b
? L为,{ab,bb} L为,{aa,ab,bb,ba}
3.3 推导树
?对于无关文法 G,如果串 ω能由该文
法产生, 则 ω的产生过程可以用推导
的办法表示, 即用符号, =>”表示,
也可以用推导树的办法表示 。
定义 3-23 推导树（语法分析树）
? 推导树是一棵有向无循环的图 。
? 树的节点是文法中的非终结符或者终结符, 如果
有空串产生式, 则 ε 也可以是树的节点, 树的根
节点是文法的开始符号 S； 如果推导使用了产生
式 A→a 1a2a3… an,其中 A是非终结符, ai是非终
结符或者是终结符；则 a1,a2,a3,…, an都是 A
的直接后继节点 （ A称为父节点, a1,a2,a3,…,
an称为子节点 ） ；
? 一个节点和它的直接后继节点之间用有向边连接
起来；
? 如果节点是终结符, 该节点称为叶子节点；
? 如果节点是非终结符, 该节点称为非叶子节点
（ 或称为分枝节点 ） ；
? 端末节点 (仅有入口, 没有出口的节点 )从左到右
的连接, 是该推导树产生的边缘 。
?注意：推导树是向下生长的。
?定理 3-24 设文法 G为无关文法，那么
S=>*α，当且仅当存在一棵以 α为边
缘的推导树。即文法和推导树都可以
产生串 α。
?证明,
?略。
?结论,端末节点从左到右的连接，就
是该推导树产生的句型。
?注意：
?推导树不仅可以表示句子的产生，也
可以表示句型的产生。
?思考：
?端末节点一定为终结符吗？
? 定义 3-24 直接子孙和子孙的定义：
? 在一个有向无循环的图 (树 )中，称满足下
列条件的节点 n为节点 m的直接子孙：有一
条有向边从节点 m出发进入节点 n。
? 如果有节点的序列,n1,n2,n3… nk，使
得 m=n1,n=nk，以及对于每一个 i,ni+1是
ni的一个直接子孙,则节点 n称为节点 m的子
孙。
?约定：
?每一个节点都是自己的子孙。
?一棵推导树 T中的每个节点
都是根节点 S的一个子孙。
?定义 3-25 推导树的另一个
定义
?无关文法 G=(∑,V,S,P)，若
一棵树满足下列条件，则称
之为文法的推导树：
?每个节点都有一个标记 (是
∑UV的一个符号或者是 ε)；
?根的标记为 S；
?若一个节点有多于 1个的子孙，
该节点标记的符号为非终结符号；
?如果节点 A的所有直接子孙，
从左到右的次序是标记为 A1，
A2,A3,…, Ak的节点，则
?A → A 1A2A3… Ak为文法 G的一
个产生式。
?实际上，存在产生句子的（完
整的）推导树，也存在产生句型的（不完整的）推导树。
?一棵推导树中，仅有一个子孙
的节点称为端末节点（该子孙就是自己）。
?定义 3-26 最左推导和最左推导的定
义
?无关文法 G，有产生式 A →β,对于一
步直接推导 α1Aα2=>α1βα2：
?若 α1∈ ∑*，则称之为一步最左推导；
?若 α2∈ ∑*，则称之为一步最右推导；
?对于文法 G和句型 w：
?如果产生 w的每一步推导都是最左推
导，则称产生 w的推导为最左推导；
?如果产生 w的每一步推导都是最右推
导，则称产生 w的推导为最右推导。
?最右推导还称为规范推导。
?一般，常使用
最左推导。
?例 3-27 文法 S→0B|1A
?A→0|0S|1AA
?B→1|1S|0BB
?对于串 0011的产生过程：
?最左推导：
S=>0B=>00BB=>001B=>0011
?最右推导：
S=>0B=>00BB=>00B1=>0011
? 推导也可以用推导树表示为：
S
0 B
0 B B
1 1
? 实际上，一棵推导树代表了一个句型（或者句子）
的最左推导和最右推导过程以及其他所有的以任
意顺序进行推导的过程。
? 在推导树中，从根节点到一个叶节点（或者端末
节点）叫一条路径，一条路径上的非终结符的个
数，叫做该路径的长度。最大的路径长度叫做该
推导树的高度。
? 定义 3-28 推导树的子树的定义,
? 在一棵推导树 T中，以任意一个非终结符 A为根，连同它
的所有后继节点（直接的节点和非直接的节点，即它的
所有子孙,并且子孙的个数 >1），构成一棵子树，称之
为推导树 T的 A-子树。
? 推导树本身就是树 T最大的一棵子树；即 S-子树。
? 注意：
? 一个非终结符本身不是一棵子树。
对于推导树：
S
0 B
0 B B
1 1
? 共有 4棵子树：除它自身外，还有
B B B
1 1 0 B B
1 1
? 3.4 空串定理
? 定理 3-29 消除空串产生式
? G是一个上下文无关文法，存在一般的空
串产生式 A→ε,若 ε!∈ L(G)，则存在另一
个上下文无关文法 G1，使得：
? ⑴ L(G)=L(G1)；
? ⑵ G1中没有任何空串产生式；
?证明,
?因为 ε!∈ L(G)，对于 C∈ V，考虑它的
所有产生式 C→w （ w不为空串 ε），
如果 w中有非终结符 A1,A2,… Ak，
B1,B2,… Bj，对于 Ai，
? 1≤i≤k有 Ai → ε ；
?首先，将 C→w 改造为 C→w ’，其中 w’
是通过 0步,1步,… k步删除 w中的 Ai
而得到的,w’共有 2k个。
?最后，去掉所有的空串产生式（包括
在改造 w的过程中引入的空串产生式，
如 C→A1,则改造为 C→A1|ε ；引入
了 C→ε ），去掉无用的非终结符就得
到 G1。
?再考虑 G产生串 β的推导树 T，如
果 β的推导中使用了空串产生式，
则树 T中有以 ε为标志的叶节点，
删除树 T中的所有产生 ε的子树，
得到树 T1，而它刚好是文法 G1产
生串 β的推导树，所以，
L(G)=L(G1)。证毕。
? 例如：
? 文法,改造成 G’：
? S→ABCD S→ACD
? C→RS C→S
? B→ε A→a
? A→a D→d
? D→d S→d
? R→ε
? S→d
? 它们产生相同的语言 L。
定理 3-30 空串定理
? G是一个无关文法，存在一般的空串产生式 A→ε,
则存在另一个无关文法 G′使得：
? ⑴ L(G)=L(G′)；
? ⑵ 若 ε!∈ (G)，则 G′中没有任何空串产生式；
? ⑶ 若 ε∈ L(G)，则 G′中有一个空串产生式,S′→ε,
且 S′不出现在 G′的其它任何产生式的右边；（ S′
是 G′开始符号）。
? 证明：
? 如果 ε!∈ L(G)，先消除文法 G中的所有空
串产生式，得到 G’。
? 假设 ε∈ L(G)，则要增加新的开始符号 S’
和两个产生式
? S’→S, S’→ε ；再按上述方法得到 G’。
? 证毕。
?根据文法的定义,G’是一个无
关文法。也是一个相关文法,所
以,任意一个无关语言也是一个
相关语言。
?文法间关系：交叉
?语言间关系：包含
? 3.5 无关语言的泵浦 (pumping)定理
? 推导树有一个性质：
推导树的性质
?假设推导树 T是终结符串 z的推导树,
并且假设在树 T的某个路径上非终结
符 A出现了两次 ；
?（ 该文法是递归的文法 ）
?例如：
推导树的性质一
S
u A y
Av x
w
推导树的性质一
?该推导树产生串 z=uvwxy，由
于文法是上下文无关的文法,
在推导时可以用下面的 A代替
上面的 A，则得到另一棵推导
树：
推导树的性质一
S
u A y
w
推导树的性质一
?它推导出串 uwy=uv0wx0y；
?同样，在推导时可以用上面
的 A代替下面的 A，并做任意
多次后，则得到另一棵推导
树,
推导树的性质一
S
u A y
A
v x
Av x
推导树的性质一
?它推导出串 uvnwxny。
w
A
推导树的性质二
? 定理 3-13 给定上下文无关文法 G，假设文法中
的产生式的右边最多有 m个符号，令 T是串
w∈ L(G)的一棵推导树，如果 T中的没有路径的
长度大于 j，则 |w|≤mj。
? 证明：
? 使用归纳法证明：若对于以任意非终结符为根，
高度 ≤j的推导树 T，结论成立。
? 基础：当 j=1时,T代表单个产生式的使用，所以
串的长度小于等于 m。
? 假设：对于以任意非终结符为根，高度 ≤j的推导树 T，结
论成立；
? 归纳：令 T是以非终结符 A为根，高度为 j+1的树，假定
树根使用的产生式是 A→v,而 v中的每个符号至多产生
一个高度为 j的树，根据假设，每个子树至多产生一个长
度为 mj的串（即 v中的每个符号都是非终结符，且它们
都使用最长的产生式进行推导），由于 |v|≤m，所以，树
T产生的串的长度
? ≤mj+ mj + mj … + mj (共 |v|个 ) ≤m * mj = mj+1 。
?利用推导树的上述两个性质，可以得
到泵浦引理。
? 定理 3-14 泵浦 (pumping)引理（或 uvwxy定理）。
? 给定上下文无关语言 L，则存在两个仅依赖于语言 L的常
数 p和 q；使得：
? 如果 z是语言 L中的串，且 |z|>p；则 z可以写成 uvwxy的形
式，并且满足：
? ⑴ |vwx|≤q；
? ⑵ v和 x至多有一个为空；
? ⑶对所有的 i≥0，串 uviwxiy都属于 L。
? 泵浦引理也可以直接称为泵引理。
? 若 G是产生语言 L的上下文无关文法,m是 G中最长
产生式右边的符号个数,k是文法 G中非终结符的
个数；令 p=mk,如果 z是语言 L中的串，且
|z|>p，根据定理 5，在 z的推导树 T中，一定有某
个路径的长度大于或等于 k+1，而文法 G仅有 k个
非终结符，则在这条路径上至少有一个非终结符
出现两次。令 A是树 T中最低的重复的非终结符，
则 A的下面不再包含重复的非终结符。
? 故以上面的 A为根的树的高度至多为 k+1；这个子
树产生串 vwx,根据定理 3-13,|vwx| ≤m k+1,令
q= mk+1,则 |vwx|≤ q；
? 用下面的 A代替上面的 A,得到串 vwx=uv0wx0y的
推导, 用上面的 A代替下面的 A（ 进行 i次 ）,
得到串 uviwxiy的推导, 所以, 对所有的 i≥ 0，
串 uviwxiy属于 L。
? 下面证明 v和 x至多有一个为空, 即不能同时为空 。
因为若 v=x=ε, 由下面的 A代替上面的 A,仍得到
串 z的推导, 但路径的长度缩短了 。 如果每个有
重复非终结符的路径都如此, 那么推导出串 z的
树的高度可能小于 k+1；这与假设是矛盾的 。 所
以, v和 x不能同时为空 。 证毕 。
? 利用泵浦引理, 可以证明某些语言不是上下文无
关的语言, 即用反证法证明语言不满足泵浦引理 。
? 例 3-33 语言 {anbncn|n>0}不是上下文无关的语言。
? 证明：
? 假设该语言是上下文无关的语言，则存在两个常数 p和 q；
使得泵浦引理成立。考虑串 arbrcr,r>p，且 r>q； 则
|arbrcr|=3r>p；根据泵浦引理，串 arbrcr可以写成 uvwxy，
且 |vwx|≤q；由于 r>q；所以串 vwx只能在
? ① a串中或者 b串中或者 c串中，即 vwx只能包含字母 a或
者 b或者 c；
? ② a,b串中或者 b,c串中，即 vwx只能包含字母 a和 b或
者 b和 c；
? 否则,|vwx|>r>q。
? 也就是说，串 vwx中最多包含两个字母，所以串
uviwxiy（ i>1）中只有最多两个终结符的数目在
增加，而不能使 a,b和 c的数目相等，所以串
uviwxiy （ i>1）不在语言 { anbncn |n>0}中，与
泵浦引理矛盾，所以假设不成立。语言 { anbncn
|n>0}不是上下文无关语言。证毕。
? 3.6 短语
? 定义 3-12 短语的定义
? 如果 αβγ是上下文无关文法 G的一个句型，若有
S=>*αAγ，并且有 A=>+β，则称 β是句型 αβγ关于
非终结符 A的一个短语（或者简称 β是句型 αβγ的
一个短语；特别地，若 A=>β，则 β是句型 αβγ的
一个直接短语。句型最左边的直接短语，就是句
柄。（注意：一个句型或者句子的短语是该句型
或者句子的一个子串）。
? 根据定义，句型 αβγ本身就是 αβγ关于开始符号 S
的一个短语。
? 利用子树的概念，可以方便地理解短语的概念。
在句型 αβγ的推导树中，若 β是 A-子树产生的串，
则 β就是句型 αβγ关于非终结符 A的短语，如果子
树只有父子两代，则 β就是直接短语。最左边的
仅有父子两代的子树产生的直接短语就是句柄。
? 注意：
? 对于文法 G的一个给定的句型（或者句子），可
以有多个短语，多个直接短语，只有一个句柄。
在指明短语（直接短语，句柄）时，一定要指明
它是哪一个句型（或句子）的短语（直接短语，
句柄）。
?定义 3-13 素短语的定义
?素短语是一个短语，至少包含一个终
结符，并且除它自身以外，不再含有
任何更小的素短语。最左素短语是指
句型（或句子）最左边的素短语。
? 例 3-41 文法
? E→E+T
? E→T
? T→T*F
? T→F
? F→ （ E）
? F→2
? 对于句型 F+2*F，
? 短语,F,2,2*F,F+2*F
? 直接短语,F,2
? 句柄,F
? 素短语,2
? 最左素短语,2
? 3.7 形式语言与高级计算机程序设计语言
? 对于某种高级计算机程序设计语言的学习，
首先要了解该语言的字母表，各类单词符
号的形成规定（即词法规则）。
? 程序设计语言的单词符号一般分为 5类：
? 保留字,标识符,运算符,常量,(分 )界符。
?标识符和常量可以有任意多个。
?保留字，运算符和 (分 )界符的个数是
规定好的（对一个具体的高级程序设计语言），是有限的。
?标识符的形成可以使用文法,(字母开
始的字母、数字串 )
?I →L
?I →IL|ID
?L →a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|
s|t|u|v|w|x|y|z
?D →0|1|2|3|4|5||6||7|8||9
?正整型常量的形成可使用文法：
? C →D|EA
? A →AD|D
? E →1|2|3|4|5||6||7|8||9
? D →0|E
?对于某种高级计算机程序设计语言的
学习和介绍，还必须了解该语言的语
法单位（如：表达式，语句，子程序，
程序）的组成规定（即语法规则）。
? 语法规则对于高级程序设计语言的设计者，
实现者和使用者都是十分有用的：
? 语法规则表达了语言设计者的意图和设计
目标；
? 指导语言的使用者写出正确的程序；
? 指导语言的实现者 (编译程序的设计者 )编
写一个语法检查程序来识别所有合法的程
序。
? 语法规则可以用自然语言描述（如汉语，
英语等）；也可以用通用的形式化的方式 -
---文法来进行语法描述（特别是上下文无
关的文法）。而程序中的各个语法单位就
是文法所产生的句子。
? 定义 3-43 二义性文法的定义
? 一个文法 G是二义性的，如果 L(G)中的某个串 x
有两棵不同的推导树，即串 x有两种不同的最左
推导或两种不同的最右推导；否则，文法 G是非
二义的文法。
? 定义 3-44 二义性语言的定义
? 对于一个语言 L，如果产生该语言的所有文法都
是二义性的文法，则 L是二义性的语言。
? 实际上，语言的二义性是不可判定的。二
义性的语言也是没有什么实际意义的。
? 绝大多数的程序设计语言的语法规定可以
用上下文无关文法进行描述。
? 例 基本 PASCAL的语法结构：
? G=(∑, V,C,P)；
? 其中：
? ∑ ={begin,end,pred,succ,,=,<>，
while,do,；, (,),0,x,y}
? V={C,S,S1,S2,A,W,U,T}
? C是开始符号
?
? P={ C→begin S1 end
? S1→SS 2
? S2→ ； S1|ε
? S→A|W|C
? A→V, =T
? T→pred(V)|succ(V)| 0
? W→while V<>V do S
? V→x|y
? }
或
? C→begin S1 end
? S1→S| S ； S1
? S→A|W|C
? A→V, =T
? T→pred(V)|succ(V)| 0
? W→while V<>V do S
? V→x|y
? 该文法产生的一个基本语法单位为：
? begin
? y,=0；
? while x<>y do
? y,=succ(y)
? end
? (文法中没有考虑回车和换行 )
? 3.8 形式语言与自然语言
? 无关文法也可以用来描述自然语言（例如对英
语）。
? 使用下列符号：
? S 代表语句 ;NP代表名词短语 ;VP代表动词短语
? Adj代表形容词； Det代表冠词； N代表名词
? V代表动词； Prep代表介词；
? A代表形容词短语； PP代表介词短语
?可以有下列文法：
?S→NP VP
?NP→Det N|Det A N
?A→Adj A|Adj
?VP→Vbe PP
?PP→Prep NP
?Vbe→am|is|are
?Det→a|an|the
?Prep→on|in|for| ……
? V→play|go| ……
? N →boy|girl| ……
? Adj→small|big|high| ……
?对于语句：
?The big red ball is on the table
?推导树 P52图 3-13。
3.9基本的语法分析方法
? 对给定的上下文无关文法 G=（ ∑,V,S，
P）及符号串 w∈ ∑*，语法分析就是判断
串 w是否是文法 G能产生的合法的句子。
即是否 S=>*w 成立?
?对于计算机程序设计语言和使用
该语言编写的程序而言，语法分
析的任务就是要判断程序中的各
个语句是否是合法的语句，进而
判断整个程序是否合法。这也是
形式语言中要研究的一个重要方
面。
? 基本的语法分析方法有两种：
? ⑴自上（顶）而下法
? 从文法的开始符号（顶）出发，能否找到一个最左推导
序列推导出 w（下），即 S=>+w；或者从根节点 S开始，
是否能向下构造一棵推导树，能产生串 w；
? ⑵ 自下（底）而上法：
? 与自上而下分析法的推导序列相反，从符号串 w(底 )出发
寻找一个归约序列，逐步对可归约串向上进行归约，直
到文法的开始符号 S（顶）。
? 例 3-46 对于算术表达式的文法（ E是开始
符号，文法表示出了运算符的优先级）
? E→E+T|T
? T→T*F|F
? F→(E)|2
? 串 2+2*2是否是文法的合法的句子呢？
? 自上而下法：
? 最左推导：
?
E=>E+T=>T+T=>F+T=>2+T=>2+T*F=>2
+F*F=>2+2*F=>2+2*2
? 最右推导：
? E=>E+T=>E+T*F=>E+T*2=>E+F*2=>E+
2*2=>T+2*2=>F+2*2=>2+2*2
? 对于自下而上的分析法，遇到的最大问题是可归约串的
定义。若每次归约的是句柄，就是 LR分析法，该过程也
称之为最左归约或规范归约，实质上是最右推导的逆过
程（因此，最右推导也被称为规范推导）。若每次归约
的是最左素短语，就是算符优先分析法。
? 自下而上法：
? LR分析法：（画下划线的是该句型的句柄）
? 2+2*2<=F+2*2<=T+2*2<=E+2*2<=E+F*2<=E+T*2<=E
+T*F<=E+T<=E
? 算符优先分析法：（画下划线的是该句型的最左素短语）
? 2+2*2<=F+2*2<=F+F*2<=F+F*F<=F+T<=E
? 可以看出，算符优先分析法比 LR分析法要简明，原因是
它省略了单个符号的产生式（形如 A→B 的产生式）的归
约。其中,A,B∈ V。
? 实际上，算符优先分析法省略了产生式右边全是非终结
符的的产生式（形如 A→W 的产生式）的归约。 其中：
A∈ V,W∈ V+。
? 因为非终结符串不可能是素短语。
? 3.10 消除左递归
?在某些情况下,需要消除一个无关文法
中的左递归。
?递归的好处是产生无穷的语言，消除
左递归，只是将左递归改造为右递归。
?左递归包括直接的和间接的。
?3.10.1 消除直接左递归
?直接左递归的产生式形式为
? A→Av
?其中,A∈ V,v∈ (∑UV)+。
?递归的产生式可以产生串的任意次连
接，可以将左递归转换为右递归。
?假设文法 G的产生式形式为：
? A→Av|w,
?其中,A∈ V,v,w∈ (∑UV)*，
? 且 w不以 A开头，
?对于 A，有 A=>*wv*
?增加一个新的非终结符 B，构造无左
递归文法：
? A→wB|w
? B→vB|v
?它产生的串也为 wv*的形式；
?或者 A→wB
? B→vB|ε
? 实际上，消除了 ε产生式，就得
? A→wB|w
? B→vB|v
? 一般，产生式的形式为：
? A→Av1|Av2| … |Avn|w1|w2|… |wm
? 对于 A，有
? A=>*(w1|w2|… |wm)(v1|v2|… |vn)*
? 增加一个新的非终结符 B，构造无左递归
文法：
? A→w1B|w2B| … |wmB|w1|w2|… |wm
? B→v1B|v2B| … |vnB|v1|v2|… |vn
? 它产生的串也为
? (w1+w2+… wm)( v1+v2+… vn)*的形式；
? 某些文法可能没有直接左递归，但可能会
有间接左递归，
? 例如：文法 S→Aa
? A→Sb|b
? 虽然它的每个产生式都没有直接左递归，
但推导 S=>Aa=>Sba导致了左递归的出现，
这种左递归就称为间接左递归。
?3.10.2 消除间接左递归
?G是一个上下文无关文法，首先使用
空串定理；然后将文法 G中的所有非
终结符按任一顺序排列为 A1，
A2,… An，根据下列算法消除可能
存在的间接左递归。
? for i,=1 to n do
? begin
? for j,=1 to i-1 do
? begin
? 将形如 Ai→Ajw 的产生式改写为：
? Ai→v 1w|v2w|… |vkw ；
? (其中,v1,v2,…, vk是 Aj的侯选式 )
? end
? 消除 Ai产生式的直接左递归；
? end
?最后，删除多余（无用）的产生式，
即在从文法开始符号 S开始的任何推
导中都不会使用的非终结符（即无用
非终结符）对应的产生式；就可以得
到没有间接左递归的文法。
?该算法思想是将推导过程中可能出现
的左递归，在文法的产生式中就体现
出来，产生式的改写实际上是推导的
体现 ---用 Aj的侯选式将 Aj代替掉。
?为方便实现，将上述算法进行改写。
?G是一个上下文无关文法，将文法 G
中的所有非终结符按任一给定的顺序
排列为 A1,A2,… An，那么，文法
的每个产生式是 Ai→Ajw 的形式（对
于 Ai→aw 形式的产生式，不用考虑，
因为它不会导致左递归的出现），而 i
和 j的大小关系只可能有 3种情况：
? Ai→Ajw
? Ai,Aj∈ V
? 而 i和 j的大小关系只可能有 3种情况
? Ai→Ajw
? i<j 称该产生式是向上的，这类产生式不用替
代。
? Ai→Ajw
? i=j 该产生式是直接左递归的；消除直接左递归。
?Ai→Ajw
?i>j 称该产生式是向下的；这类产生
式需要替代，用 Aj的侯选式将 Aj替掉，
若出现了直接左递归，还需要将直接
左递归消除；
? 首先考虑非终结符 A1：
? A1→Ajw
1<j 产生式是向上的
1=j 该产生式是直接左递归的；消除直
接左递归
? 对于非终结符 A2:
? A2→Ajw
2<j 产生式是向上的
2=j 该产生式是直接左递归的；消除直接
左递归
2>j 该产生式是向下的；这类产生式需要
替代，用 Aj的侯选式将 Aj替掉，若出现了
直接左递归，还需要将直接左递归消除；
? …
? 对于非终结符 An：
? An→Ajw
n=j 消除直接左递归；
n>j 该产生式是向下的；这类产生式需要需要
替代，用 Aj的侯选将 Aj替换掉，若出现了直接左
递归，还需要将直接左递归消除；
? 最后，删除多余的产生式，得到的文法就没有了
左递归，包括直接和间接的左递归。
? 例 3-47 消除下列文法的左递归
? S→Qc│c
? Q→Rb│b
? R→Sa│a
? 解 1,按 S,Q,R排列,代入后
? S→Qc│c
? Q→Rb│b
? R→ Rbca│bca│ca│a
? 消除 R中的直接左递归
? R→ bcaR ’│caR’│aR’
? R’→ bcaR ’│?
? 文法产生的语言,(bca|ca|a)(bca)*bc|bc|c
? 解 2：按 R,Q,S排列,代入后
? R→Sa│a
? Q→Sab│ab│b
? S→Sabc│abc │bc│c
? 消除 S中的直接左递归
? S→abcS ’│bcS’│cS’
? S’→abcS ’│?
? 文法产生的语言,(abc|bc|c)(abc)*
? 3.11 上下文无关文法的另一种表示
? 文法的存在另外一种表示方法：
? 使用 {α}表示 α可任意重复 0次至 n次；即闭
包运算 α* ；
? 使用 [α]表示 α的出现可有可无 (等价于 α│ε)
? 左递归的产生式
? A→a|b|Aw
? 改写成：
? p→(a|b){w}
? 右左递归的产生式
? p→a|b|wA
? 改写成：
? p→{w}(a|b)
? 例 3-48 标识符可定义为：
? I→L
? I→IL
? I→ID
?
L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|
w|x|y|z
? D→0|1|2|3|4|5|6|7|8|9
? 也可以定义为：
? I→L{L|D}
? L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|
w|x|y|z
? D→0|1|2|3|4|5|6|7|8|9
? 例 3-49 实数可定义为
? decimal→ [sign]integer.{digit}[exponent]
? exponent→E[sign]integer
? integer→0|digit1{digit2}
? sign→+│ -
? digit1→1|2|3|4|5|6|7|8|9
? digit2→0|digit1
? 其中,decimal,exponent,integer、
sign,digit1和 digit2代表非终结符。
?,,+,-,1,2,3,4,5,6,7,8和 9代
表终结符。
