1
第四章 文法和语言本章目的为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）
形式 工具 --形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述
2
本章知识点 (内容 )
引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法 的句型分析有关文法实用中的一些说明
3
文法的直观概念和 语言概述当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。
以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明 (或者定义 )句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第 2章所介绍的 EBNF来表示这种句子的构成规则：
4
“我是大学生,。是汉语的一个句子
〈 句子 〉 ∷ =〈 主语 〉〈 谓语 〉
〈 主语 〉 ∷ =〈 代词 〉 ｜ 〈 名词 〉
〈 代词 〉 ∷ =我 ｜ 你 ｜ 他
〈 名词 〉 ∷ =王明 ｜ 大学生 ｜ 工人 ｜ 英语
〈 谓语 〉 ∷ =〈 动词 〉〈 直接宾语 〉
〈 动词 〉 ∷ =是 ｜ 学习
〈 直接宾语 〉 ∷ =〈 代词 〉 ｜ 〈 名词 〉
5
有了一组规则以后，按照如下方式用它们导出句子：开始去找
∷ =左端的带有 〈 句子 〉 的规则并把它由 ∷ =右端的符号串代替，这个动作表示成：
〈 句子 〉?〈 主语 〉〈 谓语 〉,
然后在得到的串 〈 主语 〉〈 谓语 〉 中，选取 〈 主语 〉 或 〈 谓语 〉,再用相应规则的 ∷ =右端代替之。比如，选取了 〈 主语 〉,并采用规则 〈 主语 〉 ∷ =〈 代词 〉,
那么得到,〈 主语 〉〈 谓语 〉?〈 代词 〉〈 谓语 〉,
重复做下去，
句子：,我是大学生,的全部动作过程是：
〈 句子 〉?〈 主语 〉〈 谓语?〈 代词 〉〈 谓语 〉
我 〈 谓语?我 〈 动词 〉〈 直接宾语 〉
我是 〈 直接宾语 〉?我是 〈 名词 〉?我是大学生
6
“我是大学生,的构成符合上述规则，而,我大学生是,不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。
7
英语句子
sentence –> <subject> <verb-phrase> <object>
subject –> This | Computers | I
verb-phrase –> <adverb> <verb> | <verb>
adverb –> never
verb –> is | run | am | tell
object –> the <noun> | a <noun> | <noun>
noun –> university | world | cheese | lies
This is a university.
Computers run the world.
I am the cheese.
I never tell lies.
8
语言概述语言是由句子组成的集合，是由一组符号所构成的集合。
汉语 --所有符合汉语语法的句子的全体英语 --所有符合英语语法的句子的全体程序设计语言 --所有该语言的程序的全体每个句子构成的规律研究语言 每个句子的含义每个句子和使用者的关系
9
研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法 Syntax
语义 Semantics
语用 Pragmatics
10
语法 -- 表示构成语言句子的各个记号之间的组合规律语义 -- 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）
语用 --表示在各个记号所出现的行为中，它们的来源、使用和影响。
11
每种语言具有两个可识别的特性,即语言的形式和该形式相关联的意义 。
语言的实例若在语法上是正确的,其相关联的意义可以从两个观点来看,其一是该句子的创立者所想要表示的意义,另一是接收者所检验到的意义 。 这两个意义并非总是一样的,前者称为语言的语义,后者是其语用意义 。 幽默,双关语和谜语就是利用这两方面意义间的差异 。
12
如果不考虑语义和语用,即只从语法这一侧面来看语言,这种意义下的语言称作形式语言 。 形式语言抽象地定义为一个数学系统 。
,形式,是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述 。 形式语言理论是对符号串集合的表示法,结构及其特性的研究 。 是程序设计语言语法分析研究的基础 。
13
有关定义和记号 — 回 顾符号：可以相互区别的记号（元素）。
字母表?：符号（元素）的非空有穷集合。
符号串：由字母表?中的符号组成的任何有穷序列称为该字母表上的符号串。 1.空符号串
ε (没有 符号的符号串 )是?上的符号串 2.若 x
是?上的符号串,a是?的元素,则 xa是?上的符号串 3,y是?上的符号串,当且仅当它可以由 1和 2
导出。
例如,Σ ={a,b}
ε,a,b,aa,ab,aabba… 都 是?上的符号串
14
有关定义和记号 — 回 顾符号串 s的头（前缀）：移走符号串 s尾部的零个或多于零个符号得到的符号串,
如,b是符号串 banana的一个前缀,
符号串 s的尾（后缀）：删去符号串 s头部的零个或多于零个符号得到的符号串,
如,nana是符号串 banana的一个后缀,
符号串 s的子串：从 s中删去一个前缀和一个后缀得到的符号串,
如,ana是符号串 banana的一个子串,
15
对于每个符号串 s,s和 ε 两者 都 是符号串 s的前缀，后缀和子串。
符号串 s的真前缀，真后缀，真子串：任何非空符号串 x,相应地，是 s的前缀，后缀或子串，
并且 s? x
符号串的运算符号串的长度：符号串中符号的个数,符号串 s的长度记为 |s|。 ε 的长度为 0
连接：符号串 x,y的连接,是把 y的符号写在 x的符号之后得到的符号串 xy
如 x=ab,y=cd 则 xy=abcd 有 ε a = aε
方幂：符号串自身连接 n次得到的符号串
an 定义为 aa… aa n个 a a1=a,a2=aa则 a0=ε
16
符号串集合：若集合 A中所有元素都是某字母表?上的符号串，则称 A为字母表?上的符号串集合。
两个符号串集合 A和 B的乘积定义为
AB =?xy|x?A且 y?B?
若 集合 A=?ab,cde? B =?0,1?
则 AB =?ab1,ab0,cde0,cde1?
使用?* 表示?上的一切符号串（包括 ε ）组成的集合。 Σ *称为 Σ 的闭包 。
上的 除 ε 外 的所有符号串组成的集合记为
+ 。 Σ +称为 Σ 的正闭包 。
17
例,Σ ={a,b}
Σ *={ε,a,b,aa,ab,ba,bb,aaa,aab,… }
Σ +={a,b,aa,ab,ba,bb,aaa,aab,… }
......}{ 2*
.,,,,,}{ 32**
18
有关定义和记号语言 是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表?上 的一个语言是?上的一些符号串的集合 (字母表
上 的每个语言是?*的一个子集 )。
例如,字母表 Σ ={a,b},Σ *={ε,a,b,aa,ab,ba,bb,aaa,aab,… }
集合 {ab,aabb,aaabbb,…,anbn,… }
或表示为 {w|w∈ Σ *且 w=anbn,n≥1} 为 字母表?上 的一个语言。
集合 {a,aa,aaa,… }
或 表示为 {w|w∈ Σ *且 w=an,n≥1} 为 字母表?上 的一个语言。
ε?是一个语言。
即是一个语言 。
19
给出语言 上 的有关运算设 L是（?上的）一个语言,M是（?上的）一个语言,语言 L和 M的并，交，差，补 是一个语言。
语言 L和 M的并为 L?M,是一个语言,{w|w is
in L or is in M}
如,L1 ={a,b,… y,z} M1 ={1,2… 8,9 }
L1?M1={a,b,… y,z,1,2… 8,9 }
语言 L和 M的连接 是一个语言，记 为 LM
LM={st |s∈ L且 t∈ M}
如,L1M1 ={a1,b1,… y1,z1,a2,b2… a9… z9}
有 L?ε?=?ε?L=L。 L的 n次连接 Ln= LL...L
20
语言 上 的运算语言 L的 闭包 记 为 L*,L*= L0? L1? L2?,.,
L0=?ε?,Ln= L Ln-1= Ln-1 L,n?1
语言 L的正 闭包 记 为 L+,L+= L1? L2? L3,.,
L+= LL*= L*L
L*= L+ε?
如,L1 ={a,b,… y,z} M1 ={1,2… 8,9 }
（ L1?M1） ={a,b,… y,z,1,2… 8,9}
（ L1?M1） *={a,b,… y,z,1,2… 8,9，
aa,1a,…xyz,6789st..}
L1（ L1?M1） *={所有字母打头的字母和数字符号串 }
21
文法和语言的形式定义如何来描述一种语言？
如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。
识别方式 （自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）
22
文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造,下面给出文法的定义,进而在 文法的定义的基础上,给出 推导的概念,句型、句子和语言的定义,
23
定义文法 G定义为四元组 (VN,VT,P,S )其中
VN为非终结符号 (或语法实体，或变量 )集；
VT为终结符号集；
P为产生式 (也称规则 )的集合； VN,VT和 P是 非空有穷集。
S称作识别符号或开始符号，它是一个非终结符，
至少要在一条产生式中作为左部出现。
VN和 VT不含公共的元素，即 VN ∩ VT = φ
用 V表示 VN ∪ VT,称为文法 G的字母表或字汇表规则,也称 重写规则,产生式 或 生成式,是形如
α→ β或 α∷ =β的 (α,β)有序对，其中 α是字母表 V
的正闭包 V+中的一个符号,β是 V*中的一个符号。
α称为规则的左部,β称作规则的右部。
24
Define a grammar
A grammar G is defined as a 4-tuple (VN,VT,P,S )
VN is a set of nonterminals
VT is a set of terminals
P is a set of productions,each production
consists of a left side,an arrow(or ‘::=‘),and a
right side
S is a designation of one of the nonterminals
as the start symbol
V =VN ∪ VT is the alphabet of G
25
文法的定义例 文法 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=<标识符 >
27
文法的写法
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
元 符号,→
∷=
|
< >
习惯表示大写字母：终结符小写字母：非终结符
S –> AB
A –> Ax | y
B –> z
29
推导的定义直接推导,?”
α → β 是文法 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
30
<程序 >?<分程序 >,
<分程序 >,? <变量说明部分 > <语句 >,
VAR<标识符 >;BEGIN READ(<标识符 >)END,?
VAR A;BEGIN READ(<标识符 > ) END.
31
推导的定义若存在 v?w0?w1?..,?wn=w,(n>0)
则记为 v =>+ w,v推导出 w，或 w归约到 v
若有 v =>+ w，或 v=w，
则记为 v =>* w
32
例,G,S→ 0S1,S→ 01
0S1?00S11
00S11?000S111
000S111?00001111
S?0S1?00S11?000S111?00001111
S =>+ 00001111
S =>* S 00S11 =>* 00S11
33
What are Derivations
Derivation is a way that a grammar defines a language,In
the process of derivation a production is treated as a
rewriting rule in which the nonterminal on the left side is
replaced by the string on the right side of the production
A production u –> v is used by replacing an occurrence of
u by v,Formally,if we apply a production pP to a
string of symbols w in V to yield a new string of symbols
z in V,we say that z derived from w using p,written as
follows,w =>p z,We also use:
w => z z derives from w (production unspecified)
w =>* z z derives from w using zero or more productions
w =>+ z z derives from w using one or more productions
34
句型、句子的定义句型有文法 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
35
例,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,+,*,(和 )构成的算术表达式
36
文法，语言的定义由文法 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 }
38
S?a S BE (S→ aSBE)
a aBEBE (S→ aBE)
aabEBE ( aB→ ab )
aabBEE ( EB→ BE )
aabbEE （ bB→ bb)
aabbeE （ bE→ be)
aabbee （ eE→ ee)
G生成的每个串都在 L(G)中
L(G)中的每个串确实能被 G生成
39
使用产生式 (1)n-1次，得到推导序列：
S =>* an-1S(BE)n-1，然后使用产生式 (2)一次，得到：
S =>* an-1S(BE)n-1? an(BE)n。然后从 an(BE)n继续推导，总是对 EB使用产生式 (3)的右部进行替换，而最终在得到的串中，所有的 B都先于所有的 E。例如，若 n=3,
aaaBEBEBE? aaaBBEEBE? aaaBBEBEE
aaaBBBEEE。即有：
S =>* anBnEn
接着，使用产生式 (4)一次，得到 S =>* anbBn-1En，然后使用产生式 (5)n-1次得到：
S =>* anbnEn，最后使用产生式 (6)一次，使用产生式
(7)n-1次，得到,S =>* anbnen
也能证明，对于 n≥1，串 anbnen是唯一形式的终结符号串
40
文法的等价
若 L（ G1） =L（ G2），则称文法 G1和 G2是等价的。
如文法 G1[A],A→0R 与 G2[S],S→0S1 等价
A→01 S→01
R→A1
41
文法的类型通过对产生式施加不同的限制,Chomsky将文法分为四种类型：
0型文法：对任一产生式 α → β,都有
α ∈(V N∪V T)+,β ∈(V N∪V T)*
1型文法,对任一产生式 α → β,都有 |β |≥| α |，
仅仅 S→ ε 除外
2型文法,对任一产生式 α → β,都有 α ∈V N,
β ∈(V N∪V T)*
3型文法,任一产生式 α → β 的形式都为 A→aB 或
A→a,其中 A∈V N,B∈V N,a∈V T
42
A hierarchy of grammars
Type 0,free or unrestricted grammars
These are the most general,Productions are of the form u
–> v where both u and v are arbitrary strings of
symbols in V,with u non-null,There are no
restrictions on what appears on the left or right-hand
side other than the left-hand side must be non-empty.
Type 1,context-sensitive grammars
Productions are of the form uXw –> uvw where u,v and
w are arbitrary strings of symbols in V,with v non-null,
and X a single nonterminal,In other words,X may be
replaced by v but only when it is surrounded by u and w,
(i.e,in a particular context).
43
Type 2,context-free grammars
Productions are of the form X–> v where v is an
arbitrary string of symbols in V,and X is a single
nonterminal,Wherever you find X,you can replace
with v (regardless of context).
Type 3,regular grammars
Productions are of the form X–> a or X–> aY where X
and Y are nonterminals and a is a terminal,That is
the left-hand side must be a single nonterminal and
the right-hand side can be either a single terminal by
itself or with a single nonterminal,These grammars
are the most limited in terms of expressive power.
44
文法的类型例,1型（上下文有关）文法文法 G[S],S→CD Ab→bA
C→aCA Ba→aB
C→bCB Bb→bB
AD→aD C→ ε
BD→bD D→ ε
Aa→bD
45
文法的类型例,2型（上下文无关）文法文法 G[S],S→AB
A→BS|0
B→SA|1
46
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
47
文法的类型
2型文法
1型文法
0型文法四种 文法 之间 的 逐级,包含,关系
3型文法
48
文法和语言
0型文法产生的语言称为 0型语言
1型文法或上下文有关文法（ CSG ） 产生的语言称为 1型语言 或上下文有关 语言（ CSL）
2型文法或上下文无关文法（ CFG ） 产生的语言称为 2型语言 或上下文无关 语言（ CF L ）
3型文法或正则（正规）文法（ RG ） 产生的语言称为 3型语言 正则（正规） 语言（ RL ）
49
文法和语言四种文法之间的关系 是将产生式做进一步限制而定义的。
语言之间的关系依次：有不是上下文有关语言的 0型语言，有不是上下文无关语言的
1型语言，有不是正则语言的上下文无关语言。
50
根据形式语言理论,文法和识别系统间有这样的关系
0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何 0型语言都是递归可枚举的
1型文法（上下文有关文法）：产生式的形式为 α 1Aα 2→ α 1βα2，即只有 A出现在 α 1
和 α 2的上下文中时，才允许 β 取代 A。其识别系统是线性界限自动机。
51
带 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an-1 an
有限控制器磁头任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述
52
2型文法（上下文无关文法 CFG）：产生式的形式为 A→ β,β 取代 A时与 A的上下文无关。其识别系统是不确定的下推自动机。
3型文法（正规文法 RG）：产生的语言是有穷自动机（ FA）所接受的集合
53
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)=φ
54
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
55
定理 已知一有穷自动机 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中
56
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
57
正规文法和正规式对?上的正规式 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做变换，直到每个产生式右端至多有一个 VN
58
例 r=a(a?d)?
S?a(a?d)?
S?aA A?(a?d)?
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
59
正规文法和正规式对 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
60
正规文法和正规式
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)?
61
上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构语法树 ---句型推导 的 直观表示
62
例文法 G=(｛ E｝,｛ +,*,i,(,)｝,P,E)其中 P为：
{E→i,E→E+E,E→E*E,E→(E) }
E表示算术表达式,i表示程序的,变量,,该文法定义了由变量,+,*,(和 )组成的算术表达式的语法结构，即：
变量是算术表达式；若 E1和 E2是算术表达式，则 E1+
E2,E1*E2和 (E1)也是算术表达式
描述一种简单赋值语句的产生式：
〈 赋值语句 〉 →i ∶ =E
描述条件语句的产生式：
〈 条件语句 〉 →if 〈 条件 〉 then〈 语句 〉 ｜
if〈 条件 〉 then〈 语句 〉 else〈 语句 〉
63
句型、推导
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
64
规范推导 规范句型最左（最右）推导：在推导的任何一步
α?β,其中 α,β 是句型，都是对 α 中的最左（右）非终结符进行替换最右推导被称为规范推导。
由规范推导所得的句型称为规范句型
65
语法树设 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中的一个产生式语法树的结果：
从左到右读出叶子的标记而构成的行谓之
66
语法树 ---句型推导 的 直观表示给定文法 G=(VN,VT,P,S)，对于 G的任何句型都能构造与之关联的语法树 (推导树 )
定理：
G为上下文无关文法，
对于 α ≠ ε,有 S =>* α,当且仅当文法 G有以 α 为结果的一棵语法树 (推导树 )
67
构造语法树
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
E + T E + T
T
E
E + T
T
F
68
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
E
E + T
T T * F
F F a
a a
看不出句型中的符号被替代的顺序
69
上下文无关文法的语法树的用处用于描述上下文无关文法 句型推导 的 直观方法例,G[S]:
S→ aAS
A→ SbA
A→ SS
S→ a
A→ ba
S
a A S
S b A a
a b a
句型 aabbaa的 语法树 （推导树）
叶子结点,树中 没有子孙的结点 。
从左到右 读出推导树的 叶子标记 连接成的 文法符号 串,为 G[S]的 句型 。也把该推导树称为该 句型 的 语法树 。
70
上下文无关文法的语法树
推导过程中 施用 产生式 的 顺序例,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
71
一棵语法树表示了一个句型的种种可能的 (但未必是所有的 )不同推导过程，包括最左
(最右 )推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左 (最右 )推导呢?
72
例,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
73
二义文法若一个文法存在某个句子对应两棵不同的语法树，
则称这个文法是 二义 的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是 二义 的判定任给的一个上下文无关文法是否二义，
或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件
74
文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法 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) 规定优先顺序和结合律如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。
75
句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型,是某个 推导 的构造过程。
在语言的编译实现中，把 完成句型分析 的 程序 称为 分析程序 或 识别程序 。分析算法又称 识别算法 。
从左到右的分析算法,即 总是从 左 到 右 地 识别输入符号串,首先识别符号串中的 最左符号，进而 依次识别右边 的一个符号,直到分析结束 。
76
句型的 分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,反复使用文法的产生式,寻找 与 输入符号串 匹配 的 推导 。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
77
两种方法反映了两种语法树的构造过程。
自上而下方法 是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法 则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树
78
自上而下的语法分析例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否为该文法的 句子
S S S
c A d c A d
a b
推导过程,S? cAd cAd? cabd
79
自下而上的语法分析例：文法 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
80
(1)S → cAd (2) A → ab (3)A → a
识别输入串 w=cabd是否为该文法的 句子自上而下的语法分析若 S? cAd 后选择 (3)扩展 A，
S? cAd? cad
那将会？
w的第二个符号可以与叶子结点 a得以匹配，但第三个符号却不能与下一叶子结点 d
匹配
？宣告分析失败（其意味着，
识别程序不能为串 cad构造语法树，即 cad不是句子）
-显然是错误的结论。
导致失败的原因是在分析中对
A的选择不是正确的。
S
c A d
a
81
(1)S → cAd (2) A → ab (3)A → a
识别输入串 w=cabd是否为该文法的 句子自下而上的语法分析对串 cabd的分析中，如果不是选择 ab用产生式 (2),而是选择 a用产生式 (3)将 a归约到了 A，
那么最终就达不到归约到 S的结果，因而也无从知道 cabd是一个句子
c a b d
c A b d
a
82
句型分析的有关问题
1）在自上而下的分析方法中 如何 选择 使用 哪个 产生式进行推导？
假定要被代换的最左非终结符号是 B，且有 n条规则,B→ A1|A2|…|An,那么如何确定用哪个右部去替代 B？
2）在自下而上的分析方法中 如何 识别可归约的串？
在分析程序工作的每一步，都是从当前串中 选择一个 子串,将它 归约 到 某个非终结符号,该子串称为,可归约串,
83
刻画,可归约串,
文法 G[S]
句型的短语
S =>* α Aδ 且 A =>+ β,则称 β 是 句型 α β δ
相对于非终结符 A的 短语句型的直接短语若有 A?β,则称 β 是句型 α β δ 相对于非终结符 A 的 直接短语句型的句柄一个句型的 最左直接短语 称为 该句型 的 句柄
84
例,i*i+i 的短语、直接短语和句柄
E
E + T
T F
T * F
i3 短语,i1*i2+ i3,i1* i2,
F i2 i1,i2,i3 。
i1 直接短语,i1,i2,i3 。 句柄,
i1
G[E],E→E+T|T
T→T*F|F
F→(E)|i
句型,i*i+i
85
左递归规则 --
G[S],S→Sa
S→b L={ba n | n≥0}
W=baaa S
b
S
S a
S a
86
左递归 关于非终结符 P的规则直接左递归 若 P → P α | β
α,β ∈V *且 β 不以 P开头一般 左递归 若 P =>* P α
S→Aa
A→Sb
…
87
消除左递归消除直接左递归形如,P → P α | β
α 非?,不以 P打头改写为,P → β Q
Q → α Q|?
88
消除左递归例,E → E+T|T
T →T*F|F
F →(E)| a
G[ E],(1) E → TE’ (2) E’ → +TE’
(3) E’ →? (4) T → FT’
(5) T’ → *FT’ (6) T’ →?
(7) F → (E) (8) F → a
89
消除一般左递归 要求文法,
1.无回路 (A(=>+(A) 2.无空产生式
（ 1）,以某种顺序将文法非终结符排列 A1,A2 …An
（ 2） for i:=1 to n do
begin
for j:=1 to i-1 do
用 Ai-->?1|?2r…|? k r替代形如 Ai--> Ajr的规则,其中
Aj-->?1|?2…|?k是关于 Aj的全部产生式 ;
消除 Ai规则的直接左递归 ;
end;
（ 3） 化简由 2得到的文法
90
化简文法 文法实用中的一些说明文法中 不含有 有害规则 和 多余规则有害规则,形如 U→ U的产生式。会 引起 文法的 二义性多余规则,指文法中 任何句子的推导 都 不会用到的规则文法中 不含有 不可到达和不可终止的 非终结符
1）文法中某些 非终结符不在任何规则的右部出现,
该非终结符称为 不可到达 。
2）文法中某些 非终结符,由它 不能推出终结符号串,该非终结符称 为 不可终止 。
91
对于文法 G[S]，为了保证任一非终结符 A在句子 推导中出现，必须满足如下两个条件：
1,A必须在某句型中出现即有 S =>* αAβ，其中 α,β属于 V*
2,必须能够从 A推出终结符号串 t来即 A =>* t，其中 t∈ VT*
92
化简文法
例,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）为 多余规则 应去 掉。
93
上下文无关文法中的 ε规则上下文无关文法中某些规则可具有形式 A→ ε，称这种规则为 ε规则因为 ε规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现两种定义的唯一差别是 ε句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言 L有一个有穷的描述，则 L1=L∪ ｛ ε｝也同样有一个有穷的描述，并且可以证明，若 L是上下文有关语言、上下文无关语言或正规语言，则
L∪ ｛ ε｝和 L-｛ ε｝分别是上下文有关语言、上下文无关语言和正规语言。
94
思考本章目的为语言的语法描述寻求工具,以便：
对源程序给出精确无二义的语法描述。（严谨、简洁、
易读）
根据语言文法的特点来进行语法分析从描述语言的文法可以自动构造出可用的分析程序制导语义翻译
1.什麽是文法,什麽是它的语言?
2.我们为什麽关注上下文无关文法?
3.语法分析方法的分类?
95
[本章小结 ]
1.本章出现的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念,语法分析有关内容在后面章节会详细讨论,
2.文法作为程序语言的语法的描述工具,它用 规则只能陈述的是,语言的所有句子以什麽样的符号串能出现,请记住 文法和语言的形式定义中的,形式”的含义 — 只涉及 语言的语法不涉及语言的语义,
3.本章内容是形式语言理论的一部分,形式语言理论是对符号串集合的表示法,结构及其特性的研究 。
是程序设计语言语法分析研究的基础 。
[本章小结 ]
考察本章知识点最典型的题目是
1.已知文法 G[A]，写出它定义的语言描述如,G[A],A → 0B|1C
B → 1|1A|0BB
C → 0|0A|1CC
答案,G[A]定义的语言由 0,1符号串组成，串中 0和 1的个数相同,
2.给出语言描述，构造文法,
如：构造一文法,其定义的语言是由算符 +,*,(,)和运算对象 a构成的算术表达式的集合,
答案 1,G[E] E→E+T|T
T→T*F|F
F→(E)|a
答案 2,G[E] E→E+E|E*E|(E)|a
97
相关术语的回顾（ 英 文版）
上下文无关文法
A context free grammar(grammar for short) consists of
terminals,nonterminals,a start symbol,and productions.
Terminals are the basic symbols from which strings are
formed.
Nonterminals are syntactic variables that denote sets of
strings that help define the language generated by the
grammar.
In a grammar,one nonterminal is distinguished as the start
symbol,and the set of strings it denotes is the language
defined by the grammar.
The productions of a grammar specify the manner in which
the terminals and nonterminals can be combined to form
string.
98
句型句子和语言
Given a grammar G with start symbol S,we can use
the =>* relation to define L(G),the language
generated by G,Strings in L(G) may contain only
terminal symbols of G.
We say a string of terminals w is in L(G) if and
only if S =>* w,The string w is called a
sentence of G,
If S =>* α,wher α may contain nonterminals then
we say that α is a sentential form of G
99
验证文法生成的语言
A proof that a grammar G generates a
language L has two parts:we must show
that every string generated by G is in
L,and coversely that every string in L can
indeed be generated by G.
100
语法树和推导
A parse tree may be viewed as a graphical
representation for a derivation that filt out
the choice regarding replacement order,
The leaves of the parse tree are labeled
by nonterminals or terminals and,read
from left to right,they constitute a
sentential form,called the yield or frontier
of the tree.
101
句型分析，语法分析
Parsing is the process of determing if a string of
token can be generated by a grammar,
Most parsing methods fall into one of two
classes,called the top-down and bottom-up
methods.
These terms refer to the order in which nodes in
the parse tree are constructed.In the
former,construction starts at the root and
proceeds towards the leaves,while,in the
later,construction starts at the leaves and
proceeds towards the root.
102
二义性
A grammar that produces more than one parse tree for some
setence is said to be ambiguous,Put another way,an
ambiguous grammar is one that produces more than one
leftmost or more than rightmost derivation for the same
sentence.
Sometimes an ambiguous grammar can be rewritten to
eliminate the ambiguity,For exmple suitable grammars for
expression can often be constructed using associativity and
precedence information,as in the slide74
103
消除左递归规则
A grammar is left recursive if it has a nonterminal A such that there is
a derivation A =>+ Aα for some string α,
A left-recursive production is like:A →A α in which the leftmost
symbol on the right side is the same as the nonterminal on
the left side.
The general case is that a nonterminal A with two productions
A →A α | β where α and β are sequences of terminals and
nonterminals that do not start with A,And the left recursive pair of
productions A →A α | β could replaced by the non-left-recursive
productions,A → β A’
A’ → α A’| ε
Here A’ is a new nonterminal,The production A’ → α A’ is right
recursive.
104
练习
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是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
105
练习
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
文法的直观概念和 语言概述当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。
以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明 (或者定义 )句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第 2章所介绍的 EBNF来表示这种句子的构成规则：
4
“我是大学生,。是汉语的一个句子
〈 句子 〉 ∷ =〈 主语 〉〈 谓语 〉
〈 主语 〉 ∷ =〈 代词 〉 ｜ 〈 名词 〉
〈 代词 〉 ∷ =我 ｜ 你 ｜ 他
〈 名词 〉 ∷ =王明 ｜ 大学生 ｜ 工人 ｜ 英语
〈 谓语 〉 ∷ =〈 动词 〉〈 直接宾语 〉
〈 动词 〉 ∷ =是 ｜ 学习
〈 直接宾语 〉 ∷ =〈 代词 〉 ｜ 〈 名词 〉
5
有了一组规则以后，按照如下方式用它们导出句子：开始去找
∷ =左端的带有 〈 句子 〉 的规则并把它由 ∷ =右端的符号串代替，这个动作表示成：
〈 句子 〉?〈 主语 〉〈 谓语 〉,
然后在得到的串 〈 主语 〉〈 谓语 〉 中，选取 〈 主语 〉 或 〈 谓语 〉,再用相应规则的 ∷ =右端代替之。比如，选取了 〈 主语 〉,并采用规则 〈 主语 〉 ∷ =〈 代词 〉,
那么得到,〈 主语 〉〈 谓语 〉?〈 代词 〉〈 谓语 〉,
重复做下去，
句子：,我是大学生,的全部动作过程是：
〈 句子 〉?〈 主语 〉〈 谓语?〈 代词 〉〈 谓语 〉
我 〈 谓语?我 〈 动词 〉〈 直接宾语 〉
我是 〈 直接宾语 〉?我是 〈 名词 〉?我是大学生
6
“我是大学生,的构成符合上述规则，而,我大学生是,不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。
7
英语句子
sentence –> <subject> <verb-phrase> <object>
subject –> This | Computers | I
verb-phrase –> <adverb> <verb> | <verb>
adverb –> never
verb –> is | run | am | tell
object –> the <noun> | a <noun> | <noun>
noun –> university | world | cheese | lies
This is a university.
Computers run the world.
I am the cheese.
I never tell lies.
8
语言概述语言是由句子组成的集合，是由一组符号所构成的集合。
汉语 --所有符合汉语语法的句子的全体英语 --所有符合英语语法的句子的全体程序设计语言 --所有该语言的程序的全体每个句子构成的规律研究语言 每个句子的含义每个句子和使用者的关系
9
研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法 Syntax
语义 Semantics
语用 Pragmatics
10
语法 -- 表示构成语言句子的各个记号之间的组合规律语义 -- 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）
语用 --表示在各个记号所出现的行为中，它们的来源、使用和影响。
11
每种语言具有两个可识别的特性,即语言的形式和该形式相关联的意义 。
语言的实例若在语法上是正确的,其相关联的意义可以从两个观点来看,其一是该句子的创立者所想要表示的意义,另一是接收者所检验到的意义 。 这两个意义并非总是一样的,前者称为语言的语义,后者是其语用意义 。 幽默,双关语和谜语就是利用这两方面意义间的差异 。
12
如果不考虑语义和语用,即只从语法这一侧面来看语言,这种意义下的语言称作形式语言 。 形式语言抽象地定义为一个数学系统 。
,形式,是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述 。 形式语言理论是对符号串集合的表示法,结构及其特性的研究 。 是程序设计语言语法分析研究的基础 。
13
有关定义和记号 — 回 顾符号：可以相互区别的记号（元素）。
字母表?：符号（元素）的非空有穷集合。
符号串：由字母表?中的符号组成的任何有穷序列称为该字母表上的符号串。 1.空符号串
ε (没有 符号的符号串 )是?上的符号串 2.若 x
是?上的符号串,a是?的元素,则 xa是?上的符号串 3,y是?上的符号串,当且仅当它可以由 1和 2
导出。
例如,Σ ={a,b}
ε,a,b,aa,ab,aabba… 都 是?上的符号串
14
有关定义和记号 — 回 顾符号串 s的头（前缀）：移走符号串 s尾部的零个或多于零个符号得到的符号串,
如,b是符号串 banana的一个前缀,
符号串 s的尾（后缀）：删去符号串 s头部的零个或多于零个符号得到的符号串,
如,nana是符号串 banana的一个后缀,
符号串 s的子串：从 s中删去一个前缀和一个后缀得到的符号串,
如,ana是符号串 banana的一个子串,
15
对于每个符号串 s,s和 ε 两者 都 是符号串 s的前缀，后缀和子串。
符号串 s的真前缀，真后缀，真子串：任何非空符号串 x,相应地，是 s的前缀，后缀或子串，
并且 s? x
符号串的运算符号串的长度：符号串中符号的个数,符号串 s的长度记为 |s|。 ε 的长度为 0
连接：符号串 x,y的连接,是把 y的符号写在 x的符号之后得到的符号串 xy
如 x=ab,y=cd 则 xy=abcd 有 ε a = aε
方幂：符号串自身连接 n次得到的符号串
an 定义为 aa… aa n个 a a1=a,a2=aa则 a0=ε
16
符号串集合：若集合 A中所有元素都是某字母表?上的符号串，则称 A为字母表?上的符号串集合。
两个符号串集合 A和 B的乘积定义为
AB =?xy|x?A且 y?B?
若 集合 A=?ab,cde? B =?0,1?
则 AB =?ab1,ab0,cde0,cde1?
使用?* 表示?上的一切符号串（包括 ε ）组成的集合。 Σ *称为 Σ 的闭包 。
上的 除 ε 外 的所有符号串组成的集合记为
+ 。 Σ +称为 Σ 的正闭包 。
17
例,Σ ={a,b}
Σ *={ε,a,b,aa,ab,ba,bb,aaa,aab,… }
Σ +={a,b,aa,ab,ba,bb,aaa,aab,… }
......}{ 2*
.,,,,,}{ 32**
18
有关定义和记号语言 是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表?上 的一个语言是?上的一些符号串的集合 (字母表
上 的每个语言是?*的一个子集 )。
例如,字母表 Σ ={a,b},Σ *={ε,a,b,aa,ab,ba,bb,aaa,aab,… }
集合 {ab,aabb,aaabbb,…,anbn,… }
或表示为 {w|w∈ Σ *且 w=anbn,n≥1} 为 字母表?上 的一个语言。
集合 {a,aa,aaa,… }
或 表示为 {w|w∈ Σ *且 w=an,n≥1} 为 字母表?上 的一个语言。
ε?是一个语言。
即是一个语言 。
19
给出语言 上 的有关运算设 L是（?上的）一个语言,M是（?上的）一个语言,语言 L和 M的并，交，差，补 是一个语言。
语言 L和 M的并为 L?M,是一个语言,{w|w is
in L or is in M}
如,L1 ={a,b,… y,z} M1 ={1,2… 8,9 }
L1?M1={a,b,… y,z,1,2… 8,9 }
语言 L和 M的连接 是一个语言，记 为 LM
LM={st |s∈ L且 t∈ M}
如,L1M1 ={a1,b1,… y1,z1,a2,b2… a9… z9}
有 L?ε?=?ε?L=L。 L的 n次连接 Ln= LL...L
20
语言 上 的运算语言 L的 闭包 记 为 L*,L*= L0? L1? L2?,.,
L0=?ε?,Ln= L Ln-1= Ln-1 L,n?1
语言 L的正 闭包 记 为 L+,L+= L1? L2? L3,.,
L+= LL*= L*L
L*= L+ε?
如,L1 ={a,b,… y,z} M1 ={1,2… 8,9 }
（ L1?M1） ={a,b,… y,z,1,2… 8,9}
（ L1?M1） *={a,b,… y,z,1,2… 8,9，
aa,1a,…xyz,6789st..}
L1（ L1?M1） *={所有字母打头的字母和数字符号串 }
21
文法和语言的形式定义如何来描述一种语言？
如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。
识别方式 （自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）
22
文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造,下面给出文法的定义,进而在 文法的定义的基础上,给出 推导的概念,句型、句子和语言的定义,
23
定义文法 G定义为四元组 (VN,VT,P,S )其中
VN为非终结符号 (或语法实体，或变量 )集；
VT为终结符号集；
P为产生式 (也称规则 )的集合； VN,VT和 P是 非空有穷集。
S称作识别符号或开始符号，它是一个非终结符，
至少要在一条产生式中作为左部出现。
VN和 VT不含公共的元素，即 VN ∩ VT = φ
用 V表示 VN ∪ VT,称为文法 G的字母表或字汇表规则,也称 重写规则,产生式 或 生成式,是形如
α→ β或 α∷ =β的 (α,β)有序对，其中 α是字母表 V
的正闭包 V+中的一个符号,β是 V*中的一个符号。
α称为规则的左部,β称作规则的右部。
24
Define a grammar
A grammar G is defined as a 4-tuple (VN,VT,P,S )
VN is a set of nonterminals
VT is a set of terminals
P is a set of productions,each production
consists of a left side,an arrow(or ‘::=‘),and a
right side
S is a designation of one of the nonterminals
as the start symbol
V =VN ∪ VT is the alphabet of G
25
文法的定义例 文法 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=<标识符 >
27
文法的写法
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
元 符号,→
∷=
|
< >
习惯表示大写字母：终结符小写字母：非终结符
S –> AB
A –> Ax | y
B –> z
29
推导的定义直接推导,?”
α → β 是文法 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
30
<程序 >?<分程序 >,
<分程序 >,? <变量说明部分 > <语句 >,
VAR<标识符 >;BEGIN READ(<标识符 >)END,?
VAR A;BEGIN READ(<标识符 > ) END.
31
推导的定义若存在 v?w0?w1?..,?wn=w,(n>0)
则记为 v =>+ w,v推导出 w，或 w归约到 v
若有 v =>+ w，或 v=w，
则记为 v =>* w
32
例,G,S→ 0S1,S→ 01
0S1?00S11
00S11?000S111
000S111?00001111
S?0S1?00S11?000S111?00001111
S =>+ 00001111
S =>* S 00S11 =>* 00S11
33
What are Derivations
Derivation is a way that a grammar defines a language,In
the process of derivation a production is treated as a
rewriting rule in which the nonterminal on the left side is
replaced by the string on the right side of the production
A production u –> v is used by replacing an occurrence of
u by v,Formally,if we apply a production pP to a
string of symbols w in V to yield a new string of symbols
z in V,we say that z derived from w using p,written as
follows,w =>p z,We also use:
w => z z derives from w (production unspecified)
w =>* z z derives from w using zero or more productions
w =>+ z z derives from w using one or more productions
34
句型、句子的定义句型有文法 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
35
例,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,+,*,(和 )构成的算术表达式
36
文法，语言的定义由文法 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 }
38
S?a S BE (S→ aSBE)
a aBEBE (S→ aBE)
aabEBE ( aB→ ab )
aabBEE ( EB→ BE )
aabbEE （ bB→ bb)
aabbeE （ bE→ be)
aabbee （ eE→ ee)
G生成的每个串都在 L(G)中
L(G)中的每个串确实能被 G生成
39
使用产生式 (1)n-1次，得到推导序列：
S =>* an-1S(BE)n-1，然后使用产生式 (2)一次，得到：
S =>* an-1S(BE)n-1? an(BE)n。然后从 an(BE)n继续推导，总是对 EB使用产生式 (3)的右部进行替换，而最终在得到的串中，所有的 B都先于所有的 E。例如，若 n=3,
aaaBEBEBE? aaaBBEEBE? aaaBBEBEE
aaaBBBEEE。即有：
S =>* anBnEn
接着，使用产生式 (4)一次，得到 S =>* anbBn-1En，然后使用产生式 (5)n-1次得到：
S =>* anbnEn，最后使用产生式 (6)一次，使用产生式
(7)n-1次，得到,S =>* anbnen
也能证明，对于 n≥1，串 anbnen是唯一形式的终结符号串
40
文法的等价
若 L（ G1） =L（ G2），则称文法 G1和 G2是等价的。
如文法 G1[A],A→0R 与 G2[S],S→0S1 等价
A→01 S→01
R→A1
41
文法的类型通过对产生式施加不同的限制,Chomsky将文法分为四种类型：
0型文法：对任一产生式 α → β,都有
α ∈(V N∪V T)+,β ∈(V N∪V T)*
1型文法,对任一产生式 α → β,都有 |β |≥| α |，
仅仅 S→ ε 除外
2型文法,对任一产生式 α → β,都有 α ∈V N,
β ∈(V N∪V T)*
3型文法,任一产生式 α → β 的形式都为 A→aB 或
A→a,其中 A∈V N,B∈V N,a∈V T
42
A hierarchy of grammars
Type 0,free or unrestricted grammars
These are the most general,Productions are of the form u
–> v where both u and v are arbitrary strings of
symbols in V,with u non-null,There are no
restrictions on what appears on the left or right-hand
side other than the left-hand side must be non-empty.
Type 1,context-sensitive grammars
Productions are of the form uXw –> uvw where u,v and
w are arbitrary strings of symbols in V,with v non-null,
and X a single nonterminal,In other words,X may be
replaced by v but only when it is surrounded by u and w,
(i.e,in a particular context).
43
Type 2,context-free grammars
Productions are of the form X–> v where v is an
arbitrary string of symbols in V,and X is a single
nonterminal,Wherever you find X,you can replace
with v (regardless of context).
Type 3,regular grammars
Productions are of the form X–> a or X–> aY where X
and Y are nonterminals and a is a terminal,That is
the left-hand side must be a single nonterminal and
the right-hand side can be either a single terminal by
itself or with a single nonterminal,These grammars
are the most limited in terms of expressive power.
44
文法的类型例,1型（上下文有关）文法文法 G[S],S→CD Ab→bA
C→aCA Ba→aB
C→bCB Bb→bB
AD→aD C→ ε
BD→bD D→ ε
Aa→bD
45
文法的类型例,2型（上下文无关）文法文法 G[S],S→AB
A→BS|0
B→SA|1
46
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
47
文法的类型
2型文法
1型文法
0型文法四种 文法 之间 的 逐级,包含,关系
3型文法
48
文法和语言
0型文法产生的语言称为 0型语言
1型文法或上下文有关文法（ CSG ） 产生的语言称为 1型语言 或上下文有关 语言（ CSL）
2型文法或上下文无关文法（ CFG ） 产生的语言称为 2型语言 或上下文无关 语言（ CF L ）
3型文法或正则（正规）文法（ RG ） 产生的语言称为 3型语言 正则（正规） 语言（ RL ）
49
文法和语言四种文法之间的关系 是将产生式做进一步限制而定义的。
语言之间的关系依次：有不是上下文有关语言的 0型语言，有不是上下文无关语言的
1型语言，有不是正则语言的上下文无关语言。
50
根据形式语言理论,文法和识别系统间有这样的关系
0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何 0型语言都是递归可枚举的
1型文法（上下文有关文法）：产生式的形式为 α 1Aα 2→ α 1βα2，即只有 A出现在 α 1
和 α 2的上下文中时，才允许 β 取代 A。其识别系统是线性界限自动机。
51
带 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an-1 an
有限控制器磁头任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述
52
2型文法（上下文无关文法 CFG）：产生式的形式为 A→ β,β 取代 A时与 A的上下文无关。其识别系统是不确定的下推自动机。
3型文法（正规文法 RG）：产生的语言是有穷自动机（ FA）所接受的集合
53
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)=φ
54
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
55
定理 已知一有穷自动机 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中
56
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
57
正规文法和正规式对?上的正规式 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做变换，直到每个产生式右端至多有一个 VN
58
例 r=a(a?d)?
S?a(a?d)?
S?aA A?(a?d)?
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
59
正规文法和正规式对 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
60
正规文法和正规式
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)?
61
上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构语法树 ---句型推导 的 直观表示
62
例文法 G=(｛ E｝,｛ +,*,i,(,)｝,P,E)其中 P为：
{E→i,E→E+E,E→E*E,E→(E) }
E表示算术表达式,i表示程序的,变量,,该文法定义了由变量,+,*,(和 )组成的算术表达式的语法结构，即：
变量是算术表达式；若 E1和 E2是算术表达式，则 E1+
E2,E1*E2和 (E1)也是算术表达式
描述一种简单赋值语句的产生式：
〈 赋值语句 〉 →i ∶ =E
描述条件语句的产生式：
〈 条件语句 〉 →if 〈 条件 〉 then〈 语句 〉 ｜
if〈 条件 〉 then〈 语句 〉 else〈 语句 〉
63
句型、推导
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
64
规范推导 规范句型最左（最右）推导：在推导的任何一步
α?β,其中 α,β 是句型，都是对 α 中的最左（右）非终结符进行替换最右推导被称为规范推导。
由规范推导所得的句型称为规范句型
65
语法树设 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中的一个产生式语法树的结果：
从左到右读出叶子的标记而构成的行谓之
66
语法树 ---句型推导 的 直观表示给定文法 G=(VN,VT,P,S)，对于 G的任何句型都能构造与之关联的语法树 (推导树 )
定理：
G为上下文无关文法，
对于 α ≠ ε,有 S =>* α,当且仅当文法 G有以 α 为结果的一棵语法树 (推导树 )
67
构造语法树
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
E + T E + T
T
E
E + T
T
F
68
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
E
E + T
T T * F
F F a
a a
看不出句型中的符号被替代的顺序
69
上下文无关文法的语法树的用处用于描述上下文无关文法 句型推导 的 直观方法例,G[S]:
S→ aAS
A→ SbA
A→ SS
S→ a
A→ ba
S
a A S
S b A a
a b a
句型 aabbaa的 语法树 （推导树）
叶子结点,树中 没有子孙的结点 。
从左到右 读出推导树的 叶子标记 连接成的 文法符号 串,为 G[S]的 句型 。也把该推导树称为该 句型 的 语法树 。
70
上下文无关文法的语法树
推导过程中 施用 产生式 的 顺序例,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
71
一棵语法树表示了一个句型的种种可能的 (但未必是所有的 )不同推导过程，包括最左
(最右 )推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左 (最右 )推导呢?
72
例,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
73
二义文法若一个文法存在某个句子对应两棵不同的语法树，
则称这个文法是 二义 的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是 二义 的判定任给的一个上下文无关文法是否二义，
或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件
74
文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法 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) 规定优先顺序和结合律如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。
75
句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型,是某个 推导 的构造过程。
在语言的编译实现中，把 完成句型分析 的 程序 称为 分析程序 或 识别程序 。分析算法又称 识别算法 。
从左到右的分析算法,即 总是从 左 到 右 地 识别输入符号串,首先识别符号串中的 最左符号，进而 依次识别右边 的一个符号,直到分析结束 。
76
句型的 分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,反复使用文法的产生式,寻找 与 输入符号串 匹配 的 推导 。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
77
两种方法反映了两种语法树的构造过程。
自上而下方法 是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法 则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树
78
自上而下的语法分析例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否为该文法的 句子
S S S
c A d c A d
a b
推导过程,S? cAd cAd? cabd
79
自下而上的语法分析例：文法 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
80
(1)S → cAd (2) A → ab (3)A → a
识别输入串 w=cabd是否为该文法的 句子自上而下的语法分析若 S? cAd 后选择 (3)扩展 A，
S? cAd? cad
那将会？
w的第二个符号可以与叶子结点 a得以匹配，但第三个符号却不能与下一叶子结点 d
匹配
？宣告分析失败（其意味着，
识别程序不能为串 cad构造语法树，即 cad不是句子）
-显然是错误的结论。
导致失败的原因是在分析中对
A的选择不是正确的。
S
c A d
a
81
(1)S → cAd (2) A → ab (3)A → a
识别输入串 w=cabd是否为该文法的 句子自下而上的语法分析对串 cabd的分析中，如果不是选择 ab用产生式 (2),而是选择 a用产生式 (3)将 a归约到了 A，
那么最终就达不到归约到 S的结果，因而也无从知道 cabd是一个句子
c a b d
c A b d
a
82
句型分析的有关问题
1）在自上而下的分析方法中 如何 选择 使用 哪个 产生式进行推导？
假定要被代换的最左非终结符号是 B，且有 n条规则,B→ A1|A2|…|An,那么如何确定用哪个右部去替代 B？
2）在自下而上的分析方法中 如何 识别可归约的串？
在分析程序工作的每一步，都是从当前串中 选择一个 子串,将它 归约 到 某个非终结符号,该子串称为,可归约串,
83
刻画,可归约串,
文法 G[S]
句型的短语
S =>* α Aδ 且 A =>+ β,则称 β 是 句型 α β δ
相对于非终结符 A的 短语句型的直接短语若有 A?β,则称 β 是句型 α β δ 相对于非终结符 A 的 直接短语句型的句柄一个句型的 最左直接短语 称为 该句型 的 句柄
84
例,i*i+i 的短语、直接短语和句柄
E
E + T
T F
T * F
i3 短语,i1*i2+ i3,i1* i2,
F i2 i1,i2,i3 。
i1 直接短语,i1,i2,i3 。 句柄,
i1
G[E],E→E+T|T
T→T*F|F
F→(E)|i
句型,i*i+i
85
左递归规则 --
G[S],S→Sa
S→b L={ba n | n≥0}
W=baaa S
b
S
S a
S a
86
左递归 关于非终结符 P的规则直接左递归 若 P → P α | β
α,β ∈V *且 β 不以 P开头一般 左递归 若 P =>* P α
S→Aa
A→Sb
…
87
消除左递归消除直接左递归形如,P → P α | β
α 非?,不以 P打头改写为,P → β Q
Q → α Q|?
88
消除左递归例,E → E+T|T
T →T*F|F
F →(E)| a
G[ E],(1) E → TE’ (2) E’ → +TE’
(3) E’ →? (4) T → FT’
(5) T’ → *FT’ (6) T’ →?
(7) F → (E) (8) F → a
89
消除一般左递归 要求文法,
1.无回路 (A(=>+(A) 2.无空产生式
（ 1）,以某种顺序将文法非终结符排列 A1,A2 …An
（ 2） for i:=1 to n do
begin
for j:=1 to i-1 do
用 Ai-->?1|?2r…|? k r替代形如 Ai--> Ajr的规则,其中
Aj-->?1|?2…|?k是关于 Aj的全部产生式 ;
消除 Ai规则的直接左递归 ;
end;
（ 3） 化简由 2得到的文法
90
化简文法 文法实用中的一些说明文法中 不含有 有害规则 和 多余规则有害规则,形如 U→ U的产生式。会 引起 文法的 二义性多余规则,指文法中 任何句子的推导 都 不会用到的规则文法中 不含有 不可到达和不可终止的 非终结符
1）文法中某些 非终结符不在任何规则的右部出现,
该非终结符称为 不可到达 。
2）文法中某些 非终结符,由它 不能推出终结符号串,该非终结符称 为 不可终止 。
91
对于文法 G[S]，为了保证任一非终结符 A在句子 推导中出现，必须满足如下两个条件：
1,A必须在某句型中出现即有 S =>* αAβ，其中 α,β属于 V*
2,必须能够从 A推出终结符号串 t来即 A =>* t，其中 t∈ VT*
92
化简文法
例,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）为 多余规则 应去 掉。
93
上下文无关文法中的 ε规则上下文无关文法中某些规则可具有形式 A→ ε，称这种规则为 ε规则因为 ε规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现两种定义的唯一差别是 ε句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言 L有一个有穷的描述，则 L1=L∪ ｛ ε｝也同样有一个有穷的描述，并且可以证明，若 L是上下文有关语言、上下文无关语言或正规语言，则
L∪ ｛ ε｝和 L-｛ ε｝分别是上下文有关语言、上下文无关语言和正规语言。
94
思考本章目的为语言的语法描述寻求工具,以便：
对源程序给出精确无二义的语法描述。（严谨、简洁、
易读）
根据语言文法的特点来进行语法分析从描述语言的文法可以自动构造出可用的分析程序制导语义翻译
1.什麽是文法,什麽是它的语言?
2.我们为什麽关注上下文无关文法?
3.语法分析方法的分类?
95
[本章小结 ]
1.本章出现的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念,语法分析有关内容在后面章节会详细讨论,
2.文法作为程序语言的语法的描述工具,它用 规则只能陈述的是,语言的所有句子以什麽样的符号串能出现,请记住 文法和语言的形式定义中的,形式”的含义 — 只涉及 语言的语法不涉及语言的语义,
3.本章内容是形式语言理论的一部分,形式语言理论是对符号串集合的表示法,结构及其特性的研究 。
是程序设计语言语法分析研究的基础 。
[本章小结 ]
考察本章知识点最典型的题目是
1.已知文法 G[A]，写出它定义的语言描述如,G[A],A → 0B|1C
B → 1|1A|0BB
C → 0|0A|1CC
答案,G[A]定义的语言由 0,1符号串组成，串中 0和 1的个数相同,
2.给出语言描述，构造文法,
如：构造一文法,其定义的语言是由算符 +,*,(,)和运算对象 a构成的算术表达式的集合,
答案 1,G[E] E→E+T|T
T→T*F|F
F→(E)|a
答案 2,G[E] E→E+E|E*E|(E)|a
97
相关术语的回顾（ 英 文版）
上下文无关文法
A context free grammar(grammar for short) consists of
terminals,nonterminals,a start symbol,and productions.
Terminals are the basic symbols from which strings are
formed.
Nonterminals are syntactic variables that denote sets of
strings that help define the language generated by the
grammar.
In a grammar,one nonterminal is distinguished as the start
symbol,and the set of strings it denotes is the language
defined by the grammar.
The productions of a grammar specify the manner in which
the terminals and nonterminals can be combined to form
string.
98
句型句子和语言
Given a grammar G with start symbol S,we can use
the =>* relation to define L(G),the language
generated by G,Strings in L(G) may contain only
terminal symbols of G.
We say a string of terminals w is in L(G) if and
only if S =>* w,The string w is called a
sentence of G,
If S =>* α,wher α may contain nonterminals then
we say that α is a sentential form of G
99
验证文法生成的语言
A proof that a grammar G generates a
language L has two parts:we must show
that every string generated by G is in
L,and coversely that every string in L can
indeed be generated by G.
100
语法树和推导
A parse tree may be viewed as a graphical
representation for a derivation that filt out
the choice regarding replacement order,
The leaves of the parse tree are labeled
by nonterminals or terminals and,read
from left to right,they constitute a
sentential form,called the yield or frontier
of the tree.
101
句型分析，语法分析
Parsing is the process of determing if a string of
token can be generated by a grammar,
Most parsing methods fall into one of two
classes,called the top-down and bottom-up
methods.
These terms refer to the order in which nodes in
the parse tree are constructed.In the
former,construction starts at the root and
proceeds towards the leaves,while,in the
later,construction starts at the leaves and
proceeds towards the root.
102
二义性
A grammar that produces more than one parse tree for some
setence is said to be ambiguous,Put another way,an
ambiguous grammar is one that produces more than one
leftmost or more than rightmost derivation for the same
sentence.
Sometimes an ambiguous grammar can be rewritten to
eliminate the ambiguity,For exmple suitable grammars for
expression can often be constructed using associativity and
precedence information,as in the slide74
103
消除左递归规则
A grammar is left recursive if it has a nonterminal A such that there is
a derivation A =>+ Aα for some string α,
A left-recursive production is like:A →A α in which the leftmost
symbol on the right side is the same as the nonterminal on
the left side.
The general case is that a nonterminal A with two productions
A →A α | β where α and β are sequences of terminals and
nonterminals that do not start with A,And the left recursive pair of
productions A →A α | β could replaced by the non-left-recursive
productions,A → β A’
A’ → α A’| ε
Here A’ is a new nonterminal,The production A’ → α A’ is right
recursive.
104
练习
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是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
105
练习
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
