《二章语言的基本知识ppt课件》由会员分享，可在线阅读，更多相关《二章语言的基本知识ppt课件（50页珍藏版）》请在金锄头文库上搜索。
1、第二章言语的根本知识u学习本章的目的。u2.1 符号串u2.2 文法和言语的定义u2.3 分析树和二义性u2.4 方式言语概观学习本章的目的u构造编译程序的算法是从研讨源程序及目的程序产生的，首先找到源言语的方式描画，根据这种描画，构造出相应的分析加工程序。u言语分语法，语义和语用。程序文语语法的方式描画是很好用的，语义的方式描画不那磨好用，但它推进言语实际的开展。 2.1 符号串u2.1.1字母表u2.1.2符号串一.符号串的定义u二.术语u三.符号串的运算u四.符号串集合的运算 字母表是符号的非空有穷集合。任何程序文语都有本人的字母表，例如: 1.计算机言语：由符号“0和“1组成的字 母表
2、,=0，1 2. ASCII字符集； 3. Pascal字母表为： = AZ, az, 09, +, -, *, /, , :, , ; ，.， , (, ), , , , 2.1.1字母表一. 符号串的定义(1) 是上的一个符号串。(2) 假设x是上的符号串，而a是的元素, 那么xa是上的符号串。(3) y是上的符号串,当且仅当它由(1)和 (2)导出。 由字母表中的符号所组成的的任何有穷 序列被称之为该字母表上的符号串,也称作字。2.1.2符号串 设s是符号串前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串: 从s中删去一个前缀和一个后缀子序列: 从s中删去
3、零个或多于零个符号(这些符号不要求是延续的逆转用SR表示：将S中的符号按相反次序写出而得到的符号串。长度：是该符号串中的符号的数目。例如|aab|=3,|=0。二术语 ：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a, 子串: banana,anana,banan,anan, 真前缀，真后缀，真子串: xsx 子序列: baa(这些符号不要求是延续的逆转用SR表示：ananab长度：banana=6例1.衔接：设x和y是符号串，它们的衔接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y
4、=nana,xy=banana.2.方幂：x0=;x1=x;x2=xx;xn=xn-1x;例如,x=ba,x1=ba,x2=baba,x3=bababa,.三.符号串的运算 设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+L L* L+Li(i =1) =L1L2L3L4四. 符号串集合(言语的运算如：L=AZ,azD=091LD=AZ,az,092LD是
5、由一切用一个字母后跟一个数字组成的符号串所构成的集合。3L4是由一切的四个字母的符号串构的集合。4LLD)*是由一切的字母打头的字母和数字组成的符号串所构成的集合.5D+是由一切的长度大于等于1的数字串所构成的集合.例2.2 文法和言语的定义u2.2.1引子u2.2.2文法和言语的定义u一.文法和言语的定义u二.推导u三.言语u四.最左推导和最右推导u五。短语，直接短语，句柄引子分析：The grey wolf will eat the goat谓语主语冠词描画词名词动词直接宾语助动词句子动原冠词名词Thegreywolfwilleatthegoat为了进展机械分析，：“句子由主语后跟随谓语组
6、成表示为：句子主语谓语1主语冠词描画词名词2冠词the描画词grey谓语动词直接宾语5动词助动词动词原形6助动词will动词原形eat直接宾语冠词名词9名词wolf名词goat语法规那么 ：终结符号集，非终结符号集，语法规那么，开场符号。终结符号集VT=the，grey, wolf,will, eat, goat非终结符号集VN=句子，主语， 谓语， 冠词， 描画词， 名词 ， 动词 ， 直接宾语 ， 助动词 ，动词原形 语法规那么集P=句子 主语谓语， 开场符号S= 句子句子的语法有四部分句子主语谓语冠词描画词名词谓语the描画词名词谓语thegrey名词谓语thegreywolf谓语the
7、greywolf动词直接宾语.thegreywolfwilleatthegoat句子根据规那么推导出来句子thegreywolfwilleatthegoatthegreywolfwilleatthewolfthegreygoatwilleatthewolfthegreygoatwilleatthegrey合符语法且合符语义的句子仅是：thegreywolfwilleatthegoat+句子既要合符语法又要合符语义分析：The grey wolf will eat the goat句子主语谓语冠词描画词名词动词直接宾语助动词动原冠词名词goattheeatwillThegreywolf句型分析一
8、分析：The grey wolf will eat the goat句子主语谓语冠词描画词名词动词直接宾语助动词动原冠词名词goattheeatwillThegreywolf句型分析二 一个上下文无关文法 G= VT，VN S, P ，其中： VT是一个非空有穷终结符号集合； VN是一个非空有穷的非终结符号集合， 且VTVN； S VN ，称为开场符号。 P是一个产生式的非空有穷集合，每个产 生式的方式是A(或A :)，其中 AVN，VTVN*。开场符号S至必需在某个产生式的左部出现一次 。 缩写方式： A 1|2一文法的定义G=(a,+,*,(,),，P)P：*)aEE+TTTT*FFF(E
9、)a(2.1)例2.2算术表达式的文法G:令G=(VT,VN,S,P),假设AP,且,(VTVN)*,那么称A直接推出,表示成AA直接推出直接归约到A假设存在一个直接推导序列：012nn0表示成0n0n或者0=n或者0n+*二. 定义2.3 直接推导和推导的定义例：EE+TT+TF+Ta+Ta+Fa+a设文法 GVT，VN，S,P。假设S ,那么称是一个句型。仅含终结符号的句型是一个句子。言语 L(G是由文法G产生的一切句子所组成的集合： L(G)|S 且VT*例2.3 思索一个文法 G(a,b,S,S，P其中P：SaSb ab SaSb aaSbb a3Sb3 an-1Sbn-1 anbn*
10、+三. 定义2.4：言语的定义 设G=(VT=a,b,VN=S,A,B,S,P P由以下产生式组成:SaB|bA Aa|aS|bAA Bb|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, B b, 不能从S导出长度 为1的终极行,那么上述结论显然成立。*例2.4 设(1),(2)和(3)对于长度不超越k-1的一切w都成立。那么，证明对|w|=k也成立。 对于
11、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的证明留给同窗们。*归纳步骤归纳步骤:对于w和G,wL(G)能否存在Sw，如何构造例如，GE例2.2和w=a+aaEE+TT+TF+Ta+Ta+TFa+FFa+aFa+aa最左特点：A(A
12、)，VT*EE+TE+TFE+TaE+FaE+aaT+aaF+aaa+aa特点：A(A)，VT*最右+四.最左推导和最右推导 令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.52.3分析树和二义性u一.分析树的定义u二.如何画出分析树u三
13、.子树u四.二义性文法的定义u五.在构造编译程序中如何处置二义性文法 设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是叶子，且是它父亲独一的儿子。一.分析树的定义G=(VT,VN,S,P),其中P:SaASaASbASSba3124657891011SaASSbAaaba例2.5根据推
14、导序列，对每步推导画相应分枝ASaSbSAaabaaSbASaabASaabbaSaabbaaaASS二.如何画出分析树(1.自顶向下根据归约序列，对每步归约画相应分枝ASaSbSAaabaaAaaSbAaaSbbaaaabbaaaASS二.如何画出分析树(2.自底向上1.一个句型推导或分析用一棵树构造图示出来，它反响了一个句子语法构造的层次。2.对于一个句子的多种推导假设文法是无二义性的，采用各种推导过程，画出的分析树是一样的。分析树并未描画推导过程。3.在书中，用画分析树的过程解释语法分析过程，用分析树图解语法构造。分析树是推导的图形表示。关于分析树的几点阐明一棵分析树中一个特有的结点连同
15、它的全部后裔，衔接这些后裔的边以及这些结点的标志。例如：SAbSaSbaAaa三.子树短语：一棵子树的一切叶子自左至右陈列起来构成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的一切叶子自左至右陈列起来所构成的符号串。句柄：一个句型的分析树中最左那棵只需父子两代的子树的一切叶子的自左至右陈列。例如，对表达式文法GE和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。用子树解释短语，直接短语，句柄:EE+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*F
16、a1,a2,a1+a2*F,a2*Fa1,a2,a3,a2*a3a1+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3短语例(a)EE+TE+T*FE+T*a3E+F*a3E+a2*a3T+a2*a3F+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3例(b)描画一个句子的文法不是独一的；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四.文法的二义性的定义EE+Ea+Ea+E*Ea+a*Ea+a
17、*aEE*EE+E*Ea+E*Ea+a*Ea+a*aEE+EE*EaaaEE*E+EEaaa最左推导例(1)EE+EE+E*EE+E*aE+a*aa+a*aEE*EE*aE+E*aE+a*aa+a*aEE+EE*EaaaEE*E+EEaaa最右推导例(2)假设一个文法的句子存在两棵分析树,那磨,该句子是二义性的。假设一个文法包含二义性的句子,那么称这个文法是二义性的;否那么，该文法是无二义性的。几点阐明：1.普通来说，程序文语存在无二义性文法，对于表达式来说，文法2.1是无二义性的。对于条件语句，经常运用二义性文法描画它：SifexprthenSifexprthenSelseSother二义性
18、的句子:ife1thenife2thens1elses2四.二义性歧义性，ambiquity)的定义:下面是Smathed_sunmathed_smathed_sifexprthenmathed_selsemathed_sotherunmathed_sifexprthenSifexprthenmathed_selseunmathed_s它显然比较复杂，因此：2.在能驾驭的情况下，运用二义性文法。描画if语句的无二义性文法的产生式:3.对于恣意一个上下文无关文法，不存在一个算法，断定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。4.存在先天二义性言语。例如，aibic
19、ji,j1aibjcji,j1存在一个二义性的句子akbkck。紧缩过的文法化简了的文法：1方式的产生式：AAP；2.每个非终结符号A必需都有用途。即，SA且A，VT*+定义之3,42.4方式言语概观u2.4.1文法分类u2.4.2非上下文无关文法的言语构造u2.4.3上下文无关言语和正规言语的区别逐渐对产生式施加限制四种类型：0型，1型，2型，3型0型：G=(VT,VN,S,P)规那么方式：,(VTVN)*,推导：1型上下文有关：规那么方式：AAVN,.(VTVN)*,2型上下文无关：规那么方式：AAVN，(VTVN)*3型右线性：AaBAa左线性ABaAaaVT2.4.1文法分类在我在我们
20、运用的程序文运用的程序文语中中,有些言有些言语构造并构造并不是不是总能用上下文无关文法描画的。能用上下文无关文法描画的。例例2.9L1=wcw|wa,b+。例如。例如,aabcaab就是就是L1的一个句子。的一个句子。这个言个言语是是检查程序中程序中标识符的声明符的声明应先于援用的先于援用的笼统。例例2.10L2=anbmcndm|n,m0，它是，它是检查过程声明的形参个数和程声明的形参个数和过程援用的参数个数程援用的参数个数一致一致问题的的笼统。2.4.2非上下文无关的言语构造言语中过程定义和援用的语法并不涉及到参数个数，例如，Pascal的过程语句可描画为s-callid(r-list)r
21、-listr-list,r|r实参和形参个数的一致性检查也是放在语义分析阶段完成的。定义2.7假设一个上下文无关文法G中存在具有以下特征的非终结符A:AA其中,VTVN+,那么称A为自嵌套的,+2.4.32.4.3上下文无关言语和正那么言语的区上下文无关言语和正那么言语的区别别包含自嵌套非终结符号的文法是言语anbn|n0是上下文无关言语，缘由是找不到一个非自嵌套的上下文无关文法描画它；言语anbm|n，m0是正那么言语,缘由是存在一个正规文法描画它。在程序文语中，与词法有关的规那么属于正规文法；与部分语法有关的规那么属于上下文无关文法；而与全局语法和语义有关的部分往往要用上下文有关文法来描画
22、。上下文无关文法。上下文无关文法。用上下文有关文法描画程序文语不仅相当困难，将使语法定义变得烦杂，难懂，而且普通不能构造有效的分析程序，因此，通常用上下文无关文法描画，而把与上下文有关的限制包含在非方式描画的全局语法与语义中。把描画词法的正规文法从描画语法的上下文无关文法中分别出来。在分别出正那么文法后的上下文无关文法中，这些单词符号是属于终结符号VT中的符号。文法(2.1)中的表达式文法，a是终结符号。为什么不用上下文有关文法描画程序文语为什么不用上下文有关文法描画程序文语？：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)的结果，试给出证明。作业作业
