清华大学本科生考试试题《编译原理》

资源描述

《清华大学本科生考试试题《编译原理》》由会员分享，可在线阅读，更多相关《清华大学本科生考试试题《编译原理》（8页珍藏版）》请在金锄头文库上搜索。

1、清华大学本科生考试试题专用纸考试课程编译原理(A卷)2007年7月3日学号：(15%简答题const a=25; var x,y; procedure p;var z;begin1 . (3 %)图1是支持嵌套过程说明的语言PL0的一段程序。en d; procedure r;var x, s; procedure t;var v; begin若每个作用域栈都有各自的符号表，则在编译器处理到/*here*/时，哪些作用域是开作用域？哪些作用域是闭作用域？作用域栈的栈顶对应哪个作用域？注：该段程序包含下列作用域a, x, y, p, ren d;begi n/*here*/zend; be

2、ginx, s, tven d.图1作用域与可见性2. (3 %)如下是一个类Pascal程序片断。试分别给出遵循静态作用域规则和动态作用域规则时运行该段程序时的输出结果。var r: real procedure show;begin write(r:5:3)en d; procedure small;var r:real;beginr:=0.125; show en d;beginr:=0.25;show; small; writel n; show; small; writel n;en d.注：write(r:5:3)表示按照一定格式 (总宽度为5，小数点后有三位数字)输出r ;wr

3、itein表示输出一个换行符。3. (3 %)若按照某种运行时组织方式，如下函数 p被激活时的过程活动记录如图 2所示。其中d 是动态数组。static int N ；void p( int a) float b;float c10;float dN; float e;L一 Offset - 30+2Nd Offset = 30e Offset = 28的的d的的的Offset = 27d的的的的N的*Offset = 26c Offset = 6b Offset = 4a* Offset = 3的的的的 Offset = 0的2的的的的试指出函数p中访问di ( 0 i N )时相对于活

4、动记录基址的Offset值如何计算？若将数组 c和d的声明次序颠倒，则di ( 0 i N )又如何计算？(对于后一问题默认采用同样的运行时组织方式，若你认为可能有歧义，请予以说明)4. (3 %)简述实现参数传递方式call-by-value 和call-by-referenee 的异同(指出实参的存储与访问策略)。5. (3 %)已知语言L已在机器A上实现，即已有一个在机器A上运行的L语言的本地编译程序 X。试给出一种实现方案，可以将机器A上的语言L移植到另一机器B，即获得一个运行于机器B上的L语言的本地编译程序。(12%)1 . (8 %)(1) a:=1B1图3流图以基本块为单位的到

5、达-定值(reaching definitions)数据流方程可表示为OUTE = GEN B U (IN B|KILL B| )IN B = U p 叭 OUTp其中，P Bl为B的所有前驱基本块； GEN日为在B中定值并可到达 B出口的所有定值点集合；KILL 日为B之外的那些定值点集合，其定值的变量在 B中又重新定值；IN B为可到达 B入口处的各变量所有定值点的集合；OUT B为B出口处的各变量所有定值点的集合。对于图3所给出的流图，分别求出 Bi, B2, B3, B4入口处及出口处的到达-定值点集合，即分别计算In(B i), Out(Bi),In(B2) , Out(B2)

6、,In(B3) ,Out) ,ln(B 4),Out(B 4)。初始时，假设In(B 1)为空。2. (2%)指出图3所示流图中存在的自然循环。3. (2%)对于图3所示流图，指出语句(3)中变量c和b在基本块B2围的待用(Next Use)信息。三(18%)如下是一个简单的FTP客户端程序对应的翻译模式(省略函数的细节)，其基础文法为 G S:S A bye EXIT ( ); A A C Copen ip num OPEN ip_. val , num . val ); Cd id_CWD( id. . val ); |s_LIST ( ); put id_PUT_FILE(id_ . v

7、al ); get idGET_FILE(id . val ); 其中小写并带下划线的符号均为终结符。1. (6 pts) 试写出该文法GS的LL(1)分析表，并根据分析表说明该文法不是LL(1)文法。2. (5 pts)试通过消去文法GSI中的左递归得到一个LL(1)文法G S，并给出一个以G S为基础文法的翻译模式，其语义处理过程等效于上述以GS为基础文法的翻译模式。3. (7 pts)针对上述以G S作为基础文法设计的翻译模式，构造一个自上而下的递归下降(预测)翻译程序：注：可以直接使用类似于讲稿中的MatchToke n函数。为简洁，可以直接用文法终结符作为参数，例如MatchToke

8、 n( ip)，假设其含义如下：(1)若当前扫描的单词与终结符ip匹配，设置ip . val，读下一个单词；(2)否则，显示词法错误，退出处理。(若自己假设了不同的MatchToke n函数或其他自定义函数，请予以说明)四(12%) 给定文法G(S):SA bA B cAa AaB b回答下列问题，并给出理由：1. 该文法是否LR(0) 文法？2. 该文法是否 SLR(1)文法？3. 该文法是否 LALR(1)文法？4. 该文法是否二义文法？五(8%)给定文法G(S):(1)SA a(2)Sb A c(3)Sd c(4)Sb d a(5)Ad该文法的LR(1)自动机如图4所示:IoI 1图

9、4 LR 自动机1. 该文法是否 LR(1) 文法？ (1分)2. 该文法是否 LALR(1)文法？ (1分)3. 给出对应的LR(1)分析表。(6分)六(9%)已知某扩展文法GS的LALR(1)分析表如下:状态ACTIONGOTOatgc#S0s11s8s411s2acc2S33s11s8s4164s55s66s77r1r1r18s99s1010s11s8s41411s11s8s41212s13s213s11s8s41514r4s2r415r2s2r216r3s2r3并且已知各规则右边语法符号的个数以及左边的非终结符如下:规则编号12可4右部长度4444左部符号SS:SS1. 请写出使用上述

10、 LALR(1)分析器分析下面串的过程(只需写出前 10步，列出所有可能的ri , s j序列，注意先后次序)：acaaccgtgccaacgatgccaa2. 试指出该串相对于上述文法的句柄。七(10%)以下是语法制导生成某类TAC语句的一个L-属性文法(对应讲稿中的相应容)：Sif E the n S 1 E .true := newlabel ;E .false := S .n ext ;S 1.next := S .next ;S .code := E .code | gen(E.true ： ) | S 1 .codeSif E then S 1 else S 2 E .true

12、en(E.true: ) | S 1 .code| gen( goto S1 .next)S S1; S2 S1 .n ext := n ewlabel ;S2 .next := S .next ;S .code := S 1 .code | gen(S 1 .next: ) | S 2 .codeS SS .next := S .next ;S .code := S .codeS idj= E p := lookup (id .n ame);if ( pnil ) then S . code := E .code | gen (p := E . place)else errorE E1 or

13、 E 2 E1 .true := E . true ;E1 . false := n ewlabel ;E2 . true := E . true ;E2 . false := E . false ;E .code := E 1 .code | gen(E 1 . false ： ) | E 2 .code ./*这里略去关于布尔表达式更多的部分*/E1 + E 2E.place :=n ewtemp;E.code :=E 1 .code | E 2 .code |gen( E .place + E 2. place)/*这里略去关于算术表达式更多的部分 */E 1 . place，E .place, 语以及所涉及到的TAC语句其中，属性 S .code , E .code , S .n ext , E.true , E.false 义函数 newlabel , gen( )， lookup (id丄ame) , error与讲稿中

展开阅读全文