编译原理第2章-文法和语言

1、Compiler Construction Principles第二章 文法和语言的基本知识 形式语言理论是编译的重要理论基础。本章主要介绍编译理论中用到的有关形式语言理论的最基本概念最基本概念，重点介绍如何采用形式化的方法描述程序设计语言。Compiler Construction Principles第二章 文法和语言的基本知识q字母表和符号串字母表和符号串q文法和语言的形式定义文法和语言的形式定义q短语、直接短语和句柄短语、直接短语和句柄q语法树和文法的二义性语法树和文法的二义性q文法和语言的分类文法和语言的分类Compiler Construction Principles2.0 概

2、述 对程序设计语言的描述是从语法、语义和语用三个因素来考虑。语法是对语言结构的定义。 语用则是从使用的角度去描述语言。语义是描述了语言的含义。Compiler Construction Principles2.0 概 述例如例如 赋值语句赋值语句s s2 2* *3.14163.1416* *r r* *(r+h)(r+h)的的 非形式化的描述为：非形式化的描述为：语法：赋值语句由一个变量，后随一个赋 值号“”，再在其后面跟一个表达式构成。语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。语用：赋值语句可用来计算和保存表达式的值。Compiler Construction Pri

3、nciples2.0 概概 述述 这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。所谓形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法。 形式语言理论是编译的重要理论基础。重点介绍如何采用形式化的方法描述程序设计语言。 Compiler Construction Principles2.1 字母表和符号串字母表和符号串元素的非空有穷集合。例如，= a, b, c 1. 字母表 根据字母表的定义，是字母表，它由a、b、c三个元素组成。Compiler Construction Principles2.1 字母表和符号串字母表和符号串 是一个字

4、母表，由0、1两个元素组成。注意:例如， =0, 1 (2) 字母表中的元素, 可以是字母、数字或其他符号。(1) 字母表中至少包含一个元素。Compiler Construction Principles2.1 字母表和符号串字母表和符号串 字母表中的元素称为符号或称为字符。例如，前述例子中2. 符号（字符）a、b、c 是字母表中的符号；0、1 是字母表中的符号。Compiler Construction Principles2.1 字母表和符号串字母表和符号串 例如，设有字母表= a, b, c 符号的有穷序列称为符号串。 符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成

5、。 则有符号串 a，b，ab，ba， cba， abc 3. 符号串（字）Compiler Construction Principles2.1 字母表和符号串字母表和符号串说明说明: :不包含任何符号的符号串, 称为空符号串，用表示。符号串中符号的顺序是很重要的。ab和ba是字母表上的两个不同的符号串。空符号串由0个符号组成，其长度| |=0|=0Compiler Construction Principles2.2 符号串的运算 设x和y是符号串，则串xy称为它们的连结。则XYABC10A，YX10AABC。注意：对任意一个符号串x，1. 符号串的连结符号串的连结例如，设XABC，Y10A

6、我们有 xxx。Compiler Construction Principles2.2 符号串的运算2. 集合的乘积集合的乘积 设A和B是符号串的集合, 则A和B的乘积定义为： 集合的乘积是满足于 xA, yB的所有符号串 xy 所构成的集合。AB=xy | xA, yBCompiler Construction PrinciplesA=A=A2.2 符号串的运算例如：设A= a, b , B= c, d 则AB= ac, ad, bc, bd 由于对任意的符号串x，总有x=x=x所以, 对任意集合A, 我们有:Compiler Construction Principles2.2 符号串的运

7、算 特别指出的是， 是符号串, 不是集合，而表示由空符号串 所组成的集合, 但这样的集合不是空集合= 。Compiler Construction Principles2.2 符号串的运算 3. 符号串的幂运算符号串的幂运算 设x是符号串, 则x的幂运算定义为： x0= x1= x x2= xx x3= xxx xn= xx x=x xn-1(n0)n注意：x0 1Compiler Construction Principles2.2 符号串的运算例如, 设 xabc 则x0= x1=abcx2=xx=abcabc Compiler Construction Principles2.2 符号串

