编译原理(3).ppt

1、第三章文法和语言,3.1文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型的分析3.7有关文法实用中的一些说明,第三章文法和语言,程序设计语言与自然语言一样，完整的定义包括语法和语义两个方面。所谓语法是指一组规则，用它可以形成和产生一个合适的程序。语法只是定义什么样的符号序列是合法的，与符号的含义无关。语义有两种类型：静态语义是一系列限定规则，确定哪些合乎语法的程序是合适的；动态语义也称运行语义或执行语义，表明程序要做些什么？要计算什么。文法是阐明语法的一种工具，描述语法的规则。,3.1文法的直观概念,语法是用来描述语言的组成规则

2、。语句是组成语言的基本元素。而组成语言的语句往往是无穷列举的，这时就要给出一些规则来描述句子的组成结构。构成语句的组织规则就是语法的表现。而这种规则或者说这种语言的描述就是文法。使用文法工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻画无穷的集合的工具。,以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。“我是大学生”。是汉语的一个句子句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动

3、词=是学习直接宾语=代词名词,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。句子：“我是大学生”的全部动作过程是：句子主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,3.2符号和符号串

4、,程序设计语言的表达方式就是一个一个的程序。而程序又是由一个个指令语句组成。语句又是由数字和字母这样一些基本符号所组成。程序设计语言可以看成是在基本符号集上定义的，按照一定规则构成的一切基本符号串组成的集合。字母表：是元素的非空有穷集合，这里所指的元素就是符号。不同的语言可以有不同的字母表。符号串：由字母表中的符号组成的任何有穷序列称为符号串。符号串涉及的有关概念有：符号的顺序、符号串的长度、空符号串、符号串的头尾、符号串的省略写法、符号串的连接、符号串的幂、符号串的集合。,符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB

5、=xy|xA且yB。若集合A=ab,cde，B=0,1，则AB=ab1,ab0,cde0,cde1。使用*表示上的一切符号串（包括）组成的集合。*称为的闭包。上的除外的所有符号串组成的集合记为+。+称为的正闭包。例：=a,b*=,a,b,aa,ab,ba,bb,aaa,+=a,b,aa,ab,ba,bb,aaa,aab,指定字母表，*表示上的所有有穷长的串的集合。=0，1*=，0，1，00，01，10，11，000，001，010，*=0U1U2UUnU*称为集合的闭包:正闭包:+=1U2UUnU*=0U+=*=*,3.3文法和语言的形式定义,如何来描述一种语言？如果语言是有穷的（只含有有穷多

6、个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）,目标是用有穷的规则描述无穷的语言,3.3文法和语言的形式定义,规则(也称重写规则、产生式或生成式)：是形如或:=的(,)有序对，其中为字母表的正闭包中的符号，为字母表的闭包中的符号，称为规则的左部，称为规则的右部。规则是文法的核心。,3.3文法和语言的形式定义,所谓的形式定义就

7、是用符号串来描述文法规则的表述。形式定义1：文法G定义为四元组（VN，VT，P，S）。其中，VN为非终结符号（或语法实体，或变量）集；VT为终结符号集；P为产生式（也称规则）的集合；（VN，VT和P是非空有穷集。）S称做识别符号或开始符号，它是一个非终结符，至少要在一条规则中作为左部出现。VN和VT不含公共的元素，即VNVT=。通常用V表示VNVT，V称为文法G的字母表或字汇表。,例,文法G=（VN,VT,P,S），其中VN=SVT=0,1P=S0S1,S01可见该文法中非终结符中只含一个符号S，终结符中含两个符号0和1，由两个产生式，开始符号是S.,例文法G=（VN，VT，P，S）VN=标识

8、符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z0,9S=,很多时候不用将文法的四元组显式地表示出来，而只将产生式写出。一般约定：第一条产生式的左部是识别符号；用尖括号括起来的是非终结符号；不用尖括号括起来的是终结符号。或者用大写字母表示非终结符号，小写字母表示终结符号。如：G:S0S1S01,文法的写法1G：SaAbAabAaAbA2GS：SaAbAabAaAbA3GS：SaAbAab|aAb|,3.3文法和语言的形式定义,为定义文法所产生的语言，引入推导概念。形式定义2：如是文法G=(VN，VT，P，S)的规则(或说是P中的一产生式)，和是V*中的任意符号，若有符号串v，w

