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

《编译原理第2章编译基础.ppt》由会员分享，可在线阅读，更多相关《编译原理第2章编译基础.ppt（53页珍藏版）》请在装配图网上搜索。

1、1,第二章 编译基础,2,2.0 概 述,对程序设计语言的描述是从语法、语义和语用三个因素来考虑。,语法是对语言结构的定义。,语用则是从使用的角度去描述语言。,语义是描述了语言的含义。,3,2.0 概 述,例如 赋值语句s2*3.1416*r 的非形式化的描述为：,语法：赋值语句由一个变量，后随一个赋值号“”，再在其后面跟一个表达式构成。,语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。,语用：赋值语句可用来计算和保存表达式的值。 这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。,4,形式化方法：是用一整套带有严格规定的 符号体系来描述问

2、题的方法。,2.1 符号表,一 符号串与字母表 1字母表：元素的非空有穷集合。两含义：字母表中至少包含一个元素。字母表中元素可以是字母、数字或其它符号。 例如：= a , b , c ,5,2. 符号（字符）：字母表中元素。 3. 符号串：用字母表中的符号组成的任何有穷序列，也称字。 例如：a , ab , bba , acab , 注意： 符号串中符号的顺序是很重要的。 不包含任何符号的符号串称空串，记为。|=0 一个字母表上全部符号的集合是无穷的。,6,4. 符号串的前缀、后缀以及子串： 设x是一符号串，例如：x=abc 符号串的前缀：从x的尾部删除若干个（=0）符号后所余下的部分。例如：

3、，a，ab，abc 符号串的后缀：从x的头部删除若干个（=0）符号后所余下的部分。例如：，c，bc，abc 子串：从x中删除前缀和后缀之后所余下的部分。 例如：，a，b，ab，bc，abc,7,二. 符号串的运算 1符号串的连接：设x，y是符号串，则串xy称为它们的连接。 例如：设x=my y=computerxy=mycomputeryx=computermy 注意：对任意xX=X=X 2集合的和与乘积：设A，B是符号串的集合，则： AB=|A或B AB= xy|xA且yB 例如：设A=a,bB=c,d 则：AB=a,b,c,dAB=ac,ad,bc,bd 注意：A=A=AA=A=A=A=A

4、= ,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,

5、bb,bc, ,9,2.2 文法和语言的形式定义,一形式语言：是一字母表上按某种规则构成的所有符号串的集合。反之，任一字母表上符号串的集合均可定义为一个形式语言。 二形式语言的描述：（三种方法） 1当语言为有穷集合时，用枚举法。,例如：设有字母表 A=a,b,c 则：L1=a,bL2=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用自动机识别语言：构造一种装置来识别语言，它可以判断某符号串是否是该语言的句子

6、。 例如： 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： 文法的开始符号（识

7、别符号） 由它开始识别我们所定义的语言。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

8、 Baa|aBa Dbb|bDb 返回,15,例2已知语言 L=w|w是0和1的个数都为偶数的0，1串。 分析句子结构特征：0011001100000101 S0A|1B(A,B奇数个0,1) A0B1 推出无穷串：A0SB1S 产生0101串：C0B|1AA1C 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

9、|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+ 都不是该文法的句子。

10、,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 :

11、S0S1 | 01 S=01S=0S10S1=0011 注意：推导和规则的区别 形式上不一样 = 推导的依据是规则 有A 才有 A= ,20,2. 推导（+推导）：设x和y是符号串，如果使用若干次（=1次）规则式可以从x推导出y，则称y为x的推导，并记为x = y 。 例如：设有文法： GS : S0S1 | 01 则：S=01S=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.

12、句型句子：设有文法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 |

13、 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 ,

14、 注意：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 |

15、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，

16、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 =

17、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

