本章小结
N→SE | E S→SD | D E→0 | 2 | 4 | 6 | 8 | 10 D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
分析 因为对文法的 句子10有两棵不同的 语法树与之对应，所 以该文法是二义的
N E 10
N SE D0 1
本章小结
N→SE | E
从句型的语法树求
短语: (A((SaA)(b))) ((SaA)(b)) (SaA)
( S a A )( b )
直接短语：(SaA)、(b) 句柄：(SaA)
(b)
本章小结
4．文法二义性的判断 一个文法存在某个句子对应两棵不
同的语法树或对应两个不同的最左（最 右）推导，则该文法是二义性的。
本章小结
本章小结
例2 已知文法G[S]：S→(AS) | (b) A→(SaA) | (a)
试找出符号串(a)和(A((SaA)(b)))的短语﹑ 直接短语和句柄(如果有的话)。 分析 ∵ S(AS)((a)S)/ (a)
∴ 符号串(a))不是文法的句型，因此 它没有短语﹑直接短语和句柄。
本章小结
L2={ab,abb,abbb, …aabb,aabbb,aabbbb, … aaabbb, aabbbb，…}
P2: S→AB A→aAb | ab B→bB |ε
本章小结
例2. 给出语言 L1={a2n+1|n≥0} 的文法 分析 根据语言句子的结构特征，设计出相 应规则
L1={a, aaa, aaaaa, aaaaaaa, aaaaaaaaa，…}
第二章小结
本章重点介绍了语言的语法结构的形式描述、 语法树以及文法的二义性, 主要内容有：
1. 设计一个文法定义一个已知的语言 (1) 文法是一个四元组 G=(VN,VT, P, S)， 文法四大要素中，关键是一组规则, 它定义 （或描述）了一个语言的结构。
从文法定义可知, 文法对于程序设计者来 说，文法给出了语言的精确定义和描述。
本章小结
例5. 给出语言L={1n0m1m0n | n,m≥0}的 文法。
分析 根据语言句子的结构特征, 设计 出相应规则 L={ε,01,0011,…,10,1100,…,1010,100110,
110100,11001100…}
P : S → 1S0 | 0A1 | ε A → 0A1 | ε
本章小结
例2 文法G[N]为: N →ND | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(1) G[N]所生成的语言是什么？ (2) 给出句子0127的最左、最右推导。
本章小结
N →ND | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
E→E+T | E-T | T T→T*F | T/F | F F→(E) | i
证明 E+T*F是它的一个句型,指出这个句
型的短语﹑直接短语和句柄。
∵ EE+TE+T*F
画出该句型的语
∴ E+T*F是它的一个句型。法树: 短语: E+T*F、T*F
E
直接短语: T*F
E+ T
句柄:
T*F
T* F
S→(AS) | (b) A→(SaA) | (a) ∵S(AS)(A(AS))(A(A(b))) (A((SaA)(b)))
∴符号串(A((SaA)(b)))是文法的句型，画 出该句型的语法树如下图：
本章小结
S→(AS) | (b)
S
A→(SaA) | (a)
对于句型(A((SaA)(b)))
L(G[N])={α | α∈{0,1,2, …9}+} ={α | α为可带前导0的正整数} ={α | α为数字串}
最左推导: NNDNDDNDDDDDDD 0DDD01DD012D0127
最右推导: NNDN7ND7N27ND27 N127D1270127
本章小结
P1：A→aAa | a 或 P1': A→aB | a
B→aa | aBa
本章小结
例3. 给出语言L3={anbmck| n,m,k≥0}的文法 分析 根据语言句子的结构特征，设计出相 应规则 L3={ε,a,aa,aaa…,b,bb,bbb…,c,cc,ccc, …,
ab,abb, …,bc,bcc，…} P3: A→aA | bB | cC |ε
例3. 已知文法G[S]=( {A,B},{a,b,c,d}, P, S ) , 其中 P 为: S → AB
A → aAb | ab
B → cBd | cd 该文法 所生成的语言是什么？ 分析 ∵ SABaAbBa2Ab2B…
an-1Abn-1BanbnBanbncBd anbnc2Bd2 … anbncm-1Bdn-1anbncmdm ∴ L(G[S])={anbncmdm | n ,m≥1 }
B→bB | cC |ε C→cC |ε
本章小结
例4. 写一个 文法,使其语言是正偶数的集合,每 个偶数不以0开头。
分析 不以0开头的偶数集合中串的结构特征: L4={2,4,6,8,10,12,14,16,18,20,22,24,26,…} P4: N→E′ | AE
A→D | AD′ D→1 | 2 | 3 | …| 9 D'→0 | 1 | 2 | 3 |…| 9 E→0 | 2 | 4 | 6 | 8 E'→2 | 4 | 6 | 8
S→SD | D
E→0 | 2 | 4 | 6 | 8 | 10
D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
该文法所描述的语言是所有无符号偶数
的集合(可以0开头)。
改写后的文法G‘[S]为:
N→SE | E
S→SD | D
E→0 | 2 | 4 | 6 | 8
D→0 | 1 | 2 | 3 | 4 | 5| 6 | 7 | 8 | 9
本章小结
(2) 分析已知语言句子的结构特征, 设计 出相应的一组规则，但不唯一。
(3) 设计的文法必须能定义已知的语言, 不能超出或缩小所定义语言的范围。
(4) 若语言是无穷集合, 设计该语言的文 法一定是递归的。
本章小结
例1. 给出语言 L2={an bm| m≥n≥1} 的文法 分析 根据语言句子的结构特征，设计出相 应规则Fra bibliotek本章小结
3. 求句型的短语、直接短语和句柄 (1) 短语、直接短语和句柄是对某句 型而言的。 (2) 短语总是句型的某个子串，它对应 子树未端结点形成的符号串。 (3) 直接短语是某条规则右部，它对应 简单子树未端结点形成的符号串。
(4) 最左边的直接短语是句柄。
本章小结
例1 已知文 法G[E]：
本章小结
例6. 给出语言L={ WaWt | W∈{0|1}* }， 其中 Wt表示W的逆的文法。
分析 根据语言句子的结构特征，设计 出相应规则
W={ε,0, 1 ,01, 10, 00, 11, 101, 110, 100, 111, …} L={a, 0a0, 1a1, 01a10, 10a01, 00a00, 11a11,
例1 设有文法G[S]: S→iSeS| iS | i 试证明文法G[S]有二义性。
分析 因为对文法的句子 iiiei 有如下两 棵不同的语法树与之对应，所以该文法 是二义的
本章小结
S→iSeS| iS | i
句子 iiiei 对应下面两颗语法树：
S
S
本章小结
例2 设有文法G[N]:
N→SE | E S→SD | D E→0 | 2 | 4 | 6 | 8 | 10 D→0| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 1. 试证明文法G[N]有二义性。 2. 此文法所描述的语言是什么？ 3. 试写出另一文法G'使L(G')=L(G)且 G'是无二义性的。
101a101, 110a011, 100a001, …}
P : S → a | 0S0 | 1S1
本章小结
2. 已知一个文法，确定该文法所定义的 语言。
(1) 文法所定义的语言 L(G[S])={x|S * x且x∈VT*}
(2) 给定一个文法，可根据语言和推导定 义推导出文法的句子，从而确定出该文法 所定义的语言。
本章小结
(3) 语言可用 ①自然语言描述。 例如, L={x|x∈{a,b}+且x中a,b个数相同} ②式子描述。例如 L={a2nbb | n≥0}。 ③正规式描述。
本章小结
例1 文法G[A]=({A},{a,b},{A→bA | a}, A) 所生成的语言是什么？
分析 ∵ AbAbbAbbbA…bnAbna ∴ L(G[A])={ bna | n≥0 }
本章完