9、满足：v=，w=。则说v（应用规则）直接产生w，或说w是v的直接推导，或者说w直接规约到v，记作：vw。形式定义3：如果存在直接推导的序列：v=w0w1w2wn=w(w0)则称v推导出（产生）w（推导长度为n），或称w规约到v。记作v+w形式定义4：若有v+w，或vw，则记作：v*w,推导的举例,例：G：S0S1，S01S0S100S1100S11000S111000S11100001111S0S1.VAR;BEGINREAD()END.VARA;BEGINREAD()END.,例：G：S0S1，S010S100S1100S11000S111000S11100001111S0S100S1100

10、0S11100001111S=+00001111S=*S00S11=*00S11,3.3文法和语言的形式定义,形式定义5：设GS是一文法，如果符号串x是从识别符号推导出来的，即有S*x，则称x是文法GS的句型。若x仅由终结符号组成，即S*x，xV*T，则称x为GS的句子。例：G：S0S1，S01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01,一定是从文法开始符号出发进行推导,例：GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号a

11、，+，*，(和)构成的算术表达式,3.3文法和语言的形式定义,形式定义6：文法G所产生的语言定义为集合x|S*x，其中S为文法识别符号，且xV*T，。可用L（G）表示该集合。符号串x可从识别符号推出，也即x是句型。X仅由终结符组成，即x是文法G的句子。文法描述的语言是该文法一切句子的集合。,例1：G：S0S1，S01L(G)=0n1n|n1例2文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL（G）=anbnen|n1,SaSBE(SaSBE)aaBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bB

12、bb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,使用产生式(1)n-1次，得到推导序列：S=*an-1S(BE)n-1，然后使用产生式(2)一次，得到：S=*an-1S(BE)n-1an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S=*anBnEn接着，使用产生式(4)一次，得到S=*anbBn-1En，然后使用产生式(5)n-1次得到：S=*anb

13、nEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S=*anbnen也能证明，对于n1，串anbnen是唯一形式的终结符号串,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。如文法G1A：A0R与G2S：S0S1等价A01S01RA1,3.4文法的类型,文法分成四种类型，即0型、1型、2型、3型。这几类文法的差别在于对产生式施加不同的限制。0型文法：设G=(VN，VT，P，S)，如果它的每个产生式是这样一种结构：（VNVT）*，且至少含有一个非终结符，而（VNVT）*，则G是一个0型文法。0型文法也称短语文法。任何0型语言都是递归可枚举的；反之，递归可枚举集必

14、定是一个0型文法。对0型文法产生式的形式做某些限制，可以给出1，2和3型文法的定义。,3.4文法的类型,1型文法：设G=(VN，VT，P，S)为一文法，若P中的每一个产生式均满足|=|，仅仅S除外，则文法G是1型文法或上下文有关文法。上下文有关文法的产生式的形式描述为1A21A2，其中1、2和都在（VNVT）*中，且非空，A在VN中。体现“上下文无关”，表现在只有A出现在1和2的上下文中，才能用取代A。2型文法：设G=(VN，VT，P，S)，若P中的每一个产生式满足：是一个非终结符，（VNVT）*则此文法称为2型文法或上下文无关文法。产生式的表现为：A。取代A与它的上下文无关。3型文法：设G=

15、(VN，VT，P，S)，若P中的每一个产生式的形式都是AB或A，其中A和B都是非终结符，是终结符，则G是3型文法或正规文法。四个文法类型的定义是逐渐增加限制，因此，每一种正规文法都是上下无关的；每一种上下无关文法都是上下有关的；而每一种上下有关文法都是0型文法。,文法的类型,例：1型（上下文有关）文法文法GS：SCDAbbACaCABaaBCbCBBbbBADaDCBDbDDAabD,文法的类型,例：2型（上下文无关）文法文法GS：SABABS|0BSA|1,3型文法,GS：S0A|1B|0A0A|1B|0SB1B|1|0,GI：IlTIlTlTTdTTlTd,文法的类型,0型文法,四种文法之

16、间的逐级“包含”关系,3型文法,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）,文法和语言,四种文法之间的关系是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,3.5上下文无关文法及其语法树,从0型到3型文法,其后一类都是前一类的子集,且限制是逐步增强,而描述

17、语言的功能是逐步减弱。上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式，描述各种语句等。,例文法G=(E,+,*,i,(,),P,E)其中P为：Ei,EE+E,EE*E,E(E),赋值语句i=EE表示算术表达式,i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式描述一种简单赋值语句的产生式：赋值语句i=E描述条件语句的产生式：条件语句if条件then语句if条件then语句else语句,3.5上下文无关文法及其语法树,语法树：是一种描述上