8、的运算 4. 集合的幂运算集合的幂运算 设A是符号串的集合，则集合A的幂运算定义为：A0=A1=AA2=AA An= AA A=AAn-1(n0)nCompiler Construction Principles2.2 符号串的运算例如，设A= a, b ，则A0=A1=A= a, b A2=AA= aa, ab, ba, bb A3=AAA=A2A= aaa, aab, aba, abb, baa, bab, bba, bbb Compiler Construction Principles2.2 符号串的运算5. 集合集合A的正闭包的正闭包A与闭包与闭包A* 设A是符号串的集合，则A的正闭

9、包A和A的闭包A*的定义为:A+=A1A2 An A*= A0 A1A2 An =A+Compiler Construction Principles2.2 符号串的运算 可见,集合A的正闭包表示A上元素a,b构成的所有符号串的集合,集合A的闭包比集合A的正闭包多含一个空符号串。例如，设A= a, b , 则：A+= a, b, aa, ab, ba, bb, aaa, aab, A*= , a, b, aa, ab, ba, bb, aaa, aab, Compiler Construction Principles2.3 文法和语言的形式定义 每个形式语言都是某个字母表上按某种规则构成的所

10、有符号串的集合。反之，任何一个字母表上符号串的集合均可定义为一个形式语言。形式语言形式语言序列的集合称为形式语言。Compiler Construction Principles2.3 文法和语言的形式定义 对每个具体语言,都有语法和语义两个方面，形式语言是指不考虑语言的具体意义，即不考虑语义。 Compiler Construction Principles2.3 文法和语言的形式定义形式语言的描述形式语言的描述 对形式语言的描述有两种方法，一种方法是当语言为有穷集合时，用枚举法来表示语言。 Compiler Construction Principles2.3 文法和语言的形式定义 均表示

11、字母表A上的一个形式语言。由于这三个语言均是有限符号串的集合，因此，可枚举出其全部句子来表示该语言。 例如，设有字母表A= a, b, c ，则L1= a, b, c L2= a, aa, ab, ac L3= c, cc Compiler Construction Principles2.3 文法和语言的形式定义例如，设字母表= 0, 1 , 则+=123= 0, 1, 00, 10, 11, 01, 000, 100, 当语言为无穷集合时，用文法来描述语言。 Compiler Construction Principles2.3 文法和语言的形式定义 下面用A表示+，用式子A0表示符号串0

12、A或A生成符号串0，符号“”读作“生成”或“由组成”。则集合A可表示成： A0A1AA0AA1+=123= 0, 1, 00, 10, 11, 01, 000, 100, Compiler Construction Principles2.3.1 文法的形式定义 规则是一个符号与一个符号串的有序对（A,），通常写作： A（或A ) 1.1. 规则规则 也称产生式也称产生式 规则的作用是告诉我们如何用规则中的符号串生成语言中的序列。Compiler Construction Principles2.3.1 文法的形式定义 例如，前述例中一组规则 描述的语言序列只可能是由0和1组成的符号串。A0A

13、1AA0AA1Compiler Construction Principles2.3.1 文法的形式定义 规则中出现的符号分为两类，一类是终结符号，另一类是非终结符号。 非终结符号是出现在规则左部能派生出符号或符号串的那些符号，即每个非终结符号表示一定符号串的集合，用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。Compiler Construction Principles2.3.1 文法的形式定义 终结符号是不属于非终结符号的那些符号, 它是组成语言的基本符号，是一个语言的不可再分的基本符号，通常用小写字母表示。 例如，上例中的0和1。 Compiler Constructi

14、on Principles2.3.1 文法的形式定义 规则的非空有穷集合，通常表示成四元组VN是规则中非终结符号的集合。VT是规则中终结符号的集合。P 是文法规则的集合。 2. 文法文法G=VN,VT, P, S Compiler Construction Principles2.3.1 文法的形式定义 S 是一个非终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语言。 由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中关键是规则的集合。 Compiler Construction Principles2.3.1 文法的形式

15、定义将它们缩写为：A1 | 2 | | nA1A2An 其中每个i有时也称为是A的一个候选式。 为了书写方便，对于若干个左部相同的规则，如Compiler Construction Principles2.3.1 文法的形式定义我们约定： 第一条规则的左部是识别符号。 对文法G不用四元式显示表示，仅 只将规则写出。 Compiler Construction Principles2.3.1 文法的形式定义 G=(VN，VT，P，S )VN=AVT=0，1P: A 0 | 1 | A0 | A1S=A前例中描述+的文法是:Compiler Construction Principles2.3.1

