编译原理：第3章 文法和语言

1、3.1 文法的引入3.2 字母表和符号串3.3 文法和语言的形式定义3.4 文法和语言分类3.5 上下文无关文法及其语法树3.6 对实用文法的限制与扩充第3章 文法和语言 1第3章 文法和语言 3.1 文法的引入 20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，即用一组数学符号和规则对语言进行形式化描述。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。形式工具-“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述2自然语言：英语符合相应规则合法句子 （字母表） （语法） （含义-语义）编程语言：规定什么样的符号是程序

2、允许的（终极符集字母表）什么样的符号串是合法程序（定义语言的语法）对合法程序赋予什么样的含义（语义）语义：自然语言描述的多如：标识符先定义、后使用；标识符不能重复定义非形式化不利于机械翻译3.1 文法的引入 3本书讨论的源语言定义问题，指语法定义问题枚举法：可定义有穷语言。如：字母表上的串集 red, blue, yellow 文法生成：一个规则的有穷集，规定了语言中句子的结构，即语言的语法（可定义有穷语言、无穷语言）文法：语言的定义装置生成观点：形式语言源语言的数学模型自动机：语言的识别装置识别观点：自动机编译程序的数学模型本章从生成的观点，介绍语言的定义方法4 语言学家Noam Choms

3、ky（乔姆斯基），毕业于宾西法尼亚大学，最初从产生语言的角度研究语言。1956年，他将语言L定义为一个字母表中的字母组成的一些串的集合： L *。 字母表按照一定的规则定义一个文法（grammar），该文法所能产生的所有句子组成的集合就是该文法产生的语言。 1959年，乔姆斯基根据产生语言文法的特性，将语言划分成3大类。 知识扩充： 形式语言与自动机理论的产生与作用 5 1951年到1956年，克林（Kleene）在研究神经细胞中，建立了识别语言的系统有穷状态自动机。 1959年，乔姆斯基发现：文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性，这一成果被认为是将形式

4、语言置于了数学的光芒之下，使得形式语言真正诞生了。20世纪50年代，巴科斯范式（Backus Nour Form，BNF）实现了对高级语言ALGOL-60的成功描述。这一成功，使得形式语言在20世纪60年代得到了大力的发展。知识扩充：形式语言与自动机理论的产生与作用 6从示例抽象出文法描述The gray wolf will eat the goat.The gray wolf will eat the goat7 the gray will wolf goat从示例抽象出文法描述这就是规则的有穷集合P8终结符集 VT= the, gray, wolf, will, eat, goat非终结符

5、集 VN=,语法规则 P= , 开始符号 S=从示例抽象出文法描述9什么是文法 简单来说，文法是语言结构的定义和描述，是由一组规则（或称为产生式）组成的，用来定义抽象的语法单位。 对于程序设计语言而言，文法描述了程序的书写规则。 10文法的例子 例：下面用文法定义语言，即“由加号和减号分隔的数字序列”（递归定义）+-0| 1| 2| 3| 4| 5| 6| 7| 8| 9按照规定的语法结构组合成的符号串序列称为语言的句子。该文法定义的语言的一些合法的句子是： 2+3+4、 5-2+3、7+8。11文法的例子 +-0| 1| 2| 3| 4| 5| 6| 7| 8| 9其中list代表的语法单位

6、名是数字序列，digit代表的语法单位名是数字。它们都是需要进一步定义的抽象的语法单位，称为非终极符。+和-运算符以及数字称为该文法的终极符。12文法的例子 +-0| 1| 2| 3| 4| 5| 6| 7| 8| 9利用文法进行推导并产生句子的过程： + -+ -+ 5 - + 5 2 + 5- 2 + 3 13文法的EBNF表示 所谓文法的EBNF表示，就是在书写文法的规则时，可采用一些特殊的符号来表示文法，这些符号叫做元语言符号。下面是用来描述规则的元语言符号： 代表“定义为”。（也可以是 := ) | 代表“或者”。 代表Z是需要进一步加以定义的抽象的语法单位名 Z 代表Z出现0或任意

