资源描述:
《编译原理与技术练习题汇总》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
练习11.1为什么高级程序语言需要编译程序?1.2解释下列术语:源程序,目标程序,翻译程序,编译程序,解释程序1.3简单叙述编译程序的主要工作过程。1.4编译程序的典型体系结构包括哪些构件,主要关系如何,请用辅助图示意。1.5编译程序的开发有哪些途径?了解你熟悉的高级编程语言编译程序的开发方式。1.6运用编译技术的软件开发和维护工具有许多类,简单叙述每一类的主要用途。1.7了解一个真实编译系统的组成和基本功能。1.8简单说明学习编译程序的意义和作用。1.9如果机器H上有两个编译:一个把语言A翻译成语言B,另一个把B翻译成C,那么可以把第一个编译的输出作为第二个编译的输入,结果在同一类机器上得到从A到C的编译。请用T形图示意过程和结果。 练习22.1词法分析器的主要任务是什么?2.2下列各种语言的输入字母表是什么?(1)C(2)Pascal(3)Java(4)C#2.3可以把词法分析器写成一个独立运行的程序,也可以把它写成一个子程序,请比较各自的优劣。2.4用高级语言编写一个对C#或Java程序的预处理程序,它的作用是每次调用时都把下一个完整的句子送到扫描缓冲区,去掉注释和无用的空格、制表符、回车、换行。2.5用高级语言实现图2.5所示的Pascal语言数的状态转换图。2.6用高级语言编程实现图2.6所示的小语言的词法扫描器。2.7用自然语言描述下列正规式所表示的语言:(1)0(0|1)*0(2)((e|0)1)*)*(3)(a|b)*a(a|b|e)(4)(A|B|...|Z)(a|b|...|z)*(5)(aa|b)*(a|bb)*(6)(0|1|...|9|A|B|C|D|E)+(t|T)2.8为下列语言写正规式(1)所有以小写字母a开头和结尾的串。(2)所有以小写字母a开头或者结尾(或同时满足这两个条件)的串。(3)所有表示偶数的串。(4)所有不以0开始的数字串。(5)能被5整除的10进制数的集合。(6)没有出现重复数字的全体数字串。2.9试构造下列正规式的NFA,并且确定化,然后最小化。(1)(a|b)*a(a|b)(2)(a||b)*a(a|b)*(3)ab((ba|ab)*(bb|aa))*ab(4)00|(0|1)*|11(5)1(0|1)*01(6)1(1010*|1(010)*1*02.10请分别使用下面的技术证明(a|b)*,(a*|b*)*以及((a|e)b*)*这三个正规式是等价的:(1)仅用正规式的定义及其代数性质;(2)从正规式构造的最小DFA的同构来证明正规式的等价。 2.11构造有限自动机M,使得(1)L(M)={anbn|n³1};(2)L(M)={anbncn|n³1};(3)它能识别S={0,1}上0和1的个数都是偶数的串;(4)它能识别字母表{0,1}上的串,但是串不含两个连续的0和两个连续的1;(5)它能接受形如±dd*,±d*E和±dd的实数,其中d={0,1,2,3,4,5,6,7,8,9}。(6)它能识别{a,b}上不含子串aba的所有串。2.12分别将下列NFA确定化,并画出最小化的DFA:(a)a10a,bb(b)a40a,ba123abbba(c)eabFAa,bBCDebbaSEee2.13下面是URL的一个极其简化的扩展正规式的描述:letter→[A-Za-z]digit→[0-9]letgit→letter|digitletgit_hyphen→letgit|_letgit_hyphen_string→letgit_hyphen|letgit_hyphenletgit_hyphen_stringlabel→letter(letgit_hyphen_string?letgit)?URL→(label.)*label(1)请将这个URL的扩展正规改写成只含字母表{A,B,0,1,_,.}上符号的正规式;(2)构造出识别(1)更简化的URL串的有限自动机。2.14用某种高级语言实现(1)将正规式转换成NFA的算法;(2)将NFA确定化的算法;(3)将DFA最小化的算法。2.15描述下列语言词法记号的正规表达式:(1)描述C浮点数的正规表达式。(2)描述Java表达式的正规表达式。2.16Pascal语言的注释允许两种不同的形式:花括弧对{...},以及括弧星号对(*...*)。(1)构造一个识别这两种注释形式的DFA;(2)用Lex的符号构造它的一个正规式。2.17写一个Lex输入源程序,它将产生一个把C语言程序中(注释除外)的保留字全部大写。 练习33.1 对于文法G3.26[E]E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明(i+T)*i是它的一个句型。3.2给定文法G3.27[S]S→aAcB|BdSB→aScA|cAB|bA→BaB|aBc|a试检验下列符号串中哪些是G3.27[S]中的句子。(1)aacb(2)aabacbadcd(3)aacbccb(4)aacabcbcccaacdca(5)aacabcbcccaacbca3.3考虑文法G3.28[S]S→(L)|aL→L,S|S(1)指出该文法的终结符号及非终结符号。(2)给出下列各句子的语法分析树: ①(a,a)②(a,(a,a))③(a,((a,a),(a,a)))(3)分别构造(b)中各句子的一个最左推导和最右推导。3.4考虑文法G3.29[S]S→aSbS|bSaS|ε(1)讨论句子abab的最左推导,说明该文法是二义性的。(2)对于句子abab构造两个相应的最右推导。(3)对于句子abab构造两棵相应的分析树。(4)此文法所产生的语言是什么?3.5文法G3.30[S]为:S→Ac|aBA→abB→bc写出L(G3.30)的全部元素。3.6试描述由下列文法G[S]所产生的语言。(1)S→10S0|aAA→bA|a(2)S→SS|1A0A→1A0|ε(3)S→1A|B0A→1A|CB→B0|CC→1C0|ε(4)S→bAdcA→AS|a (5)S→aSSS→a(6)A→0B|1CB→1|1A|0BBC→0|0A|1CC3.7设已给文法G3.31=(VN,VT,P,S),其中:VN={S}VT={a1,a2,…,an,∨,∧,~,[,]}P={S→ai|i=1,2,…,n}∪{S→~S,S→[S∨S],S→[S∧S]},试指出此文法所产生的语言。3.8已知文法G3.32=({A,B,C},{a,b,c},A,P),其中P由以下产生式组成:A®abcA®aBbcBb®bBBc®CbccbC®CbaC®aaBaC®aa问:此文法表式的语言是什么?3.9已知文法G3.33[P]:P→aPQR|abRRQ→QRbQ→bbbR→bccR→cc证明aaabbbccc是该文法的一个句子。3.10构造一个文法,使其产生的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合。3.12已知语言L={anbbn|n≥1},写出产生语言L的文法。3.13写一文法,使其语言是偶正整数的集合。要求:(1)允许0打头。(2)不允许0打头。3.14文法G3.34[S]为:S→Ac|aB,A→abB→bc该文法是否为二义的?为什么?(提示:找一个句子,使之有两棵不同的分析树。)3.15证明下述文法G3.35[〈表达式〉]是二义的:〈表达式〉→a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉→+|-|*|/3.16下面的文法产生a的个数和b的个数相等的非空a、b串S→aB|bAB→bS|aBB|bA→aS|bAA|a其中非终结符B推出b比a的个数多1个的串,A则反之。(1)证明该文法是二义的。(2)修改上述文法,不增加非终结符,使之成为非二义文法,并产生同样的语言。 3.17考虑文法G3.36[R]R→R'|'R|RR|R*|(R)|a|b其中R'|'R表示R或R;RR表示R与R的连接;R*表示R的闭包。(1)证明此文法生成å={a,b}上的除了Æ和ε的所有正规表达式。(2)试说明此文法是二义性的。(3)构造一个等价的无二义性文法,该文法给出*、连接和|等运算符号的优先级和结合规则。3.18给出产生下述语言的上下文无关文法:(1){anbnambm|n,m≥0}。(2){1n0m1m0n|n,m≥0}。(3){wcwT|w∈{a,b}*},其中wT是w的逆。(4){w|w∈{a,b}+,且w中a的个数恰好比b多1}。(4){w|w∈{a,b}+,且|a|≤|b|≤2|a|}。(5){w|w是不以0开始的奇数集}。3.19设G=(VN,VT,P,S)为CFG,α1,α2,…,αn为V上的符号串,试证明:若α1α2…αnβ则存在V上的符号串β1,β2,…,βn,使β=β1β2…βn,且有aiβi(i=1,2,…,n)。3.20设G=(VN,VT,P,S)为CFG,α和β都是V上的符号串,且αβ,试证明:(1)当α的首符号为终结符号时,β的首符号也必为终结符号;(2)当β的首符号为非终结符号时,则α的首符号也必为非终结符号。3.21写出下列语言的3型文法:(a){an|n≥0}(b){anbm|n,m≥1}(c){anbmck|n,m,k≥1}3.22已知文法G3.37[S]:S→dABA→aA|aB→ε|Bb给出相应的正规式和等价的正规文法。3.23给出下列文法G[A]消除左递归后的等价文法:(1)A→BaC|CbBB→Ac|cC→Bb|b(2)A→Ba|Aa|cB→Bb|Ab|d(3)S→SA|AA→SB|B|(S)|()B→[S]|[](4)S→AS|bA→SA|a(5)S→(T)|a|εT→S|T,S 练习44.1证明:含有左递归的文法不是LL(1)文法。4.2对于文法G4.11[S]S→uBDzB→Bv|wD→EFE→y|eF→x|e(1)计算文法G4.11各非终结符的FIRST集和FOLLOW集,以及各产生式的SELLECT集。(2)判断该文法是否是LL(1)文法。(3)若不是LL(1)文法,则修改此文法,使其成为能产生相同语言的LL(1)文法。4.3已知布尔表达式文法G4.12[bexpr]bexpr→bexprorbterm|btermbterm→btermandbfactor|bfactorbfactor→notbfactor|(bexpr)|true|false改写文法G4.12为扩充的巴克斯范式,并为每个非终结符构造递归下降分析子程序。4.4已知用EBNF表示的文法G4.13[A]A→[BB→X]{A}X→(a|b){a|b}试用类C或类PASCAL语言写出其递归下降子程序。4.5已知文法G4.14[S]S→(L)|aL→L,S|S(1)消除文法G4.14的左递归,并为每个非终结符构造不带回溯的递归子程序。(2)经改写后的文法是否是LL(1)文法?给出它的预测分析表。(3)给出输入串(a,a)$的分析过程,并说明该符号串是否为文法G4.14的句子。4.6对于文法G4.15[R] R→R'|'T|TT→TF|FF→F*|CC→(R)|a|b(1)消除文法的左递归。(2)计算文法G4.15各非终结符的FIRST集和FOLLOW集。(3)构造LL(1)分析表。4.7已知文法G4.16[A]A→aABe|aB→Bb|d(1)判断该文法是否为LL(1)文法。(2)写出输入串aade$的分析过程。 练习55.1设文法G5.10[E]为E→E+T|E-T|TT→T*F|T/F|FF→F↑P|PP→(E)|i求以下句型的短语、直接短语、素短语、句柄和最左素短语:(1)E-T/F+i(2)E+F/T-P↑i(3)T*(T-i)+P(4)(i+i)/i-i5.2根据下列优先关系矩阵计算其优先函数,并说明优先函数是否存在。SABabcS≯A≮≮≌≮≮B≌a≌≮≮≯b≯≯≯≯≯≌c≯5.3对于文法G5.11[S]S→(R)|a|bR→TT→S;T|S(1)计算G5.11[S]的FIRSTTV和LASTTV;(2)构造G5.11[S]的优先关系表,并说明G5.11[S]是否为算符优先文法;(3)计算G5.11[S]的优先函数。5.4对于文法G5.12[S]S→S;G|GG→G(T)|HH→a|(S)T→T+S|S (1)构造G5.12[S]的算符优先关系表,并判断G5.12[S]是否为算符优先文法;(2)给出句型a(T+S);H;S的短语、直接短语、句柄、素短语和最左素短语;(3)分别给出(a+a)和a;(a+a)的分析过程,并说明它们是否为G5.12[S]的句子;(4)给出(3)中输入串的最右推导,分别说明它们是否为G5.12[S]的句子;(5)从(3)和(4)说明算符优先分析的优缺点。5.5对于文法G5.13[P]P→LAd|cdL→cA→aP|P|a请证明它不存在优先函数。5.6给定文法G5.14[S]S→AS|bA→SA|a(1)构造它的LR(0)的项集;(2)构造识别该文法所有活前缀的DFA;(3)这个文法是SLR(1)吗?若是,构造出它的SLR(1)分析表。5.7给定文法G5.15[S]S→AS|eA→aA|b(1)构造它的LR(1)文法;(2)构造识别该文法所有活前缀的DFA;(3)构造出它的SR(1)分析表;(4)给出字符串abab$的分析过程。5.8若有定义二进制数的文法G5.16[D]D→L.L|LL→LB|BB→0|1(1)通过构造该文法的无冲突的分析表来说明它是哪类LR文法;(2)给出输入串101.010的分析过程。5.9给定文法G5.17[S] S→L=R|RL→*R|idR→L(1)构造它的LR(0)的项集;(2)构造它的LR(0)项集规范族;(3)构造识别该文法所有活前缀的DFA;(4)该文法是SLR(1)、LR(1)以及LALAR(1)?构造相应的分析表。5.10对于文法G5.18[S]S→AA→Ab|bBaB→aAc|aAb|a(1)证明它是SLR(1)文法,但不是LR(0)文法;(2)证明所有SLR(1)文法都是LR(1)文法。5.11证明文法G5.19[M]M→NN→Qa|bQc|dc|bdaQ→D是LALR(1)文法,但不是SLR(1)文法。5.12证明文法G5.20[S]S→aAa|aBb|bAb|bBaA→cB→c是LR(1)文法,但不是LALR(1)文法。5.13对于文法G5.21[S]S→AaAb|BbBaA→eB→e(1)证明它是LL(1)文法,但不是SLR(1)文法;(2)证明所有LL(1)文法都是LR(1)文法。5.14对于下列各个文法,判断它是哪类最简单的LR文法,并构造相应的分析表。 (1)A→AA+|AA*|a(2)S→ABA→aBa|eB→bAb|e(3)S→D;B|BD→d|eB→B;a|a|e(4)S→D;B|BD→d|eB→B;a|a|e(5)S→(SR|aR→.SR|)(6)S→UTa|TbT→S|Sc|dU→US|e5.15命题演算的文法G5.22[B]B→BandB|BorB|notB|(B)|true|false|b是二义性文法。(1)为句子bandbortrue构造两个不同的最右推导,以此说明该文法是二义的。(2)为它写一个等价的非二义性文法。(3)给出无二义性规则,构造出LR(0)分析表,并给出句子bandbortrue的分析过程。 练习66.1符号表的作用有哪些?6.2符号表的表项通常包括哪些属性,主要描述的内容是什么?6.3符号表组织的数据结构有哪些种?每种组织结构选取的主要依据是什么?6.4程序块是程序语言的主要构造元素,它允许以嵌套的方式确定局部声明。大多数语言规定,程序块结构的声明作用域使最近嵌套规则,请按照这个规则写出下列声明的作用域。main(){/*开始块B0*/inta=0;intb=0;{/*开始块B1*/intb=1;{/*开始块B2*/inta=2;……}/*结束块B2*/{/*开始块B3*/intb=3;……}/*结束块B3*/……}/*结束块B1*/}6.5C语言中规定变量标识符可以定义为:extern、erternstatic、auto、localstatic和register,请对这5种变量分别说明其作用域。6.6设散列表为HT[13],哈希函数定义为hash(key)=key%13(整数除法取余运算),用链地址法解决冲突对下列关键码12,23,45,57,20,3,31,15,56,78造表。 练习77.1请考虑过程和活动记录的联系和区别。7.2请解释下列概念:生存期,过程的活动,活动树,活动记录。7.3有哪些常见的参数传输方式,请分析和比较它们各自的特点。7.4对你熟悉的高级程序语言(如C、Pascal、C++、Java或C#),了解它们的参数传输机制。7.5执行下面Pascal程序的输出a结果分别是什么,如果参数的传递机制是:(1)引用调用方式;(2)值-结果调用方式;programcopyout(input,output);vara:integer;procedureunsafe(varx:integer);beginx:=2;a:=0end;begina:=1;unsafe(a);writeln(a)end7.6执行下面程序时打印的a分别是什么,若参数的传递机制是:(1)按值调用方式;(2)引用调用方式;(3)值-结果调用方式;(4)换名调用方式。procedurep(x,y,z);beginy:=y+1;z:=z+x;endp;begina:=2; b:=3;p(a+b,a,a);printa;end;7.7设计存储分配时要考虑哪些主要因素?常见的存储分配策略有哪些?简单说明在什么情况下使用哪种存储分配策略。7.8C++语言中关于变量的存储类型符有4个:auto、register、static和extern,请说明每个说明符所表示的存储方式。7.9为下面FORTRAN程序的运行时环境构造出一个可能的组织结构,要保证对AVE的调用时存在的一个存储器指针(参考7.4节)。REALA(SIZE),AVEINTEGERN,I10READ*,NIF(N.LE.0.OR.N.GT.SIZE)GOTO99READ*,(A(I),I=1,N)PRINT*,‘AVE=‘,AVE(A,N)GOTO1099CONTINUEENDREALFUNCTIONAVE(B,N)INTEGERI,NREALB(N),SUMSUM=0.0DO20I=1,N20SUM=SUM+B(I)AVE=SUM/NEND7.10考虑C语言中的下列过程:voidf(charc,chars[10],doubler){int*x; inty[5];......}(1)使用标准C参数传递约定,利用7.5.1所描述的活动记录结构判断以下的fp的偏移:c,s[7]和y[2](假设数据大小为:整型=2个字节,字符=1个字节,双精度=8个字节,地址=4个字节)(2)假设所有的参数都是按值传递(包括数组),重做(1);(3)假设所有的参数都是引用传递(包括数组),重做(1)。7.11为下面C程序的运行时环境构造出一个可能的组织结构(参考7.5.1节)。(1)在进入函数f中的块A之后;(2)在进入函数g中的块B之后。inta[10];char*s=‘hello’;intf(inti,intb[]){intj=1;A:{inti=j;charc=b[i];......}return0;}voidg(char*s){charc=s[0];B:{inta[5];......}}main(){intx=1;x=f(x,a);g(s);return0;} 7.12使用访问链(参考7.5.2节)分别画出下面Pascal程序执行到(1)第1次调用r之后的运行时栈的内容;(2)第2次调用r之后的运行时栈的内容;programpascal1;procedurep;varx:integer;procedureq;procedurer;beginx:=2;......if...thenp;end;{r}beginr;end;{q}beginq;end;{p}begin{pascal1}p;end.7.13使用显示表display重做练习7.12。7.14对下面的Pascal程序,分别画出程序执行到点(1)和(2)时刻的运行时栈的内容。programpascal2(input,output);vari:integer;d:integer;procedurea(k:real);varp:char;procedureb;varc:char; begin...(1)...end:{b}procedurec;vart:real;begin...(2)...end:{c}begin......b;c;......end;{a}begin{pascal2}......a(d);......end.7.15使用显示表display重做练习7.14。7.16实现栈式动态存储管理的一个问题是,如何分配空闲块。请考虑有几种空闲块的分配策略,并比较每个策略的优缺点。7.17了解面向对象语言(如面向对象Pascal、C++、C#、Java)是如何实现垃圾搜集任务的。7.18存储紧缩有时也称为“单空间复制”,以区别双空间复制,请指出两者的相同之处和差异。7.19为以下的C++类画出对象的存储器框架和虚拟函数表(参考7.6.3节):classA{public:inta;virtualvoidf();virtualvoidg(); };classB:publicA{public:intb;virtualvoidf();voidh();};classC:publicB{public:intc;virtualvoidg();} 练习88.1语义分析的基本任务是什么?请简单说明它们可以在编译的哪些阶段或者由编译的哪些模块完成?8.2考虑下列无符号数的简单语法:number®digitnumber|digitdigit®0|1|2|3|4|5|6|7|8|9写出计算number整数值的属性规则。8.3根据下列文法,给出求十进制浮点数的值的语义规则(提示:用属性count表示小数点后的数字数目):num®num.numnum®numdigit|digitdigit®0|1|2|3|4|5|6|7|8|98.4考虑下面的简单的Pascal风格的声明:decl®var-list:typevar-list®var-list,id|idtype®integer|real(1)为它设计一个计算变量类型的属性文法;(2)为每个产生式对应的属性文法划一个依赖图;(3)为声明a,b,c:real画出属性依赖图。8.5修改例8.4中的文法G8.3,使之只用综合属性就可以计算based-num的值。8.6考虑下列属性文法:文法规则语义规则S®ABCB.u:=S.uA.u:=B.v+C.vS.v:=A.vA®aA.v:=2*A.uB®bB.vl:=B.uC®cC.v:=1 (1)构造出串abc的分析树及其属性依赖图,并给出计算这些属性的一个正确顺序;(2)假设S.u在属性求值之前的值是3,那么S.v在属性求值之后的值是什么?(3)如果语义规则修改如下,问题(2)的结果如何?文法规则语义规则S®ABCB.u:=S.uC.u:=A.vA.u:=B.v+C.vS.v:=A.vA®aA.v:=2*A.uB®bB.vl:=B.uC®cC.v:=C.u-28.7设计有向图的一个拓扑排序算法,并用高级程序语言实现。8.8一个包含了综合属性和继承属性的属性文法中,如果综合属性依赖于继承属性(以及其它综合属性),但是继承属性不依赖任何综合属性,那么,用一趟混合的后序遍历和前序遍历就可以计算所有的属性值。请用高级语言或伪代码设计这个算法。8.9例8.11中的三个属性isFloat、etype和val的语义规则如表8.8所示,它们需要遍历分析树或语法树两次才能计算出来。第一遍后序遍历计算出综合属性isFloat的值,第二遍用混合的前序遍历和后序遍历计算出继承属性etype与综合属性val的值。(1)请用高级语言或伪代码设计这个算法;(2)描述5/2/2.0属性的计算过程。8.10请按照例8.14中的语义规则,画出floatx,y的带属性的分析树以及依赖关系图。8.11考虑文法S®(L)|aL®L,S|S(1)写一个打印括号对数的属性文法;(2)写一个翻译模式,它输出每个a的嵌套深度。例如,对于输入串(a,(a,a))的输出是1,2,2。(3)写一个翻译模式,它打印出每个a在句子中的位置。例如,对于输入串(a,(a,a))的结果是2,5,7。8.12下列文法由S符号开始产生一个二进制数,令综合属性val给出该数的值: S®L.L|LL®LB|BL®0|1请设计求S.val的属性文法。其中B的唯一综合属性c给出由B产生的二进位的结果值。例如,输入101.101时,S.val是5.625,其中第一个二进位的值是4,最后一个二进位的值是0.125。8.13考虑下列类似于C语言包含赋值语句的表达式的文法S®EE®E:=E|E+E|(E)|id即b:=c表示把c的值赋给b的赋值表达式,而a:=(b:=c)表示c的值赋给b后再赋给a。试构造语义规则,检查表达式的左部是一个左值。提示:同非终结符E的继承属性side表示生成的表达式出现在赋值运算符的左边还是右边。8.14请根据例8.5的属性文法,(1)把语义规则翻译成LR属性求值器的栈操作代码(参考例8.12);(2)建立对应的翻译模式;(3)消除基础文法的左递归,对新增的符号增加综合属性和继承属性,编写无左递归的翻译模式;(4)编写它的递归下降属性求值器。8.15为下列类型写出类型表达式(1)指向实数的指针数组,下标范围从1到100;(2)二维数组,行的下标从1到10,列的下标从-10到10;(3)一个函数,它的定义域是从整型到整型指针的函数,值域是一个实型和字符组成的记录。8.16对下面C语言的声明:typedefstruct{inta,b:}CELL,*PCELL;CELLfoo[100];PCELLbar(x,y)int;CELLy;{...}试为类型foo和函数bar写出类型表达式。 8.17下列是一个包含文字串表的文法,其中符号的含义和图8.15中的一样。只是增加了类型list,它表示一个元素表,表中类型由of后面的类型T确定。试设计一个翻译模式/语义规则,确定表达式(E)和(L)的类型。P®D;ED®D;D|id:TT®listofT|char|integerE®(L)|literal|num|idE®E;L|E8.18修改表8.15的语义规则,使之可以处理(1)有值语句。赋值语句的值是赋值号:=右边表达式的值;条件语句和循环语句的值是语句体的值;顺序语句的值是该序列中最后一个语句的值;(2)布尔表达式。增加逻辑运算符and、or和not以及关系运算符、<、≤、=、>和≥,并且增加相应的翻译规则,给出这些表达式的类型。 练习99.1把下列表达式变换成后缀式:(1)2+3+a+b(2)a*b+2*c*d(3)(x:=x+3)*4(4)(x:=y:=2)+3*(x:=4)9.2把下列表达式变换成后缀式:(1)(notAandB)or(CornotD)(2)(AorB)and(CornotDandE)(3)if(x+y)*z=0then(a+b)*celse(a*b)+b(4)a[a[i]]=b[j+2]9.3请把doSwhileE和for(V=E1;E2;E3)S形式的循环语句写成后缀式。9.4如果允许处理过程递归,还需要改变表9.7的翻译模式。在产生式D®procid;ND1;S的S之前,执行语义动作把id插入其直接外围过程的符号表。请通过引入非终结符R及其e产生式,修改表9.7的语义动作,使它能够处理递归过程调用。9.5请根据表9.7的语义动作,补充图9.4中符号表的构造过程,画出符号表以及tblptr和offset:(1)当编译扫描完quicksort的局部变量说明vark,v:integer;时;(2)当编译扫描完partition的声明、在局部变量说明vari,j:integer;之前;(3)当编译扫描完partition的整个过程时。9.6把下列表达式翻译成三地址代码:(1)x:=y*(-a+b)(2)i:=(j+k)*(10+m)9.7一般而言,程序设计语言都把算术表达式中不同类型的运算数进行转换,通常的规则是把整数转换成实数,然后进行运算。为了区别不同类型的运算,可以在运算符前加上类型,如实数加法的符号是real+,整数乘法的符号是int*。(1)请利用单目转换符inttoreal以及表示类型的运算符,修改表9.9文法中加法表达式翻译规则,插入必要的类型转换。(提示:参考图9.6和表7.16,使用E的属性type和place)(2)把下列程序段的执行语句翻译成三地址代码: floatx,y;inta,b;x:=y+a*b9.8用9.3节所给的翻译模式,把下列赋值语句翻译成三地址代码:(1)a[i+j]:=a[i]+a[j]*10(2)A[i,j]:=B[i,j]+C[A[k,1]]+D[i+1]9.9按照表9.11翻译模式把下列布尔表达式翻译成三地址码(假设语句起始标号是10):(1)ac9.10按照表9.12翻译模式把9.9题目中的布尔表达式翻译成三地址码。9.11利用回填技术把9.9题目中的布尔表达式翻译成四元式,假设语句起始标号是10,真值出口是100,假值出口是200。9.12根据9.4.2节的翻译规则,把下列语句翻译成抽象的三地址代码:(1)whileaddoifa=1thenc:=c+1elsewhilea<=ddobegind:=d*2;c:=c-dend;9.13利用回填技术,分别把题目9.12中的语句翻译成四元式的形式。9.14C语言中的for语句的一般形式是for(E1;E2;E3)S含义如下:E1;while(E2)dobeginS;E3;end;试构造一个把C语言for语句翻译成三地址码的翻译模式。9.15给出描述下面语句的翻译模式 repeatSuntilE; 练习1010.1一个编译程序的代码生成工作需要考虑哪些因素?10.2利用语法制导的翻译技术把下列程序段翻译成目标代码:(1)x:=(a+b)*c-a(2)a>bandc=dorejgotoL2a:=u2L2:i:=u3gotoL110.4对下列中间代码序列 (1)T1:=B–CT2:=A*T1T3:=D+1T4:=E–FT5:=T3*T4W:=T2/T5W是基本块出口的活跃变量(2)T1:=A+BT2:=T1–CT3:=T2*T1T4:=T1+T3T5:=T3–EE:=T4*T5F是基本块出口的活跃变量假设可用寄存器为R0和R1,用简单代码生成算法生成目标代码,同时列出代码生成过程中的寄存器描述和地址描述。对于(2)小题,如果只有一个寄存器R0可用,结果如何?10.5对于下列基本块,假设只有寄存器R1和R2可用,开始的时候没有值在寄存器中,A和B的值在内存中,L是基本块出口的活跃变量,而且假设目标代码的算术运算不满足交换率。请用简单代码生成算法生成其目标代码,同时列出代码生成过程中的寄存器描述和地址描述。T1:=A-BT2:=A/T1T3:=3*T1L:=T3+T210.6分别把下列C语句首先转换成三地址代码,然后产生目标代码,假定三个可用的寄存器R0,R1和R2。(1)X=A[i]+1(2)A[i]=B[C[i]](3)A[i]=A[i]+A[j](4)if(i>j)A=j+1;elseA=i+1; 练习1111.1何谓代码优化?代码优化需要什么样的基础?11.2编译过程中可以进行的优化是如何分类的?11.3常用的代码优化技术有哪些?11.4使用基本的代码优化技术对下面的代码进行优化:x=1;...y=0;...if(y)x:=0;...if(x)y=1;...11.5对以下基本块B1和B2:B1:1.A:=B*C2.D:=B/C3.E:=A+D4.F:=2*E5.G:=B*C6.H:=G*G7.F:=H*G8.L:=F9.M:=LB2:10.B:=311.D:=A+C12.E:=A*C13.F:=D+E14.G:=B*F15.H:=A+C16.I:=A*C17.J:=H+I18.K:=B*519.L:=K+J20.M:=L分别构造出DAG,然后应用DAG就以下两种情况分别写出优化后的三地址中间代码:(1)假设变量G、L和M在基本块之后还要被引用; (2)假设只有变量L在基本块之后还要被引用。11.6下面的C语言程序p=0;for(i=0;i<=20;i++){p=p+a[i]*b[i]};经过编译得到的中间代码如下(1)p:=0(2)i:=1(3)t1:=4*i(4)t2:=addr(a)-4(5)t3:=t2[t1](6)t4:=4*i(7)t5:=addr(b)-4(8)t6:=t5[t4](9)t7:=t3*t6(10)p:=p+t7(11)i:=i+1(12)ifi£20goto(3)(1)把上述三地址程序划分为基本块并做出流图。(2)将每个基本块的公共子表达式删除。(3)找出流图中的循环,将循环不变量计算移出循环。(4)找出每个循环中的归纳变量,并在可能之处删除它们。11.7请用窥孔优化技术对下列指令进行优化,其中R1和R2不一定是同一寄存器。MOVR1,LMOVL,R111.8窥孔优化经常使用模式变量描述,用一条规则表示一类优化,例如MUL#2,%RÞADD%R,%R表示任何寄存器乘以2都可以用寄存器自身的加法代替(这里,用%R匹配任意的寄存器)。请考虑如何在窥孔优化器中实现这种模式匹配。11.9请利用代码优化的思想(代码外提和强度消弱),优化下列C语言程序,写出优化后的C程序。main() {inti,j;intr[20][10];for(i=0;i<20;i++){for(j=0;j<10;j++){r[i][j]=10*i*j;}}}