16、 文法的形式定义 例1 设字母表=a, b，试设计一个文法，描述语言 L= a2n, b2n | n1 分析 设计一个文法来描述一个语言, 关键是设计一组规则生成语言中的符号串。因此，为设计该语言文法，必须分析这个语言是由怎样一些符号串组成的，即首先分析语言中串的结构特征： Compiler Construction Principles2.3.1 文法的形式定义当n1 L=aa, bb L=aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, 即语言L是由偶数个a，偶数个b这样的符号串组成的集合。 L=a2n, b2n | n1当n2 L=aaaa, bbbb当n3 L=a

17、aaaaa, bbbbbbCompiler Construction Principles2.3.1 文法的形式定义因此，定义语言L的文法 G=( VN，VT，P，S )其中： VN=A, B, DVT=a, bP= Aaa S=ABaa Dbb | bbD | bb | bbD注意:VTaa,bb | aaB| aaBCompiler Construction Principles2.3.1 文法的形式定义 提出问题: 描述该语言的文法是否唯一呢？ 显然，G不同于G。由此可见，对于一个给定的语言，描述该语言的文法是不唯一的。 P : AB | DBaa | aBaDbb | bDbCompi

18、ler Construction Principles 若G和G是两个不同的文法，如果它们描述的语言相同，那么，称G和G 为等价文法。2.3.1 文法的形式定义Compiler Construction Principles描述该语言的文法是否G？2.3.1 文法的形式定义 对此例，我们提出下面这样一个问题： G=( A, a, b, P, A )P= Aaa | bb | Aaa | Abb Compiler Construction Principles 对于文法G来说，它所产生的有些符号串，如aabb，bbaa， 不属于语言L，即设计的文法超出了所定义语言的范围。 2.3.1 文法的形式

19、定义P= Aaa | bb | Aaa | Abb Compiler Construction Principles2.3.1 文法的形式定义 例2 试设计一个表示所有标识符的文法 分析 题意是用文法定义标识符，必须确定P中规则。为了设计出一组规则，首先应搞清楚集合中串的结首先应搞清楚集合中串的结构特征构特征。Compiler Construction Principles2.3.1 文法的形式定义 用I代表标识符；L代表字母；D代表数字; 则定义标识符的文法为： 字母 字母或数字串标识符的结构可用下图表示:Compiler Construction Principles2.3.1 文法的形式

20、定义 G=(VN，VT，P，S)其中： VN=I, L, DVT=a,b,c, x,y,z,0,1,2, ,9P= IL S=ILa | b | c | | x | y | zD0 | 1 | 2 | 3 | | 9 | I L| I DCompiler Construction Principles2.3.1 文法的形式定义 若将定义标识符的文法设计成： 其中 VN，VT ，S 同上 G=(VN，VT，P，S )P= IL | I DLa | b | c | |x|y|zD0 | 1 | 2 | 3 | |9 Compiler Construction Principles2.3.1 文法的

21、形式定义 该文法不能定义ab，abc 仅由字母串组成的标识符，缩小了所定义语言的范围。 P= IL | I DLa | b | c | |x|y|zD0 | 1 | 2 | 3 | |9 Compiler Construction Principles2.3.1 文法的形式定义 用I代表标识符；L代表字母；D代表数字；T代表字母数字串；则定义标识符的文法还可写为： 字母 字母或数字串Compiler Construction Principles2.3.1 文法的形式定义P: IL | LT TL | D | LT | DT La | b | c | |x|y|z D0 | 1 | 2 | 3

22、 | | 9 字母 字母或数字串Compiler Construction Principles2.3.1 文法的形式定义 例3 用文法定义一个含、*的算术表达式，定义用下述自然语言描述： 变量是一个表达式； 若 E1和 E2是算术表达式, 则 E1E2、E1*E2、(E1) 也是算术表达式。 Compiler Construction Principles2.3.1 文法的形式定义 分析 算术表达式的定义用自然语言描述，这是对算术表达式的非形式定义，题意用文法来定义算术表达式，即是用形式化的方法定义表达式。定义算术表达式的文法为： G=(E, i, +, *, (, ) , P, E )其中