7、次 Z 代表Z最多出现一次14文法的EBNF表示 1.元符号“|”：表示“或”.对于具有相同左部的那些规则 如 1、 、 n，可以缩写为: 1 | 2 | n例：定义无符号整数的文法： | 0|1|2|3|4|5|6|7|8|9 15文法的EBNF表示 2. 元符号“” 表示括起的内容是需要进一步定义的抽象的语法单位名。称为文法的非终极符。 如、等等。 16文法的EBNF表示3.元符号“”和“” 表示可重复连接，tnm表示符号串t可重复连接n到m次，而t表示符号串t可重复连接0到无穷次。例如， 13 与 | 相同而字母打头、后面可跟数字或字母的不超过8个字符的标识符文法则为： |0717文法的

8、EBNF表示4.元符号“”和“ ”：表示括起的内容可有可无, 最多出现一次。例如： IF THEN ELSE 5.元符号“（”和“）”：表示括号内的成分优先。常用于在规则中提取公因子。例如，Uxy|xw|xz 可写成：Ux（y|w|z）183.2 字母表和符号串 介绍文法和语言之前，首先介绍符号、符号串等基本概念。任何一种语言都是由该语言的基本符号所组成的符号串集合的子集。例如，C语言的基本符号有if,while,for,字母、数字和+、-、（、）、=等分界符。由这些符号组成的各种可能序列的符号串构成一个无穷的集合，而C语言就是这个集合的子集。任何一个C语言程序都是定义在这个集合上的符号串。

9、191.字母表 “字母表”是元素的非空有穷集合。字母表中的每个元素称为“符号”.例如，集合a，b，c，+，*是一个含有5个符号的字母表，而字母表0，1只有两个符号。 202 符号串 “符号串”是由字母表上0个或多个符号所组成的任何有穷序列。例如有字母表a，b，c，+，*，则a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等等都是该字母表上的符号串“空串”：不包含任何符号的串，记为。例如：=a,b，则 ,a,b,aa,bb,aba等都是上的符号串。213 符号串及其集合的运算符号串的长度：指符号串x中所含符号的个数，记为|x|。 如|abc|=3，|

10、abc+*abc|=8，而|=0 上全部有穷长符号串的集合记作* 。 例如：=a,b，则*=, a, b, aa, ab, ba, bb, aaa, 223 符号串及其集合的运算符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表上的两个符号串，则xy也是字母表上的符号串。 例如： x=ab，y=ba，那么 xy=abba注意：连接没有交换率，即 xy yx 对于空串，有 x=x=x233 符号串及其集合的运算集合的乘积运算： 设U、V*，U和V的积（连接）定义为： UV=UV=|（U）（V）例如：A=a，b ，B=c，d，则AB=ac，ad，

11、bc，bd对于空集合有：U=U=U。符号串的幂运算：若x是符号串，则x的幂运算定义为：X0=, x1=x , x2=xx ,，xn=xxx=xx n-1=x n-1 x ,其中 n0例如：x=abc, x0= , x1=abc, x2=abcabc,243 符号串及其集合的运算集合的幂运算：设A为符号串集合，则A的幂运算定义为： A0= A1=A A2=AA An=AAA=AA n-1 =A n-1 A ，其中 n0例如：A = a，b， 则 A0=A1=a,bA2=aa,ab,ba,bb253 符号串及其集合的运算集合的正闭包和集合的闭包：设A为一个集合，则集合A的正闭包用A+表示，定义为：

12、 A+ =A1 A2 . A n 集合A的闭包用A*表示，定义为： A* =A 0 A+ , 显然有 A+=AA*=A*A 例如：A = a，b，则A+ =a,b,aa,ab,ba,bb,aaa,aab, A* = ,a,b,aa,ab,ba,bb,aaa,aab, 一个集合的闭包比正闭包多个。 263.3 文法和语言的形式定义1 文法G为一个四元组 G = (VN，VT，P，S ) VN: 非终结（极）符的有穷集； （Variable） VT: 终结（极）符的有穷集； （Terminal） V = VN VT是词汇表 （VN VT = ，V中符号为文法符合） P: 规则的非空有穷集，即： 称