18、下文无关文法的句型推导的直观方法，也称推导树。给定文法G=（VN，VT，P，S），对于G的任何句型都能构成与之关联的语法树（推导树）。这棵树满足下列4个条件：每个结点都有一个标记，此标记是V的一个符号；根的标记是S；若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在VN中；如果结点n的直接子孙，从左到右的次序是结点n1,n2,nk,其标记分别为A1，A2，AK，那么AA1A2A3AK，一定是P中的一个产生式。,上下文无关文法的语法树的用处,用于描述上下文无关文法句型推导的直观方法,例:GS:SaASASbAASSSaAba,SaASSbAaaba,句型aabbaa的语法树（推导树）

19、,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。也把该推导树称为该句型的语法树。,上下文无关文法的语法树,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,SaASSbAaaba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,最左（最右）推导最右推导为规范推导；规范推导产生的句型为规范句型,句型、推导,GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TE+T

20、*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a不同的推导过程，都可以得到一个相同的结果。,规范推导规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?不是的,例：GE:EiEE+EEE*EE(E),EE+EE*Eiii,EE*

21、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,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的

22、语言是相同的。二义文法改造为无二义文法GE:EiGE：ET|E+TEE+ETF|T*FEE*EF（E）|iE(E)规定优先顺序和结合律如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,3.6句型的分析,对于上下文无关文法，语法树是句型推导过程的几何表示。语法树将句型结构直观地显示出来，是句型分析的很好工具。句型的分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。当给定一个符号串时，试图按照某文法的规则为该符号串构造推导或语法树，以此识别出它是该文法的一个句型。对于程序

23、设计语言来说，句型分析是一个识别输入符号串是否为语法上正确的程序的过程。分析算法从左到右，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而识别右边的一个符号,3.6句型的分析,分析算法又可以分成两大类，即自上向下的和自下向上的。所谓自上向下分析法，是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。所谓自下向上分析法，则是从输入符号串开始，逐步进行“规约”，直到规约到文法的开始符号。从语法树的角度的理解句型分析过程，自上而下方法是从文法符号开始，将它作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串；自下向上方法则是从输入符号串

24、开始，以它作为语法树的末端结点符号串，自底向上地构成语法树。,自上而下的分析方法,文法GS；(1)ScAd；(2)Aab；(3)Aa识别输入串w=cabd是否该文法的句子。从根符号S开始，为cabd构造一棵语法树。,S,c,A,d,a,b,推导过程：ScAdcabd,自下而上的分析方法,文法GS；(1)ScAd；(2)Aab；(3)Aa为输入符号串cabd构造推导或语法树。首先从输入符号串开始。扫描cabd，从中寻找一个子串，该子串与某一产生式的右端相匹配。,S,c,A,d,a,b,c,A,d,a,b,c,d,a,b,(1)ScAd(2)Aab(3)Aa识别输入串w=cabd是否为该文法的句子

25、自上而下的语法分析,若ScAd后选择(3)扩展A，ScAdcad那将会？w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cabd构造语法树，即cabd不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。,S,A,d,c,a,对于自上而下分析方法中的主要问题,回溯,(1)ScAd(2)Aab(3)Aa识别输入串w=cabd是否为该文法的句子自下而上的语法分析,对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么最终就达不到归约到S的结果，因而也无从知道ca

26、bd是一个句子,cabdcAbda,对于自下而上分析方法中的主要问题,精确定义“可规约串”,句型分析的有关问题,在自上而下分析方法中的主要问题是:假定要被代换的最左非终结符号是V,且有n条规则:V:=a1|a2|an那么如何确定用哪个右部去代替V呢?有一种解决办法是从各种可能的选择中随机挑选一种，并希望它是正确的。如果发现它不正确，是错误的，必须退回，重新选择。这种方式称为回溯。在自下而上分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它规约到某个非终结符号，这个子串称为“可规约串”。问题是，每一步如何确定这个“可规约子串”。,刻画“可归约串”,文法GS句型的短语S=*A且A=+，则称是句型相对于非终结符A的短语句型的直接短语若有A，则称是句型相对于非终结符A的直接短语句型的句柄一个句型的最左直接短语称为该句型的句柄,i*i+i的短语、直接短语和句柄,GE：EE+T|TTT*F|FF(E)|i句型：i*i+i短语：i1*i2+i3，i1*i2，i1，i2，i3直接短语：i1，i2，i3句柄：i1,E,E,T,+,T,F,T,F,*,F,i1,i2,i3,I1,i2,i3分别是相对于F的直接短语I1*i2是相对于T的短语,因为不能直接推导出,所以,不是直接短语.同样i1*i2+i3是相对于E的短语.,指出句型F+Fi(的短语，句柄，