大连理工大学编译原理习题课.ppt

单击此处编辑母版标题样式,单击此处编辑文本,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,大连理工大学编译原理习题课,大连理工大学编译原理习题课大连理工大学编译原理习题课LL文法套路总结1.计算FIRST集合第一个终结符，或者,2.计算FOLLOW集合三个要点，0.开场记号的FOLLOW包含$；1.句型中非终结符后面有内容；2.产生式右部末尾非终结符，把左侧非终结符FOLLOW参加。一遍可能算不完，不重不漏，注意推出的情况,3.如果问是否是LL文法，用两条规那么判断 A|有FIRST()FIRST()=；假设*，那么FIRST()FOLLOW(A)=,4.如果要画非递归分析表3个要点，0.每行对应一个非终结符，每列对应一个终结符；1.对于A 的FIRST集合，把产生式写在行列(FIRST()穿插处；2.如果在FIRST()，把A 写在行列(FOLLOW(A)穿插处,LL文法套路总结,1.计算FIRST集合第一个终结符，或者,2.计算FOLLOW集合三个要点，0.开场记号的FOLLOW包含$；1.句型中非终结符后面有内容；2.产生式右部末尾非终结符，把左侧非终结符FOLLOW参加。一遍可能算不完，不重不漏，注意推出的情况,3.如果问是否是LL文法，用两条规那么判断 A|有FIRST()FIRST()=；假设*，那么FIRST()FOLLOW(A)=,4.如果要画非递归分析表3个要点，0.每行对应一个非终结符，每列对应一个终结符；1.对于A 的FIRST集合，把产生式写在行列(FIRST()穿插处；2.如果在FIRST()，把A 写在行列(FOLLOW(A)穿插处,SLR文法套路总结,1.拓广文法,2.工程集标准族,1.新加开场记号前加点号初始状态的核心工程,2.算闭包点号落在非终结符前，抄非终结符产生式，加点号，重复算闭包，直到算不下去为止,3.对闭包里每个点号后的符号终结/非终结符均可，,尝试点号向右移动一位可能对应多个工程，得到新的核心工程。,对核心工程们算闭包，得到新状态判断是否和已有状态重复。从当前状态出发一条边，边上符号是点号移动跨过的符合，到达时新计算的状态,4.按层次计算状态，直到算不下去位置没有新的状态,SLR文法套路总结,画SLR分析表,每个状态一行上一页，每个终结符对应一列动作，每个非终结符对应一列转移,对每一条边，看边上的符号,如果是终结符，从i状态到j状态，在第i行终结符对应列写sj，移进到状态j,如果是非终结符，从状态i到状态j，在第i行非终结符列，写j，转移,在所有状态中找点号在末尾形如 A 的工程，如果有，在状态对应行，FOLLOW(A)对应列写rj，j是A的编号,S S在状态i中，第i行$列写acc,问是不是SLR文法，画分析表，无冲突，那么是；有那么不是,标准LR文法套路总结,1.拓广文法,2.工程集标准族,1.新加开场记号前加点号，后面参加搜索符$初始状态的核心工程,2.算闭包点号落在非终结符前AB,a，抄非终结符产生式，加点号，算前向搜索符FIRST(a)。重复算闭包，直到算不下去为止注意：可能出现点号终结符一样而搜索符不同观点工程，是不同的工程,3.对闭包里每个点号后的符号终结/非终结符均可，,尝试点号向右移动一位可能对应多个工程，得到新的核心工程。,对核心工程们算闭包，得到新状态判断是否和已有状态重复。从当前状态出发一条边，边上符号是点号移动跨过的符合，到达时新计算的状态,4.按层次计算状态，直到算不下去位置没有新的状态,LR文法套路总结,画LR分析表,每个状态一行上一页，每个终结符对应一列动作，每个非终结符对应一列转移,对每一条边，看边上的符号,如果是终结符，从i状态到j状态，在第i行终结符对应列写sj，移进到状态j,如果是非终结符，从状态i到状态j，在第i行非终结符列，写j，转移,在所有状态中找点号在末尾形如 A ,a 的工程，如果有，在状态对应行，a对应列写rj，j是A的编号,S S在状态i中，第i行$列写acc,LALR文法套路总结,先按LR来做，得到DFA转换关系,忽略搜索符，找到所有工程能一一对应的状态,状态捏成一个合并，参加搜索符被合并状态中搜索符的并集,按LR的方法画分析表,S属性、L属性、自上而下、自下而上的关系,综合属性：产生式左部非终结符的属性，依赖右部符号的属性或左部其他属性,继承属性：产生式右部非终结符属性，依赖其他符号的属性,S属性就是综合属性,L属性=S属性+依赖左侧记号属性的继承属性,综合属性,依赖左侧记号属性的继承属性,自上而下（LL文法）,函数返回值,函数参数,自下而上（LR文法）,归约时执行语义动作（栈代码）,引入推出空串的标记非终结符，插入在有继承属性的记号之前，把属性计算放在空串规约为标记非终结符的位置（栈代码）,右部中左侧符合的属性或左部的继承属性,设计语法制导定义和翻译方案,两者区别：是否要求执行时机,重点：判断要使用继承属性还是综合属性,可以从文法出发，随意做一个/多个推导，得到一个分析树,判断要计算的值是,从下往上传递综合属性,从上往下或从左往右传递继承属性,语法分析,1.,考虑文法,S-(L)|a,L-L,S|S,(a)建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树,(b)为(a)的两个句子构造最左推导,(c)为(a)的两个句子构造最右推导,(d)这个文法产生的语言是什么,语法分析,a分析树：,(a,(a,a)：,(a,(a,a),(a,a)：,语法分析,b(a,(a,a)和(a,(a,a),(a,a)最左推导,语法分析,c(a,(a,a)和(a,(a,a),(a,a)最右推导,语法分析,d描述的语言：,括号匹配的串，串中的各项由,隔开，项可以是括号匹配的子串或a,语法分析,S-aSbS|bSaS|,(a)为句子abab构造两个不同的最左推导，以说明此文法二义,(b)为abab构造对应的最右推导,(c)为abab构造对应的分析树,(d)这个文法产生的语言是什么,语法分析,a最左推导,S=aSbS=abSaSbS=abaSbS=ababS=abab 或 S=aSbS=abS=abaSbS=ababS=abab,b最右推导,S=aSbS=aSb=abSaSb=abSab=abab,c分析树,d语言,描述的语言是a,b数目相等的串,语法分析,3.,证明下面文法是,LL(1),的但不是,SLR(1),文法,.,S,A a A b|B b B a,A ,B ,First(AaAb)=a,First(BbBa)=b,First(AaAb),First(BbBa)=,文法是,LL(1),的,.,构造SLR(1)工程集:,I0:S .S,S .AaAb,S .BbBa,A .,B .,Follow(A)=Follow(B)=a,b,存在归约-归约冲突,该文法不是SLR(1)文法.,证明如下：,语法分析,4.试说明没有一个左递归文法可以是LL(1)的。,(1)直接左递归文法中存在产生式:,A A1|A2|.|Am|1|2|.|n,其中 1 2.n均不以A开头,First(Ai)First(j)=First(j),假设 j*,First(A i)Follow(A)=First(i),不是LL(1)文法.,(2)间接左递归文法中存在产生式集合:,A B1 1|1|2|.|n,B1 B2 2,.,Bm A,First(B1 1)=First(A m.1),First(j)First(B1 1),j=1,.,n,First(j)First(B1 1),j=1,.,n,假设 j*,First(B1 1)Follow(A)=First(m.1),不是LL(1)文法.,语法分析,5.,证明下面文法是,SLR(1),文法,并构造其,SLR,分析表,.,E,E+T (1),F,F*(5),E,T (2),F,a (6),T,T F (3),F,b (7),T,F (4),I,0,:,E,.E,E,.E+T,E .T,T .TF,T .F,F .F*,F .a,F .b,I,1,:,E,E,.,E,E.+T,I,2,:,E,T.,T,T.F,F .F*,F .a,F .b,I,3,:,T F.,F F.*,I,4,:,F,a.,I,5,:,F,b.,I,6,:,E,E+.T,T .TF,T .F,F .F*,F .a,F .b,I,7,:,T,TF.,F F.*,I,8,:,F F*.,I,9,:,E,E+T.,T T.F,F .F*,F .a,F .b,Follow(E)=+,$,Follow(T)=+,$,a,b,Follow(F)=+,$,*,a,b,action goto,+*a b$E T F,0 s4 s5 1 2 3,1 s6,acc,2 r2 s4 s5 r2 7,3 r4 s8 r4 r4 r4,4 r6 r6 r6 r6 r6,5 r7 r7 r7 r7 r7,6 s4 s5 9 3,7 r3 s8 r3 r3 r3,8 r5 r5 r5 r5 r5,9 r1 s4 s5 r1 7,语法制导的翻译,6.,对于输入的表达式,5*(4*3+2),根据语法制导定义建立一棵带注释的分析树,.,L,n,E,.val=70,T,.val=70,F,.val=5 *,T,.val=14,digit.lexval=5,F,.val=14,(E.val=14 ),E,.val=12 +,T,.val=2,T,.val=12,F,.val=2,T,.val=4 *,F,.val=3 digit.lexval=2,F,.val=4 digit.lexval=3,digit.lexval=4,（,lex,表示是从词法分析来的,）,语法制导的翻译,7.S,L.L|L,L L B|B,B 0|1,(a),试用各有关综合属性决定,S.val.,引入,L,的属性,b,记录,2,的,L,的位数次幂值,S,L,1,.L,2,S.val=L,1,.val+L,2,.val/L,2,.b;,S,L ;,L L,1,B ,L.val=L1.val*2+B.val;L.b=L.b*2;,L B ,L.val=B.val;L.b=2;,B 0 ,B.val=0;,B 1,B.val=1;,语法制导的翻译,语法制导的翻译,(b),试用一个语法制导定义来决定,S.val,在这个定义中,B,仅有综合属性,c,给出由,B,生成的位对于最后 的数值的分担额,.,引入,B,的继承属性,i,综合属性,c,S,L,1,.L,2,L,1,.i=2,0,;L,2,.i=2,-1,;,S.val=L,1,.val+L,2,.val,S,L ,L.i=2,0,;,L L,1,B ,if L.i=2,0,then begin,L,1,end,else begin,L,1,.i=L.i;L.s=L,1,.s/2;B.i=L,1,.s,end,L.val=L,1,.val+B.c,L B ,B 0 ,B.c=B.i*0,B 1,B.c=B.i*1,语法制导的翻译,语法制导的翻译,8.假设说明是由以下文法产生的:,D L id,L ,id L1|:T,T integer|real,(a)建立一个翻译模式,把每一个标识符的类型参加到符号表中.,(b)从(a)中的翻译模式构造一个与翻译程序.,(a)D,Lid addtype(id.entry,L.type,L ,id L,1,L.type=L,1,.type,addtype(id.entry,L.type,L :,T L.type=T.type,T integer T.type=0,T real T.type=1,用整数,0,表示整型,1,表示实型,.,语法制导的翻译,D,L id,L ,id L,1,|,:,T,T integer|real,(b),从,(a),中的翻译模式构造一个与翻译程序,.,procedure D;,var Ltype:integer;,begin,match(id);Ltype:=L();,addtype(id.entry,Ltype),end;,function L():integer;,var Ltype:integer;,begin,if lookahead=,then,begin,match(,);match(id);,Ltype:=L();,end,else if lookahead=:then,begin,match(:);Ltype:=T();,end;,return Ltype,end;,funtion T():integer;,begin,if lookahead=integer then,begin,match(integer);,return 0,end,else if lookahead=real then,begin,match(real);,return 1,end,end,语法制导的翻译,9.E E+T|T,T num.num|num,(a)给出一个语法制导定义以确定每个子表达式的类型.,(b)扩大(a)中的语法制导定义把表达式翻译成前缀形式,并且决定类型.,(a)E,E,1,+T if (E,1,.type=real or T.type=real then E.type=real,else E.type=integer,E,T E.type=T.type;,T,num,.,num,T.type=real;,T,num,T.type=integer;,语法制导的翻译,9.E E+T|T,T num.num|num,(b)扩大(a)中的语法制导定义把表达式翻译成前缀形式,并且决定类型.,(b)S,E S.type=E.type;S.code=E.code;,E,E,1,+T if (E,1,.t ype=real and T.type=integer)then,begin E.type=real;,E.code=+|E,1,.code|inttoreal(T.code),end,else if (E,1,.t ype=integer and T.type=real)then,begin E.type=real;,E.code=+|inttoreal(E,1,end,else begin E.type=E,1,.t ype;,E.code=+|E,1,end,语法制导的翻译,E,T E.type=T.type;E.code,=,T.code,T,num,.,num,T.type=real;T.code=(num.num).lexval,T,num,T.type=integer;T.code=num.lexval,E,T E.type=T.type;E.code,=,T.code,T,num,.,num,T.type=real;T.code=(num.num).lexval,T,num,T.type=integer;T.code=num.lexval,1.S属性定义是指只包含_属性的语法制导定义。,2.L属性定义是指包含了综合属性和那些_的继承属性。,3.语法制导定义的自上而下分析是将非终结符映射为分析过程，而继承属性映射为分析过程的_，综合属性映射为分析过程的_。,4.翻译方案是将语义规那么插入到产生式_的某个位置，反映出该语义规那么的执行时间。,5如果文法G是无二义的，那么它的任何句子，满足,a.最左推导和最右推导对应的语法树必定一样 b.最左推导和最右推导对应的语法树可能不同,c.最左推导和最右推导必定一样 d.可能存在两个不同的最左推导，但它们对应的语法树一样,6.文法G：SxSx|y所识别的语言是：,xyxb.(xyx)*c.xnyxn(n0)d.x*yx*,7.给定文法：,SaSb,SbAc,AaSA,Ac,写出翻译方案，打印出句子中共有多少个c。,课 堂 练 习,1.S属性定义是指只包含_综合_属性的语法制导定义。,2.L属性定义是指包含了综合属性和那些_只依赖于左边兄弟节点和父节点的继承属性。,3.语法制导定义的自上而下分析是将非终结符映射为分析过程，而继承属性映射为分析过程的_参数_，综合属性映射为分析过程的_返回值_。,4.翻译方案是将语义规那么插入到产生式_右部_的某个位置，反映出该语义规那么的执行时间。,5如果文法G是无二义的，那么它的任何句子，满足 a,a.最左推导和最右推导对应的语法树必定一样 b.最左推导和最右推导对应的语法树可能不同,c.最左推导和最右推导必定一样 d.可能存在两个不同的最左推导，但它们对应的语法树一样,6.文法G：SxSx|y所识别的语言是：c,xyxb.(xyx)*c.xnyxn(n0)d.x*yx*,7.给定文法：,SaSb,SbAc,AaSA,Ac,写出翻译方案，打印出句子中共有多少个c。,课 堂 练 习答案,注意：要增加一个新的开场符号！,SS print(S.num);,SaS1b S.num=S1.num;,SbAc S.num=A.num+1;,AaSA1 A.num=S.num+A1.num;,Ac A.num=1;,一、选择题:,程序所需的数据空间载程序运行前就可以确定，成为()管理技术。,动态存储 B.栈式存储 C.静态存储 D.堆式存储,2.堆式动态分配申请和释放空间遵循()原那么。,先申请先释放 B.先申请后释放 C.后申请先释放 D.任意,3.静态分配允许程序出现(),递归过程 B.可变大小的构造 C.静态变量 D.待定性质的名字,二、简答题,考虑以下c程序：,main(),char*cp1,*cp2;,cp1=“12345;,cp2=“abcdefghij;,strcpy(cp1,cp2);,printf(“cp1=%sn cp2=%sn,cp1,cp2);,该程序的输出是：cp1=abcdefghij,cp2=ghij,问：为什么cp2所指的串被修改了？,课堂练习,运行时环境,2.对于以下程序：,Program main();,procedure P(x,y,z);,Begin,y:=y+1;,z:=z+x;,End,Begin,a:=2;,b:=3;,P(a+b,a,a);,Print a;,End.,假设参数采用以下方式，结果分别是什么：,值调用,引用调用,换名调用,一、选择题:,程序所需的数据空间载程序运行前就可以确定，成为(C)管理技术。,动态存储 B.栈式存储 C.静态存储 D.堆式存储,2.堆式动态分配申请和释放空间遵循(D )原那么。,先申请先释放 B.先申请后释放 C.后申请先释放 D.任意,3.静态分配允许程序出现(C),递归过程 B.可变大小的构造 C.静态变量 D.待定性质的名字,二、简答题,考虑以下c程序：,main(),char*cp1,*cp2;,cp1=“12345;,cp2=“abcdefghij;,strcpy(cp1,cp2);,printf(“cp1=%sn cp2=%sn,cp1,cp2);,该程序的输出是：cp1=abcdefghij,cp2=ghij,问：为什么cp2所指的串被修改了？,2.对于以下程序：,Program main();,procedure P(x,y,z);,Begin,y:=y+1;,z:=z+x;,End,Begin,a:=2;,b:=3;,P(a+b,a,a);,Print a;,End.,假设参数采用以下方式，结果分别是什么：,值调用 2,引用调用 8,换名调用 9,谢谢欣赏！,2021/11/5,37,