13、为规则或产生式 S VN :是文法的开始符号 （Start Symbol）27例3.1：产生语言标识符的文法 G=（ VN, VT, P, I）其中： VN = I, L, D VT = a, b, z, 0, 1, , 9P：IL | IL | IDLa | b | | zD0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 928例3.2：生成语言 的文法GS：SABAaA | aBbB | b写文法时，可省略VN和VT ，直接写出规则即可。29例3.3：给出语言无符号整数的文法解： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9分别用推

14、导和语法树表示248的生成过程： 2 4 8图 3.1 无符号整数248的推导过程2 24 248302 元语言与源语言不同：元语言：用来定义一种语言的语言（可描述规则）对象语言：被定义的语言（源语言）31例3.4：构造无符号整数的文法|0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9检查234是否合法： 2 23 234任一文法，有一特殊的非终极符，称为开始符号S，由S出发，利用规则一步步替换，直到串中只含终极符为止，便产生了一个句子。32（1）直接推导“”是文法G的产生式，若有v, w 满足：v=, w= , 其中V*,V*则称v直接推导到w,记作 v w也称w直

15、接归约到v例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S133 （2）若存在0 1 . n,(n0)，则记为 0 + n （正闭包），称作0推导出n ，或 n归约到0 （3 ）若有0 + n 或 0 = n ， 则记为 0 * n（自反传递闭包） （4）若从0出发，经过k次推导，可推出n，记为： 0 =k n （k次复合） 推导“*”34句型、句子的定义3.句型有文法G=(VN, VT, P, S） ，若S =* x，且x(VNVT)* ，则称x是文法G的句型。4.句子有文法G，若S =* x，且xVT*，则称x是文法G

16、的句子。即仅由终极符组成的句型称为句子。例：G： S0S1， S01S 0S1 00S11 000S111 00001111G的句型S,0S1 ,00S11 ,000S111,00001111G的句子00001111, 0135(文法生成的)语言的定义5.语言由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)=x|S =* x，其中S为文法的开始符号，且x VT* 文法和语言有如下关系：(1) 给定一个文法, 就能从结构上唯一的确定其语言。 (2) 给定一种语言, 能确定其文法, 但不唯一。 36语言例：已知文法GZ为： Z aZb| ab求该文法确定的语言。 解：从识别符

17、号开始推导，反复用规则1可得: Z=aZb=a2Zb2=an-1 Zbn-1最后用规则2可得: Z=aZb=a2Zb2=an-11 Zbn-1 = anbn所以该文法确定的语言为：L(GZ)=anbn|n1 G生成的每个串都在 L(G)中；L(G)中的每个串确实能被G生成37语言例：已知语言为: L(G)=abna|n 1，构造产生该语言的文法。解：根据语言的形式，可构造其文法G为:ZaBaBBb|b还可以构造文法G1为:ZaBaBbB|b从例可看出，G与G1是两个不同的文法，但它们都可以描述语言abna|n1。 如果两个不同的文法可描述相同的语言,那么我们称这两个文法为等价文法。38文法的等

18、价6. 若L（G1）=L（G2），则称文法G1和G2是等价的。如文法G1A：ADB 与G2S：S0S1 等价 ADE S01 EAB D0 B139递归规则与递归文法1递归规则递归规则是指那些在规则的右部含有与规则左部相同符号的规则。例如：U:=xUy，右部含有与规则左部相同符号U，那么就是递归规则。如果这个相同的符号出现在右部的最左端，则为左递归规则。 如 U:=Uy如果这个相同的符号出现在右部的最右端，则为右递归规则。如 U:=xU 句子的个数是有穷还是无穷取决于文法是否是递归的。 递归文法使我们能用有穷的文法刻画无穷的语言。 40递归文法若文法中至少包含一条递归规则, 则称文法是直接递归

