资源描述
真诚为您提供优质参考资料，若有不当之处，请指正。练习 1 1.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形图示意过程和结果。33 / 33练习 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) 它能识别S0, 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-zdigit 0-9letgit letter| digit letgit_hyphen letgit | _letgit_hyphen_string letgit_hyphen | letgit_hyphen letgit_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.16 Pascal语言的注释允许两种不同的形式：花括弧对.，以及括弧星号对(*.*)。(1) 构造一个识别这两种注释形式的DFA；(2) 用Lex的符号构造它的一个正规式。2.17 写一个Lex输入源程序，它将产生一个把C语言程序中（注释除外）的保留字全部大写。练习 33.1对于文法G3.26EE T | E+T | E-TT F | T*F | T/FF (E) | i 证明(i+T)*i是它的一个句型。3.2 给定文法G3.27SS aAcB | BdS B aScA | cAB | b A BaB | aBc | a 试检验下列符号串中哪些是G3.27 S中的句子。(1) aacb (2) aabacbadcd (3) aacbccb (4) aacabcbcccaacdca (5) aacabcbcccaacbca3.3 考虑文法G3.28S S (L) | aL L, S | S(1) 指出该文法的终结符号及非终结符号。(2) 给出下列各句子的语法分析树： (a,a) (a,(a, a) (a, (a, a), (a, a) (3) 分别构造(b)中各句子的一个最左推导和最右推导。3.4 考虑文法G3.29S S aSbS | bSaS |(1) 讨论句子abab的最左推导，说明该文法是二义性的。(2) 对于句子abab构造两个相应的最右推导。 (3) 对于句子abab构造两棵相应的分析树。 (4) 此文法所产生的语言是什么？3.5 文法G3.30S为： S Ac | aB A ab B bc 写出L(G3.30)的全部元素。 3.6 试描述由下列文法GS所产生的语言。 (1) S 10S0 | aA AbA | a (2) S SS | 1A0 A1A0 | (3) S 1A | B0 A1A | C BB0 | C C1C0 | (4) S bAdc AAS | a (5) S aSS Sa(6) A 0B | 1CB 1 | 1A | 0BBC 0 | 0A | 1CC3.7 设已给文法G3.31=(VN,VT,P,S)，其中： VN = S VT = a1,a2,an, , , P = Sai| i=1,2,nS S, S SS, S SS，试指出此文法所产生的语言。3.8 已知文法G3.32=(A,B,C,a,b,c,A,P)，其中P由以下产生式组成：A abc A aBbcBb bB Bc CbccbC Cb aC aaBaC aa 问：此文法表式的语言是什么？3.9 已知文法 G3.33 P:P aPQR |abR RQ QR bQ bb bR bc cR cc 证明 aaabbbccc 是该文法的一个句子。3.10 构造一个文法，使其产生的语言是由算符+, *, (, ) 和运算对象a构成的算术表达式的集合。3.12 已知语言L=anbbn| n1, 写出产生语言L的文法。3.13 写一文法，使其语言是偶正整数的集合。 要求：(1) 允许0打头。 (2) 不允许0打头。3.14 文法G3.34 S为： S Ac|aB, A ab B bc 该文法是否为二义的？为什么？（提示：找一个句子，使之有两棵不同的分析树。） 3.15 证明下述文法G3.35表达式是二义的： 表达式 a | (表达式) |表达式运算符表达式 运算符 + | - | * | / 3.16 下面的文法产生a的个数和b的个数相等的非空a、b串 S aB | bAB bS | aBB | b A aS | bAA | a 其中非终结符B推出b比a的个数多1个的串，A则反之。(1) 证明该文法是二义的。 (2) 修改上述文法，不增加非终结符，使之成为非二义文法，并产生同样的语言。 3.17 考虑文法G3.36R RR | R | RR | R* | (R) | a | b 其中R | R表示R或R；RR表示R与R的连接；R*表示R的闭包。(1) 证明此文法生成=a, b上的除了和的所有正规表达式。 (2) 试说明此文法是二义性的。(3) 构造一个等价的无二义性文法，该文法给出*、连接和|等运算符号的优先级和结合规则。3.18 给出产生下述语言的上下文无关文法：(1) an bn am bm | n, m0。(2) 1n 0m1m 0n | n, m0。(3) wcwT | wa, b*，其中wT是w的逆。(4) w | wa,b+，且w中a的个数恰好比b多1 。(4) w | wa,b+，且|a|b|2|a| 。(5) w | w是不以0开始的奇数集 。3.19 设G=(VN,VT,P,S)为CFG，1,2,n为V上的符号串，试证明： 若 12n 则存在V上的符号串1,2，,n，使=12n，且有 aii (i=1,2,n)。3.20 设G=(VN,VT,P,S)为CFG，和都是V上的符号串，且 ，试证明：(1) 当的首符号为终结符号时，的首符号也必为终结符号；(2) 当的首符号为非终结符号时，则的首符号也必为非终结符号。3.21 写出下列语言的3型文法：(a) an | n0(b) anbm | n, m1 (c) anbmck | n, m, k1 3.22 已知文法G3.37 S：S dABA aA|aB |Bb 给出相应的正规式和等价的正规文法。3.23给出下列文法GA消除左递归后的等价文法：(1) A BaC | CbBB Ac | cC Bb | b (2) A B a | A a | cB B b | A b | d(3) S SA | A A SB | B | (S) | ( ) B S | (4) S AS | b A SA | a (5) S (T) | a | T S | T, S 练习 44.1证明：含有左递归的文法不是LL(1)文法。4.2 对于文法G4.11SS uBDz B Bv | w D EF E y | eF x | e(1) 计算文法G4.11各非终结符的FIRST集和FOLLOW集，以及各产生式的SELLECT集。(2) 判断该文法是否是LL(1)文法。(3) 若不是LL(1)文法，则修改此文法 , 使其成为能产生相同语言的 LL(1) 文法。4.3 已知布尔表达式文法G4.12bexpr bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor | (bexpr) | true | false 改写文法G4.12为扩充的巴克斯范式，并为每个非终结符构造递归下降分析子程序。4.4已知用EBNF表示的文法G4.13A A B B X A X (a | b) a | b 试用类 C 或类 PASCAL 语言写出其递归下降子程序。4.5 已知文法G4.14SS (L) | a L L, S | S (1) 消除文法G4.14的左递归，并为每个非终结符构造不带回溯的递归子程序。(2) 经改写后的文法是否是LL(1)文法？给出它的预测分析表。(3) 给出输入串 (a, a)$ 的分析过程，并说明该符号串是否为文法G4.14的句子。4.6 对于文法G4.15RR R | T | T T TF | F F F* | C C (R) | a | b(1) 消除文法的左递归。(2) 计算文法G4.15各非终结符的FIRST集和FOLLOW集。(3) 构造LL(1)分析表。4.7 已知文法G4.16A A aABe | a B Bb | d(1) 判断该文法是否为LL(1) 文法。 (2) 写出输入串aade$ 的分析过程。练习 55.1 设文法G5.10E为E E+T | E-T | TT T*F | T/F | FF FP | PP (E) | i求以下句型的短语、直接短语、素短语、句柄和最左素短语：（1）E-T/F+i（2）E+F/T-Pi（3）T*(T-i)+P（4）(i+i)/i-i5.2 根据下列优先关系矩阵计算其优先函数，并说明优先函数是否存在。SABabcSABabc5.3 对于文法G5.11SS (R) | a | b R 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 SS 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.13PP LAd | cdL cA aP | P | a请证明它不存在优先函数。5.6 给定文法G5.14 SS AS | bA SA | a（1）构造它的LR(0)的项集；（2）构造识别该文法所有活前缀的DFA；（3）这个文法是SLR(1)吗？若是，构造出它的SLR(1)分析表。5.7 给定文法G5.15SS AS | eA aA | b（1）构造它的LR(1)文法；（2）构造识别该文法所有活前缀的DFA；（3）构造出它的SR(1)分析表；（4）给出字符串abab$的分析过程。5.8 若有定义二进制数的文法G5.16DD L . L | LL LB | BB 0 | 1 （1） 通过构造该文法的无冲突的分析表来说明它是哪类LR文法;（2） 给出输入串101.010的分析过程。5.9 给定文法G5.17SS L = R| RL *R | idR L（1）构造它的LR(0)的项集；（2）构造它的LR(0)项集规范族；（3）构造识别该文法所有活前缀的DFA；（4）该文法是SLR(1)、LR(1)以及LALAR(1)？构造相应的分析表。5.10 对于文法G5.18SS AA Ab | bBaB aAc | aAb | a（1）证明它是SLR(1)文法，但不是LR(0)文法；（2）证明所有SLR(1)文法都是LR(1)文法。5.11 证明文法G5.19MM NN Qa | bQc | dc | bdaQ D是LALR(1)文法，但不是SLR(1)文法。5.12 证明文法G5.20SS aAa | aBb | bAb | bBaA cB c是LR(1)文法，但不是LALR(1)文法。5.13 对于文法G5.21SS AaAb | BbBa A 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.22B B B and B | B or B | not B | (B) | true | false | b是二义性文法。（1）为句子b and b or true构造两个不同的最右推导，以此说明该文法是二义的。（2）为它写一个等价的非二义性文法。（3）给出无二义性规则，构造出LR(0)分析表，并给出句子b and b or true的分析过程。练习 66.1 符号表的作用有哪些？6.2 符号表的表项通常包括哪些属性，主要描述的内容是什么？6.3 符号表组织的数据结构有哪些种？每种组织结构选取的主要依据是什么？6.4程序块是程序语言的主要构造元素，它允许以嵌套的方式确定局部声明。大多数语言规定，程序块结构的声明作用域使最近嵌套规则，请按照这个规则写出下列声明的作用域。main()/* 开始块B0 */int a = 0;int b =0; /* 开始块B1 */int b = 1; /* 开始块B2 */int a = 2; /* 结束块B2 */ /* 开始块B3 */int b = 3; /* 结束块B3*/ /* 结束块B1*/6.5C语言中规定变量标识符可以定义为：extern、ertern static、auto、local static和register，请对这5种变量分别说明其作用域。6.6 设散列表为HT13，哈希函数定义为hash(key)=key%13（整数除法取余运算），用链XXX法解决冲突对下列关键码12，23，45，57，20，3，31，15，56，78造表。练习 77.1 请考虑过程和活动记录的XXX和区别。7.2 请解释下列概念：生存期，过程的活动，活动树，活动记录。 7.3有哪些常见的参数传输方式，请分析和比较它们各自的特点。7.4对你熟悉的高级程序语言（如C、Pascal、C+、Java或C#），了解它们的参数传输机制。7.5执行下面Pascal程序的输出a结果分别是什么，如果参数的传递机制是：（1）引用调用方式；（2）值结果调用方式；program copyout (input, output);var a: integer;procedure unsafe （var x: integer）;begin x := 2; a := 0 end;begina := 1; unsafe (a); writeln (a)end7.6 执行下面程序时打印的a分别是什么，若参数的传递机制是：（1）按值调用方式；（2）引用调用方式；（3）值结果调用方式；（4）换名调用方式。procedure p(x, y, z);beginy := y +1; z := zx;end p;begina := 2;b := 3;p(a+b, a, a);print a;end;7.7 设计存储分配时要考虑哪些主要因素？常见的存储分配策略有哪些？简单说明在什么情况下使用哪种存储分配策略。7.8C+语言中关于变量的存储类型符有4个：auto、register、static和extern，请说明每个说明符所表示的存储方式。7.9为下面FORTRAN程序的运行时环境构造出一个可能的组织结构，要保证对AVE的调用时存在的一个存储器指针（参考7.4节）。REAL A(SIZE), AVEINTEGER N, I10READ *, NIF (N .LE. 0 .OR. N .GT. SIZE) GOTO 99READ *, (A(I), I=1, N)PRINT *, AVE = , AVE(A, N)GOTO 1099CONTINUEENDREAL FUNCTION AVE (B, N)INTEGER I, NREAL B(N), SUMSUM = 0.0DO 20 I=1, N20SUM = SUM+B(I)AVE = SUM/NEND7.10考虑C语言中的下列过程：void f ( char c, char s10, double r) int * x; int y 5; .（1）使用标准C参数传递约定，利用7.5.1所描述的活动记录结构判断以下的fp的偏移：c，s7和y2（假设数据大小为：整型2个字节，字符1个字节，双精度8个字节，XXX4个字节）（2）假设所有的参数都是按值传递（包括数组），重做（1）；（3）假设所有的参数都是引用传递（包括数组），重做（1）。7.11为下面C程序的运行时环境构造出一个可能的组织结构（参考7.5.1节）。(1)在进入函数f中的块A之后；(2)在进入函数g中的块B之后。int a10;char *s = hello;int f ( int i, int b )int j = 1; A: int i = j;char c = bi;. return 0;void g (char *s)char c = s0;B: int a5; . main () int x = 1; x = f (x, a); g (s); return 0;7.12使用访问链（参考7.5.2节）分别画出下面Pascal程序执行到（1） 第1次调用r之后的运行时栈的内容；（2） 第2次调用r之后的运行时栈的内容；program pascal1;procedure p;var x: integer;procedure q;procedure r;beginx := 2;.if . then p;end; r beginr;end; q beginq;end; p begin pascal1 p;end.7.13使用显示表display重做练习7.12。7.14对下面的Pascal程序，分别画出程序执行到点（1）和（2）时刻的运行时栈的内容。program pascal2 (input, output);var i: integer; d: integer;procedure a ( k: real );var p: char;procedure b;var c: char;begin.(1).end: bprocedure c;var t: real;begin.(2).end: cbegin.b;c;.end; abegin 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节）：class A public:int a;virtual void f();virtual void g(); ;class B: public A public:int b;virtual void f();void h();；class C: public B public:int c;virtual void g(); 练习 88.1 语义分析的基本任务是什么？请简单说明它们可以在编译的哪些阶段或者由编译的哪些模块完成？8.2 考虑下列无符号数的简单语法：number digit number | digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9写出计算number整数值的属性规则。8.3根据下列文法，给出求十进制浮点数的值的语义规则（提示：用属性count表示小数点后的数字数目）：num num.numnum num digit | 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中的语义规则，画出float x, 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语言的声明：typedef struct int a,b: CELL, *PCELL;CELL foo100;PCELL bar(x, y) int;CELL y;.试为类型foo和函数bar写出类型表达式。8.17下列是一个包含文字串表的文法，其中符号的含义和图8.15中的一样。只是增加了类型list，它表示一个元素表，表中类型由of 后面的类型T确定。试设计一个翻译模式/语义规则，确定表达式(E)和(L)的类型。P D; ED D; D | id:T T list of T | char | integerE (L) | literal | num | idE E; L | E8.18修改表8.15的语义规则，使之可以处理（1）有值语句。赋值语句的值是赋值号:=右边表达式的值；条件语句和循环语句的值是语句体的值；顺序语句的值是该序列中最后一个语句的值；（2）布尔表达式。增加逻辑运算符and、or和not以及关系运算符、和，并且增加相应的翻译规则，给出这些表达式的类型。练习 99.1把下列表达式变换成后缀式：（1）23ab（2）a*b + 2*c*d（3）(x := x +3) *4（4）(x := y := 2) + 3*(x := 4)9.2把下列表达式变换成后缀式：（1）(not A and B) or (C or not D)（2）(A or B) and (C or not D and E)（3）if (x+y) *z = 0 then (a+b) *c else (a*b) +b（4）aai = b j+29.3请把do S while E和for (V = E1; E2; E3) S形式的循环语句写成后缀式。9.4如果允许处理过程递归，还需要改变表9.7的翻译模式。在产生式D proc id; N D1; S的S之前，执行语义动作把id插入其直接外围过程的符号表。请通过引入非终结符R及其e产生式，修改表9.7的语义动作，使它能够处理递归过程调用。9.5请根据表9.7的语义动作，补充图9.4中符号表的构造过程，画出符号表以及tblptr和offset：（1）当编译扫描完quicksort的局部变量说明var k, v: integer；时；（2）当编译扫描完partition的声明、在局部变量说明var i, j: integer；之前；（3）当编译扫描完partition的整个过程时。9.6把下列表达式翻译成三XXX代码：（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）把下列程序段的执行语句翻译成三XXX代码：float x, y;int a, b;x := y + a*b9.8用9.3节所给的翻译模式，把下列赋值语句翻译成三XXX代码：（1）ai+j := ai+aj*10（2）Ai, j := Bi, j + CAk, 1 + Di+19.9按照表9.11翻译模式把下列布尔表达式翻译成三XXX码（假设语句起始标号是10）：（1）ab or cd and ec9.10按照表9.12翻译模式把9.9题目中的布尔表达式翻译成三XXX码。9.11利用回填技术把9.9题目中的布尔表达式翻译成四元式，假设语句起始标号是10，真值出口是100，假值出口是200。9.12根据9.4.2节的翻译规则，把下列语句翻译成抽象的三XXX代码：（1）while a b doif c d then x := y + z; else x:= y - z;（2）while a d do if a = 1 then c := c + 1 elsewhile a b and cd or e j goto L2a := u2L2: i := u3goto L110.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，用简单代码生成算法生成目标代码，同时列出代码生成过程中的寄存器描述和XXX描述。对于（2）小题，如果只有一个寄存器R0可用，结果如何？10.5对于下列基本块, 假设只有寄存器R1和R2可用，开始的时候没有值在寄存器中，A和B的值在内存中，L是基本块出口的活跃变量，而且假设目标代码的算术运算不满足交换率。请用简单代码生成算法生成其目标代码，同时列出代码生成过程中的寄存器描述和XXX描述。T1 := ABT2 := A / T1T3 := 3*T1L := T3T210.6 分别把下列C语句首先转换成三XXX代码，然后产生目标代码，假定三个可用的寄存器R0，R1和R2。（1）X = A i +1（2）Ai = BCi（3）Ai = Ai + Aj（4）if (i j ) A = j + 1; else A = 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:1. B := 32. D := A+C3. E := A*C4. F := D+E5. G :=B*F6. H := A+C7. I := A*C8. J := H+I9. K := B*510. L := K+J11. M := L分别构造出DAG，然后应用DAG就以下两种情况分别写出优化后的三XXX中间代码：（1）假设变量G、L和M在基本块之后还要被引用；（2）假设只有变量L在基本块之后还要被引用。11.6 下面的C语言程序p = 0;for ( i = 0; i= 20; i + ) p = p + ai *bi ;经过编译得到的中间代码如下(1) p := 0(2) i := 1(3) t1 := 4*i(4) t2 := addr(a) - 4(5) t3 := t2t1(6) t4 := 4*i(7) t5 := addr(b) - 4(8) t6 := t5t4(9) t7 := t3*t6(10) p := p + t7(11) i := i + 1(12) if i 20 goto (3)（1）把上述三XXX程序划分为基本块并做出流图。（2）将每个基本块的公共子表达式删除。（3）找出流图中的循环，将循环不变量计算移出循环。（4）找出每个循环中的归纳变量，并在可能之处删除它们。11.7 请用窥孔优化技术对下列指令进行优化，其中R1和R2不一定是同一寄存器。MOV R1, LMOV L, R111.8窥孔优化经常使用模式变量描述，用一条规则表示一类优化，例如MUL #2, %R ADD %R, %R表示任何寄存器乘以2都可以用寄存器自身的加法代替（这里，用%R匹配任意的寄存器）。请考虑如何在窥孔优化器中实现这种模式匹配。11.9 请利用代码优化的思想（代码外提和强度消弱），优化下列C语言程序，写出优化后的C程序。main ()int i, j;int r2010;for ( i = 0; i 20; i+ ) for ( j = 0; j 10; j+ )rij = 10*i*j;
展开阅读全文