编译原理chapter语言基本知识ppt课件

1、 字母表是符号的非空有穷集合。任何程序文语都有本人的字母表，例如: 1.计算机言语：由符号“0和“1组成的字 母表,=0，1 2. ASCII字符集； 3. Pascal字母表为： = AZ, az, 09, +, -, *, /, , :, , ; ，.， , (, ), , , , 一. 符号串的定义(1) 是上的一个符号串。(2) 假设x是上的符号串，而a是的元素, 那么xa是上的符号串。(3) y是上的符号串,当且仅当它由(1)和 (2)导出。 由字母表中的符号所组成的的任何有穷 序列被称之为该字母表上的符号串,也称作字。 设s是符号串前缀：移走s的尾部的零个或多于零个符号后缀：删去s

2、的头部的零个或多于零个符号子串: 从s中删去一个前缀和一个后缀子序列: 从s中删去零个或多于零个符号(这些符号不要求是延续的逆转用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=61.衔接：设x和y是符号串，

3、它们的衔接 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,. 设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 如

4、：L=AZ,az D=09 1LD=AZ,az ,09 2LD是由一切用一个字母后跟一个数字 组成的符号串所构成的集合。 3L4是由一切的四个字母的符号串构的集合。 4LLD)* 是由一切的字母打头的字母和数字组成的符号串所构成的集合. 5D+是由一切的长度大于等于1的数字串所构成的集合.分析：The grey wolf will eat the goat谓语主语冠词描画词名词动词直接宾语助动词句子动原冠词名词The grey wolf will eat the goat 为了进展机械分析， ：“句子由主语后跟随谓语组成表示为： 句子 主语 谓语 1 主语 冠词 描画词 名词 2 冠词the

5、描画词 grey 谓语 动词 直接宾语 5 动词 助动词 动词原形 6 助动词will 动词原形 eat 直接宾语 冠词 名词 9 名词wolf 名词 goat ：终结符号集，非终结符号集，语法规那么，开场符号。终结符号集VT=the，grey, wolf,will, eat, goat非终结符号集VN=句子，主语， 谓语， 冠词， 描画词， 名词 ， 动词 ， 直接宾语 ， 助动词 ，动词原形 语法规那么集P=句子 主语谓语， 开场符号S= 句子句子主语 谓语 冠词 描画词 名词 谓语 the 描画词 名词 谓语 the grey名词 谓语 the grey wolf 谓语 the grey

6、 wolf 动词 直接宾语 . the grey wolf will eat the goat句子 the grey wolf will eat the goat the grey wolf will eat the wolf the grey goat will eat the wolf the grey goat will eat the grey合符语法且合符语义的句子仅是： the grey wolf will eat the goat+ 分析：The grey wolf will eat the goat句子主语谓语冠词描画词名词动词 直接宾语助动词动原冠词名词goat theeat

7、willThe greywolf分析：The grey wolf will eat the goat句子主语谓语冠词描画词名词动词 直接宾语助动词动原冠词名词goat theeatwillThe greywolf 一个上下文无关文法 G= VT，VN S, P ，其中： VT是一个非空有穷终结符号集合； VN是一个非空有穷的非终结符号集合， 且VTVN； S VN ，称为开场符号。 P是一个产生式的非空有穷集合，每个产 生式的方式是A(或A :)，其中 AVN，VTVN*。开场符号S至必需在某个产生式的左部出现一次 。 缩写方式： A 1|2G=(a,+,*,(,),， ， ，P ) P： *

