编译原理第2章编译基础.ppt

1,第二章 编译基础,2,2.0 概 述,对程序设计语言的描述是从语法、语义和语用三个因素来考虑。,语法是对语言结构的定义。,语用则是从使用的角度去描述语言。,语义是描述了语言的含义。,3,2.0 概 述,例如 赋值语句s2*3.1416*r 的非形式化的描述为：,语法：赋值语句由一个变量，后随一个赋值号“”，再在其后面跟一个表达式构成。,语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。,语用：赋值语句可用来计算和保存表达式的值。 这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。,4,形式化方法：是用一整套带有严格规定的 符号体系来描述问题的方法。,2.1 符号表,一 符号串与字母表 1字母表：元素的非空有穷集合。两含义：字母表中至少包含一个元素。字母表中元素可以是字母、数字或其它符号。 例如：= a , b , c ,5,2. 符号（字符）：字母表中元素。 3. 符号串：用字母表中的符号组成的任何有穷序列，也称字。 例如：a , ab , bba , acab , 注意： 符号串中符号的顺序是很重要的。 不包含任何符号的符号串称空串，记为。 |=0 一个字母表上全部符号的集合是无穷的。,6,4. 符号串的前缀、后缀以及子串： 设x是一符号串，例如：x=abc 符号串的前缀：从x的尾部删除若干个（=0）符号后所余下的部分。例如：，a，ab，abc 符号串的后缀：从x的头部删除若干个（=0）符号后所余下的部分。例如：，c，bc，abc 子串：从x中删除前缀和后缀之后所余下的部分。 例如：，a，b，ab，bc，abc,7,二. 符号串的运算 1符号串的连接：设x，y是符号串，则串xy称为它们的连接。 例如：设x=my y=computer xy=mycomputer yx=computermy 注意：对任意x X=X=X 2集合的和与乘积：设A，B是符号串的集合，则： AB=|A或B AB= xy|xA且yB 例如：设 A=a,b B=c,d 则： AB=a,b,c,d AB=ac,ad,bc,bd 注意：A=A=A A=A= A=A=A = ,8,3. 符号串的幂运算：若x是符号串，则 x0=, x1=x, x2=xx, 例如：设 x=abc 则： x0=, x1=abc, x2=abcabc, 4. 集合的幂运算：若A是符号串的集合，则 A0=, A1=A, A2=AA, 例如：设 A=a,b 则： A0=, A1=a,b, A2=aa,ab,ba,bb, 5. 集合的A(正闭包)和A*（自反传递闭包）: 设A为任一集合，则： A= A1A2A3 An （A上所有符号串所组成的集合） A*=A0 A= A 例如：设A=a,b,c A=a,b,c,aa,ab,ac,ba,bb,bc, A*=, a,b,c,aa,ab,ac,ba,bb,bc, ,9,2.2 文法和语言的形式定义,一形式语言：是一字母表上按某种规则构成的所有符号串的集合。反之，任一字母表上符号串的集合均可定义为一个形式语言。 二形式语言的描述：（三种方法） 1当语言为有穷集合时，用枚举法。,例如：设有字母表 A=a,b,c 则：L1=a,b L2=a,aa,ab,ac L3=c,cc,10,2用文法描述语言 例如：设有字母表 =0，1 + =0，1，00，01，11，10，000，100， 用A表示+ ，A0 （定义为，生成，导出） 用产生式表示+： A0 A1 AA0 AA1 3用自动机识别语言：构造一种装置来识别语言，它可以判断某符号串是否是该语言的句子。 例如： 1100 是（接收） 11ab 不是（不接收）,自动机,11,三 文法的形式定义,1 规则（产生式）：是一个符号与一个符号串的有序对（A，），通常写作：A或 A= 2非终结符与终结符： 非终结符：出现在规则左部能派生出符号或符号串的那些符号。通常用大写字母表示。 终结符：是组成语言不可再分的基本符号，通常用小写字母表示。,12,3文法的形式定义：是规则的非空有穷集合，通常定义为四元组： GS=（Vn，Vt，P，S） 其中： Vn：规则中非终结符的集合。 Vn=A Vt：规则中终结符的集合。 Vt=0，1 P： 文法规则式的集合。 P: A0 A1 AA0 AA1 S： 文法的开始符号（识别符号） 由它开始识别我们所定义的语言。S=A 例1 例2 例3 例4 例5 继续,13,例1设有字母表 =a，b，请为语言 L=a2n, b2n | n=1 设计一个文法。 首先分析语言中串的结构特征：L=aa,bb,aaaa,bbbb, （偶数个a或偶数个b组成） GS =（Vn，Vt，P，S） 其中： Vn=A, B, D Vt=a，b P: Aaa|aaB|bb|bbD Baa|aaB Dbb|bbD S=A 易错：Aaa|aaA|bb|bbA 会出现句子 aabb 扩大了语言范围,14,问题：描述是否唯一？（回答不唯一） P1: AB|D Baa|aaB Dbb|bbD 等价文法： P2: AB|D Baa|aBa Dbb|bDb 返回,15,例2已知语言 L=w|w是0和1的个数都为偶数的0，1串。 分析句子结构特征：001100 110000 0101 S0A|1B (A,B奇数个0,1) A0 B1 推出无穷串：A0S B1S 产生0101串：C0B|1A A1C B0C 文法：GL=（A, B, C, S, 0, 1 , P，S） P: S0A|1B A0S|1C|0 B1S|0C|1 C0B|1A 返回,16,例3. 试给出不以0开头的正奇数文法（作业P36.7) 分析：奇数集合1，3，5，7，9，11， 易错： A1|2*A+1 P: Sd1A|d3 Ad2A|d3 d11|2|3|4|5|6|7|8|9 d20|1|2|3|4|5|6|7|8|9 d31|3|5|7|9 返回,17,例4. 用文法定义一个含+，*的算术表达式，定义用自然语言（非形式化） 描述： 变量是一个算术表达式 若E1和E2是算术表达式，则E1+E2 , E1*E2 , (E1) 也是算术表达式。 分析：符号串的集合i , i+i , i*i , (i) , i+i*i , GE=(E , i , + , * , ( , ) , P , E ） P : Ei EE+E EE*E 返回 E(E) 说明：并不是做加法和乘法运算，仅描述哪些符号串是该文法的句子（算术表达式），如 ii+i , i*i+ 都不是该文法的句子。,18,例5 . 设计一个表示所有标识符的文法。 （标识符的定义：以字母开头的字母数字串） I标识符 L字母 D数字 P : IL | I L| I D La|b|c|x|y|z D 0|1|2|3|4|5|6|7|8|9 比较： P1: IL | I D (以字母开头的数字串，缩小了语言范围） P2: IL | I L| I D | D (有可能以数字开头，扩大了语言范围） P3: IL | L I | D I (有可能以数字开头，扩大了语言范围）,19,四. 语言的形式定义,1. 直接推导：设x和y是符号串，若用一次规则式可以从x推导出y，则称y为x的直接推导，并记为 x = y 例如：设有文法GS : S0S1 | 01 S=01 S=0S1 0S1=0011 注意：推导和规则的区别 形式上不一样 = 推导的依据是规则 有A 才有 A= ,20,2. 推导（+推导）：设x和y是符号串，如果使用若干次（=1次）规则式可以从x推导出y，则称y为x的推导，并记为 x = y 。 例如：设有文法： GS : S0S1 | 01 则： S=01 S=0S1 S=0S1 =00S11=000111 S=000111 3.广义推导（*推导）：设x和y是符号串，如果使用若干次（=0次）规则式可以从x推导出y，则称y为x的广义推导，并记为 x = y 。 x=y 等价于 x=y 或 x=y,+,+,*,*,+,21,4. 句型句子：设有文法GS，能从文法开始符号S推导出来的符号串称为G的一个句型。 A= ， （VNVT）* 仅由终结符号组成的句型称为句子。 S=01（句子） S=0S1（句型） S=000111 （句子） 例如：已知文法GE:E E+E| E*E | (E) | i ,试证明符号串(i*i+i) 是该文法的一个句子。 分析：只要证明符号串对文法G存在一个推导。 解: E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i) E= (i*i+i) (i*i+i)是文法G的一个句子。,*,*,*,*,22,5. 语言的定义：文法G全体句子所组成的集合。 L(GS)= w | S=w 且 wVt* 定义式意义如下： w是从文法开始符号推导出来的 w仅由终结符号组成，称为该语言的句子 L(G)是由所有这样的句子组成的 语言L(G)是Vt*的子集，但反过来不一定成立 对一给定的文法，可以唯一地确定语言；反过来，给定一语言，可以由不同的文法来描述。,+,23,例1：文法： GS : S0S1 | 01 所描述的语言是什么？ 分析：从文法开始符号出发，将推导出什么样的句子，找出句子的规律，用式子或自然语言描述出来。 解：S=0S1 =00S11 = = 0n-1 S 1n-1= 0n 1n L(GS)=0n 1n |n1 即: L=01 , 0011 , 000111 , 注意：V*T=, 0 , 1 , 00 , 01 , (L是V*T 的子集） 比较：文法 S0S | 1S | 所描述的语言是什么？ L(GS)=, 0 , 1 , 00 , 01 , = x | x 0 , 1* ,24,例2：已知文法GS，求该文法所描述的语言？ GS： S AB A aAb | ab B cBd | cd 解： S = AB =aAbB = a2Ab2B = = an-1Abn-1B = anbnB = anbn cBd = anbn c2Bd2 = = anbn cm-1Bdm-1 = anbn cmdm S = anbn cmdm L(GS)= anbn cmdm | n ,m 1,+,25,例3：已知文法GS，求该文法所描述的语言？ GS： S A | B A aAb | 0 B aBbb | 1 解： S = A =aAb = a2Ab2 = = anAbn = an 0 bn S = B = aBbb = a2B(bb)2 = = an B(bb)n = an 1b2n S = an 0 bn | an 1b2n L(GS)= an 0 bn , an 1b2n | n 0,26,五. 规范推导和规范归约,问题：对一个句子的推导过程是不是唯一的？ （回答是否定的。） 例如：文法GN1 : N1 N , N ND | D , D 0 | 1 | 2 ( 由0，1，2 组成的无符号正整数） 看22的推导过程： N1 = N =ND = N2 =D2 =22 (最右推导） N1 = N =ND = DD =2D =22 (最左推导） N1 = N =ND = DD =D2 =22 (左右推导） 同一句子可以通过不同的推导序列推出，为确定推导序列，只考虑两种特殊推导。,27,1. 最左（或最右）推导：在推导过程中任何一步，被替换的总是当前符号串中的最左（或最右）非终结符。最右推导也称规范推导，用规范推导推出的句型称规范句型。 例如：已知文法GS，给出句子babaab的最左，最右推导。 GS: S AB A Aa | bB B a | Sb 最右推导: S = AB = ASb =AABb =AAab = AbBab = Abaab = bBbaab = babaab 最左推导: S = AB = bBB =baB =baSb = baABb = babBBb = babaBb = babaab,28,2. 归约：句型中某子串用一个非终结符来替换的过程。 对规则式： A 则 xAy =xy 是推导 xy = xAy 是归约 例1：22 = D2 = N2 = ND = N = N1 (最右推导的逆过程最左归约规范归约） 例2：设有文法：GS: S a | | (T) T T,S |S 请给出符号串 （a,(a,a) 的规范归约。 （a,(a,a) =（S,(a,a) = （T,(a,a) = （T,(S,a) = （T,(T,a) =（T,(T,S) = （T,(T) = （T,S) = (T) = S,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,29,六. 递归性,1.规则递归:若文法中有规则式：A A ，称规则左递归。 若文法中有规则式：A A ，称规则右递归。 若文法中有规则式：A A ，称规则递归。 2.文法递归：若有推导 A =A , 称文法左递归。 若有推导 A =A , 称文法右递归。 若有推导 A =A , 称文法递归。 举例：文法GN1 : N1 N , N ND | D , D 0 | 1 | 2 ( 由0，1，2 组成的无符号正整数） N ND 规则左递归，文法左递归 （正因为递归，使得有限的文法规则式能刻画一个无穷的语言） 文法GU : U Vx , V Uy |a 无规则左递归，但文法左递归 U=Vx=Uyx 即U=Uyx,+,+,+,+,30,2.3 句型的分析,句型的分析：构造一种算法，用以判断所给的符号串是否为该文法的句型（或句子）。 两种方法： 自顶向下分析法： 从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。 自底向上分析法：从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串中的相应子串，逐步归约成文法开始符号的一种方法。,31,一、短语与句柄,1 短语：设有文法GS，w=是它的一个句型，如果有S= A，且A=，则称是句型w相对于非终结符A的短语。 2 直接短语：设有文法GS，w=是它的一个句型，如果有S= A，且A=，则称是句型w相对于非终结符A的直接短语。 3 句柄：最左边的直接短语是句柄。 特征： 它是直接短语（某个产生式的右部） 具有最左性,*,*,+,32,例：设有文法： SAB AAa | bB Ba | Sb 求句型baSb的全部短语，直接短语和句柄。 解：首先建立句型baSb的推导过程 最左：S=AB=bBB=baB=baSb 最右：S=AB=ASb=bBSb=baSb S=S 且 S=baSb 句型本身是一个短语 S=baB 且 B=Sb Sb是句型baSb的直接短语 S=ASb 且 A=ba ba是句型baSb的短语 S=bBSb 且 B=a a是句型baSb的直接短语,*,*,*,*,+,+,33,二. 语法树,1 .语法树：对句型的推导过程给出一种图形表示。也称推导树。 例如：已知文法GE, 证明T/(E-T)*F+i是它的一个句型,并画出相应的语法树。 GE:E E+T|E-T|T T T*F | T/F | F F ( E) | i 证明： E =E+T=E+F=E+i (最右推导） =T+i =T*F+i =T/F*F+i =T/(E)*F+i =T/(E-T)*F+i,E E + T T * F F T / F i ( E ) E - T,34,子树：由某一结点及其分枝组成，是原树的一棵子树。 简单子树：只有单层分枝的子树。 说明：语法树的构造过程是从文法的开始符号 出发，构造一个推导过程。 每个句型都有一棵语法树 一棵语法树等价于一个最左推导,35,2. 语法树与短语： 每棵子树（某一结点及其分枝组成）的叶子形成的符号串组成一个短语。 每棵简单子树（单层分枝）的叶子形成的符号串组成一个直接短语。 最左边简单子树的叶子组成一个句柄。,36,例1：设有文法： GS: SaAcBe Ab AAb Bd 解：句型aAbcde的语法树为：,若有句型aAbcde，试问b是它的直接短语吗？它的短语是什么？句柄是什么？,S a A c B e A b d,显然，b不是句型的直接短语。该句型的短语有： aAbcde Ab d 句柄是：Ab,37,例2：设有文法GS: Sa | | (T) TT , S | S 请给出句子(a , ( a , a ) )的最右推导以及最左归约每一步的句柄。 解： S=(T) 句柄为(T) =(T,S) 句柄为T,S =(T,(T) 句柄为(T) =(T,(T,S) 句柄为T,S = (T,(T,a) 句柄为a = (T,(S,a) 句柄为S = (T,(a,a) 句柄为a = (S,(a,a) 句柄为S = (a,(a,a) 句柄为a,S ( T ) T , S S ( T ) a T , S S a a,38,例3：设有文法GE: EE+T | E-T | T TT*F | T/F | F F(E) | i 求句型(F+i)-T*(E-T)的短语，直接短语和句柄。 解：,E E - T T T * F F ( E ) ( E ) E - T E + T T F F i,由语法树可知，短语有： F 直接短语，句柄 i 直接短语 F+i (F+i) E-T 直接短语 (E-T) T*(E-T) (F+i)-T*(E-T),39,三. 文法的二义性,若一个文法的某个句子对应两棵不同的语法树，或者有两个不同的最左（或最右）推导，则称这个文法是二义的。,40,例1：证明文法GE: E E+E | E*E | (E) | i是二义性文法。 证明：对句型(i*i+i)有两个最左推导 推导1： E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i) 推导2： E=(E)=(E*E)=(i*E)=(i*E+E)=(i*i+E)=(i*i+i) 该文法是二义性文法 改写文法：构造一个等价的无二义性文法 规定：*优先于+ 并且 +、*左结合（文法左递归-左结合） P: E E+E | T T T*F | F F ( E ) | i,E ( E ) E + E E*E i i i,E ( E ) E * E i E + E i i,41,例2. 条件语句：C if B then C | if B then C else C | S 证明该文法是二义性文法没。 证明：句子if B then if B then S else S 有两棵语法树,C If B then C if B then C else C S S,C if B then C else C if B then C S S,改写文法：规定：else与最近的then匹配 C C1 | C2 C1 if B then C1 else C1 | S C2 if B then C | if B then C1 else C2,42,例3：已知文法： GN: N SE | E S SD |D E 0 | 2 | 4 | 6 | 8 | 10 D 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 问题：证明该文法是二义的。 该文法所描述的语言是什么？ 构造一个无二义性文法G ，使L(G )=L(G) 解：句子10有两棵语法树（10结尾的都行） 语言为所有无符号偶数 改写文法： E 0 | 2 | 4 | 6 | 8,N S E D 0 1,N E 1 0,43,2.4 文法的化简和改造,一.无用符号和无用产生式的删除 1.无用符号和无用产生式：我们说文法G中的一个符号xV是有用的，是指x必须同时满足两个条件： 存在,V* 有S= x (x至少出现在某句型中） 存在 tVt* , 使 x=t (从x能推出终结符号串） 否则，x是无用符号，如果一个产生式含有无用符号，则该产生式称为无用产生式。 2.删除方法：（直观看） 删除P P形式的产生式 删除不能导出终结符号串的产生式 删除在推导中永远不使用的产生式,*,+,+,44,例如：化简下述文法，其中S是文法的开始符号。 S Be S Ec A Ae A e A A B Ce B Af C Cf D f G b 解： 根据原则，可消去 根据原则，可消去 根据原则，可消去 化简后文法为： S Be B Af A Ae A e,45,二.单产生式的消除,1.单产生式：右部仅含一个非终结符的产生式。 例如：A B (文法含单产生式，增加编译程序的时间和空间，要删除） 2.算法： 构造非终结符号集，对文法G中的每个非终结符A，求： A= B | A=B, BVN 若有A=B，且文法G中有B x , 则在文法中扩充规则： A x , 并且删除单产生式和无用产生式,+,+,46,例如：设有文法G1A: A B | dE B A | D |b D B | d E e |Ea 求：不含单产生式的文法G2 ，使得L(G1)=L(G2)。 解： A=A=dE A=B=b A=D=d A= A , B , D 同理：B=A=dE B=B=b B=D=d D=A=dE D=B=b D=D=d B= A , B , D D= A , B , D E= 扩充规则：A b |d , B dE | d , D dE | b 删除单产生式得文法G2A: A dE | b |d , B dE |b | d , D dE | b |d , E e | Ea 删除无用产生式：由于B, D均不在任何句型中出现，故删除 文法G2A: A dE | b |d E e | Ea,+,+,+,+,+,+,+,+,+,47,2.5 文法和语言的分类,一. 0型文法（PSG，短语文法，无限制文法）： 若文法G中任一产生式具有如下形式： V+， V* ，则称为0型文法。 0型文法所描述的语言称为0型语言或递归可枚举语言。0型语言可以用图灵机TM（Turing Maching)来识别。 例如：GS=( S, A, B, C, D, E , a , P , S ) P: S ACaB , Ca aaC , CB DB , CB E aD Da , AD AC , aE Ea , AE 以上文法是一个0型文法，所产生的语言为： L(G)=ai | i是2的正整数次方=aa , aaaa ,aaaaaaaa , 特点：没有对产生式作更多的限制，仅要求中至少含有一个非终结符。,48,二.1型文法（上下文有关文法） 简写CSG(Context Sensitive Grammar),若文法G中任一产生式具有如下形式：A U AVN , UV+， , V* ，则称为1型文法。 1型文法所描述的语言称为1型语言或上下文有关语言。1型语言可以用线性界限自动机LBA