19、的。有些文法，表面看上去没有递归规则，但经过几步推导，也能造成文法的递归性，则称为间接递归文法。例如，有文法为: U Vx ， V Uy|v 有推导过程U=Vx=Uyx，所以该文法为间接递归文法。41递归文法例：判定如下文法所描述的语言是否是有穷的。ZaBaBbB|b解：因为文法中的第二条规则BbB|b是递归规则，所以该文法描述的语言是无穷的。该文法描述的语言为abna|n1。 42文法的二义性 如果一个文法存在某个句子对应两棵不同的语法树，或者说它有两个不同的最左（或最右）推导，则称文法是歧义（也称二义）文法。 文法的歧义不等价语言的歧义，只有当产生一个语言的所有文法都是歧义的，这个语言才被

20、认为是歧义的。43文法的二义性 例如:有文法G1E：E E+E | E*E |（E）| id| num，分析该文法是否为二义性文法。解：该文法产生语言算术表达式。 文法G1E中的非终极符E代表算术表达式， 终极符集合是+，-，*，/，（，），id,num, 其中助记符id代表标识符，num代表无符号整数。 44文法的二义性 例如:有文法G1E：E E+E | E*E |（E）| id| num，分析该文法是否为二义性文法。 为了判断该文法是否为二义性文法，我们找一个句子id+id*id，如果能够构造出两个不同的语法树，则说明该文法是二义性文法。45E E+E | E*E |（E）| id| n

21、um (a) 先推出加运算的语法树1 (b)先推出乘运算的语法树2 显然该文法是二义性文法。 产生歧义的原因是文法没有限定运算符的优先级和结合性。 EE+EE*EidididEE*EEEididid+id+id*id46文法的二义性 (a) 先推出加运算的语法树1 (b)先推出乘运算的语法树2 二义性产生的后果会导致分析结果不同，导致对句子的理解不同。由于图 (a)语法树1中的*先作为句柄归约，可理解成*优先于+进行运算，而图 (b)语法树2中的+先作为句柄归约，表示+优先于*进行运算。由于文法的二义性会造成不同的分析结果，所以算术表达式规定乘除高于加减，从而避免二义性。 EE+EE*Eidi

22、didEE*EEEididid+id+id*id47在算术表达式中，规定乘除高于加减，避免其二义性。例，改写文法G1E：E E+E | E*E |（E）| i，使其无二义性。解：新添非终结符号T和F，将文法写成G2E：E T |E+TT F |T*FF (E) | iET+EF*TTiFFii48 G2E： E T |E+T，T F |T*F，F (E) | I 引进非终极符T代表项，F代表因子。 算术表达式看成是项或项的加减运算，即只有项才能参加加减运算。 项看成是因子或因子的乘除运算，因子是算术表达中的基本单位。该文法要求乘除运算必须在加减运算之前执行。 由于文法G1E和文法G2E产生相同

23、的语言算术表达式，因此它们是等价文法。49文法的二义性程序设计语言中的嵌套IF语句都要求ELSE与最近的IF配对，也是因为IF语句的文法存在二义性。例：IF语句文法如下： IFTHEN |IFTHENELSE |说明该文法是二义性文法。解：假设有一个IF语句嵌套的句型为：IFTHEN IFTHENELSE 根据文法可构造两棵语法树如图 (a)和图(b)所示： 50文法的二义性语句 布尔表达式 IF THEN 语句 布尔表达式 IF THEN 语句 ELSE 语句 语句 布尔表达式 IF THEN 语句 布尔表达式 IF THEN 语句 ELSE 语句 图 (a) IF语句语法树1 图 (b)

24、IF语句语法树2 由于这两棵语法树不同，所以该文法是二义性文法。图 (a) IF语句的语法树意味着ELSE和第2个THEN配对（就近配对），而图 (b) IF语句的语法树表示ELSE和第1个THEN配对。 51文法练习例：已知语言anbn | n1，求文法 。解： SaSb |ab 例：已知语言anbnambm | n, m0，求文法 。解： SAA | A AaAb | 52文法练习例：已知语言aibaj | i, j0，求文法 。解： SAbA AaA | 或者 SaS | bA | b AaA | 53文法练习解：SAB AaAb|ab BcB|例：已知语言anbnci | n 1, i

