编 译 原 理 指导教师:杨建国 二零一零年三月

第三章 文法和语言 第一节 文法的直观概念 第二节 符号和符号串 第三节 文法和语言的形式定义 第四节 文法的类型 第三章　文法和语言 第一节 文法的直观概念 第二节 符号和符号串 第三节 文法和语言的形式定义 第四节 文法的类型 第五节 上下文无关文法及其语法树 第六节 句型分析 第七节 有关文法实用中的一些说明 第八节 典型例题及解答

知识结构

第三章 文法和语言 3.1 文法的直观概念 所谓一个语言的语法是指一组规则，用它可以形成和产生 一个合适的程序 　一个合适的程序 目前广泛使用的手段是上下文无关文法，即用上下文无关 　文法作为程序设计语言语法的描述工具

程序设计语言的描述： 语法：程序的结构或形式 语义：语言所代表的含义 语用：语言的实际应用

例如，对于赋值语句 x : = a + b * c 的非形式描述是： 语法：赋值语句＝变量＋:=＋表达式 语义：先求右部，然后把结果给左部变量 语用：赋值语句可用来计算和保存表达式的值 形式化方法：用一整套带有严格规定的符号体系来描述问 　题的理论和方法 形式语言：一种不考虑含义的符号语言

程序设计语言的语义分成： 静态语义：是一系列限定规则，并确定哪些合乎语法的程 　序是合适的 动态语义（运行语义、执行语义）：表明程序要做什么， 　要计算什么

以自然语言为例，人们无法列出全部句子，但是人们可以 　给出一些规则，用这些规则来说明（或者定义）句子的组 　成结构：

例如, 有一组规则: < 句子 > :: = < 主语 > < 谓语 > < 主语 > :: = < 冠词 > < 形容词 > < 名词 > < 冠词 > :: = the < 冠词 > :: = a < 形容词 > :: = big < 谓语 > :: = < 动词 > < 直接宾语 > 　　 < 动词 > :: = ate < 直接宾语 > :: = < 冠词 > < 名词 > < 名词 > :: = cat < 名词 > :: = mouse 　　显然, 由这一组规则可以产生句子: 　　The big cat / mouse ate a mouse / cat

这样的语言描述称为文法 使用文法作为工具，不仅为了严格地定义句子的结构， 　 也是为了适当条数的规则把语言的全部句子描述出来， 可以说文法是以有穷的集合刻画无穷的集合的一个工具

3.2 符号和符号串 一.字母表和符号串 1.语言可以看成在一个基本符号集上定义的，按一定规则 构成的一切基本符号串组成的集合 　构成的一切基本符号串组成的集合 2.字母表（符号集）：是一个非空有穷集合 3.符号（字符）：字母表中的元素 4.符号串：符号的有穷序列。注意： 表示空符号串！ 5.符号串集合：字母表上若干个符号串组成的集合

重要约定： 小写字母 a, b, c, ••• , r 表示符号 小写字母 s, t, u, ••• , z 表示符号串 大写字母 A, B, C, ••• , Z 表示符号串集合

二.符号串的运算 1.符号串相等：设 x 、y 是字母表  上的两个符号串，若 x 　与 y 的诸符号依次相等，则该两符号串相等，记为 x = y 　例：x=ab, y=ba, x=y?

2.符号串长度：设 x 是字母表上的符号串，符号串中包含 　符号的个数称为符号串 x 的长度，用 x 表示 例: (1). | abc | = ? (2). |  | = ? (3). | a x | = | x a | = | x | + 1 ( a ∈∑ )

3. 符号串的连结：设 x 与 y 是字母表  上的两个符号串， 　把 y 的所有符号相继写在 x 的符号之后所得到的符号串 　称为x 与 y 的连结，用 x y 表示 　注意: | x y | = | x | + | y |  x = x  = x x y ≠ y x ( 一般说来 )

4 .符号串的逆：设 x 是字母表  上的符号串，其逆为符号串 x 　的倒置，记为 。 . 若 x = abcd , 则 = ? (2). = 

5.符号串的前缀、后缀和子串：设 x、y、z 是字母表  上的 　符号串，则称 x 为符号串 x y 的前缀，y 是符号 串 x y 的 　后缀， x、y 、 z 、xy 、yz 是符号串 x y z 的子串 　例: abcd前缀、后缀、子串是什么？