23、P为：Ei | E+E | E*E | (E)Compiler Construction Principles2.3.1 文法的形式定义P为：Ei | E+E | E*E | (E) i, i+i, i*i, i+i*i, (i+i), 注意：是符号串的集合Compiler Construction Principles2.3.1 文法的形式定义 例4 设字母表 = a, b , 试设计一个文法，描述语言 L= abna | n0 分析 该语言中串的结构特征是 当n1 L= aba L= aa, aba, abba, 当n2 L= abba 当n0 L= aa (b0=)Compiler Co

24、nstruction Principles2.3.1 文法的形式定义所以定义语言的文法为： G=( A, B, a, b, P, A )P= AaBa BBb | L= aa, aba, abba, Compiler Construction Principles2.3.1 文法的形式定义 例5 设字母表= (, ) ,试设计一个文法描述语言 L= (n )n | n0分析 该语言中串的结构特征是 当n=0 L= 注: (0 )0= 当n=1 L= ( ) 当n=2 L= ( ) L= , ( ), ( ), ( ), Compiler Construction Principles2.3.1

25、 文法的形式定义P: S | ( S )所以定义语言的文法为： L= (n )n | n0Compiler Construction Principles2.3.2 语言的形式定义 1. 直接推导 令G是一文法，我们称 xAy直接推导出 xy ，即 xAyxy 仅 A 是 G 的一条规则, 且 x, y(VNVT)*。也就是说从符号串 xAy 直接推导出 xy 仅使用一次规则。 Compiler Construction Principles2.3.2 语言的形式定义例如，设有文法GS: S01 使用规则 S01 此时 x， yP为：S 0 1 | 0 S 1 有如下直接推导：S0S1 使用规

26、则 S0S1 此时 x， yCompiler Construction Principles2.3.2 语言的形式定义 0S10011 使用规则 S01 此时 x0， y1 00S11000S111 使用规则 S0S1 此时 x00 , y11 000S11100001111 使用规则 S01 此时 x000 y111S 0 1 | 0 S 1Compiler Construction Principles2.3.2 语言的形式定义 (1) 形式上的区别，推导用“”表示，规则用“”表示 。 (2) 对文法G中任何规则A，我们有A，即推导的依据是规则。 注意推导和规则的区别：Compiler C

27、onstruction Principles即表示从0 出发，经 一步或若干步 或者说 使用若干次规则可推导出 n。 2.3.2 语言的形式定义 如果存在一个直接推导序列： 则我们称这个序列是一个从0至n的长度为n的推导，记为 2推导0 1 2 n+0 nCompiler Construction Principles2.3.2 语言的形式定义 例如 设有文法GE=(E,T,F,i,+,*,(,),P,E)对 i+i*i 有如下直接推导序列: 我们可记为 其中P为：EE+T | TTT*F | FF(E) | iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEi+i*i+C

28、ompiler Construction Principles2.3.2 语言的形式定义 3广义推导 我们有： 0n表示从0出发，经0步或若干步， 可推导出n。* 也就是说0n意味着0n或者0=n。*+EE*Ei+i*i*对上例 EE+T | T TT*F | F F(E) | iCompiler Construction Principles2.3.2 语言的形式定义 区别：直接推导的长度为1，推导的长度大于等于1，而广义推导的长度大于等于0。 Compiler Construction Principles2.3.2 语言的形式定义 4. 句型和句子 设有文法GS（S是文法G的开始符号）

29、如果S x, x (VNVT)* 则称符号串x 为文法GS的句型。* 如果S x, x VT* 则称符号串x为文法 GS的句子。*Compiler Construction Principles2.3.2 语言的形式定义 例1 设有文法GS： 我们有: 显然，符号串01、0S1、00S11和000111 都是文法GS的句型，而01和000111又是文法GS的句子。 S01 | 0S1S 01*S 0S1*S 00S11*S 000111*Compiler Construction Principles2.3.2 语言的形式定义 例2 设有文法GE： 试证明符号串 (i*i+i) 是文法GE的一