25、0，求文法 。例：给出生成非零开头的正偶数集合的文法. 解:SABC | 2 | 4 | 6 | 8A1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9BAB| 0B |C0 | 2 | 4 | 6 | 854由语言构造文法要注意的问题 文法生成语言的句子必须完全，既不能多一个，也不能少一个。通常没有写文法的一个形式化的算法，一般采用“串联”和“并联”两种手段。 “串联”：把一个句子结构分解为几个相连接的子结构。“并联”：难以用统一形式表达的句子，可用几种不同方式表达出来，构成不相交的划分。 由文法产生语言时，可以用规范的数学描述方式，有时则要用自然语言方式。55文法练习例：已

26、知下列文法，求文法生成的语言是什么 ？（1）S0S0 | 1S1 |（2）SaCa，CaCa|b（3）SS（S）S |56文法练习例：已知下列文法，求文法生成的语言是什么 ？（1）S0S0 | 1S1 |S00SS00SS11SS00S解：文法产生的句子形式为：00，11，0110，1001，其特点是镜像结构。L（G）=XX-1 | X0, 1*，X-1为X的逆，没有中心元素的镜像结构语言 57文法练习例：已知下列文法，求文法生成的语言是什么 ？（2）SaCa，CaCa | b 解：L（G）=anban | n1 文法生成的语言采用数学公式描述。58文法练习例：已知下列文法，求文法生成的语言是

27、什么 ？（3）SS（S）S |解：L（G）=|为空串或可任意嵌套的配对的左右圆括号序列 SSS ）S（SSS ）S（SSS ）S（分析如下：首先文法的终极符是（和），即句子只能是左、右圆括号组成。而S的每一次非推导，都会产生一对左右圆括号。并且在已产生的（）的前面、后面和里面都可以产生圆括号对，且能递归分析下去。若使用S产生式，将去掉句型中的某个S，这就使得句子中左右圆括号的配对和嵌套具有随意性。593.4 文法和语言分类 著名的语言学家乔姆斯基在1956年对形式语言进行了定义。根据文法中的规则的形式，可定义如下四类文法和相应的四种形式语言： 60文法和语言分类0型文法(规则不受限制的文法)若

28、文法中有如下形式的规则： ，其中 V* VN V* ，V* ，V= VNVT且对，不加任何其它的限制.例如 ： aSbcAd 0型文法描述的语言为0型语言，用L0表示。61例: 一个0型文法的例子GS：SACaB，CaaaC，CBDB，CBE，aDDa，ADAC，aEEa，AELG=ai | i 为2的正整次方即L=aa, aaaa, aaaaaaaa, 62文法和语言分类1型文法(上下文有关文法, Context-Sensitive-Grammar，CSG)若一个0型文法G中有如下形式的规则： Uu， 其中 UVN，、V*， u V + ，V= VNVT即规则左部可为符号序列，其中U为非终结

29、符号。当把规则应用到推导中，只有在上下文和中，才能把U重写为u。例如：aUbaABBaab 1型文法描述的语言为1型语言，用L1表示。 63文法和语言分类1型文法(上下文有关文法, Context-Sensitive-Grammar，CSG)1型文法的另一等价定义：若一个0型文法G中所有产生式都满足如下的条件：|（，V+，但S除外，且S不得出现在任何产生式的右边），则称G为1型文法。64例:语言anbncn | n1在结构上有什么特点？解：属于上下文敏感语言。该语言要求a、b、c的个数必须相等，上下文敏感文法能够“记3项的数”。分析：仿照anbn | n1的产生式，写anbncn | n1的文

