程序语言的基本知识.ppt

编译原理,杭州电子科技大学,2019/12/16,2,第2章程序语言的基本知识,符号串的集合文法和语言分析树和二义性形式语言概观,2019/12/16,3,2.1符号串的集合,字母表,字母表是符号的非空有穷集合，用表示,符号：可以相互区别的记号（元素）,不同的语言有不同的字母表英语26个英文字母Pascal语言AZ,az,09,+,-,*,/,:,；,.,(,),2019/12/16,4,2.1符号串的集合,符号串,符号串是由字母表中的符号所组成的有穷序列,例如：=a,b则a,b,aa,ab,aabba都是上的符号串是任何上的符号串,在语言理论中，符号串又称为:句子、字,2019/12/16,5,2.1符号串的集合,符号串的长度符号串中包含符号的个数符号串s的长度记为|s|,例，对于字母表a,b,c，aab是其上的一个符号串，|aab|=3注意：空符号串，|=0,2019/12/16,6,2.1符号串的集合,符号串的前缀、后缀、子串,后缀：删去符号串s头部的零个或多于零个符号得到的符号串,前缀：移走符号串s尾部的零个或多于零个符号得到的符号串,2019/12/16,7,2.1符号串的集合,符号串的真前缀、真后缀和真子串非空,子串：从s中删去一个前缀和一个后缀得到的符号串,*对于每个符号串s，s和两者都是符号串s的前缀、后缀和子串,2019/12/16,8,2.1符号串的集合,符号串的运算：连接：符号串、的连接，是把的符号写在的符号之后得到的符号串,如=ab,=cd则=abcd注：=,方幂：符号串自身连接n次得到的符号串,n定义为n个1=,2=，注：0=,2019/12/16,9,2.1符号串的集合,例:汉语所有符合汉语语法的句子构成的集合PASCAL语言所有合法的PASCAL程序构成的集合,注意：空集、和的不同,语言,某个字母表上的符号串的集合,2019/12/16,10,2.1符号串的集合,语言的运算：,语言是符号串的集合，集合的运算有并、交、差等,并运算等同于集合的并运算,2019/12/16,11,2.1符号串的集合,连接两个符号串集合L和M的乘积定义为：LM=st|sL且tM,例如：集合A=ab,cdeB=0,1则AB=ab1,ab0,cde0,cde1,L=L=LLLL=LnL0=,2019/12/16,12,2.1符号串的集合,*闭包（Kleene闭包）L*=L0L1L2L3,+闭包（正闭包）L+=L1L2L3L*=L+,2019/12/16,13,2.1符号串的集合,注意:后面通常是考虑字母表的*闭包和+闭包,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2019/12/16,14,2.1符号串的集合,综合性的例子：P10例2.1L=A,B,C,Z,a,b,c,zD=0,1,9,把L和D两个字母表看作长度为1的符号串集合，即语言,1.LD2.LD3.L44.L*5.L(LD)*6.D+,2019/12/16,15,2.2文法和语言,如何来描述一种语言？,如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示,如果语言是无穷的，找出语言的有穷表示。,2019/12/16,16,2.2文法和语言,语言有穷表示的两个途经,*文法即是以生成方式描述语言的,生成方式,语言中的每个句子可以用严格定义的规则来构造,2019/12/16,17,2.2文法和语言,*自动机即是以识别方式描述语言的,识别方式,用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远运行下去）,2019/12/16,18,2.2文法和语言,一个自然语言的例子,规则（文法）,句子主语谓语（1）主语冠词形容词名词（2）冠词the形容词grey谓语动词直接宾语（5）动词助动词动词原形（6）助动词will动词原形eat直接宾语冠词名词（9）名词wolf名词goat,2019/12/16,19,句子主语谓语冠词形容词名词谓语the形容词名词谓语thegrey名词谓语thegreywolf谓语thegreywolf动词直接宾语.thegreywolfwilleatthegoat,句子可根据规则推导（生成）出来：,Thegreywolfwilleatthegoat,分析句子,2019/12/16,20,谓语,主语,冠词,形容词,名词,动词,直接宾语,句子,Thegreywolfwilleatthegoat,2019/12/16,21,2.2文法和语言,文法G,VT,VN,S,P,终结符号集,非终结符号集,开始符号,产生式集合,文法的形式定义,2019/12/16,22,终结符号集VT,代表语言中不可再分的基本符号，如汉语中的汉字、PASCAL语言中的基本字,其中的元素一般用小写字母或数字表示（a,b,c,0,1),2.2文法和语言,2019/12/16,23,非终结符号集VN,代表语法单位，如汉语中的语句、段落，PASCAL语言中的语句、表达式、子程序等，其中的元素一般用大写字母表示（A,B,C），或者用尖括号括起一个串来表示,2.2文法和语言,2019/12/16,24,开始符号S,是一个特殊的非终结符号，代表最高级的语法单位，S至少要在一条产生式中作为左部出现,2.2文法和语言,2019/12/16,25,产生式集合P,2.2文法和语言,产生式（重写规则、生成式），是形如或=的（，）有序对，且V+，V*，其中V=（VTVN）称为产生式的左部，不能为空称为产生式的右部，可以为空（如：A）,2019/12/16,26,2.2文法和语言,例1：文法G=（VT，VN，S，P）VN=SVT=0,1P=S0S1,S01,可以只写出产生式，通过产生式可以得到文法的其它部分,左部相同的产生式可以写在一起，如:S0S1|01,2019/12/16,27,2.2文法和语言,例2：文法G=（VT，VN，S，P）VN=，VT=a,b,c,x,y,z,0,1,9P=a,z0,9S=,2019/12/16,28,2.2文法和语言,推导,直接推导,直接归约,归约,如果A是G的一条产生式，则称用代替A为一步直接推导，记为A,2019/12/16,29,2.2文法和语言,推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程,直接推导,直接归约,用A代替为一步直接归约，记为=A,2019/12/16,30,2.2文法和语言,推导的长度直接推导的次数，长度大于等于1的推导，长度大于等于0的推导,推导的例子：S0S100S11000111，长度为3记为：S000111SS,2019/12/16,31,2.2文法和语言,最左推导,最右推导,对中的最左非终结符进行展开,对中的最右非终结符进行展开,2019/12/16,32,2.2文法和语言,例子：表达式文法EE+TETTT*FTFF（E）Fa,最左推导：ETT*FF*Fa*Fa*a,*最右推导又称为规范推导,最右推导：ETT*FT*aF*aa*a,2019/12/16,33,2.2文法和语言,最右归约,最左归约,最左推导的逆过程是最右归约，即对最右边的可归约串进行归约,最右推导的逆过程是最左归约，即对最左边的可归约串进行归约,a*a=a*F=F*F=T*F=T=E,a*a=F*a=T*a=T*F=T=E,*最左归约称为规范归约,2019/12/16,34,2.2文法和语言,句型,句子,只包含终结符号的句型称为句子。句子是一种特殊的句型。,从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串（S）。句型可以既包含终结符号又包含非终结符号。,2019/12/16,35,2.2文法和语言,例：在推导ETT*FF*Fa*Fa*a中，,句型有：E、T、T*F、F*F、a*F、a*a,句子是：a*a,EE+TETTT*FTFF（E）Fa,2019/12/16,36,2.2文法和语言,语言的形式定义,文法G推导出的所有句子组成的集合，称为语言，记为L（G）,L（G）=|S，VT*,2019/12/16,37,2.2文法和语言,例子：G1：SAA0A1A01,是由一个或多个0开头，后跟同样数目的1的符号串构成的集合（语言），,可记为：L(G)=0n1n|n1,2019/12/16,38,2.2文法和语言,G2：EidEE+EEE*EE（E）,产生的是表达式的集合,2019/12/16,39,2.2文法和语言,G3：EE+TETTT*FTFF（E）Fid,产生的也是表达式的集合,2019/12/16,40,2.2文法和语言,一个文法对应一个语言，但一个语言可能有若干个文法产生它，这若干个文法是等价的，称为等价文法,例G2与G3,2019/12/16,41,2.2文法和语言,上下文无关文法能够描述现今程序设计语言的大部分语法结构,算术表达式赋值语句条件语句等,2019/12/16,42,2.2文法和语言,表达式文法：G=(+,*,id,(,),E,E,P)P:EidEE+EEE*EE(E),E表示算术表达式，id表示程序的“变量”，该文法定义了由变量，+，*，(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式。,2019/12/16,43,2.2文法和语言,描述一种简单赋值语句的产生式：赋值语句id=E,描述条件语句的产生式：条件语句if条件then语句if条件then语句else语句,2019/12/16,44,2.3分析树和二义性,分析树是描述上下文无关文法句型推导的一种直观方法，也称为推导树,分析树,句型推导,对应关系,2019/12/16,45,2.3分析树和二义性,为句型推导构造分析树例子：,ET,EE+TETTT*FTFF（E）Fa,T*F,F*F,a*F,T,T,*,F,F,a,a,E,a*a,2019/12/16,46,2.3分析树和二义性,分析树的特性：,根标识为开始符号,内部结点标识为非终结符号,每一内部结点及其子结点对应一条产生式，该结点是产生式的左部，子结点从左至右排列构成产生式的右部,叶结点从左至右排列构成句型,T,T,*,F,F,a,a,E,2019/12/16,47,2.3分析树和二义性,分析树与句型推导的关系,一次推导（不是一个句型）对应一棵分析树,一棵分析树可能对应若干个推导,例如下面的推导对应的也是上面那棵分析树ETT*FT*aF*aa*a,T,T,*,F,F,a,a,E,2019/12/16,48,2.3分析树和二义性,说明分析树没有严格反映推导的顺序,但是一棵分析树对应一个最左推导，也只能对应一个最右推导,T,T,*,F,F,a,a,E,2019/12/16,49,2.3分析树和二义性,对应最左推导,分析树,对应最右推导,分析树,2019/12/16,50,2.3分析树和二义性,分析句型：短语、直接短语、句柄,如果SA和A，则称是关于A的，句型的一个短语（子树的叶子）,S,A,2019/12/16,51,2.3分析树和二义性,例：句型F*a的短语,T,T,*,F,F,a,E,F*a,EE+TETTT*FTFF（E）Fa,F,a,2019/12/16,52,2.3分析树和二义性,如果SA和A，则称是关于A的，句型的一个直接短语（只有父子两代的子树的叶子）,S,A,2019/12/16,53,2.3分析树和二义性,例：句型F*a的直接短语,T,T,*,F,F,a,E,F,a,2019/12/16,54,2.3分析树和二义性,最左直接短语称为句柄最左性体现在分析树和句型中,S,A,2019/12/16,55,2.3分析树和二义性,例：句型F*a的句柄,T,T,*,F,F,a,E,F,2019/12/16,56,2.3分析树和二义性,句型的素短语、最左素短语,1、是关于A的，句型的一个短语,2、至少含有一个终结符,3、除自身外不含更小的带终结符的短语,称是关于A的，句型的一个素短语,句型最左边的素短语称为最左素短语,2019/12/16,57,例：,E,E,+,T,E,+,T,F,T,T,*,F,a,句型：T+T*F+a,短语：T+T*F+a、T+T*F、T*F、T（左边）、a,直接短语：T、T*F、a,句柄：T,素短语：T*F、a,最左素短语：T*F,EE+TETTT*FTFF（E）Fa,2019/12/16,58,2.3分析树和二义性,句子、文法和语言的二义性,如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的,最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导,2019/12/16,59,2.3分析树和二义性,EE+Eid+Eid+E*Eid+id*Eid+id*id,EE*EE+E*Eid+E*Eid+id*Eid+id*id,E,E,+,E,id,*,E,E,id,id,E,E,*,E,id,+,E,E,id,id,例：,EidEE+EEE*EE（E）,2019/12/16,60,2.3分析树和二义性,如果一个文法有一个句子是二义的，此文法称为二义文法,EidEE+EEE*EE（E）,2019/12/16,61,2.3分析树和二义性,如果一个语言的所有文法都是二义的，称此语言是二义的,希望文法是无二义的，因为希望对于每一个句子进行唯一确定的分析,2019/12/16,62,2.4形式语言概观,乔姆斯基（Chomsky）在1956年提出形式语言理论，他将形式文法分为四类(0,1,2,3)，对应四类形式语言(0,1,2,3),分类的方法是对文法的产生式进行不同的限制,2019/12/16,63,2.4形式语言概观,0型文法|0，即（）,1型（上下文有关）文法|（）,2型（上下文无关）文法AVN，（VTVN）*（A）,3型（正规）文法Aa或AaB（右线性）Aa或ABa（左线性）,2019/12/16,64,2.4形式语言概观,例：1型（上下文有关）文法文法G：SCDAbbACaCABaaBCbCBBbbBADaDCBDbDDAabDL(G)=ww|wa,b*,2019/12/16,65,2.4形式语言概观,例：2型（上下文无关）文法文法G1：SaB|bAAa|aS|bAABb|bS|aBB文法G2：S0A|1B|0A0A|1B|0SB1B|1|0,2019/12/16,66,2.4形式语言概观,例：3型（正规）文法文法G：S0A|1B|0A0A|1B|0SB1B|1|0,2019/12/16,67,2.4形式语言概观,0型文法产生的语言称为0型语言,1型文法或上下文有关文法产生的语言称为1型语言或上下文有关语言,2型文法或上下文无关文法产生的语言称为2型语言或上下文无关语言,3型文法或正则（正规）文法产生的语言称为3型语言正则（正规）语言,2019/12/16,68,2.4形式语言概观,四种文法（语言）之间的逐级“包含”关系,2型文法（语言）,1型文法（语言）,0型文法（语言）,3型文法（语言）,2019/12/16,69,2.4形式语言概观,识别各类语言的数学模型（自动机）,图灵机（0型语言）,有界图灵机、线性有界自动机（1型语言）,下推自动机（2型语言）,有限自动机（3型语言）,2019/12/16,70,TheEnd!,