《编译方法》第2章形式语言和文法.ppt

,2.1形式语言,第2章形式语言和文法,2.4文法的二义性,2.3文法的分类和化简,2.2文法,2.1形式语言,2.1.1语言的概念,2.1.2语言的定义方式,语言：符号串的集合。元素符号串该语言的一个句子。字母表符号串中符号的来源。句子的构成按一定规则。程序设计语言：程序的集合句子程序（一个或长或短的字符串）。字母表固定的字符集，语言可以使用的所有符号。编程时必须遵循一定的规则语法规则和语义规则。语言的描述工具文法,2.1.1语言的概念,2.1语言,1.什么是语言,（1）有穷字母表一个元素的非空有穷集合，其中的元素也称符号。每个语言均有一固定的字母表。,例：C语言的字母表由基本字符集（字母，数字，括号，专用字符+、*、）、保留字（int、long、if、struct、static、typedef、sizeof、）等组成。,2.1.1语言的概念,2.1语言,2符号串的相关概念和术语,通常用V、或其他大写字母表示。例如V=0，1，=a，b，c，d，e等。,（2）符号串字母表中的符号组成的任何有穷序列。,相关术语：长度：符号串中符号的个数。符号串x的长度表示为x，x=m0。空符号串：无任何符号的串，简称空串，用表示，|=0省略写法：z=xz=xz=x,2.1.1语言的概念,2.1语言,【例2-1】=a，b，c，z，x=“laugh”，则|x|=5=I，you，he，am，is，are，a，student，y=“Iamastudent”，空格不计算长度，则|y|=4。,（3）符号串的运算,连接：符号串x、y的连接xy为一个新的符号串，该串的前面部分为x，后面部分为y。,成立的等式：|xy|=|x|+|y|x=x=x,【例2-2】若x=“home”，y=“work”则|x|=4,|y|=4xy=“homework”|xy|=4+4=8,2.1.1语言的概念,2.1语言,方幂：符号串x的方幂就是n个x自身连接次，表示为xn。规定x0=。,【例2-3】若x=“ab”则x0=x1=“ab”x2=“abab”x3=“ababab”,成立的等式：x1=x，x2=xx，x3=xxx，若n0，则有：xn=xxn-1=xn-1xx*表示x的任意多次方幂（可以是0次）x+表示x的任意非0次方幂。,2.1.1语言的概念,2.1语言,（4）符号串的集合若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。,乘积：两符号串集U、V的乘积为UV=|UV成立的等式：U=U=UVn=VVV（n个V）规定：V0=V*=V0V1V2V+=V1V2,【例2-4】若U=a，b，V=c，d则UV=ac，ad，bc，bd,2.1.1语言的概念,2.1语言,闭包：若指定字母表，则*表示上的所有有穷长的串的集合。*=012n*称为集合的闭包。+=12n+称为集合的正闭包。成立的等式：*=0+，+=*=*若符号串x是*的元素,则表示为x*,否则x*。,2.1.1语言的概念,2.1语言,语言的句子个数有限枚举语言的句子有很多甚至是无穷多个给出一些规则说明这个语言的句子的组成结构。规则文法规则,2.1.2语言的定义方式,2.1语言,【例2-5】文法规则：studentEnglishcomputerIyouheamisarehavestudyaanthe,文法规则的作用：（1）严格定义了一个语言的句子的结构；（2）用适当条数的规则描述了一个语言的全部句子。,2.1.2语言的定义方式,2.1语言,2.2文法,2.2.1文法的形式定义,2.2.2文法的表示方法,2.2.3相关概念,2.2文法,表示语言中的语法单位的符号，常用尖括号“”括起。一个非终结符一般可以推导出终结符串。一个语言可使用的所有非终结符组成的集合称为非终结符集，用VN表示。,1终结符,不可分割的符号串，是组成句子的最基本的单位。一个语言允许使用的所有终结符组成的集合称为终结符集，用VT表示。,2非终结符,2.2.1文法的形式定义,2.2文法,3规则（重写规则、产生式、生成式）,形如或或（，）的有序对，其中：某字母表V的V+中的一个符号串（左部）：V*中的一个符号串（右部）,定义：一个文法是一个四元组G（VN，VT，S，P）VN：非终结符集（非空）；VT：终结符集（非空），VNVT；S：识别符号或开始符号，SVN，且至少在一条规则中作为左部出现；P：规则（产生式）的集合。用V表示VNVT，称G的字母表或词汇表。,4文法,2.2.1文法的形式定义,2.2文法,G：S0S1或GS：S0S1或G：S0S1|01S01S01注意：左部相同的产生式可合并，用“|”表示“或”。,简化表示只写出规则（产生式），且第一条规则的左部是开始符号，用“”括起的或大写字母表示非终结符，不用“”括起的或小写字母表示终结符。文法G也常写成GS，方括号中的S为开始符号。,【例2-6】有一文法G（VN，VT，S，P）其中:VN=SVT=0，1开始符号是SP=S0S1，S01,2.2.1文法的形式定义,2.2文法,【例2-7】文法G=(VN，VT，S，P)为：VN=，VT=student，computer，sister，English，I，you，he，am，is，are，have，study，a，an，the开始符号是P=studentcomputersisterEnglishIyouheamisarehavestudyaanthe,2.2.1文法的形式定义,2.2文法,【例2-8】FORTRAN语言中对标识符的规定是字母开头、长度小于等于8的字母数字串，则标识符的规则可以描述为：,1.BNF表示法巴科斯-诺尔范式（巴科斯范式）采用四个元符号描述文法：“”（或“”）、“”，“|”2.扩展的BNF表示法增加三对元符号：（1）“”表示符号串t的多次重复，n为重复的最小次数，m为重复的最大次数，省略n、m表示t可以重复0到任意多次。,2.2.2文法的表示方法,2.2文法,（2）“()”用于提取产生式的公共因子，从而可以简化产生式。若有文法规则Ax1|x2|xn表示为Ax(1|2|n)【例2-9】文法规则S0S1|01简化为S0(S1|1)或S(0S|0)1或S0(S|)1（3）“”：t表示符号串t可选（即可有可无）。【例2-10】C程序设计语言的条件语句的文法规则BNF表示：if()；|if()；else；扩展BNF表示：if()；else；,2.2.2文法的表示方法,2.2文法,3.语法图表示法【例2-11】C语言条件语句的语法图,2.2.2文法的表示方法,2.2文法,终结符,非终结符,【例2-13】对文法G：S0S1S01有直接推导序列：S0S100S11000111,定义：如是文法G（VN，VT，S，P）的一条规则，、V*，若有符号串v、w满足v=，w=则称v（应用规则）直接产生w，或称w是v的直接推导，反过来称w直接归约到v，记作vw。,1推导和归约,2.2.3相关概念,2.2文法,定义：如果存在直接推导序列：v=w0w1w2wn=w则称v推导（产生）出w，推导长度为n，反过来称w归约到v，记作vw。如果有vw，或v=w，则记作vw。,2.2.3相关概念,2.2文法,【例2-15】推导S0S100S11000111,定义：文法G（VN，VT，S，P），若符号串x可由开始符号S推导出（Sx），则称x是G的一个句型，若x仅由终结符组成，则称x为G的一个句子。,*,2句型和句子,句型,句子,2.2.3相关概念,2.2文法,注意：句型和句子都必须由开始符号S推出！,定义：文法描述的语言是该文法的所有句子的集合，记作L(G)。集合形式表示：L(G)=|SVT*,【例2-16】文法G：S0S1S01描述的语言：L(G)=0n1n|n1,3形式语言,+,2.2.3相关概念,2.2文法,【例2-17】有文法GA：A0RA01RA1,定义：若有文法G1、G2，它们描述的语言相同，即L(G1)=L(G2)则称两文法G1和G2等价。,描述的语言L(G)=0n1n|n1。,4文法的等价性,2.2.3相关概念,2.2文法,2.2.3相关概念,2.2文法,5.递归规则和递归文法,递归文法：含有递归规则的文法称递归文法。,递归规则：形如P1P2的规则称递归规则。若1=则称左递归规则;若2=则称右递归规则。,P1P2的递归称间接递归,含间接递归的文法也是递归文法。,+,2.3文法的分类和化简,2.3.1文法的分类,2.3.2两个定理,2.3.3文法的化简,2.3文法的分类和化简,1.0型文法（无限制文法或短语文法）,2.3.1文法的分类,定义2-7设G=(VN，VT，P，S)，如果它的每个产生式满足、(VNVT)*，且至少含有一个非终结符，则G是一个0型文法。,结论0型文法的能力相当于图灵机，它所定义的语言为0型语言。任何0型语言都是递归可枚举的，反之，递归可枚举集也必定是一个0型语言，可由图灵机来识别。,2.3文法的分类和化简,定义2-8设G=(VN，VT，P，S)，如果它的每个产生式满足|（仅S除外），则G是一个1型文法。另一种描述：文法的产生式形如1A212其中AVN，、(VNVT)*且。,【例2-18】1型文法GS：SxSYZ|xYZyZyzxYxyZYYZyYyyzZzz,21型文法,（上下文有关文法）,2.3.1文法的分类,2.3文法的分类和化简,32型文法（上下文无关文法）,【例2-19】2型文法GS：SETP|TPFi|(E)ET|ETPF|FP,定义2-9设G=(VN，VT，P，S)，如果它的每个产生式中的是一个非终结符，则G是一个2型文法或上下文无关文法。,2.3.1文法的分类,2.3文法的分类和化简,43型文法（正规文法或正则文法）,【例2-20】3型文法GS：SaAAaAAaSaAdAAd,定义2-10设G=(VN，VT，P，S)，如果它的每个产生式均形如AaB或Aa其中A、BVN，aVT。,2.3.1文法的分类,2.3文法的分类和化简,描述句法,描述词法,|,VN,=aB|a,2.3文法的分类和化简,2.3.1文法的分类,定理2-1：含有A的文法产生的语言也可由不含A的另一个文法产生（S除外）。定理2-2：若存在一个上下文有关文法G，则必存在另一个上下文有关文法G1，使得L(G1)=L(G)，且G1的开始符号不出现在任何产生式的右边。在使用上下文无关文法描述语言时不限制产生式的使用。,2.3文法的分类和化简,2.3.2两个定理,文法应没有多余的或有害的规则。化简：(1)删除形如AA的产生式。(2)删除不可到达的文法符号及其相应的产生式。(3)删除不可终止的非终结符及其相应的产生式。,【例2-21】文法G：SaS|W|UUaVbV|acWaW,W是不可终止的V是不可到达的。,化简后的文法G：SaS|UUa,2.3.3文法的化简,2.3文法的分类和化简,1.语法树,2.4文法的二义性,2.3文法的二义性,定义：语法树是一棵数据结构意义上的“树”，满足四个条件：（1）每个结点都有一个标记（字母表V的一个符号）；（2）根的标记是S（文法的开始符号）；（3）若一个结点n至少有一个它自身除外的子孙，且有标记A，则A必在VN中（是非终结符）；（4）若标记为A的结点n的直接子孙从左到右的次序是结点n1、n2、nk，其标记分别为A1、A2、Ak，则AA1A2Ak必是文法产生式集P中的一个产生式。对给定文法G，它的任何句型均能构造与之相关的语法树。,2.4文法的二义性,2.3文法的二义性,i*ii的语法树,【例2-22】对算术表达式文G：EiEE+EEE*EE(E),“i*ii”的推导过程可以是：(1)EE+EE*E+Ei*E+Ei*i+Ei*i+i(2)EE+EE+iE*E+iE*i+ii*i+i(3)EE+EE+iE*E+ii*E+ii*i+i,2.4文法的二义性,2.3文法的二义性,可见：（1）一棵语法树表示了一个句型的多种可能的不同推导过程，但未必是所有的。（2）一个句型未必只有一棵语法树。,最左推导：在推导的任何一步（、是句型）都是对中的最左非终结符进行替换。最右推导：在推导的任何一步（、是句型）都是对中的最右非终结符进行替换。也称规范推导，推出的句型称规范句型。,例如最左推导：EE*Ei*Ei*E+Ei*i+Ei*