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

《清华大学本科生考试试题《编译原理》.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华大学本科生考试试题专用纸考试课程《编译原理》（A卷）2007年7月3日学号：姓名：一.（15%）简答题consta=25;varx,y;procedurep;varz;begin……end;procedurer;varx,s;proceduret;varv;begin……end;begin/*here*/……end;begin……end.图1作用域与可见性1．(3%)图1是支持嵌套过程说明的语言PL0的一段程序。若每个作用域栈都有各自的符号表，则在编译器处理到/*here*/时，哪些作用域是开作用域？哪些作用域是闭作用域？作用域栈的栈顶对应哪个作用域？注：该段程序包含

2、下列作用域{a,x,y,p,r}{z}{x,s,t}{v}2．(3%)如下是一个类Pascal程序片断。试分别给出遵循静态作用域规则和动态作用域规则时运行该段程序时的输出结果。varr:realprocedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writeln;end.注：write(r:5:3)表示按照一定格式（总宽度为5，小数点后有三位数字）输出r；writeln表示输出一

3、个换行符。3．(3%)若按照某种运行时组织方式，如下函数p被激活时的过程活动记录如图2所示。其中d是动态数组。staticintN；voidp(inta){floatb;floatc[10];floatd[N];floate;…}试指出函数p中访问d[i]（0£i

4、问策略)。5．(3%)已知语言L已在机器A上实现，即已有一个在机器A上运行的L语言的本地编译程序X。试给出一种实现方案，可以将机器A上的语言L移植到另一机器B，即获得一个运行于机器B上的L语言的本地编译程序。二(12%)1．(8%)图3流图以基本块为单位的到达-定值（reachingdefinitions）数据流方程可表示为OUT[B]=GEN[B]∪（IN[B]-KILL[B]）IN[B]=∪pÎP[B]OUT[p]其中，P[B]为B的所有前驱基本块；GEN[B]为在B中定值并可到达B出口的所有定值点集合；KILL[B]为B之外的那些定值点集合,其定值的变量在B中又重新

5、定值；IN[B]为可到达B入口处的各变量所有定值点的集合；OUT[B]为B出口处的各变量所有定值点的集合。对于图3所给出的流图，分别求出B1，B2，B3，B4入口处及出口处的到达-定值点集合，即分别计算In(B1)，Out(B1)，In(B2)，Out(B2)，In(B3)，Out(B3)，In(B4)，Out(B4)。初始时，假设In(B1)为空。2．(2%)指出图3所示流图中存在的自然循环。3．(2%)对于图3所示流图，指出语句（3）中变量c和b在基本块B2范围内的待用（NextUse）信息。三(18%)如下是一个简单的FTP客户端程序对应的翻译模式（省略函数的细节）

6、，其基础文法为G[S]：S®Abye{EXIT();}A®AC{}½e{}C®openipnum{OPEN(ip.val,num.val);}½cdid{CWD(id.val);}½ls{LIST();}½putid{PUT_FILE(id.val);}½getid{GET_FILE(id.val);}其中小写并带下划线的符号均为终结符。1.(6pts)试写出该文法G[S]的LL(1)分析表，并根据分析表说明该文法不是LL(1)文法。2.(5pts)试通过消去文法G[S]中的左递归得到一个LL(1)文法G’[S]，并给出一个以G’[S]为基础文法的翻译模式，其语义处理过程

7、等效于上述以G[S]为基础文法的翻译模式。3.(7pts)针对上述以G’[S]作为基础文法设计的翻译模式，构造一个自上而下的递归下降（预测）翻译程序：注：可以直接使用类似于讲稿中的MatchToken函数。为简洁，可以直接用文法终结符作为参数，例如MatchToken(ip)，假设其含义如下：（1）若当前扫描的单词与终结符ip匹配，设置ip.val，读下一个单词；（2）否则，显示词法错误，退出处理。（若自己假设了不同的MatchToken函数或其他自定义函数，请予以说明）四(12%)给定文法G(S)：S®Ab½ABcA®aA½