18、,(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 (

19、由0，1，2 组成的无符号正整数） N ND 规则左递归，文法左递归 （正因为递归，使得有限的文法规则式能刻画一个无穷的语言） 文法GU : U Vx , V Uy |a 无规则左递归，但文法左递归 U=Vx=Uyx 即U=Uyx,+,+,+,+,30,2.3 句型的分析,句型的分析：构造一种算法，用以判断所给的符号串是否为该文法的句型（或句子）。 两种方法： 自顶向下分析法：从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。 自底向上分析法：从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串中的相应子串，逐步归约成文法开始符号的一种方法

20、。,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句

21、型本身是一个短语 S=baB 且 B=SbSb是句型baSb的直接短语 S=ASb 且 A=baba是句型baSb的短语 S=bBSb 且 B=aa是句型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 +

22、T T * F F T / F i ( E ) E - T,34,子树：由某一结点及其分枝组成，是原树的一棵子树。 简单子树：只有单层分枝的子树。 说明：语法树的构造过程是从文法的开始符号出发，构造一个推导过程。 每个句型都有一棵语法树 一棵语法树等价于一个最左推导,35,2. 语法树与短语： 每棵子树（某一结点及其分枝组成）的叶子形成的符号串组成一个短语。 每棵简单子树（单层分枝）的叶子形成的符号串组成一个直接短语。 最左边简单子树的叶子组成一个句柄。,36,例1：设有文法： GS:SaAcBe Ab AAb Bd 解：句型aAbcde的语法树为：,若有句型aAbcde，试问b是它的直接短语

23、吗？它的短语是什么？句柄是什么？,S a A c B e A b d,显然，b不是句型的直接短语。该句型的短语有： aAbcdeAbd 句柄是：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 (

24、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：证明文法G

25、E: 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. 条

26、件语句：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

27、|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至少出现在某句

28、型中） 存在 tVt* , 使 x=t (从x能推出终结符号串） 否则，x是无用符号，如果一个产生式含有无用符号，则该产生式称为无用产生式。 2.删除方法：（直观看） 删除P P形式的产生式 删除不能导出终结符号串的产生式 删除在推导中永远不使用的产生式,*,+,+,44,例如：化简下述文法，其中S是文法的开始符号。 S BeS EcA Ae A eA AB Ce B AfC CfD f G b 解：根据原则，可消去 根据原则，可消去 根据原则，可消去 化简后文法为： S Be B Af A Ae A e,45,二.单产生式的消除,1.单产生式：右部仅含一个非终结符的产生式。 例如：A B (

29、文法含单产生式，增加编译程序的时间和空间，要删除） 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=dEA=B=bA=D=d A= A , B , D 同理：B=A=dEB=B=bB=D=d D=A=dED=B=bD=D=d B= A , B , D D= A , B ,

30、 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 M

31、aching)来识别。 例如：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

32、型文法所描述的语言称为1型语言或上下文有关语言。1型语言可以用线性界限自动机LBA（Linear Bounded Automata)来识别。 例如：GS=( S, A, B, C, D , a, b, c , P , S ) P:S A ,A aABD ,A abD , DB CB CB CD , CD BD ,bB bb ,D c 以上文法是一个1型文法，所产生的语言为： L(G)=an bn cn | n1 当n=1时：S=A=abD=abc 当n=2时： S=aABD=a2 bDBD= a2 bCBD= a2 bCDD = a2 bBDD= a2 b2 DD= a2 b2 c2,49,三

33、.2型文法（上下文无关文法）简写CFG(Context Free Grammar),若文法G中任一产生式具有如下形式： A AVN , V* ，则称为2型文法。 2型文法所描述的语言称为2型语言，或者上下文无关语言。 2型语言可以用下推自动机PDA（Push Down Automata)来识别。 例如：GS=( S , a, b , P , S ) P: SaSb , Sab 以上文法是一个2型文法，所产生的语言为： L(G)=an bn | n1 通常，利用2型文法描述高级语言的句法部分，然后用PDA来识别。,50,四. 3型文法（正规文法）,若文法G中任一产生式具有如下形式： AaB ,

34、Aa右线性文法 ABa , Aa左线性文法 其中： A, BVN , a VT ， 3型文法所描述的语言称为正规语言，或者有限状态语言。 3型语言可以用有穷自动机FA（Finite Automata) 来识别。,51,例如，用左线性正规文法和右线性正规文法定义标识符,用I代表标识符; l代表任意一个字母; d代表任意一个数字; 则定义标识符的文法为：,左线性文法: P: I l | Il | Id,右线性文法: P: I l | lT Tl | d | lT| dT,52,例如，用左线性正规文法和右线性正规文法定义无符号整数,用N代表无符号整数; d代表任意一个数字；则定义的无符号整数文法为：,左线性文法: P: N Nd | d,右线性文法: P: N dN | d,53,由上述四类文法的定义可知, 从0型文法到3型文法, 是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法, 而由它们所定义的语言类是依次缩小的， 有 L0 L1 L2 L3 。,