编译原理第03章文法和语言.ppt

1,编译原理文法和语言,华东交通大学软件学院网络工程教研室万仲保Tel:704682113907097766E-mail:zbwan,2,第三章文法和语言,本章目的为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具-形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。,3,3.1文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型分析3.7实用说明,第三章文法和语言,4,文法的直观概念,一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系阐明语法的一个工具是文法，这是形式语言理论的基本概念之一。示例：汉语句子的描述语言概述,5,汉语句子的描述,语法规则定义字符串的判断,6,语法规则定义,句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,7,字符串的判断,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词，那么得到：主语谓语代词谓语，重复做下去。句子：“我是大学生”的全部动作过程是：句子主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生,8,字符串的判断,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,9,符号和符号串,定义：符号：可以相互区别的记号（元素）。字母表（）：符号（元素）的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串2.若x是上的符号串,a是的元素,则xa是上的符号串3.y是上的符号串,当且仅当它可以由1和2导出。例如：=a,b,a,b,aa,ab,aabba都是上的符号串符号串的运算,10,符号串的运算,既然将语言定义为一个集合，那么有关集合的运算也适合语言。即：设L是（上的）一个语言,M是（上的）一个语言，则语言L和M的并，交，差，补是一个语言。符号串的头、尾、子串符号串的长度符号串的连接符号串的方幂符号串的集合,11,符号串的头、尾、子串,符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀.符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana的一个后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串.对于每个符号串s，s和两者都是符号串s的前缀，后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串x,相应地，是s的前缀，后缀或子串，并且sx。,12,符号串中符号的个数。符号串s的长度记为|s|。的长度为0,符号串的长度,13,符号串的连接,设x、y是符号串，则x、y的连接是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd有a=a,14,符号串的方幂,方幂：设x是符号串，把x自身连接n次得到的符号串z，即z=aaaa称为符号串x的方幂。写作z=an示例：a1=a,a2=aaa0=,15,符号串集合,若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为：AB=xy|xA且yB若集合A=ab,cdeB=0,1，则AB=ab1,ab0,cde0,cde1使用*表示上的所有有穷长符号串（包括）组成的集合。*称为的闭包。上的除外的所有符号串组成的集合记为+。+称为的正闭包。*=012n+=12n*=+=*=*,16,文法和语言的形式定义,文法和语言的形式定义文法的定义推导的定义句型（子）的定义语言的定义文法等价的定义,17,语言概述,语言是由句子组成的集合，是由一组符号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体每个句子构成的规律语言研究每个句子的含义每个句子和使用者的关系每个程序构成的规律研究程序设计语言每个程序的含义每个程序和使用者的关系语法Syntax语言研究的三个方面语义Semantics语用Pragmatics,18,程序设计语言,研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax语义Semantics语用Pragmatics,19,语言研究的三个方面,语法-表示构成语言句子的各个记号之间的组合规律语义-表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用-表示在各个记号所出现的行为中，它们的来源、使用和影响。每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,20,文法的定义,文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VNVT=通常用V表示VNVT，称为文法G的字母表或字汇表。规则，也称重写规则、产生式或生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。示例：例3.1例3.2,21,例3.1,文法G=（VN，VT，P，S），VN=S,VT=0,1，P=S0S1,S01。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。,22,例3.2,文法G=(VN，VT，P，S)其中VN=标识符，字母，数字VT=a,b,c,，x,y,z,0,1,，9P=标识符字母标识符标识符字母标识符标识符数字字母a字母b字母z数字0数字1数字9S=标识符这里，使用尖括号和括起非终结符。,23,推导的定义,直接推导“”：如是文法G=(Vn，VT，P，S)的规则(或说是P中的一产生式)，和是V*中的任意符号，若有符号串v，w满足：v=，w=则说v(应用规则)直接产生w，或者说，w是v的直接推导，也可以说，w直接归约到v，记作vw。如果存在直接推导的序列：示例：直接推导多步推导,24,直接推导的示例,对于例3.1的文法G，可以给出直接推导的一些例子如下：v=0S1,w=0011，直接推导：0S10011，使用的规则：S01，这里=0，=1。v=S,w=0S1，直接推导：S0S1使用的规则：S0S1，这里=，=v=0S1,w=00S11，直接推导：0S100S11，使用的规则：S0S1，这里=0，=1。对于例3.2的文法G，直接推导的例子有：v=标识符，w=标识符字母，直接推导：标识符标识符字母，使用的规则：标识符标识符字母，这里=v=标识符字母数字，w=字母字母数字，直接推导：标识符字母数字字母字母数字，使用的规则：标识符字母。这里=，字母数字。v=abc数字，w=abc5，直接推导：abc数字abc5,使用的规则：数字5，这里=abc,=。,25,多步推导的示例,对例3.1的文法，存在直接推导序列v=0S100S11000S11100001111=w，即0S100001111，也可记作0S100001111对例3.2的文法，存在直接推导序列v=标识符标识符数字字母数字x数字x1=w，即x1，也可记作x1。,26,句型(子)的定义,设GS是一文法，如果符号串x是从识别符号推导出来的，即有Sx，则称x是文法GS的句型。若x仅由终结符号组成，即Sx，xVT*，则称x为GS的句子。例：S，0S1，000111都是例3.1的文法G的句型，其中000111是G的句子。标识符字母，字母数字，a1等都是例3.2文法G的句型，其中a1是G的句子。,27,语言的定义,文法G所产生的语言定义为集合x|Sx，其中S为文法识别符号，且xVT*。可用L(G)表示该集合。从定义可以看出两点：第一，符号串x可从识别符号推出，也即x是句型。第二，x仅由终结符号组成，即x是文法G的句子。也就是说，文法描述的语言是该文法一切句子的集合。例：例3.1G：S0S1，S01L(G)=0n1n|n1例3.3,28,例3.3,设G=(VN，VT，P，S)，VN=S,B,E，VT=a,b,e，P由下列产生式组成：(1)SaSBE(2)SaBE(3)EBBE(4)aBab(5)bBbb(6)bEbe(7)eEee则L（G）=anbnen|n1,29,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。示例：文法G1A：A0RA01RA1与G2S：S0S1S01等价。,30,文法的类型,乔姆斯基分类示例：例3.4例3.5乔姆斯基分类文法之间关系对应于乔姆斯基分类文法的语言文法和语言之间的关系,31,乔姆斯基对文法的分类,通过对产生式施加不同的限制，Chomsky（乔姆斯基）将文法分为四种类型：0型文法：对文法G=(VN，VT，P，S)的任一产生式，都有(VNVT)*且至少含有一个非终结符，(VNVT)*。1型文法（上下文有关文法）：对文法G=(VN，VT，P，S)的任一产生式，都有|，仅仅S除外。2型文法（上下文无关文法）：对文法G=(VN，VT，P，S)的任一产生式，都有VN，(VNVT)*。3型文法（正规文法）：设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是AaB或Aa，其中A和B都是非终结符，a是终结符。3型文法G=(VN，VT，P，S)的P中的规则有两种形式：一种是前面定义的形式，即：AaB或Aa其中A，BVN，aVT*，另一种形式是：ABa或Aa，前者称为右线性文法，后者称为左线性文法。正规文法所描述的是VT*上的正规集。,32,例3.4,G=(S,A,B,a,b,P,S)，其中P由下列产生式组成：SaBAbAASbABbAaBbSAaSBaBB或将P改写为：SaB|bAAbA|aAa|AaSBbS|BaB|b则G是正规文法或3型文法。,33,例3.5,文法G=(S,A,B,0,1,P,S)，其中P由下列产生式组成：S0AA1BS1BB1BS0B1A0AB0A0S或将P改写为：S0A|1B|0A0S|1B|0AB1B|1|0则G是正规文法或3型文法。,34,乔姆斯基分类文法之间关系,2型文法,1型文法,0型文法,四种文法之间的逐级“包含”关系,3型文法,35,对应乔姆斯基分类文法的语言,0型文法产生的语言称为0型语言。1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）。2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）。3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）。,36,文法和语言之间的关系,四种文法之间的关系是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,37,上下文无关文法及其语法树,语法树句型能够构造关联语法树的条件示例：例3.7最左（右）推导二义性文法判断依据示例：例3.8二义性文法与二义性语言的区别,38,句型能够构造关联语法树的条件,给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树满足下列4个条件：每个结点都有一个标记，此标记是V的一个符号。根的标记是S。若一结点n至少有一个它自己除外的子孙（子结点），并且有标记A，则A肯定在VN中。如果结点n的直接子孙，从左到右的次序是结点n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2Ak一定是P中的一个产生式。,39,例3.7,G=(S,A,a,b,P,S)，其中P为：SaASASbAASSSaAba右图是G（aabbaa）的一棵推导树。,40,最左（右）推导,如果在推导的任何一步，其中，是句型，都是对中的最左(最右)非终结符进行替换，则称这种推导为最左(最右)推导。在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。最左推导示例SaASaSbASaabASaabbaSaabbaa最右推导示例SaASaAaaSbAaaSbbaaaabbaa,41,二义文法的判断依据,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，即，不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义的。我们所能做的事是为无二义性寻找一组充分条件(当然它们未必都是必要的)。,42,例3.8,文法G=(E,+,*,i,(,),P,E)其中P=EiEE+EEE*EE(E)是二义性的，假若规定了运算符“+”与“*”的优先顺序和结合规则，即按惯例，让“*”的优先性高于“+”，且它们都服从左结合，那么就可以构造出一个无二义文法。定义表达式的无二义文法GE：ET|E+TTF|T*FF(E)|i它和上述文法产生的语言是相同的。即它们是等价的。,43,二义性文法与二义性语言的区别,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。,44,句型的分析,句型分析是识别一个输入符号串是否为语法上正确的程序的过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。句型的分析算法分类句型的分析算法反映语法树的构造过程句型分析的有关定义句型分析的有关问题,45,句型的分析算法分类,自上而下分析法：是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。示例：例3.9自下而上分析法：从输入符号串开始，逐步进行“归约”，直至归约到文法的开始符号。示例,46,两种方法反映语法树的构造过程,自上而下方法：自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。自下而上方法：自下而上方法是从输入符号串开始，以它做为语法树的末端结点符号串，自底向上地构造语法树。,47,例3.9：自上而下分析,例：考虑文法GS；ScAdAabAa识别输入串w=cabd是否该文法的句子。,推导过程：ScAdcabd,48,示例：自下而上分析,例：考虑文法GS；ScAdAabAa识别输入串w=cabd是否该文法的句子。,SAAcabdcabdcabd规约过程构造的推导：cAdcabdScAd,49,句型分析的有关定义,令G是一文法，S是文法的开始符号，是文法G的一个句型。如果有：SA且A则称是句型相对于非终结符A的短语。特别，如有A则称是句型相对于规则A的直接短语(也称简单短语)。一个句型的最左直接短语称为该句型的句柄。示例从句型的推导树中查找方法,50,示例,文法GE的一个句型i*i+i。为了叙述方便，将句型改写为i1*i2+i3。因为有：EF*i2+i3且Fi1则称i1是句型i1*i2+i3的相对于非终结符F的短语，也是相对于规则Fi的直接短语。又有：Ei1*F+i3且Fi2则i2是句型i1*i2+i3的相对于F的短语，也是相对于规则Fi的直接短语，还有：Ei1*i2+F且Fi3则i3也是句型i1*i2+i3的相对于F的短语，也是相对于规则Fi的直接短语。ET*i2+i3，且Ti1则i1是句型i*i2+i3的相对于T的短语。Ei1*i2+T且Ti3则i3是句型i1*i2+i3的相对于T的短语。EE+i3且Ei1*i2则i1*i2是句型i1*i2+i3的相对于E的短语。EE且Ei1*i2+i3则i1*i2+i3是句型i1*i2+i3相对于E的短语。即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短语，而且i1，i2，i3均为直接短语，其中i1是最左直接短语，即句柄。虽然i2+i3是句型i1*i2+i3的一部分，并不是它的短语，因为尽管有Ei2+i3，但不存在从文法开始符号E到i1*E的推导。,51,从句型的推导树中查找方法,从句型的推导树上很容易找出句型的短语和直接短语。设A是句型的某一子树的根，其中是形成此子树的末端结点的符号串，则其中是句型的相对于A的短语。若这个子树只有一层分支，则是句型的直接短语。示例,52,示例：推导树中找短语,53,句型分析的有关问题,在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。存在确定和不确定分析。,54,实用说明,有关文法的实用限制上下文无关文法中的规则无用符号和无用产生式的消除-产生式的消除单产生式的消除,55,有关文法的实用限制,在实用中，我们将限制文法中不得含有有害规则和多余规则：有害规则，是指形为UU的产生式。它对描述语言显然是没有必要的。说它有害，是说它只会引起文法的二义性。多余规则，是指文法中那些连一个句子的推导都用不到的规则，这类规则在文法中以两种形式出现。一种是文法中某些非终结符不在任何规则的右部出现，所以任何句子的推导中不可能用到它。对文法G=(VN，VT，P，S)来说，为了保证其任一非终结符A在句子推导中出现，必须满足如下两个条件：A必须在某句型中出现。即有SA，其中，属于(VTVN)*。必须能够从A推出终结符号串t来。即At，其中tVT。若程序设计语言的文法包含有多余规则时，其中必定有错误存在，因此检查文法是否包含多余规则是很有必要的。,56,上下文无关文法中的规则,上下文无关文法中某些规则可具有形式A，称这种规则为规则。规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现。上下文无关文法的相关定理定理3.1定理3.2,57,定理3.1,若L是由文法G=(VN，VT，P，S)产生的语言，P中的每一个产生式的形式均为A，其中AVN，(VNVT)*(即可能为)，则L能由这样一种文法产生：每一个产生式或者为A形式，其中AVN，(VNVT)+(即)，或者S且S不出现在任何产生式右边。,58,定理3.2,如果G=(VN，VT，P，S)是一个上下文有关文法，则存在另一个上下文有关文法G1，它所产生的语言与G产生的相同，即L(G)=L(G1)，其中G1的开始符号不出现在G1的任何产生式的右边。若G为上下文无关文法或正规文法，类似结论成立。,59,无用符号和无用产生式的消除,定义：设G=(VN，VT，P，S)是一文法，我们说G中的一个符号x(VNVT)是有用的指x至少出现在一个句子的推导过程中。即x必须同时满足以下两个条件：存在、V*，有S*x存在wVT*,x*w否则就说x是无用的。如果一个产生式的左部或右部含有无用符号，则此产生式称之为无用产生式。消除算法算法1算法2示例,60,算法1,1、分别置VN(1)和P(1)为；2、对于P中的每一产生式A，若VT*，则将A置于VN(1)中；3、对于P中的每一产生式Ax1x2xm若每个xi都属于VN(1)或VT，则将A置于VN(1)；4、重复步骤3，直到VN(1)不再增大为止；5、对于P中的每一产生式By1y2yn，若B及每一个yi都属于VN(1)VT，则将此产生式By1y2yn置于P(1)。,61,算法2,1、分别置VN、VT和P为；2、将文法的开始符号S置入VN中；3、对于G(1)中任何形如Ax1|x2|xm的产生式，若AVN，则将符号串x1，x2，xm中的全部非终结符号置于VN中，而将其中的全部终结符号置于VT中；4、重复步骤3，直到VN和VT都不再增大为止；5、将P中左右部仅含VNVT中符号的所有产生式置P。,62,示例,文法的定义已知文法G=（S,U,V,W，a,b,c，P，S），产生式P的组成如下：SaSSWSUUaVbVVacWaW执行算法1执行算法2,63,执行算法1,第一步，由于产生式Ua、Vac的右部均为终结符号串，故置VN(1)=U，V；第二步，对于产生式SU，由于UVN(1)，故将S置于中，所以VN(1)=S，U，V；于是得到以下文法G1：G1=（S,U,V,a,b,c,P(1),S），其中P(1)由如下产生式组成：SaSSUUaVbVVac,64,执行算法2,第一步，置VN=S；第二步，因为G1中含有产生式SU、Ua，故应将U、a分别置于，即VN=S，UVT=a;因此得到等价的且不含无用符号和无用产生式的文法为G2=（S，U，a，P，S），其中，P由如下产生式组成：SaSSUUa,65,-产生式的消除,算法3算法4（不属于文法所产生的语言）算法5（属于文法所产生的语言）示例：不属于文法所产生的语言属于文法所产生的语言,66,算法3,1、作集合W1=A|产生式AP；2、作集合序列WK+1=WKUB|BP,且WK+；K1并使WK+1收敛；令W=WK+1,则对于每一个AW，有A*。对于上述W，如果G中不含有可能导出的符号，则W=。,67,算法4,1、利用算法3，可将分VN为两个不相交的子集：W和VN-W；设AX1X2Xm是P中的任一产生式，则按以下规则将所有形如AY1Y2Ym的产生式置入P中：（1）若XiVNW，则取Yi=Xi；（2）若XiW，则Yi分别取Xi和，若所有的均Xi属于W，则不将所有Yi的取。,68,不属于文法所产生的语言,已知文法G=（S,A,B,C，a,b,c，P，S），产生式P的组成如下：SaAABCBbBCcCBC执行算法3，得到W=A,B,C执行算法4，可得到P如下：对于SaA,将产生式SaA、Sa放入P；对于ABC,将产生式ABC、AB、AC放入P；对于BbB，将产生式BbB、Bb放入P；对于CcC，将产生式CcC、Cc放入P。则消除-产生式之后的文法的产生式如下：SaASaABCABACBbBBbCcCCc,69,算法5,1、引入新的符号S（SVNUVT）作为G的开始符号，令=VNUS；2、作产生式集P=PUS|产生式SP3、对文法G=（VN，VT，P，S）执行算法4消去P中全部-产生式。4、将S加入到所得的产生式集中。,70,属于文法所产生的语言,已知文法G=（S,A,B，a,b,c，P，S），产生式P的组成如下：ScSSABAaAbBBbAB引入新的符号S；作产生式集P=PUScS,SAB利用算法4消去P中的-产生式，并加入S，得到全部的产生式如下：ScSScSABSASBSScSScSABSASBAaAbAabBBbBb,71,单产生式的消除,算法：1、设A=A1,A2,An，对于每一个Ai，作集合序列W1(Ai)=AiWK+1(Ai)=WK(Ai)UD|CD,CWK(Ai),DVN，并使其收敛为Wi。构造产生式集P=Ai|产生式BP，BWi，VN，此时P中不含有单产生式。示例,72,示例：单产生式的消除,已知文法G=（S,A,B，a,b，P，S），产生式P的组成如下：SASBSABAaAbBBbAabBb对于G，执行算法得到：W(S)=S,A,BW(A)=AW(B)=B由此可构造产生式集P如下：SABSaAbSabSBbSbAaAbAabBBbBb,