30、个句子。 分析 只要证明符号串 (i*i+i) 对文法 G存在一个推导，就可证明符号串 (i*i+i) 是文法GE的一个句子。 EE+E | E*E | (E) | iCompiler Construction Principles2.3.2 语言的形式定义 EE+E | E*E | (E) | iE(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i) 即有 E(i*i+i), 所以符号串(i+i*i)是文法 GE的一个句子。 *Compiler Construction Principles（2）L(G)是VT* 的子集。即属于VT* 的符 号串 x 不一定属于L(G)。

31、2.3.2 语言的形式定义 5语言 文法GS产生的所有句子的集合称为文 法G所定义的语言,记为L(GS)： 由语言定义可知：（1）一当文法给定，语言也就确定。L(GS)=x|Sx且xVT*Compiler Construction Principles2.3.2 语言的形式定义 例3 设有文法GS ：S01 | 0S1求该文法所描述的语言是什么？ 分析 由识别符号S出发，将推出一些什么样的句子，也就是说，L(GS)将由什么样的一些符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。 Compiler Construction Principles2.3.2 语言的形式定义 我们应用第

32、二个规则n1次，然后再应用第一个规则1次，有： S0S100S110n-1S1n-10n1n即S0n1n*可见，此文法定义的语言为L(GS)= 0n1n | n1S01 | 0S1Compiler Construction Principles2.3.2 语言的形式定义 例4 设有文法GS：S0S | 1S |该文法所定义的语言是什么？ 由该文法所确定的语言为 L(GS)=, 0, 1, 00, 01, 10, 11, = x | x0,1* Compiler Construction Principles2.3.2 语言的形式定义 例5 设有文法GA： 该文法所定义的语言是什么？ 分析 从文

33、法开始符号A出发可推导出以y开头后面跟一个或多个x结尾的符号串，所以该文法定义的语言为AyBB xB | xL(GA)= yxn | n1Compiler Construction Principles2.3.2 语言的形式定义 由此可见，从已知文法确定语言的中心思想是：从文法的开始符号出发，反复连续地使用规则替换、展开非终结符，找出句子的规律，用式子或自然语言描述出来。 Compiler Construction Principles2.3.2 语言的形式定义 形式语言理论可以证明如下两点：(1) 给定一种语言，能确定其文法，但这种文法不是唯一的，即：LG1或G2或(2) 给定一个文法，就能

34、从结构上唯一确定其语言，即：GL(G)；Compiler Construction Principles2.3.3 规范推导和规范归约 文法和语言是密切相关的，文法所定义的任一句型和句子, 都可以根据文法推导出来。我们提出一个问题：这种推导过程是否唯一？这种推导过程是否唯一？Compiler Construction Principles2.3.3 规范推导和规范归约 同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中与所选择非终结符的次序无关。Compiler Construction Principles2.3.3 规范推导和规范归约例如，设有文法GN1 N1NNND

35、| DD0 | 1 | 2 N1NNDN2D212 N1NNDDD1D12 N1NNDDDD212句子12有下列三种不同的推导序列:Compiler Construction Principles2.3.3 规范推导和规范归约 最左(最右)推导，是指对于一个推导序列中的每一步直接推导 , 都是对 中的最左(最右)非终结符进行替换。 最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。 Compiler Construction Principles2.3.3 规范推导和规范归约 例 设有文法GS: 请给出句子101001的最右、最左推导。 分析 最右推导是指在推导过程中任何一步 (和是

36、句型)，都是对中的最右非终结符进行替换。SABAA0 | 1BB0 | S1Compiler Construction Principles2.3.3 规范推导和规范归约SABAS1AAB1AA01A1B01A10011B1001101001句子101001的最右推导为: SABAA0 | 1BB0 | S1Compiler Construction Principles2.3.3 规范推导和规范归约 最左推导是指在推导过程中任何一步 (和是句型), 都是对的最左非终结符进行替换。句子101001的最左推导为： SABAA0 | 1BB0 | S1SAB1BB10B10S110AB1101BB

