编译原理及其习题解答(武汉大学出版社)课件chap2.ppt
《编译原理及其习题解答(武汉大学出版社)课件chap2.ppt》由会员分享,可在线阅读,更多相关《编译原理及其习题解答(武汉大学出版社)课件chap2.ppt(84页珍藏版)》请在三一文库上搜索。
1、1,第二章 文法和语言,要点(本章是基础) 1、概念:文法,推导,直接推导,最左(右)推导,产生式,句型,短语,直接短语,句柄,语法树,规范推导,二义文法等 2、4种文法的定义、文法的构造和文法的推导 3、语法树的构造和最左(右)推导; 4、二义文法、二义性的证明; 5、句型分析;,2,词法规则:自动机 语法规则:上下文无关文法,3,引言,语言包括语法和语义两方面。 语法是一组规则,用以判断什么样的符号序列是合法的; 语义指含义,如变量的类型、作用域是否符合正确的语法。常把程序设计语言的语义分为二类:静态语义和动态语义。静态语义是一系列限定规则,并确定哪些合乎语法的程序是合适的;动态语义(或称
2、运行语义、执行语义),表明程序要做些什么,要计算什么。 阐明语法的一个工具是文法,常采用上下文无关文法作为程序设计语言语法的描述工具。,4,补充: 文法的直观概念(1/5),描述一种语言,无非是说明这种语言的句子。如果该语言所含的句子是有限的,那么只要一一列举出即可;若是无限的,则存在如何给出有穷表示的问题。但无论如何,某语言的句子总是存在着一种组成结构,即所谓的规则(或称文法)。 文法:描述语言的语法结构的形式规则(即语法规则)。,5,直观文法举例(2/5),例如:简单的汉语句子的构成规则 := := | := 我 | 你 | 他 :=王明| 大学生|工人|英语 := :=是 |学习 :=
3、| 则 “我是大学生”是句子,6,“我是大学生”的推导过程: 我 我 我是 我是 我是大学生 依次可以推导出句子“王明是大学生”、“我学习英语”等等,推导过程(3/5),7,程序设计语言对文法的要求(4/5),这些规则必须是准确的,易于理解的,且应当有相当强的描述能力,足以描述各种不同的结构。,8,文法作用(5/5),(1)定义句子的结构; (2)用适当条数的规则把语言的全部句子描述出来,以有穷集合刻划无穷集合。,9,2 符号串及其运算 (1)符号串:由字母表中的符号组成的任何有穷序列。 说明: 字母间的顺序 不同顺序组成的符号串是不同的; (2)符号串长度 符号串内所含符号的个数,若x=st
4、ring,则|x|=6; 其中不含任何符号的符号串称为空符号串,长度| |0,2.1 语言成分,1 字母表(符号表)与符号 元素(或称符号)的非空有穷集合,用符号表示。 不同语言有不同的字母表。如汉语包括汉字、数字、标点符号等;C语言包括字母、数字和保留字等等。,10,符号串的运算(1/3),符号串的头尾,固有头和固有尾: 设 z=xy 是一个符号串,则x是z的头,y是z的尾。如果x是非空的,那么y是是固有尾;如果y是非空的,那么x是固有头。,例:z=abc,则 z的头:、a、ab、abc; 固有头: 、a、ab; z的尾:、c、bc、abc; 固有尾: 、c、bc;,当我们对符号z=xy 的
5、头感兴趣而对其余部分不感兴趣时,我们可以采用省略写法:z=x。如果只是为了强调x在符号串中的某处出现,则可表示为:z=x;符号t是符号串z的第一个符号,则表示为:z=t。,11,(3)符号串的连接,设x和y是符号串,它们的连接xy是把y的符号写在x的符号之后得到的符号串。 例如:x=abc,y=DEF,则xy=abcDEF;,若| x | = n,| y |m,则| xy | = n+m,对任意的符号串x,有 x = x = x,12,(4) 符号串集合的乘积,设A、B是两个符号串的集合,则AB表示A与B的乘积,定义为: AB=xy|xA,yB 如:若A=ab,c, B=d,efg,则AB=a
6、bd,abefg,cd,cefg 特别地,有:A=A=A 空集 表示不含任何元素的空集。 有: A=A = 请区别: ,三种表示方法的含义,13,(5) 符号串的方幂,同一符号串的连接可以写成方幂的形式。 设x是符号串,把x自身连接n次得到的符号串z,即z=xxxx,称为符号串x的方幂,记作z=xn,有: x0= x1= x x2= xx x3= xxx 当n0时, xn x xn-1 = xn-1 x,14,(6)符号串集合的方幂,同一符号串集合的连接也可以写成方幂的形式。 设符号串集合为A,则有: A0= A1= A A2= AA A3= AAA 当n0时, An A An-1 = An-
7、1 A 例如:A=ab,c,则AA= AAA= ,15,(7)符号串集合的正闭包,设符号串集合为A,则A的正闭包记为A+ ,定义为: A+ = A1 A2 An 表示A上所有有穷长串的集合 例如:A=ab,c,AA= , AAA= ,(8)符号串集合的自反闭包,设符号串集合为A,则A的自反闭包记为A* ,定义为: A* = A0 A1 A2 An 即A* = A0 A+ = A+ 例如: A= a,b,则 A*=, a, b, aa, ab, ba, bb, aaa, ,A+ = A* A = AA*,16,2.2 产生式文法和语言,2.2.1 文法的形式定义是一个四元组 G =(VN,VT,
8、P,S) VN 非终结符号集,非终结符号代表的是语法范畴,也就是它是一类(或集合)的记号,而不是一个个体记号。如“表达式”、“语句”、“分程序”等等,都是表达一定的语法概念。因此,每个非终结符表示一定符号串的集合(由终结符和非终结符 组成);(如简单汉语句子中。),VT 终结符号集合,终结符是构成语言的基本符号,也就是说,它是一个语言的不可再分的基本符号;,P 产生式(或称规则,重写规则,生成式)集合。所谓产生式是定义语法范畴的一种书写规则。一个产生式的形式是 (或:= ),其中 “”读为“是”或“定义为”; 产生式的左部 (VNVT )*且至少含有一个非终结符号,右部(VNVT)* ,即由终
9、结符或(与)非终结符组成的一符号串,允许是空字,17,2.2 产生式文法和语言,例如:简单的汉语句子的构成规则 := := | := 我 | 你 | 他 :=王明| 大学生|工人|英语 := :=是 |学习 := | 则 “我是大学生”是句子,18,文法的形式定义,S 开始符号,即文法的第一个非终结符。 开始符号代表了所定义的语言中我们最感兴趣的语法范畴,如在程序语言中,我们感兴趣的是“程序”,注意: 1、 VN VT 即不含公共元素 ; 2 、产生式是有限的; 3、开始符号S至少必须在某个产生式的左部出现一次; 4、为书写方便,若干个左部相同的产生式如: P1, P2,Pn 合并成: P1|
10、2|n 其中i称为P的一个候选式。,19,文法定义举例1,例2.1 表示算术表达式的文法描述:G1 =(VN,VT,P,S) 其中VNE VT =i , +,*, ( , ) P=E i , E E + E , E E * E , E ( E ) S=E 或者直接写为: G1 =(E, i , +,*, ( , ) , E i , E E + E , E E * E , E ( E ) , E ),20,文法定义举例2,例2 文法G =(VN,VT,P,S) 其中VN标识符,字母,数字, VT a, b, c, , x, y, z, 0,1, , 8, 9 P= | | , a|b|c|x|y
11、|z, 0|1|2|8|9 S = ,21,用文法定义语言的中心思想是:从文法的开始符号出发,反复连续使用产生式,对非终结符施行替换和展开。 例如文法G:E E+E | E*E | ( E ) | i,其中唯一非终结符E可以看成是代表一类算术表达式。 从E出发,进行一系列的推导,推出种种不同的算术表达式。如根据上述规则可推出 ( i+i ): E = ( E )= ( E+E )= ( i+E )= ( i+i) 我们称这样的一串替换是从E推出( i+i )的一个推导,这个推导提供了一个证明,证明( i+i )是文法G所定义的一个算术表达式。,2.2.2 文法的推导,22,有关推导的定义,定义
12、2.3 直接推导 = 若A直接推导出 ,即 A=,当且仅当A-是一个产生式,且、(VNVT)* 符号 =指推导一步,即推导每前进一步总是引用一条规则(产生式),定义2.4 长度为n(n1)的推导 若存在直接推导序列a1= a2= =an,则称a1可推导出an。 a1 an 表示:从a1出发经过一步或若干步,可推导出an 。,定义2.5 长度为n(n0)的推导 a1 an 表示:从a1出发经过0步( a1 an )或若干步,可推导出an 。,23,2.2.3 句型、句子、语言,例1:证明终结符号串( i*i+i )是文法G:E E+E | E*E | (E)| i的一个句子 证明: E =( E
13、 ) =(E+E)=(E*E+E) =(i*E+E) =(i*i+E)=(i*i+i) 是从开始符号E到( i*i+i )的一个推导。 其中E、(E)、(E+E)、(E*E+E)、 (i*E+E) 、 (i*i+E) 、 (i*i+i)都是这个文法的一个句型,1.句型:设GS是一个文法,S是它的开始符号,若S ,则称是文法GS的句型。 2.句子:仅含终结符的句型是一个句子,即S ,VT*, 则是句子。 3.语言:文法G所产生的句子的全体是一个语言,记作L(G) L(G)=|S ,且VT*,24,语言的例子,例2:文法G2 A :A bA | cc,证明cc、bcc、bbcc属于L(G2)。 证
14、明: A=cc, A= Ba=bcc, A =bA =bbA = bbcc cc、bcc、bbcc、是属于L(G2)的,例3:文法GS: (1) S0S1;(2) S01。GS的语言是什么? 解:对第一个产生式使用n-1次,然后使用第二个产生式一次,得到: S = 0S1 = 00S11= = 0n-1S1n-1 = 0n1n 因此L(G)=0n1n|n 1,例4:下列文法的语言是什么? GS=(S, , S - , S ) GA=(A, , ,A ),25,2.2.4 文法的等价,若L(G1) = L(G2),则称文法G1和G2是等价的 例1:G1=(VN, VT, P, S), VN =S
15、, VT =0, 1,P由下列产生式组成: (1) S0S1; (2) S01; G2=(VN, VT, P, A), VN =A, R, VT =0, 1,P由下列产生式组成: (1) A 0R ; (2) A 01; (3) R A1,26,什么是递归文法?,1.递归规则:规则右部有与左部相同的符号 对于 U - xUy 若x=,即U - Uy,左递归; 若y=,即U - xU,右递归;,2.递归文法:文法G,存在U VN 若 U=U, 则G为递归文法; 若 U=U, 则G为左递归文法; 若 U=U, 则G为右递归文法;,27,4. 递归文法的优点:可用有穷条规则,定义无穷语言,例:对于前
16、面给出的标识符的文法是有递归文法,用y有限条规则就可以定义出所有的标识符。若不用递归文法,那将要用多少条规则呢?,!,3. 左递归文法的缺点:不能用自顶向下的方法来进行语 分析,会造成死循环,28,2.3 文法的分类,2.3.1 文法分类 乔姆斯基(Chomsky)建立的形式语言对计算机科学的发展具有深刻的意义。他把文法分成四种类型:0型、1型、2型和3型。0型强于1型,1型强于2型,2型强于3型,它们的差别在于对产生式施加不同的限制。,29,定义 0型文法(或称短语文法, phrase structure grammar,PSG),G=( VN, VT, P, S)是0型文法是指: 若它的每
17、个产生式是这样一种结构: (VNVT)+且至少含有一个非终结符, (VNVT)*。 任何0型文法都是递归可枚举的。 0型文法的能力相当于图灵机(计算机的一种简单的理论模型)。 称L为递归可枚举的:若存在一个产生L的过程。 称L为递归的:若存在一个识别L的算法。,30,定义 1型文法(或称上下文有关文法,CSG Context Sensitive Grammar),如果对0型文法加以以下的限制,则可得到1型文法。 设G=( VN, VT, P, S)为一文法,若G的任何产生式 均满足| | (指符号串的长度),仅仅S 例外。 课本P24例2.2。,例:设G=(VN, VT, P, S), VN
18、=S, B, E, VT =a, b, e,P由下列产生式组成: (1) S aSBE ; (2) S aBE ; (3) EB BE ; (4) aB ab ; (5) bB bb ; (6) bE be ; (7) eE ee ; 求 GS的语言是什么。,31,接上页例子,分析:条产生式中只有第条具有递归性,其它的产生式最终都向终结符靠拢。 注意: S aSBE 与S0S1的相似性,都可用同一模板来表示S S 使用产生式(1) n-1次,得推导序列:S an-1S(BE)n-1; 使用产生式(2) 一次,得到: S an(BE)n; 使用产生式(3)的右部替换EB,使最终得到的串中,所有的
19、B都先于所有的E,即S anBnEn;,32,接上例,使用产生式(4)一次,得到S an bBn1En; 使用产生式(5) n-1次,得到S an bnEn; 使用产生式(6) 一次,得到S an bn eEn-1; 使用产生式(7) n-1次,得到S an bn en; 因此,L(G)=an bn en | n 1,说明:上述分析中,步骤是关键一步,否则不能推导出终结符号串。例如假设n=3,S aaaBEBEBE aaaBBEEBE aaabBEEBE aaabbEEBE aaabbeEBE aaabbeeBE,33,上下文有关,顾名思义就是对非终结符进行替换时必须考虑上下文。例如,1型文法
20、G的产生式也可写成A ,其中、都在(VNVT)*中,且 ,A VN ,则说明了非终结符A必须在、这样一个上下文环境中才可以替换。 上下文有关文法能生成anbncn类特征的语言。但它不能描述L=c|(a|b)*类语言。,对上下文有关文法的说明,34,定义 2型文法(或称上下文无关文法,CFG Context Free Grammar),设G=( VN, VT, P, S)为一文法,若G的任何产生式形似A ,其中A VN, (VNVT)+ 。,例:G=(S,A,B,a,b,P,S),其中P由下列产生式组成 SaB|bA Aa|aS|bAA Bb|bS|aBB 例:G=(VN, VT, P, S),
21、 VN =S, VT =0, 1,P由下列产生式组成: (1) S0S1; (2) S01;,35,上下文无关文法的说明,上下文无关,顾名思义就是非终结符的替换可以不必考虑上下文。由于这种文法对程序已基本可以描述,因此,上下文无关文法常简称为文法。 上下文无关文法最多能生成anbn类特征的语言,不能生成anbncn类特征的语言。,36,设G=( VN, VT, P, S)为一文法,若G的任何产生式A 或A B ,其中A、B VN , VT* 。 对任何正规文法G,都可以设计一个不确定的有穷自动机NFA,它能够而且只能够识别G的语言。,定义 3型文法(或称正规文法,RG Regular Gram
22、mar),例:文法G=(S,A,B,0,1,P,S),其中P由下列产生式组成 S 0A|1B|0 A 0A|1B|0S B 1B|1|0,37,左线性文法,设G=( VN, VT, P, S)为一文法,若G的任何产生式A或A B ,其中A、B VN , VT* 。,左线性文法=右线性文法(非严格的转换) 设左线性文法为G=( VN, VT, P, S),右线性文法为G=( VN, VT, P, S),其中 VN= VN+S,P转化方式为:,38,2.3.2 文法分类的意义,自动机 具有有穷描述的某种机器,对于给定文法,可接收某个终结符号串,并确定是否能从该文法推导出来。 分析器 判定(分析)一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 及其 习题 解答 武汉 大学出版社 课件 chap2
链接地址:https://www.31doc.com/p-2258584.html