二章语言的基本学习.ppt

二章语言的基本知识 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望学习本章的目的u构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。u语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那磨好用，但它推动语言理论的发展。2 2.1符号串u2.1.1 字母表u2.1.2 符号串 一.符号串的定义u 二.术语u 三.符号串的运算u 四.符号串集合的运算3 字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:1.计算机语言：由符号“0”和“1”组成的字 母表,=0，1 2.ASCII字符集；3.Pascal字母表为：=AZ,az,09,+,-,*,/,:,;，.，,(,),2.1.1字母表4一.符号串的定义(1)是上的一个符号串。(2)若x是上的符号串，而a是的元素,则xa是上的符号串。(3)y是上的符号串,当且仅当它由(1)和 (2)导出。由字母表中的符号所组成的的任何有穷 序列被称之为该字母表上的符号串,也称作字。2.1.2符号串5 设s是符号串前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）逆转（用SR表示）：将S中的符号按相反次序写出而得到的符号串。长度：是该符号串中的符号的数目。例如|aab|=3,|=0。二术语6 ：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,子串:banana,anana,banan,anan,真前缀，真后缀，真子串:xsx 子序列:baa(这些符号不要求是连续的）逆转（用SR表示）：ananab长度：banana=6例71.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：x0=;x1=x;x2=xx;xn=xn-1x;例如,x=ba,x1=ba,x2=baba,x3=bababa,.三.符号串的运算8 设L和M是两个符号串集合，则 1.合并：LMs|sL or sM 2.连接：LM st|sL and tM 3.方幂：L0=，L1L，L2LL,.,LnLn-1L 4.语言L的Kleene闭包，记作L*，L*Li(i=0)=L0L1L2L3 5语言L的正闭包，记作L+（L+LL*）L+Li(i=1)=L1L2L3L4四.符号串集合(语言）的运算9如：L=AZ,azD=091LD=AZ,az,092LD是由所有用一个字母后跟一个数字 组成的符号串所构成的集合。3L4是由所有的四个字母的符号串构的集合。4L（LD)*是由所有的字母打头的字母和数字组成的符号串所构成的集合.5D+是由所有的长度大于等于1的数字串所构成的集合.例102.2 文法和语言的定义u2.2.1引子u2.2.2文法和语言的定义u一.文法和语言的定义u二.推导u三.语言u四.最左推导和最右推导u五。短语，直接短语，句柄11引子分析：Thegreywolfwilleatthegoat谓语主语冠词形容词名词动词直接宾语助动词句子动原冠词名词Thegreywolfwilleatthegoat12为了进行机械分析，：“句子由主语后跟随谓语组成”表示为：句子主语谓语（1）主语冠词形容词名词（2）冠词the形容词grey谓语动词直接宾语（5）动词助动词动词原形（6）助动词will动词原形eat直接宾语冠词名词（9）名词wolf名词goat语法规则13 ：终结符号集，非终结符号集，语法规则，开始符号。终结符号集VT=the，grey,wolf,will,eat,goat非终结符号集VN=句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形语法规则集P=句子主语谓语，开始符号S=句子句子的语法有四部分14句子主语谓语冠词形容词名词谓语the形容词名词谓语thegrey名词谓语thegreywolf谓语thegreywolf动词直接宾语.thegreywolfwilleatthegoat句子根据规则推导出来15句子thegreywolfwilleatthegoatthegreywolfwilleatthewolfthegreygoatwilleatthewolfthegreygoatwilleatthegrey合符语法且合符语义的句子仅是：thegreywolfwilleatthegoat+句子既要合符语法又要合符语义16分析：Thegreywolfwilleatthegoat句子主语谓语冠词形容词名词动词直接宾语助动词动原冠词名词goattheeatwillThegreywolf句型分析一17分析：Thegreywolfwilleatthegoat句子主语谓语冠词形容词名词动词直接宾语助动词动原冠词名词goattheeatwillThegreywolf句型分析二18 一个上下文无关文法 G=（VT，VN S,P），其中：VT是一个非空有穷终结符号集合；VN是一个非空有穷的非终结符号集合，且VTVN；S VN，称为开始符号。P是一个产生式的非空有穷集合，每个产 生式的形式是A(或A:)，其中 AVN，（VTVN）*。开始符号S至必须在某个产生式的左部出现一次。缩写形式：A 1|2一文法的定义19G=(a,+,*,(,),，P)P：*（)aEE+TTTT*FFF(E)a(2.1)例2.2算术表达式的文法G:20令G=(VT,VN,S,P),若AP,且,(VTVN)*,则称A直接推出,表示成AA直接推出直接归约到A 如果存在一个直接推导序列：012 n（n0）表示成 0 n 0 n 或者0=n或者0 n+*二.定义2.3 直接推导和推导的定义21例：EE+TT+TF+Ta+Ta+Fa+a22设文法 G（VT，VN，S,P）。如果S ,则称是一个句型。仅含终结符号的句型是一个句子。语言 L(G）是由文法G产生的所有句子所组成的集合：L(G)|S 且VT*例2.3 考虑一个文法 G(a,b,S,S，P）其中P：SaSbabSaSbaaSbba3Sb3an-1Sbn-1anbn*+三.定义2.4：语言的定义23 设G=(VT=a,b,VN=S,A,B,S,P P由下列产生式组成:SaB|bA Aa|aS|bAABb|bS|aBBL(G)=w|wa,b+,且w中有相同个数的a和b。用归纳法证明下面结论（对w的长度）：(1)S w,当且仅当w中含有相同个数的a和b。(2)A w,当且仅当w中a的个数比b的个数多一个。(3)B w,当且仅当w中b的个数比a的个数多一个。归纳基础归纳基础 当|w|=1，Aa,Bb,不能从S导出长度为1的终极行,则上述结论显然成立。*例2.424 设(1),(2)和(3)对于长度不超过k-1的所有w都成立。那么，证明对|w|=k也成立。对于（1），推导的第一步必是SaB或SbA,对于第一种情形，必有w=aw1且B w1，|w1|=k-1，它含的b个数比a多一个，因此，w中a,b的个数相等。推导的第一步是SbA,证明完全类似。反之，|w|=k,w中a,b的个数相等,要证S w。考虑的S推导，推导出的开始符号，或为a或为b。若SaB,B w1,|w1|=k-1,w1中b的个数比a多一个,w=aw1。若S bA，证明和类SaB类似。（2）和（3）的证明留给同学们。*归纳步骤归纳步骤25:对于w和G,wL(G)是否存在Sw，如何构造例如，GE（例2.2）和w=a+aaEE+TT+TF+Ta+Ta+TFa+FFa+aFa+aa（最左）特点：A(A)，VT*EE+TE+TFE+TaE+FaE+aaT+aaF+aaa+aa特点：A(A)，VT*（最右）+四.最左推导和最右推导26 令GS是一个文法，如果有 S A 且A 则称是一个关于非终结符号A的，句型的短语。其次如果有 S A 且 A则称是直接短语。一个句型的最左直接短语称为该句型的句柄。文法（21）的一个句型 a1*a2+a3，尽管有E a2a3，但是 a2a3 并不是该句型的一个短语,因为不存在 E a1*E。短语：a1,a2,a3，a1*a2,a1*a2+a3 直接短语:a1，a2,a3 句柄:a1+*+定义2.5272.3分析树和二义性u一.分析树的定义u二.如何画出分析树u三.子树u四.二义性文法的定义u五.在构造编译程序中如何处理二义性文法28 设G=（VT，VN，S，P）,G的一棵分析树满足如下条件：1.每一个结点有一个标记，此标记是VTVN中的符号。2根的标记是S。3如果一个结点是内部结点，且有标记A,那么A必在VN中。4如果编号为n的结点有标记A,结点n1,n2,nk是点n的从左到右的儿子，并分别有标记X1,X2,Xk，则AX1X2Xk必须是P中的产生式。5.如果结点n有标记，那么结点n是叶子，且是它父亲唯一的儿子。一.分析树的定义29G=(VT,VN,S,P),其中P:SaASaASbASSba3124657891011SaASSbAaaba例2.530根据推导序列，对每步推导画相应分枝ASaSbSAaabaaSbASaabASaabbaSaabbaaaASS二.如何画出分析树 (1.自顶向下）31根据归约序列，对每步归约画相应分枝ASaSbSAaabaaAaaSbAaaSbbaaaabbaaaASS二.如何画出分析树 (2.自底向上）321.一个句型推导或分析用一棵树结构图示出来，它反应了一个句子语法结构的层次。2.对于一个句子的多种推导（若文法是无二义性的），采用各种推导过程，画出的分析树是一样的。分析树并未描述推导过程。3.在书中，用画分析树的过程解释语法分析过程，用分析树图解语法结构。分析树是推导的图形表示。关于分析树的几点说明33一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记。例如：SAbSaSbaAaa三.子树34短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例如，对表达式文法GE和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄:35EE+TT+TF+Ta1+Ta1+T*Fa1+F*Fa1+a2*FE+TT,T+TF,F+Ta1,a1+Ta1,T*F,a1+T*Fa1,F,F*F,a1+F*Fa1,a2,a1+a2*F,a2*Fa1,a2,a3,a2*a3a1+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3短语例(a)36EE+TE+T*FE+T*a3E+F*a3E+a2*a3T+a2*a3F+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3例(b)371.描述一个句子的文法不是唯一的；2.2.对于一个句子的分析应是唯一的。考虑表达式下面的文法GE,其产生式如下：EE+EE*E(E)a对于句子a+a*a,有如下两个最左推导：EE+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*a四.文法的二义性的定义38EE+Ea+Ea+E*Ea+a*Ea+a*aEE*EE+E*Ea+E*Ea+a*Ea+a*aEE+EE*EaaaEE*E+EEaaa最左推导例(1)39EE+EE+E*EE+E*aE+a*aa+a*aEE*EE*aE+E*aE+a*aa+a*aEE+EE*EaaaEE*E+EEaaa最右推导例(2)40如果一个文法的句子存在两棵分析树,那磨,该句子是二义性的。如果一个文法包含二义性的句子,则称这个文法是二义性的;否则，该文法是无二义性的。几点说明：1.一般来说，程序语言存在无二义性文法，对于表达式来说，文法（2.1）是无二义性的。对于条件语句，经常使用二义性文法描述它：SifexprthenSifexprthenSelseSother二义性的句子:ife1thenife2thens1elses2四.二义性（歧义性，ambiquity)的定义:41下面是Smathed_sunmathed_smathed_sifexprthenmathed_selsemathed_sotherunmathed_sifexprthenSifexprthenmathed_selseunmathed_s它显然比较复杂，因此：2.在能驾驭的情况下，使用二义性文法。描述if语句的无二义性文法的产生式:423.对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。4.存在先天二义性语言。例如，aibicji,j1aibjcji,j1存在一个二义性的句子akbkck。压缩过的文法（化简了的文法）：压缩过的文法（化简了的文法）：1形式的产生式：AAP；2.每个非终结符号A必须都有用处。即，SA且A，VT*+定义之3,4432.4形式语言概观u2.4.1 文法分类u2.4.2 非上下文无关文法的语言结构u2.4.3 上下文无关语言和正规语言的区别44逐渐对产生式施加限制四种类型：0型，1型，2型，3型0型：G=(VT,VN,S,P)规则形式：,(VTVN)*,推导：1型（上下文有关）：规则形式：AAVN,.(VTVN)*,2型（上下文无关）：规则形式：AAVN，(VTVN)*3型（右线性）：AaBAa（左线性）ABaAaaVT2.4.1文法分类45在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。例例2.92.9L1=wcw|wa,b+。例如,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。例例2.102.10L2=anbmcndm|n,m0，它是检查过程声明的形参个数和过程引用的参数个数一致问题的抽象。2.4.2非上下文无关的语言结构非上下文无关的语言结构46语言中过程定义和引用的语法并不涉及到参数个数，例如，Pascal的过程语句可描述为s-callid(r-list)r-listr-list,r|r实参和形参个数的一致性检查也是放在语义分析阶段完成的。定义定义2.72.7如果一个上下文无关文法G中存在具有下列特征的非终结符A:AA其中,VTVN+,则称A为自嵌套的,+2.4.32.4.3上下文无关语言和正则语言的区别上下文无关语言和正则语言的区别47包含自嵌套非终结符号的文法是语言anbn|n0是上下文无关语言，原因是找不到一个非自嵌套的上下文无关文法描述它；语言anbm|n，m0是正则语言,原因是存在一个正规文法描述它。在程序语言中，与词法有关的规则属于正规文法；与局部语法有关的规则属于上下文无关文法；而与全局语法和语义有关的部分往往要用上下文有关文法来描述。上下文无关文法。上下文无关文法。48用上下文有关文法描述程序语言不仅相当困难，将使语法定义变得烦杂，难懂，而且一般不能构造有效的分析程序，因此，通常用上下文无关文法描述，而把与上下文有关的限制包含在非形式描述的全局语法与语义中。把描述词法的正规文法从描述语法的上下文无关文法中分离出来。在分离出正则文法后的上下文无关文法中，这些单词符号是属于终结符号VT中的符号。文法(2.1)中的表达式文法，a是终结符号。为什么不用上下文有关文法描述程序语言为什么不用上下文有关文法描述程序语言？49：1.1GS:(b),(c),(d),(e)1.2GS:(a),(b),(c),(d)1.3Gbexpr:(b)1.写出下面语言的三型文法：（a)ann0(b)anbmn,m1(c)anbmckn,m1(d)Pascal的标识符(e)Pascal的整数2.已知文法GS，其产生式如下：S(S)(a)L(GS)是什磨？(b)对于(a)的结果，试给出证明。作业作业50