37、11010B1101001Compiler Construction Principles2.3.3 2.3.3 规范推导和规范归约规范推导和规范归约归约是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替换的过程，而归约则是把句型中的某个子串用一个非终结符来替换的过程。 若用表示归约，设A是文法G中的 一个规则，则我们有： .xAyxyxyxAy.Compiler Construction Principles2.3.3 2.3.3 规范推导和规范归约规范推导和规范归约例如，例文法GN1中有规范推导： 则有规范归约： 规范推导的逆过程，称为最左归约，也称为规范归约。 N1NNDN

38、2D21212D2.N2.ND.N.N1.Compiler Construction Principles2.3.4 递归规则与文法的递归性递归规则 如果文法中有规则 AA 称为规则左递归。 如果文法中有规则 A A 称为规则右递归。 如果文法中有规则 A A 称为规则递归。Compiler Construction Principles2.3.4 递归规则与文法的递归性文法的递归性若文法中有推导AA 称文法左递归。+若文法中有推导A A称文法右递归。+若文法中有推导A A 称文法递归。+Compiler Construction Principles2.3.4 递归规则与文法的递归性例如 文

39、法中有如下规则： 这三条规则都不是递归规则，但有 在文法中使用递归规则，使得我们能用有限的规则去定义无穷集合的语言。 UVxVUy | zUVx Uyx , 则该文法是左递归的。Compiler Construction Principles2.3.4 递归规则与文法的递归性 例2 考虑文法GA： 由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为: AaB | bBBa | bL(GA)= aa, ab, ba, bb Compiler Construction Principles 2.3.4 递归规则与文法的递归性例3 考虑文法GN1 该文法有直接左递归规则 NND, 则称

40、该文法为左递归文法或说文法左递归，其定义的语言为0,1,2+。 N1NNND | DD0 | 1 | 2Compiler Construction Principles 2.3.4 递归规则与文法的递归性 也就是说，当一个语言是无穷集合时，则定义该语言的文法一定是递归的。 若不用递归规则，则 NND 需要用 ND | DD | DDD | 即无穷多条规则来定义由数字0,1,2 组成的所有无符号整数。 Compiler Construction Principles2.4 文法的类型 著名的语言学家乔姆斯基(Chomsky) 将文法和语言分为四大类，即0型、1型、 2型、3型。划分的依据是对文法

41、中的规 则施加不同的限制。 Compiler Construction Principles2.4 文法和语言的分类 0型文法（无限制文法） 若文法G=(VN,VT, P, S)中的每条规则 是这样一种结构： 而且中至少含一个非终结符, 则称G 是0型文法。(VNVT)+ , (VNVT)*0型文法描述的语言是0型语言。0型文法没有加任何限制条件，又称为 无限制性文法，相应的语言称为无限制 性语言。0型语言由图灵机识别。Compiler Construction Principles2.4 文法和语言的分类 例如，有0型文法G=(VN,VT, P, S) 其中：VN=A,B,S , VT=0,

42、1 其描述的 0 型语言为 L0(GS)= P: S 0AB 1B 0 B SA | 01 A1 SB1 A0 S0BCompiler Construction Principles2.4 文法和语言的分类 1型文法（上下文有关文法） 1型文法也称为上下文有关文法， 相应 的语言又称为上下文有关语言。 若文法G=(VN,VT, P, S)中的每一条规则的 形式为 A , 其中： , (VNVT)* ,AVN ,则称G是1型文法。1型文法描述的语言是1型语言。1型语言由线性界限自动机识别。 (VNVT)+Compiler Construction Principles2.4 文法和语言的分类 例

43、如，有1型文法G=(VN,VT, P, S) 其中：VN=S,A,B , VT=a,b,c P: S aSAB | abB BA BA BA AA AA AB bA bb bB bc cB cc其描述的1型语言为L1(GS)=anbncn | n1 Compiler Construction Principles2.4 文法和语言的分类 2型文法（上下文无关文法） 2型文法又称上下文无关文法，其产生的 语言又称为上下文无关的语言。 若文法G=(VN,VT, P, S)中的每一条规则的 形式为 A , 其中： AVN ,(VNVT)*则称G是2型文法。2型文法描述的语言是2型语言。2型语言由下推