6.符号串集合的乘积：设A、B为两个符号串集合，其乘积为 AB={xy|xA,y B} 例: (1). 若 A = { ab, cd }, B = { ef, gh } ，AB＝？ (2). ∵  x = x  = x ∴ {  } A = A {  } = A

7.空集：不含任何元素的集合，记为 Ø 注意: (1). Ø A = A Ø = Ø (2).   Ø

8.符号串的幂：设 x 是字母表  上的符号串，则 x 的幂运算 　为x 0 =  x 1=x x 2=xx •••••• x n=x n-1x (xx n-1) 　例: 若 x = ab 则: x 0 = ?, x 1 = ?, x 2 = ?, ••••••, 　　　x n = ?

9.符号串集合的幂：设 A 是符号串集合，则符号串 A 的幂运 　算为： A0={} A1=A A2=AA •••••• An=A n-1A (AA n-1) 　例: 若 A = { ab, cd } ,则: A 0 = ?, A 1 = ?, A 2 = ?, ••••••

则: A*= {, a, b, aa, ab, ba, bb, aaa, ••• } 注意: A*=A0∪A+ A+=AA*=A*A 若 A = { a, b } 则: A*= {, a, b, aa, ab, ba, bb, aaa, ••• } A+= {a, b, aa, ab, ba, bb, aaa, ••• }

3.3 文法和语言的形式定义 规则（重写规则、产生式、生成式）： 一个规则是一个二元组,通常写作α::= β 或 α β 　一个规则是一个二元组,通常写作α::= β 或 α β α称为规则的左部，β称为规则的右部， (::=)读作 　“定义为”，这是一条关于α的规则（产生式）

定义3.1：文法G定义为四元组（VN，VT，P，S） P：规则（α　 β）集合，α∈(VN∪VT)*且至少包含 　一个非终结符，β ∈(VN∪VT)* VN、VT、P是非空有穷集 S：开始符（识别符），它是一个非终结符，至少要在一 　条规则中作为左部出现 VN∩VT= Ø V=VN∪VT，称为文法G的字母表（字汇表）

例3.1 文法G=（VN，VT，P，S），其中 　VN = { S }， 　VT ={ 0, 1 }， 　P={ S　　0S1, S　　01 } 思考：S＝？

例3.2　文法G=（VN，VT，P，S），其中 VN ={标识符，字母，数字} ，S=<标识符> VT ={a,b,c,…x,y,z,0,1,…,9} P＝{<标识符>　　<字母> 　 <标识符>　　<标识符><字母> <标识符>　　<标识符><数字> 　 <字母>　　a 　　　　……　　　 　　　 <字母>　　z 　　 <数字>　　0 　　　　 …… 　　　 <数字>　　9 } 思考：S＝？

很多时候，不用将文法G的四元组显式地表示出来，而 　只将产生式写出

一般约定： 第一条产生式的左部是识别符 用尖括号括起来的是非终结符（或者用大写字母表示） 不用尖括号括起来的是终结符（或者用小写字母表示） 将G也写成G[S]，其中S是识别符

推导： 　定义V*中的符号之间的关系： 直接推导： 长度为n(n≥1)的推导： 长度为n(n ≥0)的推导： + *

定义3.2：文法G＝（VN，VT，P，S），α　 β是一条 　规则，γ和δ是V*中的任意符号，若有符号串v，w满 　足：v=γαδ，w= γβδ，则称v直接推导到w， 　 v　  w，或w直接归约到v 例：G： S　　0S1， S　　01 　S 　0S1 　00S11 　000S111 　00001111

定义3.3：如果存在直接推导的序列： 　v=w0　　w1　　w2…　　wn=w (n>0) 　则称v推导出w（推导长度为n），或称w归约到V， 　记作 +

+ * 定义3.4：若有v　　w，或v=w，则记作：

* 定义3.5：若有S　　x，则称x是文法G[S]的句型，若x仅 　由终结符组成，则称x为G[S]的句子

定义3.6：文法G所产生的语言定义为集合 　L(G)=｛x|S　　x，其中S为文法识别符号，且x∈VT*｝ 文法描述的语言是该文法一切句子的集合 例：G： S　　0S1， S　　01 　　　L(G)={0n1n|n≥1} *

例3.3　文法文法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 } 思考：a4b4e4怎么推导？