8、 ) a E E+T T T T*F F F ( E ) a (2.1)令G=(VT,VN,S,P), 假设AP,且,(VTVN)*,那么称A直接推出,表示成 A A直接推出 直接归约到A 假设存在一个直接推导序列： 012 nn0 表示成 0 n 0 n 或者0=n或者0 n+*A产生式EE+TEE+TE+TT+TET+TT+TF+TTF+TF+Ta+TFa+Ta+Ta+FTFa+a+Fa+aFaa+设文法 GVT，VN，S,P。假设S ,那么称是一个句型。仅含终结符号的句型是一个句子。言语 L(G是由文法G产生的一切句子所组成的集合： L(G)|S 且VT*例2.3 思索一个文法 G(a,

9、b,S,S，P其中P：SaSb ab SaSb aaSbb a3Sb3 an-1Sbn-1 anbn*+ 设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的终极行,那么上述结论显然成立。* 设(1),(2)和(3)对于长

10、度不超越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的证明留给同窗们。* : 对于w和G,wL(G) 能否存在S w，如何构造例如，GE例2.2和w=a+a aEE+T T+

11、T F+T a+T a+TF a+F F a+a F a+aa 最左特点：A (A) ， VT*EE+T E+T F E+ T a E+FaE+aa T+aa F+aa a+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

12、句柄:a1+*+ 设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是叶子，且 是它父亲独一的儿子。例2.5 G=(VT,VN,S,P), 其中P: SaASa A SbA SS ba3124657891011SaASSbAaaba 根据推导序列，对每步推导画相应分枝ASaSbSAaaba

13、aSbAS aabAS aabbaS aabbaa aAS S 根据归约序列，对每步归约画相应分枝ASaSbSAaaba aAa aSbAa aSbbaa aabbaa aAS S1. 一个句型推导或分析用一棵树构造图示 出来，它反响了一个句子语法构造的层次。2. 对于一个句子的多种推导假设文法是无二义性的，采用各种推导过程，画出的分析树是一样的。分析树并未描画推导过程。3. 在书中，用画分析树的过程解释语法分析过程，用分析树图解语法构造。 分析树是推导的图形表示。一棵分析树中一个特有的结点连同它的全部后裔，衔接这些后裔的边以及这些结点的标志。例如：SAbSaSbaAaa短语：一棵子树的一切叶

14、子自左至右陈列起来构成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的一切叶子自左至右陈列起来所构成的符号串。句柄：一个句型的分析树中最左那棵只需父子两代的子树的一切叶子的自左至右陈列。例如，对表达式文法GE和句子a1+a2*a3，挑选出推导过程中产生的句型中的短语，直接短语，句柄。EE+TT+TF+T a1+T a1+T*F a1+F * F a1+a2 *FE+T T,T+T F,F+T a1, a1+T a1, T*F, a1+T*Fa1, F,F*F, a1+F*F a1, a2,a1+ a2 *F, a2 *F a1, a2, a3, a2 * a3 a1+ a2 *a

15、3EE+TTFa1T*FFa2a3a1+a2 *a3短语 EE+TE+T*FE+T*a3E+F* a3E+a2 * a3 T+a2 * a3 F+a2 * a3 EE+TTFa1T*FFa2a3a1+a2 *a3描画一个句子的文法不是独一的； 2. 对于一个句子的分析应是独一的。思索表达式下面的文法 GE,其产生式如下： EE+EE*E (E) a 对于句子a+a*a, 有如下两个最左推导： EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a EE+E a+E a+E*E a+a*E a+a*a E E*EE+E*E a+E*Ea+

16、a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推导 EE+E E+E*E E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*aEE+EE*EaaaEE*E+EEaaa最右推导假设一个文法的句子存在两棵分析树,那磨,该句子是二义性的。假设一个文法包含二义性的句子,那么称这个文法是二义性的; 否那么，该文法是无二义性的。几点阐明：1 . 普通来说，程序文语存在无二义性文法， 对于表达式来说，文法2 .1是无二义性的。对于条件语句，经常运用二义性文法描画它：S if expr then S if expr then S else S other二义性

17、的句子: if e1 then if e2 then s1 else s2 下面是 Smathed_s unmathed_s mathed_s if expr then mathed_s else mathed_s otherunmathed_s if expr then S if expr then mathed_s else unmathed_s 它显然比较复杂，因此：2. 在能驾驭的情况下，运用二义性文法。3. 对于恣意一个上下文无关文法，不存在 一个算法，断定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。4. 存在先天二义性言语。例如， aibicji,j1

18、 aibjcji,j1存在一个二义性的句子akbkck。紧缩过的文法化简了的文法： 1方式的产生式： AA P ； 2. 每个非终结符号A必需都有用途。即， S A 且 A ，VT* *+ 逐渐对产生式施加限制 四种类型： 0型，1型，2型，3型0型：G=(VT,VN,S,P) 规那么方式 ： , (VTVN)*, 推导：1型上下文有关 ： 规那么方式 ： A A VN, ,. (VTVN)*, 2型上下文无关：规那么方式 ： A A VN， (VTVN)* 3型右线性： A aB A a 左线性 A Ba A a a VT在我们运用的程序文语中在我们运用的程序文语中,有些言语构造并有些言语构

19、造并不是总能用上下文无关文法描画的。不是总能用上下文无关文法描画的。例例2.9L1=wcw|wa,b+。例如。例如,aabcaab就是就是L1的一个句子。这个言语是检查程序中的一个句子。这个言语是检查程序中标识符的声明应先于援用的笼统标识符的声明应先于援用的笼统。例例2.10L2=anbmcndm|n,m0，它是检查，它是检查过程声明的形参个数和过程援用的参数个数过程声明的形参个数和过程援用的参数个数一致问题的笼统。一致问题的笼统。 言语中过程定义和援用的语法并不涉及到参数个数，例如，Pascal的过程语句可描画为 s-callid(r-list) r-listr-list, r |r 实参和形参个数的一致性检查也是放在语义分析阶段完成的。 定义2.7