44、自动机识别。Compiler Construction Principles例如前面描述算术表达式的文法GE:EE+E | E*E | (E) | i2.4 文法和语言的分类 Compiler Construction Principles 其描述的语言为 L2(GS)=x | x a, b+ 且x中a和b的个数相同 例如，有2型文法G=(VN,VT, P, S) 其中：VN=S, A, B , VT=a, b P= S aB | bA A a | aS | bAA B b | bS | aBB 2.4 文法和语言的分类 Compiler Construction Principles2.4

45、文法和语言的分类 3型文法（正规文法） 右线性文法和左线性文法都称为3型文法。 若文法G=(VN,VT, P, S)中的每一条规则的形式 为A aB 或 A a , 其中： A , BVN, a VT*, 则称G是右线性文法。 若文法G=(VN,VT, P, S)中的每一条规则的形式 为A Ba 或 A a , 其中： A , BVN , a VT*, 则称G是左线性文法。3型文法描述的语言是3型语言。3型语言由有穷自动机识别。 3型文法也称正规文法。正规文法产生的语言 称为正规语言。Compiler Construction Principles 例如，用左线性正规文法和右线性正规文法定义标

46、识符 2.4 文法和语言的分类 用I代表标识符; l代表任意一个字母; d代表任意一个数字; 则定义标识符的文法为：左线性文法: P: I l | Il | Id右线性文法: P: I l | lT Tl | d | lT| dTCompiler Construction Principles 例如，用左线性正规文法和右线性正规文法定义无符号整数2.4 文法和语言的分类 用N代表无符号整数; d代表任意一个数字；则定义的无符号整数文法为：左线性文法: P: N Nd | d右线性文法: P: N dN | dCompiler Construction Principles2.4 文法和语言的分

47、类 由上述四类文法的定义可知, 从0型文法到3型文法, 是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法, 而由它们所定义的语言类是依次缩小的，有 L0 L1 L2 L3 。 Compiler Construction Principles2.4 文法和语言的分类2型文法型文法1型文法型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法Compiler Construction Principles2.5 上下文无关文法与语法树上下文无关文法有足够的

48、能力描述程序设计语言的语法结构上下文无关文法有足够的能力描述程序设计语言的语法结构描述简单算术表达式的文法G=(E,+,*,i,(,),P,E)其中P为：Ei , EE+E , EE*E , E(E) 描述一种简单赋值语句的产生式：赋值语句i =E描述条件语句的产生式：条件语句if条件then语句 if条件then语句else语句Compiler Construction Principles2.5 上下文无关文法与语法树1.规范推导和规范归约规范推导和规范归约Gs: SaAS ASbA ASS Sa Aba构造句子构造句子aabbaa推导过程推导过程推导过程一：推导过程一：S aAS aAa

49、 aSbAa aSbbaa aabbaa推导过程二：推导过程二：S aAS aSbAS aabAS aabbaS aabbaa推导过程三：推导过程三：S aAS aSbAS aSbAa aabAa aabbaaCompiler Construction Principles2.5 上下文无关文法与语法树1.规范推导和规范归约规范推导和规范归约最左（最右）推导：最左（最右）推导：在推导的任何一步在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中中的最左（右）非终结符进行替换的最左（右）非终结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范

50、推导所得的句型称为规范句型练习：设有文法练习：设有文法GE： EE+T|T TT*F|F F(E)|i给出句子给出句子i*i+i的最左和最右推导的最左和最右推导Compiler Construction Principles2.5 上下文无关文法与语法树推导和语法树推导和语法树 2. 语法树语法树 对句型的推导过程给出一种图形表示, 这种表示称为语法树，也称推导树。 Compiler Construction Principles 2.5.1 推导和语法树例如 设有文法GE:构造句型i*i+i的语法树。首先给出句型的推导过程 (最左推导) ：EE+T | ET | TTT*F | T/F |

51、FF(E) | iEE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+iCompiler Construction Principles2.5.1 推导和语法树根据推导过程构造句型i*i+i的语法树如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+T ii*i+Tii*i+FFi*i+iiCompiler Construction Principles2.5.1 推导和语法树 由例可知，语法树的构造过程是从文法的开始符号出发，构造一个推导的过程。 因为文法的每一个句型 (句子) 都存在一 个推导，所以文法的每个句型(句子) 都存在一棵对应的语法树。Comp