定义3.7：若L(G1)＝L(G2)，则称文法G1和G2是等价的 例如文法G[A]： A　　0R A　　01 R　　A1 　和文法G[S]： S　　0S1 S　　01 等价　L(G)={0n1n|n≥1}

3.4 文法的类型 乔姆斯基(Chomsky)于1956年建立形式语言的描述 他把文法分成：0型、1型、2型、3型 四个文法类的定义是逐渐增加限制的 0型 1型 2型 3型

设G＝（VN，VT，P，S），如果它的每个产生式 　含一个非终结符， β∈(VN∪VT)*，则G是一个0型文法 　（短语文法、无限制文法）

思考：这样定义可以吗？ 设G＝（VN，VT，P，S），如果它的每个产生式 　α　　β是这样一种结构：α∈(VN∪VT)+， β∈(VN∪VT)*，则G是一个0型文法

重要的理论结果： 0型文法的能力相当于图灵机（Turing） 或者说，任何0型语言都是递归可枚举的 反之，递归可枚举集必定是一个0型语言

设G＝（VN，VT，P，S），如果它的每个产生式 例3.1、3.2、3.3

例：文法G[S]： 　　　　　　 S　　CD Ab　　bA C　　aCA Ba　　aB C　　bCB Bb　　bB AD　　aD C　　ε BD　　bD D　　ε Aa　　bD L(G)={w|w∈{a,b}*}

有些定义中，将上下文有关文法的产生式的形式描述为 　α1Aα2　　α1βα2，其中α1、α2和β都在V*中， 　β≠ε，A在VN中

设G＝（VN，VT，P，S），如果它的每个产生式

有时将2型文法的产生式表示为A　　β的形式，其中 　A∈VN，也就是用β取代非终结符A时，与A所在的上下 　文无关，因此取名为上下文无关 例3.1、3.2

例3.4：文法G[S]： 　　　　S　　aB|bA 　A　　a|aS|bAA 　B　　b|bS|aBB

设G＝（VN，VT，P，S），如果它的每个产生式 　A　　αB或A 　　α，其中A和B都是非终结符， 　α∈VT*，则文法G是3型文法（正规文法） 例3.5：文法G[S]： 　　　　S　　0A|1B|0 　A　　0A|1B|0S 　B　　1B|1|0 你会忘记我吗？

例：判断下面文法G[S]是哪一类方法，并说明你的理由？ 　　　　S　　B|aB 　B　　D|a 　D　　b|ε

4个文法类的定义是逐渐增加限制的，因此，每一种正规 　文法都是上下文无关的，每一种上下文无关文法都是上 　下文有关的，而每一种上下文有关文法都是0型文法 称0型文法产生的语言为0型语言，上下文有关文法、上 　下文无关文法和正规文法产生的语言分别称为上下文有 　关语言、上下文无关语言和正规语言

3.5 上下文无关文法及其语法树 上下文无关文法有足够的能力描述现今程序设计语言的 语法结构，比如描述算术表达式、描述各种语句等 　语法结构，比如描述算术表达式、描述各种语句等 例3.6：文法G=({E},{+,*,i,(,)},P,E)其中P为： 　　　　E　　i 　E　　E+E 　E　　E*E E (E) <条件语句>　　if<条件>then<语句>| 　　　　　　　　if<条件>then<语句>else <语句>

给定文法G=（VN，VT，P，S），对于G的任何句型都 　能构造与之关联的语法树（推导树、语法分析树、分 　析树）。这棵树满足下列4个条件： （1）每个结点都有一个V中的符号作标记 （2）根的标记是开始符号S （3）若一结点n至少有一个它自己除外的子孙，并且有标记 　　A，则A∈VN （4）如果结点n的直接子孙，从左到右的次序是结点 n1,n2,…,nk，其标记分别为A1,A2,…,Ak，那么 A　　A1A2…Ak一定是P中的一个产生式

例3.7：文法G=({S，A},{a,b},P,E)其中P为： 　　　　(1)S　　aAS 　(2)A　　SbA 　(3)A　　SS (4)S a (5)A ba 图3.1的推导树是文法G的 　句型aabbaa的推导过程 把aabbaa叫做推导树的结果， 　把推导树叫做句型 　aabbaa的语法树 图3.1 推导树