30、法：anbn | n1的文法是SaSb | abanbncn | n1的文法可能是SaSbc | abc即前面增加一个a，后面增加一个b和c。65分析Sabc | aSbc产生的一个句子：aaabcbcbc题中语言产生的一个句子是aaabbbccc。显然必须实现c与b的换位，但由于无法通过终极符换位，所以考虑用非终极符B和C标记b和c，修改文法：SaBC | aSBCCBBC此时产生的一个句子是：aaaBBBCCC由于只有B的前面是a或b，才能将B重写为b，即 aBab bBbb66aaaBBBCCC 同理，只有C的前面是b或c，才能将C重写为c，即 bCbc cCcc语言anbncn | n

31、1的文法是：SaBC | aSBCCBBCbBbbaBabcCccbCbc67文法和语言分类2型文法(上下文无关文法, Context-Free-Grammars, CFG )若一个1型文法G中的规则都具有如下形式： Au，其中 A VN ， u V*，V=VNVT则称G为2型文法，又称为上下文无关文法。所定义的语言是2型语言或称为上下文无关语言，用L2表示。 68文法和语言分类2型文法中的规则左部必须是一个非终结符号，规则右部u是V上的符号序列。如果A是2型文法的产生式，则无论A出现在句型中的任何位置，都可将A替换为而不需考虑A的上下文。2型文法的特性使得对程序设计语言的语法分析（推导或归约

32、）变得相对简单。目前大多数的高级程序设计语言的语法特性都是上下文无关的。69例：分析语言anbn | n1的语言结构解：语言属于上下文无关的。即它能够“记2项的数，但不能记3项的数”。文法 GS：SaSb| ab上下文无关文法适合描述程序设计语言中的表达式、语句等具有嵌套结构的语法规则。70利用上下文无关文法定义程序设计语言样本S语言的定义 int ID; | int ID;if () then else | if () then | while () do | ID=| ; | 71 and | or | ID relop ID | ID + | - | * | / | () | ID |

33、NUM72文法和语言分类3型文法（又称为正则文法，Regular Grammar，RG） 若在一个2型文法中仅含有如下形式的产生式：Ua 或U Wa（左线性正则文法） 或 UaW（右线性正则文法）其中 U，W VN， a VT *规则右部或是终结符号、或是非终结符号与终结符号。 73文法和语言分类3型文法（又称为正则文法，Regular Grammar，RG） 3 型文法描述的语言为3型语言，用L3表示。 高级程序设计语言的单词符号，如标识符、无符号整数等都是采用3型文法来描述的。正则文法描述嵌套结构无能为力。74注意：同一文法中，既有左线性、又有右线性，不能称之为正则文法。 例：语言0n1n

34、 | n1的规则 S0S1 | 01（是2型文法）可改写为： S0A | 01 AS1 （左、右线性都有，但不是正则文法） 75用正则文法定义标识符和整常数 a | b | |z | a | z| 0 | | 9 0 | 1| |9| 0 | 9 76文法和语言分类 在上述四类文法中，从0型到3型文法对规则的限制逐渐增加，产生的语言类却逐步缩小，即： 0型语言包含1型语言，1型语言包含2型语言，2型语言包含3型语言。 因此，可以说3型文法是2型文法的特例，2型文法是1型文法的特例，1型文法又是0型文法的特例。 77四类文法之间的逐级“包含”关系：L3（T3） L2（T2） L1（T1） L0（

35、T0） 2型语言1型语言0型语言3型语言上述定义的4类文法在描述语言的能力上是从0型开始依次减弱（但规则的限制逐步增强）。783.4 文法的分类通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式，都有 (VNVT)* VN (VNVT)* ， (VNVT)*1型文法：对任一产生式，都有| (|表示 串长)2型文法：对任一产生式，都有VN 3型文法：任一产生式的形式都为 （1） AaB或Aa：G为右线性文法； （2） ABa或Aa：G为左线性文法； （都为3型文法） 其中AVN ，BVN ，aVT *7980从生成语言的角度来说，语言可由文法定义，从识别语言的角

