1
第四章 文法和语言为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）
形式 工具 --“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述
2
本章内容文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法 的句型分析有关文法实用中的一些说明
3
文法和语言的形式定义如何来描述一种语言？
如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
生成方式 （文法）：语言中的每个句子可以用严格 定义的规则来构造。
识别方式 （自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。
4
文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造文法的定义推导的概念句型、句子和语言的定义,
5
文法 定义文法 G定义为四元组 (VN,VT,P,S )其中
VN:非终结符号 (或语法实体，或变量 )集；
VT:终结符号集；
P,规则的集合；
VN,VT和 P是 非空有穷集。
S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。
VN和 VT不含公共的元素，即 VN ∩ VT = φ
用 V表示 VN ∪ VT,称为文法 G的字母表或字汇表规则,也称 重写规则,产生式 或 生成式,是形如
→?或?∷ =?的 (?,?)有序对，其中?是字母表 V
的正闭包 V+中的一个符号,?是 V*中的一个符号。
称为规则的左部,? 称作规则的右部。
6
文法的定义例 文法 G=（ VN,VT,P,S）
VN = { S },VT ={ 0,1 }
P={ S→ 0S1,S→ 01 }
S为开始符号例 文法 G=（ VN,VT,P,S）
VN ={标识符，字母，数字 }
VT ={a,b,c,…x,y,z,0,1,…,9}
P={<标识符 >→ <字母 >
<标识符 >→ <标识符 ><字母 >
<标识符 >→ <标识符 ><数字 >
<字母 >→ a
…
<字母 >→z
<数字 >→0
…
<数字 >→9 }
S=<标识符 >
8
文法的写法 元 符号,→ ∷= | < >
习惯 大写字母表示非终结符 小写字母表示终结符
(1) G,S→aA b
A→ab
A→aA b
A→ ε
(2) G[S],A→ab
A→aA b
A→ ε
S→aS b
(3) G[S]:A→ab |aA b |ε
S→aS b
9
推导的定义直接推导,?”
α → β 是文法 G的产生式，若有 v,w满足：
v=γ α δ,w= γ β δ,其中 γ ∈V *,δ ∈V *
则称 v直接 推导 到 w,记作 v? w
也称 w直接 归约 到 v
例,G,S→ 0S1,S→ 01
0S1?00S11
00S11?000S111
000S111?00001111
S?0S1
10
推导
<程序 >?<分程序 >,
(<程序 >? <分程序 >,)
<分程序 >,? <变量说明部分 > <语句 >,
(<分程序 >? <变量说明部分 > <语句 >)
VAR<标识符 >;BEGIN READ(<标识符 >)END,?
VAR A;BEGIN READ(<标识符 > ) END.
(<标识符 >?A)
VAR A;BEGIN READ(<标识符 > ) END,?
VAR A;BEGIN READ( A) END.
(<标识符 >?A)
11
推导的定义若存在 v =w0?w1?..,?wn=w,(n>0)
则记为 v =>+ w，称作 v推导出 w，或 w归约到 v
若有 v =>+ w 或 v=w,则记为 v =>* w
12
例,G,S→ 0S1,S→ 01
0S1?00S11
00S11?000S111
000S111?00001111
S?0S1?00S11?000S111?00001111
S =>+ 00001111
S =>* S 00S11 =>* 00S11
13
句型、句子的定义
句型有文法 G，若 S =>* x，则称 x是文法 G的句型。
句子有文法 G，若 S =>* x，且 x∈V T*，则称 x是文法 G的句子。
例,G,S→ 0S1,S→ 01
S?0S1?00S11?000S111?00001111
G的句型 S,0S1,00S11,000S111,00001111
G的句子 00001111,01
14
句型、句子例,G[E],E→E+T|T
T→T*F|F
F→(E)|a
E?E+T?T+T?F+T?a+T?a+T*F
a+F*F?a+a*F?a+a*a
句子：用符号 a,+,*,(和 )构成的算术表达式
15
(文法生成的 )语言的定义由文法 G生成的语言记为 L(G),它是文法 G的一切句子的集合,
L(G)={x|S =>* x，其中 S为文法的开始符号，且 x ∈V T*}
例,G,S→ 0S1,S→ 01
L(G)={0n1n|n≥ 1}
例 文法 G[S]：
（ 1） S→ aSBE
（ 2） S→ aBE
（ 3） EB→ BE
（ 4） aB→ ab
（ 5） bB→ bb
（ 6） bE→ be
（ 7） eE→ ee
L（ G） ={ anbnen | n≥ 1 }
G生成的每个串都在 L(G)中
L(G)中的每个串确实能被 G生成
17
文法的等价
若 L（ G1） =L（ G2），则称文法 G1和 G2是等价的。
如文法 G1[A],A→DB 与 G2[S],S→0S1 等价
A→DE S→01
E→AB
D→0
B→1
18
文法的类型通过对产生式施加不同的限制,Chomsky将文法分为四种类型：
0型文法：对任一产生式 α → β,都有
α ∈(V N∪V T)+,β ∈(V N∪V T)*
1型文法,对任一产生式 α → β,都有 |β |≥| α |，
仅仅 S→ ε 除外
2型文法,对任一产生式 α → β,都有 α ∈V N
3型文法,任一产生式 α → β 的形式都为 A→aB 或
A→a,其中 A∈V N,B∈V N,a∈V T *
19
文法的类型例,1型（上下文有关）文法文法 G[S],S→CD Ab→bA
C→aCA Ba→aB
C→bCB Bb→bB
AD→aD C→a
BD→bD D→b
Aa→bD
20
文法的类型例,2型（上下文无关）文法文法 G[S],S→AB
A→BS|0
B→SA|1
21
3型文法
G[S]：
S→0A|1B|0
A→0A|1B|0S
B→1B|1|0
G[I],I → lT
I → l
T → lT
T → dT
T → l
T → d
22
文法的类型
2型文法
1型文法
0型文法四类 文法 之间 的 逐级,包含,关系
3型文法
23
文法和语言
0型文法产生的语言称为 0型语言
1型文法或上下文有关文法（ CSG ） 产生的语言称为 1型语言 或上下文有关 语言（ CSL）
2型文法或上下文无关文法（ CFG ） 产生的语言称为 2型语言 或上下文无关 语言（ CF L ）
3型文法或正则（正规）文法（ RG ） 产生的语言称为 3型语言 正则（正规） 语言（ RL ）
24
文法和语言四种文法之间的关系 是将产生式做进一步限制而定义的。
语言之间的关系依次：有不是上下文有关语言的 0型语言，有不是上下文无关语言的
1型语言，有不是正则语言的上下文无关语言。
25
根据形式语言理论,文法和识别系统间有这样的关系
0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何 0型语言都是递归可枚举的
1型文法（上下文有关文法）：产生式的形式为 α 1Aα 2→ α 1βα2，即只有 A出现在 α 1
和 α 2的上下文中时，才允许 β 取代 A。其识别系统是线性界限自动机。
26
带 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an-1 an
有限控制器磁头任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述
27
2型文法（上下文无关文法 CFG）：产生式的形式为 A→ β,β 取代 A时与 A的上下文无关。其识别系统是不确定的下推自动机。
3型文法（正规文法 RG）：产生的语言是有穷自动机（ FA）所接受的集合
28
3型文法产生的语言是有穷自动机（ FA）所接受的集合,
定理 设 G=（ VN,VT,P,S）是 3型文法，则存在一个有穷自动机 M=(K,∑,f,A,Z),使得 L(M)=L(G)
有穷自动机 NFA M
· ∑= VT
· K= VN ∪{ N},N为一个新状态,它不在 VN中
· A=S
· Z={N}
·对 G中的形如 D→tB 的产生式,t为终结符或 ε,有 f(D,t)=B；
对 G中形如 D→t 的产生式,t为终结符或 ε,有 f(D,t)=N;
对 VT中的每一个 a,有 f(N,a)=φ
29
3型文法 和 有穷自动机（ FA）
G［Ｓ］：
S→aA|bB
A→bB|aD|a
B→aA|bD|b
D→aD|bD|a|b
B
A
S
a
a
a
b
b
b
a,b
D Z
a
b
a
b
30
3型文法 和 有穷自动机（ FA）
定理 已知一有穷自动机 M= (K,∑,f,A,Z),
存在有一个 3型文法 G = （ VN,VT,P,S）,使得 L(G)=L(M)
G 的定义：
· VT =∑ · VN= K
· S = A
·若 f(D,t)=B,则 D→tB 在 P中若 f(D,t)=B,且 B在 Z中，则 D→t 在 P中
31
3型文法 和 有穷自动机（ FA）
G［Ｓ］：
S→aA|bB
A→bB|aD|a
B→aA|bD|b
D→aD|bD|a|bDB
A
S
a
a a
b
b
a,b
b
32
正规文法和正规式对?上的正规式 r,存在一个 RG=(VN,VT,P,S)：
L(G)=L(r)
初始,VT=?,S? VN,生成正规产生式 S?r
(R.1) 对形如 A?r1r2的 正规产生式,A?r1B
B?r2
B?VN
(R.2)对形如 A?r?r1的 正规产生式,A?rB
A?r1
B?rB
B?r1 B?VN
(R.3)对形如 A?r1?r2的 正规产生式,A?r1
A? r2
不断应用 (R.x)做变换，直到每个产生式右端至多有一个 VN
33
例 r=a(a?d)?
(1) S?a(a?d)?
(2) S?aA A?(a?d)?
(3) A?(a?d)B
A
B?(a?d)B
B
G[s],
S?aA
A VT={a,d}
A?aB VN={S,A,B}
A?dB
B?aB
B?dB
B
34
正规文法和正规式对 G=(VN,VT,P,S),存在一个? =VT上的正规式 r,
L(r)=L(G)
A?xB,B?y 形成正规式 A=xy
A?xA?y 形成正规式 A=x?y
A?x?y 形成正规式 A=x?y
35
正规文法和正规式
G[s]:S?aA|a
A?aA?a?dA?d
A?(a?d)A?(a?d)
A?(a?d)?(a?d)
S=a(a?d)?(a?d)?a
=a((a?d)?(a?d))
=a((a?d))
R=a(a?d)?
36
上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构语法树 ---句型推导 的 直观表示
37
语法树 ---句型推导 的 直观表示 (句型、推导 )
G[E],E→E+T|T
T→T*F|F
F→(E)|a
E?E+T?T+T?F+T?a+T?a+T*F
a+F*F?a+a*F?a+a*a
E?E+T?E+T*F?E+T*a?E+F*a?E+a*a
T+a*a?F+a*a?a+a*a
E?E+T?T+T?T+T*F?F+T*F?F+F*F
a+F*F?a+F*a?a+a*a
38
规范推导 规范句型最左（最右）推导：在推导的任何一步
α?β,其中 α,β 是句型，都是对 α 中的最左（右）非终结符进行替换最右推导被称为规范推导。
由规范推导所得的句型称为规范句型
39
语法树设 G=( VN,VT,P,S)为一 cfg，若一棵树满足下列 4个条件，
则此树称作 G的语法树 (推导树 )(派生树）：
1,每个结点都有一个标记，此标记是 V的一个符号
2,根的标记是 S
3,若一结点 n至少有一个它自己除外的子孙，并且有标记 A，则肯定 A∈V N
4,如果结点 n有标记 A,其直接子孙结点从左到右的次序是 n1,n2,…,nk，其标记分别为 A1,A2,…,
Ak，那么 A→A 1A2,…,Ak一定是 P中的一个产生式语法树的结果：
从左到右读出叶子的标记而构成的行谓之
40
上下文无关文法的语法树
句型 aabbaa的可能 推导 序列和语法树例,G[S]:
S→ aAS
A→ SbA
A→ SS
S→ a
A→ ba
S
a A S
S b A a
a b a
S?aAS?aAa?aSbAa?aSbbaa?aabbaa
S?aAS?aSbAS?aabAS?aabbaS?aabbaa
S?aAS?aSbAS?aSbAa?aabAa?aabbaa
41
语法树 ---句型推导 的 直观表示给定文法 G=(VN,VT,P,S)，对于 G的任何句型都能构造与之关联的语法树 (推导树 )
定理：
G为上下文无关文法，
对于 α ≠ ε,有 S =>* α,当且仅当文法 G有以 α 为结果的一棵语法树 (推导树 )
42
一棵语法树表示了一个句型的种种可能的 (但未必是所有的 )不同推导过程，包括最左
(最右 )推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左 (最右 )推导呢?
43
例,G‘[E]:
E → i
E → E+E
E → E*E
E → (E)
E
E + E
E * E i
i i
E
E * E
i E + E
i i
句型 i*i+i 的两个不同的最左推导：
推导 1,E? E+E? E*E+E? i*E+E? i*i+E? i*i+i
推导 2,E? E*E? i*E? i*E+E? i*i+E?i*i+i
44
二义文法若一个文法存在某个句子对应两棵不同的语法树，
则称这个文法是 二义 的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是 二义 的判定任给的一个上下文无关文法是否二义，
或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件
45
文法的二义性和语言的二义性文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法 G和 G′,其中 G是二义的，但是却有 L(G)=L(G′),也就是说，
这两个文法所产生的语言是相同的。
二义文法改造为无二义文法
G‘[E]:E → i G[E],E → T|E+T
E → E+E T → F|T*F
E → E*E F → （ E） |i
E → (E) 规定算符优先性和结合性如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。
46
（ 上下文无关文法） 句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型,是某个 推导 的构造过程。
在语言的编译实现中，把 完成句型分析 的 程序 称为 分析程序 或 识别程序 。分析算法又称 识别算法 。
从左到右的分析算法,即 总是从 左 到 右 地 识别输入符号串,首先识别符号串中的 最左符号，进而 依次识别右边 的一个符号,直到分析结束 。
47
句型的 分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,反复使用文法的产生式,寻找 与 输入符号串 匹配 的 推导，
或者说，为输入串寻找一个最左推导。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
48
两种方法反映了两种语法树的构造过程。
自上而下方法 是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法 则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树
49
自上而下的语法分析例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否为该文法的 句子
S S S
c A d c A d
a b
推导过程,S? cAd cAd? cabd
50
自下而上的语法分析例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否该文法的 句子
S
A A
c a b d c a b d c a b d
规约 过程构造的推导,cAd? cabd S? cAd
51
自上而下的语法分析
(1)S → cAd (2) A → ab (3) A → a
识别输入串 w=cad是否为该文法的 句子若 S? cAd 后选择 (2)扩展 A，
S? cAd? cabd
那将会？
w的第二个符号可以与叶子结点 a得以匹配，但第三个符号却不能与下一叶子结点 d
匹配
？宣告分析失败（其意味着，
识别程序不能为串 cad构造语法树，即 cad不是句子）
-显然是错误的结论。
导致失败的原因是在分析中对
A的选择不是正确的。
S
c A d
a b
这时应该 回朔,把 A为根的子树剪掉，扫描过的输入串中的 a吐出来,再试探用产生式（ 3）
52
(1)S → cAd (2) A → ab (3)A → a
识别输入串 w=cabd是否为该文法的 句子自下而上的语法分析对串 cabd的分析中，如果不是选择 ab用产生式 (2),而是选择 a用产生式 (3)将 a归约到了 A，
那么在 c A b d
中无法找到一个可归约串了，最终就达不到归约到 S的结果，因而也无从知道 cabd是一个句子
c a b d
c A b d
a
53
句型分析的有关问题
1）在自上而下的分析方法中 如何 选择 使用 哪个 产生式进行推导？
假定要被代换的最左非终结符号是 B，且有 n条规则,B→ A1|A2|…|An,那么如何确定用哪个右部去替代 B？
2）在自下而上的分析方法中 如何 识别可归约的串？
在分析程序工作的每一步，都是从当前串中 选择一个 子串,将它 归约 到 某个非终结符号,该子串称为,可归约串,
54
文法实用中的一些说明限制 化简文法文法中 不含有 有害规则 和 多余规则有害规则,形如 U→ U的产生式。会 引起 文法的 二义性多余规则,指文法中 任何句子的推导 都 不会用到的规则文法中 不含有 不可到达和不可终止的 非终结符
1）文法中某些 非终结符不在任何规则的右部出现,该非终结符称为 不可到达 。
2）文法中某些 非终结符,由它 不能推出终结符号串,该非终结符称 为 不可终止 。
55
对于文法 G[S]，为了保证任一非终结符 A在句子 推导中出现，必须满足如下两个条件：
1,A必须在某句型中出现即有 S =>* αAβ，其中 α,β属于 V*
2,必须能够从 A推出终结符号串 t来即 A =>* t，其中 t∈ VT*
56
化简文法
例,G[S],1) S→ Be
2) B→ Ce D为不可到达
3) B→ Af C为不可终止
4) A→ Ae
5) A→ e
6) C→ Cf
7) D→ f
产生式 2）,6）,7）为 多余规则 应去 掉。
57
上下文无关文法中的 ε规则上下文无关文法中某些规则可具有形式 A→ ε，称这种规则为 ε规则因为 ε规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现两种定义的唯一差别是 ε句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言 L有一个有穷的描述，则 L1=L∪ ｛ ε｝也同样有一个有穷的描述，并且可以证明，若 L是上下文有关语言、上下文无关语言或正规语言，则
L∪ ｛ ε｝和 L-｛ ε｝分别是上下文有关语言、上下文无关语言和正规语言。
58
练习
1,写一文法，使其语言是偶正整数的集合。
要求：
(1) 允许 0打头 (2) 不允许 0打头
2.证明下述文法 G［ 〈 表达式 〉 ］是二义的。
〈 表达式 〉 ∷ =a|(〈 表达式 〉 )|〈 表达式 〉〈 运算符 〉〈 表达式 〉
〈 运算符 〉 ∷ =+|-|*|/
3,令文法 G［ E］为：
E→T|E+T|E -T
T→F|T*F|T/F
F→(E)|i
证明 E+T*F是它的一个句型
59
练习
4,给出生成下述语言的上下文无关文法：
（ 1） { anbnambm| n,m>=0}
(2) { 1n0m 1m0n| n,m>=0}
5,给出生成下述语言的三型文法：
(1) { anbm|n,m>=1 }
(2){anbmck|n,m,k>=0 }
6,给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
第四章 文法和语言为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）
形式 工具 --“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述
2
本章内容文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法 的句型分析有关文法实用中的一些说明
3
文法和语言的形式定义如何来描述一种语言？
如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
生成方式 （文法）：语言中的每个句子可以用严格 定义的规则来构造。
识别方式 （自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。
4
文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造文法的定义推导的概念句型、句子和语言的定义,
5
文法 定义文法 G定义为四元组 (VN,VT,P,S )其中
VN:非终结符号 (或语法实体，或变量 )集；
VT:终结符号集；
P,规则的集合；
VN,VT和 P是 非空有穷集。
S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。
VN和 VT不含公共的元素，即 VN ∩ VT = φ
用 V表示 VN ∪ VT,称为文法 G的字母表或字汇表规则,也称 重写规则,产生式 或 生成式,是形如
→?或?∷ =?的 (?,?)有序对，其中?是字母表 V
的正闭包 V+中的一个符号,?是 V*中的一个符号。
称为规则的左部,? 称作规则的右部。
6
文法的定义例 文法 G=（ VN,VT,P,S）
VN = { S },VT ={ 0,1 }
P={ S→ 0S1,S→ 01 }
S为开始符号例 文法 G=（ VN,VT,P,S）
VN ={标识符，字母，数字 }
VT ={a,b,c,…x,y,z,0,1,…,9}
P={<标识符 >→ <字母 >
<标识符 >→ <标识符 ><字母 >
<标识符 >→ <标识符 ><数字 >
<字母 >→ a
…
<字母 >→z
<数字 >→0
…
<数字 >→9 }
S=<标识符 >
8
文法的写法 元 符号,→ ∷= | < >
习惯 大写字母表示非终结符 小写字母表示终结符
(1) G,S→aA b
A→ab
A→aA b
A→ ε
(2) G[S],A→ab
A→aA b
A→ ε
S→aS b
(3) G[S]:A→ab |aA b |ε
S→aS b
9
推导的定义直接推导,?”
α → β 是文法 G的产生式，若有 v,w满足：
v=γ α δ,w= γ β δ,其中 γ ∈V *,δ ∈V *
则称 v直接 推导 到 w,记作 v? w
也称 w直接 归约 到 v
例,G,S→ 0S1,S→ 01
0S1?00S11
00S11?000S111
000S111?00001111
S?0S1
10
推导
<程序 >?<分程序 >,
(<程序 >? <分程序 >,)
<分程序 >,? <变量说明部分 > <语句 >,
(<分程序 >? <变量说明部分 > <语句 >)
VAR<标识符 >;BEGIN READ(<标识符 >)END,?
VAR A;BEGIN READ(<标识符 > ) END.
(<标识符 >?A)
VAR A;BEGIN READ(<标识符 > ) END,?
VAR A;BEGIN READ( A) END.
(<标识符 >?A)
11
推导的定义若存在 v =w0?w1?..,?wn=w,(n>0)
则记为 v =>+ w，称作 v推导出 w，或 w归约到 v
若有 v =>+ w 或 v=w,则记为 v =>* w
12
例,G,S→ 0S1,S→ 01
0S1?00S11
00S11?000S111
000S111?00001111
S?0S1?00S11?000S111?00001111
S =>+ 00001111
S =>* S 00S11 =>* 00S11
13
句型、句子的定义
句型有文法 G，若 S =>* x，则称 x是文法 G的句型。
句子有文法 G，若 S =>* x，且 x∈V T*，则称 x是文法 G的句子。
例,G,S→ 0S1,S→ 01
S?0S1?00S11?000S111?00001111
G的句型 S,0S1,00S11,000S111,00001111
G的句子 00001111,01
14
句型、句子例,G[E],E→E+T|T
T→T*F|F
F→(E)|a
E?E+T?T+T?F+T?a+T?a+T*F
a+F*F?a+a*F?a+a*a
句子：用符号 a,+,*,(和 )构成的算术表达式
15
(文法生成的 )语言的定义由文法 G生成的语言记为 L(G),它是文法 G的一切句子的集合,
L(G)={x|S =>* x，其中 S为文法的开始符号，且 x ∈V T*}
例,G,S→ 0S1,S→ 01
L(G)={0n1n|n≥ 1}
例 文法 G[S]：
（ 1） S→ aSBE
（ 2） S→ aBE
（ 3） EB→ BE
（ 4） aB→ ab
（ 5） bB→ bb
（ 6） bE→ be
（ 7） eE→ ee
L（ G） ={ anbnen | n≥ 1 }
G生成的每个串都在 L(G)中
L(G)中的每个串确实能被 G生成
17
文法的等价
若 L（ G1） =L（ G2），则称文法 G1和 G2是等价的。
如文法 G1[A],A→DB 与 G2[S],S→0S1 等价
A→DE S→01
E→AB
D→0
B→1
18
文法的类型通过对产生式施加不同的限制,Chomsky将文法分为四种类型：
0型文法：对任一产生式 α → β,都有
α ∈(V N∪V T)+,β ∈(V N∪V T)*
1型文法,对任一产生式 α → β,都有 |β |≥| α |，
仅仅 S→ ε 除外
2型文法,对任一产生式 α → β,都有 α ∈V N
3型文法,任一产生式 α → β 的形式都为 A→aB 或
A→a,其中 A∈V N,B∈V N,a∈V T *
19
文法的类型例,1型（上下文有关）文法文法 G[S],S→CD Ab→bA
C→aCA Ba→aB
C→bCB Bb→bB
AD→aD C→a
BD→bD D→b
Aa→bD
20
文法的类型例,2型（上下文无关）文法文法 G[S],S→AB
A→BS|0
B→SA|1
21
3型文法
G[S]：
S→0A|1B|0
A→0A|1B|0S
B→1B|1|0
G[I],I → lT
I → l
T → lT
T → dT
T → l
T → d
22
文法的类型
2型文法
1型文法
0型文法四类 文法 之间 的 逐级,包含,关系
3型文法
23
文法和语言
0型文法产生的语言称为 0型语言
1型文法或上下文有关文法（ CSG ） 产生的语言称为 1型语言 或上下文有关 语言（ CSL）
2型文法或上下文无关文法（ CFG ） 产生的语言称为 2型语言 或上下文无关 语言（ CF L ）
3型文法或正则（正规）文法（ RG ） 产生的语言称为 3型语言 正则（正规） 语言（ RL ）
24
文法和语言四种文法之间的关系 是将产生式做进一步限制而定义的。
语言之间的关系依次：有不是上下文有关语言的 0型语言，有不是上下文无关语言的
1型语言，有不是正则语言的上下文无关语言。
25
根据形式语言理论,文法和识别系统间有这样的关系
0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何 0型语言都是递归可枚举的
1型文法（上下文有关文法）：产生式的形式为 α 1Aα 2→ α 1βα2，即只有 A出现在 α 1
和 α 2的上下文中时，才允许 β 取代 A。其识别系统是线性界限自动机。
26
带 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an-1 an
有限控制器磁头任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述
27
2型文法（上下文无关文法 CFG）：产生式的形式为 A→ β,β 取代 A时与 A的上下文无关。其识别系统是不确定的下推自动机。
3型文法（正规文法 RG）：产生的语言是有穷自动机（ FA）所接受的集合
28
3型文法产生的语言是有穷自动机（ FA）所接受的集合,
定理 设 G=（ VN,VT,P,S）是 3型文法，则存在一个有穷自动机 M=(K,∑,f,A,Z),使得 L(M)=L(G)
有穷自动机 NFA M
· ∑= VT
· K= VN ∪{ N},N为一个新状态,它不在 VN中
· A=S
· Z={N}
·对 G中的形如 D→tB 的产生式,t为终结符或 ε,有 f(D,t)=B；
对 G中形如 D→t 的产生式,t为终结符或 ε,有 f(D,t)=N;
对 VT中的每一个 a,有 f(N,a)=φ
29
3型文法 和 有穷自动机（ FA）
G［Ｓ］：
S→aA|bB
A→bB|aD|a
B→aA|bD|b
D→aD|bD|a|b
B
A
S
a
a
a
b
b
b
a,b
D Z
a
b
a
b
30
3型文法 和 有穷自动机（ FA）
定理 已知一有穷自动机 M= (K,∑,f,A,Z),
存在有一个 3型文法 G = （ VN,VT,P,S）,使得 L(G)=L(M)
G 的定义：
· VT =∑ · VN= K
· S = A
·若 f(D,t)=B,则 D→tB 在 P中若 f(D,t)=B,且 B在 Z中，则 D→t 在 P中
31
3型文法 和 有穷自动机（ FA）
G［Ｓ］：
S→aA|bB
A→bB|aD|a
B→aA|bD|b
D→aD|bD|a|bDB
A
S
a
a a
b
b
a,b
b
32
正规文法和正规式对?上的正规式 r,存在一个 RG=(VN,VT,P,S)：
L(G)=L(r)
初始,VT=?,S? VN,生成正规产生式 S?r
(R.1) 对形如 A?r1r2的 正规产生式,A?r1B
B?r2
B?VN
(R.2)对形如 A?r?r1的 正规产生式,A?rB
A?r1
B?rB
B?r1 B?VN
(R.3)对形如 A?r1?r2的 正规产生式,A?r1
A? r2
不断应用 (R.x)做变换，直到每个产生式右端至多有一个 VN
33
例 r=a(a?d)?
(1) S?a(a?d)?
(2) S?aA A?(a?d)?
(3) A?(a?d)B
A
B?(a?d)B
B
G[s],
S?aA
A VT={a,d}
A?aB VN={S,A,B}
A?dB
B?aB
B?dB
B
34
正规文法和正规式对 G=(VN,VT,P,S),存在一个? =VT上的正规式 r,
L(r)=L(G)
A?xB,B?y 形成正规式 A=xy
A?xA?y 形成正规式 A=x?y
A?x?y 形成正规式 A=x?y
35
正规文法和正规式
G[s]:S?aA|a
A?aA?a?dA?d
A?(a?d)A?(a?d)
A?(a?d)?(a?d)
S=a(a?d)?(a?d)?a
=a((a?d)?(a?d))
=a((a?d))
R=a(a?d)?
36
上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构语法树 ---句型推导 的 直观表示
37
语法树 ---句型推导 的 直观表示 (句型、推导 )
G[E],E→E+T|T
T→T*F|F
F→(E)|a
E?E+T?T+T?F+T?a+T?a+T*F
a+F*F?a+a*F?a+a*a
E?E+T?E+T*F?E+T*a?E+F*a?E+a*a
T+a*a?F+a*a?a+a*a
E?E+T?T+T?T+T*F?F+T*F?F+F*F
a+F*F?a+F*a?a+a*a
38
规范推导 规范句型最左（最右）推导：在推导的任何一步
α?β,其中 α,β 是句型，都是对 α 中的最左（右）非终结符进行替换最右推导被称为规范推导。
由规范推导所得的句型称为规范句型
39
语法树设 G=( VN,VT,P,S)为一 cfg，若一棵树满足下列 4个条件，
则此树称作 G的语法树 (推导树 )(派生树）：
1,每个结点都有一个标记，此标记是 V的一个符号
2,根的标记是 S
3,若一结点 n至少有一个它自己除外的子孙，并且有标记 A，则肯定 A∈V N
4,如果结点 n有标记 A,其直接子孙结点从左到右的次序是 n1,n2,…,nk，其标记分别为 A1,A2,…,
Ak，那么 A→A 1A2,…,Ak一定是 P中的一个产生式语法树的结果：
从左到右读出叶子的标记而构成的行谓之
40
上下文无关文法的语法树
句型 aabbaa的可能 推导 序列和语法树例,G[S]:
S→ aAS
A→ SbA
A→ SS
S→ a
A→ ba
S
a A S
S b A a
a b a
S?aAS?aAa?aSbAa?aSbbaa?aabbaa
S?aAS?aSbAS?aabAS?aabbaS?aabbaa
S?aAS?aSbAS?aSbAa?aabAa?aabbaa
41
语法树 ---句型推导 的 直观表示给定文法 G=(VN,VT,P,S)，对于 G的任何句型都能构造与之关联的语法树 (推导树 )
定理：
G为上下文无关文法，
对于 α ≠ ε,有 S =>* α,当且仅当文法 G有以 α 为结果的一棵语法树 (推导树 )
42
一棵语法树表示了一个句型的种种可能的 (但未必是所有的 )不同推导过程，包括最左
(最右 )推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左 (最右 )推导呢?
43
例,G‘[E]:
E → i
E → E+E
E → E*E
E → (E)
E
E + E
E * E i
i i
E
E * E
i E + E
i i
句型 i*i+i 的两个不同的最左推导：
推导 1,E? E+E? E*E+E? i*E+E? i*i+E? i*i+i
推导 2,E? E*E? i*E? i*E+E? i*i+E?i*i+i
44
二义文法若一个文法存在某个句子对应两棵不同的语法树，
则称这个文法是 二义 的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是 二义 的判定任给的一个上下文无关文法是否二义，
或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件
45
文法的二义性和语言的二义性文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法 G和 G′,其中 G是二义的，但是却有 L(G)=L(G′),也就是说，
这两个文法所产生的语言是相同的。
二义文法改造为无二义文法
G‘[E]:E → i G[E],E → T|E+T
E → E+E T → F|T*F
E → E*E F → （ E） |i
E → (E) 规定算符优先性和结合性如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。
46
（ 上下文无关文法） 句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型,是某个 推导 的构造过程。
在语言的编译实现中，把 完成句型分析 的 程序 称为 分析程序 或 识别程序 。分析算法又称 识别算法 。
从左到右的分析算法,即 总是从 左 到 右 地 识别输入符号串,首先识别符号串中的 最左符号，进而 依次识别右边 的一个符号,直到分析结束 。
47
句型的 分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,反复使用文法的产生式,寻找 与 输入符号串 匹配 的 推导，
或者说，为输入串寻找一个最左推导。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
48
两种方法反映了两种语法树的构造过程。
自上而下方法 是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法 则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树
49
自上而下的语法分析例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否为该文法的 句子
S S S
c A d c A d
a b
推导过程,S? cAd cAd? cabd
50
自下而上的语法分析例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否该文法的 句子
S
A A
c a b d c a b d c a b d
规约 过程构造的推导,cAd? cabd S? cAd
51
自上而下的语法分析
(1)S → cAd (2) A → ab (3) A → a
识别输入串 w=cad是否为该文法的 句子若 S? cAd 后选择 (2)扩展 A，
S? cAd? cabd
那将会？
w的第二个符号可以与叶子结点 a得以匹配，但第三个符号却不能与下一叶子结点 d
匹配
？宣告分析失败（其意味着，
识别程序不能为串 cad构造语法树，即 cad不是句子）
-显然是错误的结论。
导致失败的原因是在分析中对
A的选择不是正确的。
S
c A d
a b
这时应该 回朔,把 A为根的子树剪掉，扫描过的输入串中的 a吐出来,再试探用产生式（ 3）
52
(1)S → cAd (2) A → ab (3)A → a
识别输入串 w=cabd是否为该文法的 句子自下而上的语法分析对串 cabd的分析中，如果不是选择 ab用产生式 (2),而是选择 a用产生式 (3)将 a归约到了 A，
那么在 c A b d
中无法找到一个可归约串了，最终就达不到归约到 S的结果，因而也无从知道 cabd是一个句子
c a b d
c A b d
a
53
句型分析的有关问题
1）在自上而下的分析方法中 如何 选择 使用 哪个 产生式进行推导？
假定要被代换的最左非终结符号是 B，且有 n条规则,B→ A1|A2|…|An,那么如何确定用哪个右部去替代 B？
2）在自下而上的分析方法中 如何 识别可归约的串？
在分析程序工作的每一步，都是从当前串中 选择一个 子串,将它 归约 到 某个非终结符号,该子串称为,可归约串,
54
文法实用中的一些说明限制 化简文法文法中 不含有 有害规则 和 多余规则有害规则,形如 U→ U的产生式。会 引起 文法的 二义性多余规则,指文法中 任何句子的推导 都 不会用到的规则文法中 不含有 不可到达和不可终止的 非终结符
1）文法中某些 非终结符不在任何规则的右部出现,该非终结符称为 不可到达 。
2）文法中某些 非终结符,由它 不能推出终结符号串,该非终结符称 为 不可终止 。
55
对于文法 G[S]，为了保证任一非终结符 A在句子 推导中出现，必须满足如下两个条件：
1,A必须在某句型中出现即有 S =>* αAβ，其中 α,β属于 V*
2,必须能够从 A推出终结符号串 t来即 A =>* t，其中 t∈ VT*
56
化简文法
例,G[S],1) S→ Be
2) B→ Ce D为不可到达
3) B→ Af C为不可终止
4) A→ Ae
5) A→ e
6) C→ Cf
7) D→ f
产生式 2）,6）,7）为 多余规则 应去 掉。
57
上下文无关文法中的 ε规则上下文无关文法中某些规则可具有形式 A→ ε，称这种规则为 ε规则因为 ε规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现两种定义的唯一差别是 ε句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言 L有一个有穷的描述，则 L1=L∪ ｛ ε｝也同样有一个有穷的描述，并且可以证明，若 L是上下文有关语言、上下文无关语言或正规语言，则
L∪ ｛ ε｝和 L-｛ ε｝分别是上下文有关语言、上下文无关语言和正规语言。
58
练习
1,写一文法，使其语言是偶正整数的集合。
要求：
(1) 允许 0打头 (2) 不允许 0打头
2.证明下述文法 G［ 〈 表达式 〉 ］是二义的。
〈 表达式 〉 ∷ =a|(〈 表达式 〉 )|〈 表达式 〉〈 运算符 〉〈 表达式 〉
〈 运算符 〉 ∷ =+|-|*|/
3,令文法 G［ E］为：
E→T|E+T|E -T
T→F|T*F|T/F
F→(E)|i
证明 E+T*F是它的一个句型
59
练习
4,给出生成下述语言的上下文无关文法：
（ 1） { anbnambm| n,m>=0}
(2) { 1n0m 1m0n| n,m>=0}
5,给出生成下述语言的三型文法：
(1) { anbm|n,m>=1 }
(2){anbmck|n,m,k>=0 }
6,给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