文法G的句型aabbaa的推导过程： （1）SaASaAaaSbAaaSbbaaaabbaa （2）SaASaSbASaabASaabbaSaabbaa （3）SaASaSbASaSbAaaabAaaabbaa 如果在推导的任何一步α　　 β，其中α、β是句型，都 　是对α中的最左（最右）非终结符进行替换，则称这种推 　导为最左（最右）推导。在形式语言中，最右推导被称为 　规范推导，由规范推导所得的句型称为规范句型 你会忘记我吗？

一个句型是否只对应唯一的一棵语法树？一个句型是否只 　有唯一的一个最左（最右）推导？ 不是 例：G[E]: E 　 　i E 　 E+E E 　 E*E E 　 (E) 句型 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

图3.2　推导1的语法树 图3.3　推导2的语法树

若一个文法存在某个句子对应两棵不同的语法树，则称这 　个文法是二义的。或者，若一个文法存在某个句子有两个 　不同的最左（右）推导，则称这个文法是二义的

注意，文法的二义性和语言的二义性是两个不同的概念。 　因为可能有两个不同的文法G和G`，其中G是二义的，但 　是却有L(G)=L(G`) 产生某上下文无关语言的每一个文法都是二义的，则称此 　语言是先天二义的 你是怎么理解我的？

判定任给的一个上下文无关文法是否二义，或它是否产生 　一个先天二义的上下文无关语言，这两个问题是递归不可 　解的。但可以为无二义性寻找一组充分条件　　

解决二义性的基本方法： 设置一个规则，该规则可在每个二义性情况下指出哪一个 　分析树是正确的。这样的好处：不用修改文法就可以消除 　二义性。缺点：语言的语法结构不能由文法单独提供 将文法改变成一个强制正确分析树的构造的格式

例：　G[E]： E 　　　E T E | (E) | 6 T +|-|* 　　　　　　　　 6-6*6=? 6-6-6=? 　　 规定优先性、结合规则就可以构造出一个无二义文法

3.6 句型的分析 句型分析是一个识别输入符号是否为语法上正确的程序的 过程 在语言的编译实现中，把完成句型分析的程序称为分析程 　过程 在语言的编译实现中，把完成句型分析的程序称为分析程 　序（识别程序），分析算法又称为识别算法 介绍的分析算法都称之为从左到右的分析算法 分析算法分为： 自上而下分析法：从文法的开始符号出发，反复使用各种 　产生式，寻找匹配于输入串的推导 自下而上的方法：从输入符号串开始，逐步进行归约，直 　到归约到文法的开始符号

一.自上而下分析方法 例3.9　考虑文法G[S] （1）S　　cAd （2）A　　ab （3）A　　a 识别输入串 w=cabd 是否该文法的句子 所构造的推导过程为： 　S　　cAd　　cabd 图3.4　自上而下的分析步骤

二.自下而上分析方法 例3.9　考虑文法G[S] （1）S　　cAd （2）A　　ab （3）A　　a 识别输入串 w=cabd 是否该文法的句子 所构造的推导过程为： 　S　　cAd　　cabd 图3.5　自下而上的分析

三.句型分析的有关问题 在自上而下的分析中，对于例3.9的文法，在扩展A时，有 　两个选择，如果选择另一个，推导序列为 　S　　cAd　　cad，语法树如图3.6所示 这时，就与w=cabd不符，宣告失败 应该用哪条规则去替换呢？一种解决办法从各种可能的选 　择中随机挑选一种，并希望它是正确的，如果失败，退回 　去，再试另一种，这种方式称为回溯。显然这种方式代价 　极高，效率很低 图3.6 cad的语法树

在自下而上的分析中，对于例3.9的文法，在归约的时候， 　也存在选择哪一条规则进行归约的问题，因此需要精确定 　义“可归约串”。事实上，存在种种不同的方法刻画“可归 　约串”。对这个概念的不同定义形成了不同的自下而上分 　析文法。在一种“规范归约”的分析中，这种“可归约串”称 　作“句柄”

定义3.8　令G是一文法，S是文法的开始符号，αβδ是文 如果有：S　 αAδ且A　 β则称β是句型αβδ相对 　于非终结符A的短语 如果有A　　 β则称β是句型αAδ相对于规则A　　 β 　的直接短语（简单短语） 一个句型的最左直接短语称为该句型的句柄 * + 你会忘记我吗？

E T F * i3 + i1 i2 例G[E]: E 　　T|E+T 　　　　 T 　　F|T*F F 　　（E）|i 　句型i*i+i 短语：i1、i2 、i3 、i1*i2 、i1*i2+i3 直接短语：i1 、i2 、i3 句柄：i1

