编译原理章课件.ppt

《编译原理章课件.ppt》由会员分享，可在线阅读，更多相关《编译原理章课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理章第1页，此课件共30页哦2.3 程序语言的语法描述程序语言的语法描述一、符号和符号串一、符号和符号串字母表字母表：字母表：字母表是符号元素的是符号元素的非空非空集合。集合。符号符号：字母表中的元素。：字母表中的元素。符号串符号串：字母表中的符号所组成的任何：字母表中的符号所组成的任何有穷有穷序列。序列。例如，若有字母表例如，若有字母表=a,b则则a，b是字母表是字母表中的元素中的元素(符号符号)；a，b，aa，ab，ba都是符号串。都是符号串。注意：符号串中的注意：符号串中的符号与顺序有关，符号与顺序有关，ab和和ba是不同的是不同的符号串符号串特别定义特别定义:空符号串空符号串不含

2、任何符号的符号串，用不含任何符号的符号串，用 表示。表示。第2页，此课件共30页哦设有字母表=az,AZ,09,各种运算符和其它特殊符号，则，由这些字母表中的元素(符号)可以组成不同的符号串：Program example;Var sum,I:integer;Begin Sum:=0;For I:=1 to 10 do sum:=sum+I;12345:=sum;End.Write(sum=,sum);A=第3页，此课件共30页哦符号串的运算符号串的运算：符号串的连接（联结、乘积）符号串的连接（联结、乘积）：符号串：符号串x和和y的连接是指的连接是指x和和y的符的符号按先后顺序排列在一起组成一

3、个新的符号串，用号按先后顺序排列在一起组成一个新的符号串，用xy表示。表示。例，若字母表例，若字母表=a,b，符号串符号串x=ab，y=ba则则xy=abba符号串的长度符号串的长度：符号串中符号的个数为符号串的长度。：符号串中符号的个数为符号串的长度。注意注意:(1)连接运算不满足交换律，即连接运算不满足交换律，即xyyx (2)任何符号串任何符号串x与空串与空串的的连连接都等于接都等于x，即即：x=x=x。若若ab是符号串，则是符号串，则|ab|表示符号串的长度。表示符号串的长度。|ab|=2同理：同理：|aabb|=4 注意：特别规定注意：特别规定|=0。若有两个符号串若有两个符号串x=

4、ab,y=cde那么，那么，|xy|=?5第4页，此课件共30页哦符号串的前缀与后缀符号串的前缀与后缀(头和尾头和尾)：若有符号串若有符号串 z=xy(x,y是符号串是符号串),我我们称们称x为为z的前缀的前缀，y为为z的后缀。的后缀。例例z=abcd则：则：z的头有，的头有，,a,ab,abc,abcd z的尾有，的尾有，,d,cd,bcd,abcd符符 号号 串串 的的 幂幂 运运 算算：设设 X是是 一一 个个 符符 号号 串串，则则：X0=，X1=X，X2=XX，Xn=XX=Xn例：若有符号串例：若有符号串x=ab，则：则：x0=,x1=ab,x2=abab,x3=ababab显然，若

5、显然，若n0,则则Xn=XXn-1=Xn-1X。即：符号串的幂运算服从结合律即：符号串的幂运算服从结合律 第5页，此课件共30页哦符号串符号串集合集合的运算的运算：符号串集合的乘积运算：符号串集合的乘积运算：设设A、B为符号串集合（集合中各元为符号串集合（集合中各元素都是字母表上的字符串），两个字符串集合的乘积定义为：素都是字母表上的字符串），两个字符串集合的乘积定义为：AB=xy|xA,yB（笛卡儿乘积）笛卡儿乘积）设有字母表=a,b,c,d，令A=aa,bb，B=cc,dd则AB=aacc,aadd,bbcc,bbdd，BA=ccaa,ccbb,ddaa,ddbb。显然 AB BA，即符号