52、iler Construction PrinciplesEE+T E+F E+i T+i T*F+i T*i+i F*i+i i*i+i2.5.1 推导和语法树 对句型i*i+i，还可给出最右推导： EE+TTT*FFiiFiCompiler Construction Principles2.5.1 推导和语法树 这也就是说，一棵语法树表示了 一个句型的种种可能的(但未必是所 有的)不同推导过程, 包括最左(最右) 推导。Compiler Construction Principles3.5.1 推导和语法树 子树语法树的子树是由某一结点连同所有分枝组成的部分。EE+TTT*FFiiFiCom

53、piler Construction Principles3.5.1 推导和语法树 简单子树 语法树的简单子树是指只有单层分枝的子树。EE+TTT*FFiiFiCompiler Construction Principles2.5.2 文法的二义性从前面的讨论可以看出，对于文法G中 任一句型的推导序列, 我们总能为它构造 一棵语法树，现在我们提出一个问题： 文法的某个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左(最右)推导呢？ Compiler Construction Principles2.5.2 文法的二义性 例如 设有文法GE： 句子 i*i+i 有两个不同的最左

54、推导，对应两棵不同的语法树。E E+E | E*E | (E) | iCompiler Construction Principles2.5.2 文法的二义性 最左推导1 EE+EE*E+E i*E+Ei*i+E i*i+i 最左推导2 EE*Ei*E i*E+Ei*i+E i*i+i EE*EE+EiiiEE+EE*EiiiCompiler Construction Principles2.5.2 文法的二义性 如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。 或者说，若一个文法中存在某个句子，它有两个不同的最左 (最右) 推导，则这个文法是二义性的。 E E+E |

55、E*E | (E) | iCompiler Construction Principles文法的二义性和语言的二义性是两个不同的文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法概念。因为可能有两个不同的文法G和和G，其中其中G是二义的，但是却有是二义的，但是却有L(G)=L(G)，也，也就是说，这两个文法所产生的语言是相同的。就是说，这两个文法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是个程序设计语言来说，常

56、常希望它的文法是无二义的，因为希望对它的每个语句的分析无二义的，因为希望对它的每个语句的分析是唯一的。是唯一的。Compiler Construction Principles2.6 句型分析l句型分析句型分析就是识别一个符号串是否为某文法的句就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。型，是某个推导的构造过程。l在语言的编译实现中，把完成句型分析的程序称在语言的编译实现中，把完成句型分析的程序称为为分析程序分析程序或或识别程序识别程序。分析算法又称。分析算法又称识别算法识别算法。l从左到右的分析算法从左到右的分析算法，即总是从左到右地识别输，即总是从左到右地识别输入符号串，首

57、先识别符号串中的最左符号，进而入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。依次识别右边的一个符号，直到分析结束。Compiler Construction Principles句型的分析算法分类l分析算法可分为：分析算法可分为：l自上而下分析法自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。寻找与输入符号串匹配的推导。l自下而上分析法自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。文法的开始符号。 Compi

58、ler Construction Principles1.自上而下的语法分析例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabdCompiler Construction Principles2.自下而上的语法分析例：文法例：文法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 cAdComp

59、iler Construction Principles句型分析中的关键问题1）在自上而下的分析方法中）在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产生式产生式进行推导进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有，且有n条规则：条规则：BA1|A2|An，那么如何确定用哪个右部去替代，那么如何确定用哪个右部去替代B？2）在自下而上的分析方法中）在自下而上的分析方法中如何如何识别可归约的串识别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一个选择一个子串子串，将它，将它归约归约到到某个非终结符号某个非终结符

60、号，该子串称为，该子串称为“可可归约串归约串”Compiler Construction Principles2.6短语、直接短语和句柄短语短语 令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 则称 是相对于非终结符A的, 句型的短语。SA*+且 A Compiler Construction Principles2.6 短语、直接短语和句柄则称是直接短语。 直接短语直接短语 SA*且 A 令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 Compiler Construction Principles2.6 短语、直接短语和句柄 注意：短语和直接短语的区