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

2019/12/17,1,第三章文法和语言,课前思考,高级语言有哪些一般特性？你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的？学习编译程序为什么要研究语言的描述问题？,2019/12/17,2,学习目标,本章目的是为语言的语法描述寻求工具掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一文法。熟练使用文法定义程序设计语言的单词和语法成分对形式语言的理论有一个初步基础,2019/12/17,3,学习指南,什么是文法,什么是它定义的语言？在乔姆斯基（Chomsky）的文法类型中，我们为什么关注上下文无关文法？什么是语法分析？语法分析方法的分类？,2019/12/17,4,难重点,关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。,2019/12/17,5,知识结构,2019/12/17,6,引言和预备知识,高级语言程序语言是一个记号系统语法语义,语法任何语言程序都可以看成是一定字符集（字母表）上的字符串语法使得这串字符形成一个形式上正确的程序语法=词法规则+语法规则例如：0.5*x1+c0.5、x1、c、*、+是语言的单词符号0.5*x1+c是语言的语法单位,词法单词符号语言中具有独立意义的最基本结构词法规则词法规则规定了字母表中哪些字符串是单词符号单词符号一般包括：常数、标识符、基本字、算符、界限符等我们用正规式和有限自动机理论来描述词法结构和进行词法分析,语法单词符号语法单位表达式、子句、语句、函数、过程、程序语法规则规定了如何从单词符号来形成语法单位现在多数程序语言使用上下文无关文法来描述语法规则语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据,例，对于一个PASCAL程序来说，一个上下文无关文法可以定义A:=B+C是合乎语法的，而A:=B+是不合乎语法的。,语义对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义离开语义，语言只是一堆符号的集合各种语言中有形式上完全相同的语法单位，含义却不尽相同对某种语言，可以定义一个程序的意义的一组规则称为语义规则目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义,对于高级程序设计语言及其编译程序来说，语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题，编译原理的主要内容也可以归纳为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段,2019/12/17,14,3.2符号和符号串,任何一种语言都是由该语言的基本符号组成的符号串的集合。基本符号集任何语言的单词符号就是定义在它的字符集上的字符串该语言的任何语句就是定义在其单词符号集上的单词串(符号串),2019/12/17,15,字母表：是元素的非空有穷集合，把字母表中的元素称为符号，因此字母表也称符号集。例，a，b，c，+，就是含有5个元素的一个字母表。一般用和V来表示符号：是语言当中最基本的不可再分的单位,2019/12/17,16,符号串：字母表中的符号所组成的任何有穷序列。例，V=a，b，c是一个字母表，则a，b，c，aa，ab，bc，abc等等都是V上的符号串空串：不含有任何符号的串称为空串，记作,句子：字母表上符合某种规则构成的串语言：字母表上句子的集合注：约定用a,b,c表示符号；用,表示符号串；用A,B,C表示其集合,2019/12/17,18,符号串的长度：如果某符号串中有m个符号，则其长度为m，记为|=m。例，|abc|=3的长度为0符号串的连接：设和是符号串，它们的连接是把的符号写在的符号之后得到的符号串。例，若=NPU，=1108，则=NPU1108，=1108NPU,符号串的方幂：设是符号串，把自身连接n次得到符号串，即=，称为符号串的方幂，写作=n。符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。,2019/12/17,19,两个符号串集合A和B的乘积（连接）：AB=|A且B注：1）串集的自身乘积称作串集的方幂2）A0=字母表V的n次方幂是字母表V上所有长度为n的串集,2019/12/17,20,2019/12/17,21,字母表V的闭包V*和正闭包V+：,字母表上的语言，是字母表上正闭包的子集。,2019/12/17,22,3.1文法的直观概念,文法的定义对语言结构的描述和定义，即在形式上用来描述和规定语言结构的称为“文法”(或“语法”)。,比如：“我是大学生。”是汉语的一个句子汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语:=:=|:=我|你|他:=王明|大学生|工人|英语:=:=是|学习:=|,2019/12/17,23,2019/12/17,24,一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找:=左端的带有句子的规则并把它表示成:=右端的符号串规则中的“:=”也常用“”表示，含义是使用一条规则，代替=左边的某个符号，产生右端的符号串。注意文法中，描述某个特定的语法成分的规则可能不只一条。,2019/12/17,25,得到句子“我是大学生”的全部动作过程是：我我我是我是我是大学生,2019/12/17,26,“我是大学生”的构成是符合上述规则“我大学生是”不符合上述规则这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。,2019/12/17,27,3.3文法和语言的形式定义,前面已经对规则(或产生式)的概念进行了非形式化的说明，我们已经对其有了一个直观的了解。下面将对其进行形式化说明，并在此基础上抽象地定义文法和语言。,2019/12/17,28,文法G定义为四元组（VN，VT，P，S）VN：非终结符集VT：终结符集P：产生式（规则）集合S：开始符号（或识别符号）VNVT=，SVNV=VNVT，称为文法G的文法符号集合,定义3.1,2019/12/17,29,句子的语法结构，可以用一组规则来描述。规则也称为“重写规则”、“产生式”或“生成式”，是形如或:=的(，)有序对，且V+，V*，V为某字母表。称为规则的左部(或产生式的左部)称为规则的右部(或产生式的右部)这里使用的符号（:=）读作“定义为”,2019/12/17,30,例3.1文法G=（VN，VT，P，S）VN=S,VT=0,1P=S0S1,S01S为开始符号,2019/12/17,31,例3.2文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z0,9S=,2019/12/17,32,习惯上不用将文法G的四元组显示地表示出来，只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成GS，S是开始符号G：S0S1S01GS：S0S1S01,2019/12/17,33,有时，为书写简洁，常把相同左部的产生式，形如Aa1，Aa2Aan缩写为：Aa1|a2|.|an注意：元符号“|”读作“或”,2019/12/17,34,一个文法的几种写法例：G=（S，A，a,b，P，S）其中：P：SaAbAabAaAbAG：SaAbAabAaAbAGS：AabAaAbASaAbGS：Aab|aAb|SaAb,2019/12/17,35,直接推导“”定义3.2：如是文法G=(Vn，VT，P，S)的规则（或说是P中的一产生式），若有符号串v，w满足：v=，w=，其中V*，V*则称v直接推导出w，记作vw或w直接归约到v,对于例3.1的文法G:S0S1，S01，可以给出直接推导的一些例子如下：v=0S1，w=0011，直接推导：0S10011，使用的规则：S01，这里=0，=1。v=S，w=0S1，直接推导：S0S1，使用的规则：S0S1，这里=，=v=0S1，w=00S11，直接推导：0S100S11，使用的规则：S0S1，这里=0，=1。,2019/12/17,36,对于例3.2的文法G，直接推导的例子有：v=，w=，直接推导：，使用的规则：，这里=v=，w=，直接推导：，使用的规则：。这里=，。v=abc，w=abc5，直接推导：abcabc5,使用的规则：5，这里=abc，=,2019/12/17,37,2019/12/17,38,定义3.3如果存在直接推导的序列：vw0w1.wn=w(n0)则称v推导出（产生）w（推导长度为n），或称w归约到v。记作vw定义3.4若有vw，或v=w，则记为vw,对例3.1的文法，存在直接推导序列v=0S100S11000S11100001111=w，即0S100001111，也可记作0S100001111对例3.2的文法，存在直接推导序列v=xx1=w，即x1，也可记作x1,2019/12/17,39,2019/12/17,40,文法的句型、句子的定义,句型有文法GS，若Sx，则称x是文法G的句型。句子有文法GS，若Sx，且xVT*，则称x是文法G的句子。例：G：S0S1，S01S0S100S11000S11100001111S，0S1，000111都是文法G的句型，其中00001111是G的句子。,2019/12/17,41,定义3.6由文法G所产生的语言记为L(G)，它是文法G的一切句子的集合:L(G)=x|Sx，其中S为文法的开始符号，且xVT*例：G：S0S1，S01L(G)=0n1n|n1,2019/12/17,42,例3.3文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee,2019/12/17,43,SaSBE(SaSBE)aaSBEBE(SaSBE)aaaBEBEBE(SaBE)aaaBBBEEE(EBBE)aaabBBEEE(aBab)aaabbBEEEaaabbbEEE（bBbb)aaabbbeEE（bEbe)aaabbbeeEaaabbbeee（eEee),L（G）=anbnen|n1,2019/12/17,44,文法的等价,若L(G1)=L(G2)，则称文法G1和G2是等价的。如文法G1A：A0R与G2S：S0S1等价A01S01RA1,2019/12/17,45,3.4文法的类型,Chomsky将文法分为四种类型：0型文法：G=(VN，VT，P，S)对任一产生式，都有(VNVT)*，且至少含有一个非终结符，(VNVT)*,0型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的,2019/12/17,46,带a0a1a2a3a4a5a6a7a8an-1an,1型文法（上下文有关文法）：设G=(VN，VT，P，S)为一文法，若P中的每一个产生式，都有|，仅仅S除外1型文法也可描述为1A212，其中1、2和都在V*中，A在VN中。即只有A出现在1和2的上下文中时，才允许取代A。,2019/12/17,47,2019/12/17,48,例：1型（上下文有关）文法文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee,2型文法（上下文无关文法）：设G=(VN，VT，P，S)，若P中的每一个产生式满足：是一非终结符，(VNVT)*有时将2型文法的产生式表示为形如：A其中AVN，也就是说用取代非终结符A时，与A所在的上下文无关，因此取名为上下文无关文法。,2019/12/17,49,2019/12/17,50,例：2型（上下文无关）文法文法GS：SaB|bAAa|aS|bAABb|bS|aBB文法GS：S0A|1B|0A0A|1B|0SB1B|1|0,3型文法（正规文法）：设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是AaB或Aa，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法。,2019/12/17,51,2019/12/17,52,例：定义标识符的3型（正规）文法文法GI：IiTIiTiTTdTTiTd,2019/12/17,53,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）,2019/12/17,54,2019/12/17,55,3.5上下文无关文法及其语法树,上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式语句赋值语句条件语句读语句,2019/12/17,56,例：算术表达式上下文无关文法表示,文法G=(E，+，*，i，(，)，P，EP:EiEE+EEE*EE(E),若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式。,描述语句的产生式：|描述一种简单赋值语句的产生式为：i:=E描述条件语句的产生式：ifthen|ifthenelse,2019/12/17,57,上下文无关的语法树,2019/12/17,58,用于描述上下文无关文法的句型推导的直观方法给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树（推导树）。定义：用来表示语言句子结构的树作用：使用语法树可以使得语法分析过程直观、形象。易于判断文法二义性,语法树满足下列4个条件：每个结点都有一个标记，此标记是V的一个符号。根的标记是S。若一结点n至少有一个它自己除外的子孙，并且标记A，则A肯定在Vn中。如果结点n的直接子孙，从左到右的次序是结点n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式。,2019/12/17,59,2019/12/17,60,例:GS:SaASASbAASSSaAba,SaASSbAaaba,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型aabbaa称为推导树的结果。也把该推导树称为句型aabbaa的语法树。,2019/12/17,61,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,SaASSbAaaba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,2019/12/17,62,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导由规范推导所得的句型称为规范句型,2019/12/17,63,二义性,问题：一个句型是否对应唯一的一棵语法树？,例：GE:EiEE+EEE*EE(E),EE+EE*Eiii,EE*EiE+Eii,句型i*i+i的两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i,2019/12/17,64,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。,2019/12/17,65,注：二义性会给语法分析带来不确定性文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否为二义文法若要证明是二义性，只要举出一例,2019/12/17,66,若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事二义文法改造为无二义文法GE:EiGE：ET|E+TEE+ETF|T*FEE*EF(E)|iE(E)规定优先顺序和结合律,2019/12/17,67,3.6句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。,2019/12/17,68,分析算法可分为：自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种不同的语法树的构造过程,2019/12/17,69,自上而下的语法分析,例：文法G：ScAdAabAa识别输入串w=cabd是否该文法的句子,SSScAdcAdab推导过程：ScAdcabd,2019/12/17,70,自下而上的语法分析,例：文法G：ScAdAabAa识别输入串w=cabd是否该文法的句子,SAAcabdcabdcabd归约过程：ScAdcabd,2019/12/17,71,句型分析的有关问题,1）如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？2）如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,2019/12/17,72,句型分析,短语、直接短语、句柄的定义：令G是一文法，S是文法的开始符号，是文法G的一个句型。如果有：SA且A则称是句型相对于非终结符A的短语。若有A则称是句型相对于该规则A的直接短语（简单短语）。一个句型的最左直接短语称为该句型的句柄。,2019/12/17,73,子树与短语、句柄,子树：在一棵语法树中，由某一结点及其所有分支组成的部分称为原树的一棵子树。一棵子树的所有叶子自左至右排列起来形成一个相对子树根的短语。（如上例）一个句型的句柄是这个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。,2019/12/17,74,句型分析,EETTFFi1*i2+i3短语：直接短语：句柄：,GE：EE+T|TTT*F|FF(E)|i句型：i1*i2+i3,T,F,i1*i2+i3，i1*i2，i1，i2，i3,i1，i2，i3,i1,2019/12/17,75,例：设文法GS：SaAS|aASbA|SS|ba则aabbaa是该文法的一个句子，求此句子的短语和句柄,短语：1、a1a2b1b2a3a42、a2b1b2a33、a44、a25、b2a3句柄：a2,2019/12/17,76,3.7有关文法实用中的一些说明,有关文法的实用限制上下文无关文法中的规则,2019/12/17,77,3.7.1有关文法的实用限制,文法中不得含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的,文法简化的步骤查找有无形如PP的产生式，若有则删除若某个产生式在推导过程中永远不会被用到，删除它若某个产生式在推导过程中不能从中导出终结符，删除它最后，整理所有剩余产生式，就得到简化的文法,2019/12/17,79,化简文法,例：GS0)SBe*1)SEc2)AAe3)Ae*4)AA*5)BCe6)BAf*7)CCf（不可终止的）*8)Df（不可到达的）,(0)SBe(1)BAf(2)AAe(3)Ae,2019/12/17,80,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1）A必须在某句型中出现。2）必须能从A推出终结符号串t来。即1）文法GS，对某两个符号串和：SA2）At，tVT*,2019/12/17,81,3.7.2上下文无关文法中的规则,具有形式A的规则称为规则，其中AVN某些著作和讲义中限制这种规则的出现。因为规则会使有关文法的一些讨论和证明变得复杂,复习重点,文法的概念字母表、符号串和集合的概念及运算文法的定义（四元组表示）什么推导句型、句子的概念语言的形式定义,等价文法文法的类型最左（右）推导规范推导规范句型规范归约二义性短语、句柄、直接短语,