6、串集合乘积不满足交换律。注意：因注意：因x=x=x故，故，A=AA=A=A=A 特别定义：空符号串集合：特别定义：空符号串集合：空集合：空集合：=A=A=第6页，此课件共30页哦符号串集合的幂运算：符号串集合的幂运算：设设A为符号串集合，则集合的幂运算定为符号串集合，则集合的幂运算定义如下义如下:A0=A1=AA2=AAAn=AAAn个个=AAn-1=An-1A符号串集合的闭包：符号串集合的闭包：设设A为符号串集合，则集合的闭包定义如下为符号串集合，则集合的闭包定义如下:A的的正闭包正闭包：A+=A1A2A的的闭包：闭包：A*=A0A1A2设集合设集合A=a,b，则则 A+=a,b,aa,ab

7、,ba,bb,aaa,A*=,a,b,aa,ab,ba,bb,aaa,显然：显然：A*=A0A+A+=AA*第7页，此课件共30页哦二、上下文无关二、上下文无关文法文法(p26)文法文法(Grammar):是描述语言的语法结构的形式规则是描述语言的语法结构的形式规则（即语法规则）。（即语法规则）。The big monkey ate a banana.第8页，此课件共30页哦规则规则：规则又叫：规则又叫产生式产生式(production rule)，它是语法，它是语法单位结构的一种表示，它引入了符号单位结构的一种表示，它引入了符号“:=:=”或或“”表示表示“由由组成组成”，上述句子的结构可以

8、表示如，上述句子的结构可以表示如下：下：the big ate a monkey banana第9页，此课件共30页哦句子的推导句子的推导：用规则：用规则(产生式产生式)按一定方式去推导或产按一定方式去推导或产生句子的过程。生句子的过程。the big ate a monkey banana The The big The big monkey The big monkey The big monkey ate The big monkey ate The big monkey ate a The big monkey ate a banana The big monkey ate a ban