36、度来说，语言可由自动机识别。对应的关系如下：生成装置 语言识别装置0型文法 L0图灵机 （递归可枚举集）1型文法L1线性有界自动机 （上下文相关语言）2型文法L2下推自动机 （上下文无关语言）3型文法L3有穷状态自动机 （正规集）81例：语言的文法规则为： SA | AB A0 | 0A B1 | 11 试写出语言。解： S A，S AB A 0A 00A 00 00 L（A）=0n | n1 B 1，B 11 L（B）=1, 11 L（S）=L（A）L（A）L（B） L（S）=0, 00, 01, 001, 0001, 011, 0011, 00011, 82下面给出的语言在结构上有什么特点

37、？（1）语言 anbmcmdn | n,m1（2）语言 anbncmdm | n,m1（3）语言 wcw| wa,b*（4）语言 anbmc ndm| n,m083（1）语言 anbmcmdn | n,m1 解：该语言是上下文无关的。 SaSd| aAd AbAc | bc （2）语言 anbncmdm | n,m1 解：该语言是上下文无关的。 SAB AaAb | ab BcBd | cd84（3）语言 wcw| wa,b* 解：该语言是一个抽象语言， 第1个 w代表标识符的声明，第2个 w代表标识符的引用。这个语言是关于检查程序中标识符的声明应先于其使用的问题的抽象。因此该语言是上下文敏感

38、的。 由于程序设计语言的语法特性绝大多数是上下文无关的，因此编译器是在语法分析阶段检查上下文无关的语法特性，而上下文敏感的语法特性在语义分析阶段检查。85（4）语言 anbmc ndm| n,m0解： 该语言是关于检查过程声明的形参个数和过程调用的实参个数一致的问题的抽象，是上下文敏感语言。 编译器在语义分析阶段检查参数的匹配问题。an，bm 代表两个过程定义的形参表中形参个数分别是n，m。cn，dm 代表两个过程调用的实参表中实参个数分别是n，m。86练习：已知语言 w c wR| w（a|b）*， wR 代表w的逆，写出文法。SaSa|bSb|cSaaSSaaSSbbSSaaSc87（1）

39、L1=00，01，10，11（2）L2=0，1，00，01，10，11，000， =+（正闭包)（0、1上的所有非空串）（3）L3=,0,1,00,01,10,11,000, = *（克林闭包）+= *= * (* : 上的所有串)（4）L4= 0n| n=1（5）L5=0n1n| n=1 （6）L6=0n1m| n,m=1 令=0，1，下列语言在结构上有什么样的特点？(1)(4) 3型 (5) 2型 （6) 3型88（7）L7 =0n1n0n| n=1 （8） L8 =0n1m0k| n,m,k=1（9） L9 =x|x+，且x中0和1的个数相同 2型（10）L10 =0n1m0n| n，m

40、=1（11）L11=xxR | x(0|1)*, xR是x的逆 令=0，1，下列语言在结构上有什么样的特点？(7) 1型 (8) 3型 (9) （11) 2型 89例：设G=N,T,P,S, N=S,A,B, T=a，bP: SaB|bA Aa|aS|bAA Bb|bS|aBB求产生的语言答：由相同个数的a、b组成的串的集合 （可用数学归纳法证明）901.一个文法GS若存在推导序列S=+S,则称GS是_文法，该文法产生的句子有_个2.文法G所描述的语言是_的集合A.文法G的词汇表V中所有符号组成的符号串B.文法G的词汇表V的闭包V*中的所有符号串C.由文法的识别符号推出的所有符号串D.由文法的

41、识别符号推出的所有终结符号串3.BNF是一种广泛采用的_的工具A. 描述规则 B.描述语言C.描述文法 D.描述句子递归无数DC914.一个语言的文法是_A.唯一的 B.不唯一的 C.个数有限的5.设有文法GS=S,B,b,Sb|bB,BbS,S。该文法所描述的语言是_A.bi|i=0 B. b2i|i=0 C. b2i+1|i=0 D. b2i+1|i=16.给出生成非0开头的正偶数集的文法解：SXYZ | 2 | 4 | 6 | 8X1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Z0 | 2 | 4 | 6 | 8YYX | Y0 |Bc927.设有GS：SB|IF A

