编译原理及其习题解答(武汉大学出版社)课件chap2.ppt
《编译原理及其习题解答(武汉大学出版社)课件chap2.ppt》由会员分享,可在线阅读,更多相关《编译原理及其习题解答(武汉大学出版社)课件chap2.ppt(84页珍藏版)》请在三一办公上搜索。
1、1,第二章 文法和语言,要点(本章是基础)1、概念:文法,推导,直接推导,最左(右)推导,产生式,句型,短语,直接短语,句柄,语法树,规范推导,二义文法等2、4种文法的定义、文法的构造和文法的推导3、语法树的构造和最左(右)推导;4、二义文法、二义性的证明;5、句型分析;,2,词法规则:自动机 语法规则:上下文无关文法,3,引言,语言包括语法和语义两方面。语法是一组规则,用以判断什么样的符号序列是合法的;语义指含义,如变量的类型、作用域是否符合正确的语法。常把程序设计语言的语义分为二类:静态语义和动态语义。静态语义是一系列限定规则,并确定哪些合乎语法的程序是合适的;动态语义(或称运行语义、执行
2、语义),表明程序要做些什么,要计算什么。阐明语法的一个工具是文法,常采用上下文无关文法作为程序设计语言语法的描述工具。,4,补充:文法的直观概念(1/5),描述一种语言,无非是说明这种语言的句子。如果该语言所含的句子是有限的,那么只要一一列举出即可;若是无限的,则存在如何给出有穷表示的问题。但无论如何,某语言的句子总是存在着一种组成结构,即所谓的规则(或称文法)。文法:描述语言的语法结构的形式规则(即语法规则)。,5,直观文法举例(2/5),例如:简单的汉语句子的构成规则:=:=|:=我|你|他:=王明|大学生|工人|英语:=:=是|学习:=|则“我是大学生”是句子,6,“我是大学生”的推导过
3、程:我 我 我是 我是 我是大学生 依次可以推导出句子“王明是大学生”、“我学习英语”等等,推导过程(3/5),7,程序设计语言对文法的要求(4/5),这些规则必须是准确的,易于理解的,且应当有相当强的描述能力,足以描述各种不同的结构。,8,文法作用(5/5),(1)定义句子的结构;(2)用适当条数的规则把语言的全部句子描述出来,以有穷集合刻划无穷集合。,9,2 符号串及其运算(1)符号串:由字母表中的符号组成的任何有穷序列。说明:字母间的顺序 不同顺序组成的符号串是不同的;(2)符号串长度 符号串内所含符号的个数,若x=string,则|x|=6;其中不含任何符号的符号串称为空符号串,长度|
4、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 的头感兴趣而对其余部分不感兴趣时,我们可以采用省略写法:z=x。如果只是为了强调x在符号串
5、中的某处出现,则可表示为: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=abd,abefg,cd,cefg特别地,有:A=A=A 空集 表示不含任何元素的空集。有:A=A=请区别:,三种表示方法的含义
6、,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=AA2=AAA3=AAA 当n0时,An A An-1=An-1 A例如:A=ab,c,则AA=AAA=,15,(7)符号串集合的正闭包,设符号串集合为A,则A的正闭包记为A+,定义为:A+=A1 A2 An 表示A上所有有穷长串的集合例如:
7、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,P,S)VN 非终结符号集,非终结符号代表的是语法范畴,也就是它是一类(或集合)的记号,而不是一个个体记号。如“表达式”、“语句”、“分程序”等等,都是表达一定的语法概念。因此,每个非终结符表示一定符号串的集合(由终结符和非终结符 组成);(如简单汉语句
8、子中。),VT 终结符号集合,终结符是构成语言的基本符号,也就是说,它是一个语言的不可再分的基本符号;,P 产生式(或称规则,重写规则,生成式)集合。所谓产生式是定义语法范畴的一种书写规则。一个产生式的形式是(或:=),其中“”读为“是”或“定义为”;产生式的左部(VNVT)*且至少含有一个非终结符号,右部(VNVT)*,即由终结符或(与)非终结符组成的一符号串,允许是空字,17,2.2 产生式文法和语言,例如:简单的汉语句子的构成规则:=:=|:=我|你|他:=王明|大学生|工人|英语:=:=是|学习:=|则“我是大学生”是句子,18,文法的形式定义,S 开始符号,即文法的第一个非终结符。开
9、始符号代表了所定义的语言中我们最感兴趣的语法范畴,如在程序语言中,我们感兴趣的是“程序”,注意:1、VN VT 即不含公共元素;2、产生式是有限的;3、开始符号S至少必须在某个产生式的左部出现一次;4、为书写方便,若干个左部相同的产生式如:P1,P2,Pn 合并成:P1|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
10、文法G=(VN,VT,P,S)其中VN标识符,字母,数字,VT a,b,c,x,y,z,0,1,8,9 P=|,a|b|c|x|y|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所定义的一个算
11、术表达式。,2.2.2 文法的推导,22,有关推导的定义,定义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的一个句子
12、证明:E=(E)=(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)。证明:A=cc,A=Ba=bcc,A
13、=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,VT=0,1,P由下列产生式组成:(1)S0S1;(2)S01;G2=(VN,VT,P,A),VN=A,R,VT=0,1,
14、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.递归文法的优点:可用有穷条规则,定义无穷语言,例:对于前面给出的标识符的文法是有递归文法,用y有限条规则就可以定义出所有的标识符。若不用递归文法,那将要用多少条规则呢?,!,3.左递归文法的缺点:不能用自顶向下的方法来进行语分析,会造成死循环,28,2.
15、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型文法是指:若它的每个产生式是这样一种结构:(VNVT)+且至少含有一个非终结符,(VNVT)*。任何0型文法都是递归可枚举的。0型文法的能力相当于图灵机(计算机的一种简单的理论模型)。称L为递归可枚举的:若存在一个产生L的过程。称L
16、为递归的:若存在一个识别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=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,接上页例子,分析:条产生式中只有第条具有递归
17、性,其它的产生式最终都向终结符靠拢。注意:S aSBE 与S0S1的相似性,都可用同一模板来表示S S 使用产生式(1)n-1次,得推导序列:S an-1S(BE)n-1;使用产生式(2)一次,得到:S an(BE)n;使用产生式(3)的右部替换EB,使最终得到的串中,所有的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,说明:上述分析中,步骤
18、是关键一步,否则不能推导出终结符号串。例如假设n=3,S aaaBEBEBE aaaBBEEBE aaabBEEBE aaabbEEBE aaabbeEBE aaabbeeBE,33,上下文有关,顾名思义就是对非终结符进行替换时必须考虑上下文。例如,1型文法G的产生式也可写成A,其中、都在(VNVT)*中,且,A VN,则说明了非终结符A必须在、这样一个上下文环境中才可以替换。上下文有关文法能生成anbncn类特征的语言。但它不能描述L=c|(a|b)*类语言。,对上下文有关文法的说明,34,定义 2型文法(或称上下文无关文法,CFG Context Free Grammar),设G=(VN,
19、VT,P,S)为一文法,若G的任何产生式形似A,其中A VN,(VNVT)+。,例:G=(S,A,B,a,b,P,S),其中P由下列产生式组成SaB|bA Aa|aS|bAABb|bS|aBB例:G=(VN,VT,P,S),VN=S,VT=0,1,P由下列产生式组成:(1)S0S1;(2)S01;,35,上下文无关文法的说明,上下文无关,顾名思义就是非终结符的替换可以不必考虑上下文。由于这种文法对程序已基本可以描述,因此,上下文无关文法常简称为文法。上下文无关文法最多能生成anbn类特征的语言,不能生成anbncn类特征的语言。,36,设G=(VN,VT,P,S)为一文法,若G的任何产生式A
20、或A B,其中A、B VN,VT*。对任何正规文法G,都可以设计一个不确定的有穷自动机NFA,它能够而且只能够识别G的语言。,定义 3型文法(或称正规文法,RG Regular Grammar),例:文法G=(S,A,B,0,1,P,S),其中P由下列产生式组成S 0A|1B|0A 0A|1B|0SB 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
21、.2 文法分类的意义,自动机 具有有穷描述的某种机器,对于给定文法,可接收某个终结符号串,并确定是否能从该文法推导出来。分析器 判定(分析)一个终结符号串是否是某个文法的句子,给出给定串的推导序列,完成此工作的自动机,称为分析器。正规文法与自动机 自动机由一个有穷状态集和一个状态对偶之间的转换集组成。CFG与自动机 CFG可以由下推自动机来识别。,39,文法分类的意义,文法的分类,对于实现程序设计语言的编译程序,具有重要意义。语言的词法规则:用正规文法(RG)描述。语言的语法规则:局部语法用CFG描述;全局语法用CSG描述。语言的语义描述:CSG(实际定义采用CFG)。编译程序在实现时,一般采
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 及其 习题 解答 武汉大学 出版社 课件 chap2
链接地址:https://www.31ppt.com/p-6002693.html