9、ana第10页，此课件共30页哦语法树语法树(Parse Tree):句子结构的图形表示方式句子结构的图形表示方式monkeybigTheatebananaa第11页，此课件共30页哦归纳：什么是文法归纳：什么是文法 the big ate a monkey banana第12页，此课件共30页哦三、文法和语言的形式定义三、文法和语言的形式定义定义定义2 文法文法是一个四元组：是一个四元组：GS=(VN,VT,P,S)其中：其中：VN为非终结符集合；为非终结符集合；VT为终结符集合；为终结符集合；VNVT=，一般令一般令 V=VNVT，V中的符号称为文法符号；中的符号称为文法符号；(V字汇表）

10、字汇表）P为产生式集合；为产生式集合；P中的每个产生式写为：中的每个产生式写为：或或=。S为开始符号为开始符号(或称根符号，识别符号或称根符号，识别符号)。定义定义1 产生式产生式(或规则或规则)是一有序对是一有序对(A,)，通常写为：，通常写为：A 或或A=其中其中A是一个符号作为产生式左部，是一个符号作为产生式左部，为有穷符号串作为产生式为有穷符号串作为产生式的右部，的右部，“”或或“=”表示表示“定义为定义为”或或“由由组成组成”。另外：另外：GS也可简写为也可简写为G 在规则左部出现的符号称为非终结符，它们的全体形成VN在规则中只在右部出现的符号称为终结符，它们的全体形成VT第13页，

11、此课件共30页哦例例 G1=(N,0，1,N0N,N1N,N0,N1,N）其中其中:非终结符非终结符 VN=N终结符终结符VT=0，1V=N，0，1 P=N0N，N1N，N0，N1开始符号开始符号S 为为N通常情况下，文法只用产生式集合表示：通常情况下，文法只用产生式集合表示：G1N:N0N N1N N0 N1第14页，此课件共30页哦定义定义3 符号串的符号串的推导与归约推导与归约：已给文法：已给文法G=(VN,VT,P,S)，V=VNVT，令令x,y,V*，且且P，此时，由符号串此时，由符号串xy能能够直接产生出符号串够直接产生出符号串xy，我们称：我们称：符号串符号串xy是符号串是符号串

12、xy的的直接推导直接推导；符号串符号串xy是符号串是符号串xy的的直接归约直接归约；记作记作:xy xy 对于上例中文法：对于上例中文法：G1N:N0N N1N N0 N1存在以下直接推导：存在以下直接推导：N 1N 11xyxyx yx y若有若有1，2，nV*且且1 2 ，n-1 n则称则称n是是1的推导的推导记作：记作：1+n特别约定：若在推导关系特别约定：若在推导关系1n中允许中允许1=n，+则称则称n是是1 的广义推导记作的广义推导记作 1*nN+11N*N第15页，此课件共30页哦引用引用巴科斯范式巴科斯范式(BNF)表示文法：表示文法：对于具有相同左部的那些产生式，如：对于具有相

13、同左部的那些产生式，如：Ux,Uy,Uz可以缩写为：可以缩写为：Ux|y|z (“|”可理解为可理解为“或或”)(1)(2)(3)(4)0(5)1(6)2(7)3(8)4(9)5(10)6(11)7(12)8(13)9(1)(2)|(3)0|1|2|3|4|5|6|7|8|9|用此文法和直接推导的定义可以推导用此文法和直接推导的定义可以推导出任一无符号整数出任一无符号整数(56)5 56可表示为可表示为:+56第16页，此课件共30页哦 V*，则称则称为文法为文法G的句型的句型 VT*，则称则称为文法为文法G的句子的句子 文法文法G所对应的语言，记作所对应的语言，记作L(G)=|VT*，且且S

14、+例例:前面提到的文法前面提到的文法G=VN，VT，P，无符号整数无符号整数其中，其中，VT=0，1，2，3，4，5，6，7，8，9 VN=无符号整数，数字串，数字无符号整数，数字串，数字 P：0123456789 5 56 试给出该文法的句试给出该文法的句型、句子举例，并型、句子举例，并说明它所确定的语说明它所确定的语言。言。由此我们可以看出，文法和语言是密切相关的，根据文法由此我们可以看出，文法和语言是密切相关的，根据文法可以推导出任一句型和句子，而所有句子的集合则为该文可以推导出任一句型和句子，而所有句子的集合则为该文法所对应的语言，即法所对应的语言，即语言是所有句子构成的集合，它是所有

15、语言是所有句子构成的集合，它是所有终结符号串所组成的集合终结符号串所组成的集合VT*的子集的子集：L(G)VT*定义定义4 句型和句子句型和句子:设设G=(VN,VT,P,S)是一文法，若是一文法，若 S*那么，句型和句子的区别那么，句型和句子的区别是什么是什么?第17页，此课件共30页哦定义定义5 规范推导规范推导(归约归约):对于直接推导对于直接推导xy xy，如果如果y只包含只包含终结符号终结符号或为空符号串，那么就把这种直接推导称为规范或为空符号串，那么就把这种直接推导称为规范(最右最右)推推导，跟其对应的归约称为规范导，跟其对应的归约称为规范(最左最左)归约，且记作：归约，且记作：x

16、y rxy下面的推导是否规范推导下面的推导是否规范推导：5 56 6 6 56若推导：若推导：1+n中的每一步直接推导都中的每一步直接推导都是规范的，那么我们就是规范的，那么我们就把推导：把推导：1+n称为是规范的，且记作：称为是规范的，且记作：1n+r+r56每次对符号串最右非终结符号进行替换第18页，此课件共30页哦例例 文法文法GE:EE+E|E*E|(E)|i 给出句子给出句子i*i+i的最右及最左推导的最右及最左推导。例例2.1 p30例例2.2例例2.3同样，可给出最左推导的定义。同样，可给出最左推导的定义。p30-31第19页，此课件共30页哦形式语言理论可以证明以下两点：形式语

17、言理论可以证明以下两点：(1)给定一个文法给定一个文法G，就可以从结构上唯一地确定其语言：就可以从结构上唯一地确定其语言：GL(G)(2)给定一种语言给定一种语言L，能确定其文法，但这种文法可能不是唯能确定其文法，但这种文法可能不是唯一的：一的：LG1或或G2例例1：有文法：有文法GZ:(1)ZaZb (2)Z ab它确定的语言是什么？它确定的语言是什么？用BNF表示：Z aZb|ab由产生式由产生式(2)知：知：zab 故故ab是文法的一个句子是文法的一个句子用产生式用产生式(1)(2)：zaZba2b2 故故a2b2是文法的一个句子是文法的一个句子反复使用产生式反复使用产生式(1)：zaZ

18、ba2Zb2 an-1Zbn-1 anbn所以，文法所确定的语言为：所以，文法所确定的语言为：L(GZ)=anbn|n 1第20页，此课件共30页哦例例2：已知语言为：已知语言为 L(G)=abna|n 1 试给出其文法。试给出其文法。G1Z:Z aBa B bB|bG2Z:Z aBa B Bb|b定义定义6 等价文法等价文法：如果：如果L(G1)=L(G2)，那么称那么称G1和和G2为等价为等价文法。文法。定义定义7 递归产生式和递归文法递归产生式和递归文法：设给定文法：设给定文法G=(VN,VT,P,S)若若x=且且y,则称产生式则称产生式A是是左递归产生式左递归产生式；若若x且且y=,则

19、称产生式则称产生式A是是右递归产生式右递归产生式。B BbB bB(1)若存在产生式若存在产生式AP 且有且有 A xAy成立，则称成立，则称产生式产生式A是递归产生式；是递归产生式；*若若具有具有xAy形式形式,则称产生式则称产生式A是是直接递归产生式直接递归产生式。第21页，此课件共30页哦(2)递归文法：递归文法：若文法中至少存在一条直接递归产生式则称该文法是若文法中至少存在一条直接递归产生式则称该文法是直接递直接递归的文法归的文法；否则；否则 若有若有A+xAy，或，或A+Ay，或，或A+xA则称文法为则称文法为间接递归的文法间接递归的文法。可见，对于文法中任一非终结符号，若能建立一个

20、推导过程，在推可见，对于文法中任一非终结符号，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符号本身，则文法是递归的。导所得的符号串中又出现了该非终结符号本身，则文法是递归的。应当注意，一般的文法都是递归的应当注意，一般的文法都是递归的，文法，文法G只有递归定义，只有递归定义，L(G)中中句子才是无穷的句子才是无穷的 例：有文法例：有文法GS:S aB|bB B a|b是否是递归文法，确定什是否是递归文法，确定什么语言？么语言？非递归非递归文法，文法，L(GS)=aa,ab,ba,bb第22页，此课件共30页哦例：有文法例：有文法G(1)(2)|(3)0|1|2|3|4|5|6|7

21、|8|9|该文法中有直接左递归产生式：该文法中有直接左递归产生式：所以是递归文法。所以是递归文法。它是否为递归文法，确定的语言是什么？它是否为递归文法，确定的语言是什么？所确定的语言为：所有无符号整数。所确定的语言为：所有无符号整数。L(G)=VT+若不用递归规则表示文法，就要用到无穷多条产生式：若不用递归规则表示文法，就要用到无穷多条产生式：|总之，总之，使用递归文法，可用有穷的产生式来描述无穷的使用递归文法，可用有穷的产生式来描述无穷的语言语言，反之，一个语言若是无穷的，则描述语言的文法，反之，一个语言若是无穷的，则描述语言的文法必定是递归的。必定是递归的。(程序设计语言一般是无穷的程序设

22、计语言一般是无穷的)。课堂练习课堂练习（见教案）（见教案）第23页，此课件共30页哦定义定义8 短语、简单短语和句柄短语、简单短语和句柄：设文法：设文法 G=(VN,VT,P,S)，且且 U VN，x,y,u V*(1)若有若有SxUy*+xuy，则则u称为句型称为句型xuy的相对于的相对于U的的短语短语；(2)若有若有SxUy*xuy，则则u称为句型称为句型xuy的相对于的相对于U的的简单简单(直接直接)短语短语；例例：有文法：有文法G(1)(2)|(3)0|1|2|3|4|5|6|7|8|9|因有：因有：*+6xyUyxuU=u=6x,y=6是句型是句型6相对于相对于的短语的短语第24页，

23、此课件共30页哦(3)任一句型的任一句型的最左简单短语最左简单短语称为该句型的称为该句型的句柄句柄.因有：因有：*66是句型是句型6相对于相对于的短语，且为的短语，且为简单短语简单短语xUyxyu说明：当句型有两个以上的简单短语同时存在时，我们把说明：当句型有两个以上的简单短语同时存在时，我们把位于最左边的那个简单短语称为位于最左边的那个简单短语称为“最左简单短语最左简单短语”，即该，即该句型的句柄；若句型只有一个简单短语，那么，它就是最句型的句柄；若句型只有一个简单短语，那么，它就是最左简单短语，即句柄。左简单短语，即句柄。例例1：在：在“6”中，中，6是句型是句型6中唯一的中唯一的一个简单

24、短语，所以它是句柄一个简单短语，所以它是句柄.例例2：在：在“78”中，中，、7和和8都是是句都是是句型简单短语，所以位于左边的型简单短语，所以位于左边的 是句柄是句柄.注意：可从语法树的角度理解短语和句柄。注意：可从语法树的角度理解短语和句柄。p31例例：有文法：有文法G(1)(2)|(3)0|1|2|3|4|5|6|7|8|9|第25页，此课件共30页哦2.4语法树和文法的二义性语法树和文法的二义性语法树语法树:设文法设文法G=(VN,VT,P,S)，所谓语法树是一张图，这张图表所谓语法树是一张图，这张图表示一个句型的推导过程。语法树结构是一棵倒立的树结构，其中，结示一个句型的推导过程。语

25、法树结构是一棵倒立的树结构，其中，结点的名字点的名字NV，根结点的名字根结点的名字S是文法是文法G的开始符号，树中的中的开始符号，树中的中间结点是句型推导过程中使用的非终结符间结点是句型推导过程中使用的非终结符，树的端末结点自，树的端末结点自左向右排列就是所给句型。左向右排列就是所给句型。例例2.7 文法文法GE:EE+TT TT*FF FEi 句型句型E+F*i对应的语法树对应的语法树如右图所示：如右图所示：EE T+T*F F i可以看出，语法树的生成过程直观的给出了句型的推导过程。可以看出，语法树的生成过程直观的给出了句型的推导过程。第26页，此课件共30页哦子树子树：由语法树的某个结点

26、：由语法树的某个结点(子树的根子树的根)连同它下面发出的部分组成连同它下面发出的部分组成语法树的子树。只含有单层分支的子树为简单子树。语法树的子树。只含有单层分支的子树为简单子树。EE T+T*F F i子树与短语子树与短语：在句型所对应的：在句型所对应的语法树中，若某些符号按从左语法树中，若某些符号按从左到右的顺序组成某棵子树的末到右的顺序组成某棵子树的末端结点，那么由这些末端结点端结点，那么由这些末端结点所组成的符号串是相对于子树所组成的符号串是相对于子树根结点的短语。根结点的短语。例如：例如：F是句型相对于是句型相对于T的短语，且为简单短语的短语，且为简单短语;i是句型相对于是句型相对于

27、F的短语，且为简单短语的短语，且为简单短语;F*i 是句型相对于是句型相对于T的短语的短语;E+F*i是句型相对于是句型相对于E的短语的短语.补充补充2个例子（教案个例子（教案P30-31）原则上语法树有多少棵子树，就有多少个短语哪个是句柄？哪个是句柄？第27页，此课件共30页哦文法的二义性文法的二义性：若一个文法存在某个句子对应两棵不同的语法树，：若一个文法存在某个句子对应两棵不同的语法树，则称此文法是二义性文法，运用文法描述程序设计语言的语句成份，则称此文法是二义性文法，运用文法描述程序设计语言的语句成份，一般希望所给文法是非二义文法，但是，有时候采用二义性文法比非一般希望所给文法是非二义

28、文法，但是，有时候采用二义性文法比非二义文法要简单的多，所以，经常用二义性文法描述程序设计语言。二义文法要简单的多，所以，经常用二义性文法描述程序设计语言。例例1：文法文法GE:EE+E|E*E|(E)|i 试为符号串试为符号串E*E+i构造语法树构造语法树.EEE+EE*iEEE*EE+i先乘后加先加后乘所以文法是二义性的。在进行语法分析时通过所以文法是二义性的。在进行语法分析时通过人工干预人工干预(规定算符的优先级规定算符的优先级)，确定归约，确定归约(分析分析)顺序顺序 例例2：if 语句语句(1)(2)(3)第28页，此课件共30页哦2.5文法的分类文法的分类 按照文法中产生式的不同情

29、况，按照文法中产生式的不同情况，Chomsky把文法分成四把文法分成四种类型，四种类型的文法对应着四种类型的语言。种类型，四种类型的文法对应着四种类型的语言。0型文法型文法：产生式形式为产生式形式为:u v 且且 u V+v V*u中应至少含有一个非终结符号，这种文法又叫短语文法，它中应至少含有一个非终结符号，这种文法又叫短语文法，它所确定的语言称为所确定的语言称为0型语言。型语言。1型文法型文法:产生式形式为产生式形式为 xUy xuy 且且 U VN u V+x,y V*则则称该文法为称该文法为1型文法，也称为上下文敏感文法或上下文有关文法。型文法，也称为上下文敏感文法或上下文有关文法。即

30、只有在即只有在U的左部为符号串的左部为符号串x而右部为符号串而右部为符号串y时，才允许把非时，才允许把非终结符终结符U用符号串用符号串u来代替，即来代替，即U必须在上下文必须在上下文xy中才行。这种中才行。这种文法所对应的语言为文法所对应的语言为1型语言。型语言。第29页，此课件共30页哦2型文法型文法:产生式形式为产生式形式为 U u 且且 U VN u V*则称该文法为则称该文法为2型文法，也称为上下文无关文法。型文法，也称为上下文无关文法。2型文法所型文法所确定的语言为确定的语言为2型语言，大部分程序设计语言都是型语言，大部分程序设计语言都是2型语言。型语言。例例:文法文法G=（S，a,

31、b，SaSb,Sab，S）3型文法型文法:产生式形式为产生式形式为 UxV|y xV|y 或或 U Vx|y U Vx|y 且且 U,V VU,V VN N，x,yVx,yVT T+则称该文法为则称该文法为3型文法，也称线性文法、型文法，也称线性文法、正则文法或正规文法正则文法或正规文法。这种文法所对应的语言称为这种文法所对应的语言称为3型语言型语言(正则语言、正规语言正则语言、正规语言)，大多数程序设计语言的单词大多数程序设计语言的单词(标识符、无符号整数标识符、无符号整数)的文法都的文法都是是3型文法。型文法。从从0型文法到型文法到3型文法是逐渐增加限制的，而它们所确定的语言是型文法是逐渐增加限制的，而它们所确定的语言是逐步缩小的。逐步缩小的。u vxUy xuyU u UxV|y第30页，此课件共30页哦