42、 then A else ABC|B+C|+CCD|C*D|*DDx|(A)|-D 写出VN, VT VN =S,B,C,D VT= IF, then, else, +, *, x, -, (, ), A933.5 上下文无关文法及其语法树CFG用于描述PL的语法结构（如表达式、语句）特点：规则A V*此类文法的句型推导-语法树（推导树）94一 语法树定义定义1 设G=( VN,VT,P,S)是给定文法，对于G的任何句型，则称满足下列条件的树为G的一颗语法树。1. 每个结点都有G的一个文法符号，且根结点标有初始符S，非叶结点标有非终极符；2. 如果结点n有标记A，其直接子孙结点从左到右的次序是

43、n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式。语法树的结果：从左到右读出叶子的标记而构成的行。95语法树-句型推导的直观表示 (句型、推导)GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a以上推导对应的语法树是否相同？96例：G E:E iE E+EE E*EE (E) E E + E E

44、 * 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+i97上下文无关文法的语法树句型aabbaa的可能推导序列和语法树 例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa98 根据推导序列，对每步推导画相应分枝ASaSbSAaaba aS

45、bAS aabAS aabbaS aabbaa aAS S 二 如何画出分析树 (自顶向下）99 根据归约序列，对每步归约画相应分枝ASaSbSAaaba aAa aSbAa aSbbaa aabbaa aAS S 二 如何画出分析树 (自底向上）1002.最左（右）推导 左（右）句型最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由最左推导所得的句型称为左句型由规范推导所得的句型称为右句型（规范句型）101左分析：由文法开始符号S到句子x的最左推导中所用规则序列称为x的一个左分析按左分析来建立句子的语法树，则语法树的生长次序是自顶

46、向下（根叶子）左分析又称自顶向下分析右分析：由S到句子x的最右推导所用规则逆序列称为x的一个右分析。按右分析来建立句子的语法树，则语法树的生长次序是自底向上的。右分析又称自底向上分析102自上而下的语法分析例：文法G： S cAd A ab A a识别输入串w=cabd是否为该文法的句子SSScAdcAd a b推导过程：S cAd cAd cabd103自下而上的语法分析例：文法G： S cAd A ab A a识别输入串w=cabd是否该文法的句子SAA c a b d c a b d c a b d 规约过程构造的推导： cAd cabd S cAd104一个句型推导或分析用一棵树结构图

47、示出来，它反应了一个句子语法结构的层次。2. 对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。 分析树并未描述推导过程。在书中，用画分析树的过程解释语法分析过程，用分析树图解语法结构。 分析树是推导的图形表示。关于分析树的几点说明105 一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记。SAbSaSbaAaa三、 子树 梯形中为一棵子树。106短语：一棵子树的所有叶子自左至右排列起来形成 一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶 子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左最下那棵

48、只有父子 两代的子树的所有叶子的自左至右排列。 例如，对表达式文法GE和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄:107EE+TT+TF+T a1+T a1+T*F a1+F * F a1+a2 *FE+T T,T+T F,F+T a1, a1+T a1, T*F, a1+T*Fa1, F,F*F, a1+F*F a1, a2,a1+ a2 *F, a2 *F a1, a2, a3, a2 * a3 a1+ a2 *a3EE+TTFa1T*FFa2a3a1+a2 *a3短语 108EE+TE+T*FE+T*a3E+F* a3E+a2 * a3 T+a2 * a3 F+a2 * a3 EE+TTFa1T*FFa2a3a1+a2 *a3109四 歧义文法（二义文法）(1)语法树与最左（或最右）推导是一一对应的。 对于非歧义文法，不同的推导对应同一棵语法树。即：语法树是各种推导的共同抽象(2)歧义文法：文法G是歧义的，如果L(G)中至少存在一个句子，它有两棵以上的语法树。（或有两个不同的最左（右）推导）(3)文法歧义不等价于语言歧义(4)只有文法是非歧义的，语法分析才可唯一进行110二义文法改造为无二义文法GE:E i GE： E T|E+T E E+E T