例题：句型aabbab中的短语、简单短语、句柄是谁？

3.7 有关文法实用中的一些说明 一.有关文法的实用限制 有害规则：形如U U的产生式 多余规则：文法中那些连一个句子的推导都用不到的规则 某些非终结符不在任何规则的右部出现（不可到达的） 不能够从这些非终结符推出终结符号串（不可终止的）

例3.10　文法G[S]： （1） S　　Be （2） B　　Ce （3） B　　Af （4）A　　Ae （5）A　　e （6）C　　Cf （7） D　　f 该文法的有害规则和多余规则是哪些？

对文法G=(VN,VT,S,P)来说，为了保证其任一非终结符A在 　句子推导中出现，必须满足如下两个条件： ①A必须在某句型中出现。即S　　αAβ,其中α,β属于V* ②必须能够从A推出终结符号串t。即A　　t,其中t∈VT* * +

二.上下文无关文法中的ε规则 ε规则：形如A　　 ε的产生式，其中A∈VN 某些著作和讲义中限制这种规则的出现。因为ε规则会使 　有关文法的一些讨论和证明变得复杂 两种定义的唯一差别是ε句子在不在语言中 如果语言L有一个有穷的描述，则L∪{ε}也同样有一个有 　穷描述。并且可以证明，若L是上下文有关语言、上下文 　无关语言或正规语言，则L∪{ε}和L-{ε}分别是上下文有 　关语言、上下文无关语言和正规语言

定理3.1　若L是由文法G=(VN,VT,P,S)产生的语言，P中的 　每一个产生式的形式均为A　　α,其中A∈VN，α∈V*， 　则L能由这样的一种文法产生，即每一个产生式或者为 　A　　β形式，其中A∈VN， β ∈V+,或者 S　　ε形式， 　且 S不出现在任何产生式右边

定理3.2　如果G是上下文有关文法，则存在另一个上下文 　有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1 　的任何产生式的右边 又如果G是一个上下文无关文法，也能找到这样一个上下 文无关文法G1 如果G是是一个正规文法，则也能找到这样一个正规文法 G1

3.8 典型例题及解答 1.证明文法G=({E,O},{(,),+,*,v,d},P,E)是二义的 E EOE|(E)|v|d O +|* 2.给出生成下述语言的正规文法： 　L={ambn|n,m>=1}

(2)S aS|aA (1)S AB A bA|b A aA|a B bB|b (3)S aA (4)S aA A aA|B A aA|bB 我家没双胞胎 我是对的 (2)S　 　　aS|aA 　A　　　bA|b (1)S　 　　AB 　A　　　aA|a B bB|b 我家没有a 我家少ab (3)S　 　　aA 　A　　　aA|B B bB|b|ε (4)S　 　　aA 　A　　　aA|bB B bB|b 我是对的 我是对的 (5)S　 　　aA 　A　　　aA|B B bB|b (6)S　 　　aA 　A　　　aA|bB|b B bB|ε

(7)S aA A aA|bB B bB|ε (8)S aS|aA A bA|bB B ε (9)S aA A aA|aB|b B bB|b 我是对的 (7)S　 　　aA 　A　　　aA|bB B bB|ε (8)S　 　　aS|aA 　A　　　bA|bB B ε 我是对的 我家少ab2 我是对的 (9)S　 　　aA 　A　　　aA|aB|b B bB|b (10)S　 　aA 　A　　　aA|bB|b B bB|b 我是对的 (12)S　 　aA|aS 　A　　　bB B bB|ε 我是对的 (11)S　 　a(A|S) 　A　　　b(A|ε)

【本章小结】 ① 本章出现的概念较多,应重点理解文法,推导,句型句子及语 　言的定义等概念.语法分析有关内容在后面章节会详细讨论 ② 文法作为程序语言的语法的描述工具,它用规则只能陈述 　的是:语言的所有句子以什麽样的符号串能出现.请记住文 　法和语言的形式定义中的 “形式”的含义-只涉及语言的语 　法不涉及语言的语义 ③ 本章内容是形式语言理论的一部分.形式语言理论是对符 　号串集合的表示法、结构及其特性的研究。是程序设计语 　言语法分析研究的基础

第3章　作业题 P47： 1. 6.(5)进行最左推导　(6)进行最右推导 8. 9. 11. 13. 14. 16.