吉林大学2004级《编译原理》期末考试试题A第页共NUMPAGES4页2006-2007学年第1学期2004级《编译原理》期末考试试题A考试时间：2007年1月16日填空题（每空1分，共20分）高级语言的实现方式主要有：____________、____________和____________。一个上下文无关文法所含四个组成部分是____________、____________、____________、____________。设有文法G1，它的部分LL(1)分析表如下，将该表补充为一个完整的LL(1)分析表，将其画在答题纸上。G1:S->aBc[1]|bAB[2]A->aAb[3]|b[4]B->b[5]|ε[6]abc#S12A34B设有文法G2，它的部分LR(1)状态机如下，将其中的状态0，状态1，状态2和状态3填写完整，将其画在答题纸上。G2:S->TT->T(T)T->ε????TT(正则表达式RE和有限自动机DFA的描述能力是____________的。表示空串ε的自动机的状态转换图表示为___________________。四元式(ENDWHILE,_____,_____,_____)的作用是__________和__________。为安全起见，循环不变式外提优化时，__________运算和__________运算不外提。填空题（每空2分，共20分）设有二义性文法G3，则句子--a-bc的所有可能语法树有_____课。设有文法G4，则句型（a,S）的句柄为__________。设有文法G5，则非终级符R的Follow集是__________。设有如下文法G6，符号（和L的简单优先关系为__________。假设采用局部Display表的方法建立变量访问环境，局部Display表相对于活动记录起始地址的偏移用D表示，当前过程层数为n。若用()分别代表第i层过程的活跃活动记录的起始地址，变量x的抽象地址是（L,off），其中L<n，则变量x的绝对地址是__________。同心状态合并时，可能会引起_____________冲突，一定不会引起__________冲突。表达式的后缀式表示为_____________________________。目标代码中撤销活动记录的两条指令是_______________和_______________。简答题（每小题5分，共30分）整型数据占1个单元，实型数据占2个单元，写出下列类型的内部表示。A:array[1..5]ofarray[1..10]ofrecordx:integer;y:realend设数组按行存储，写出计算下标变量A[i][j]地址的四元式，其中数组A的类型如题1声明。什么是过程活动记录？它主要由哪些内容构成？变量访问环境的作用是什么？变量标识符的语义信息一般需要包括哪些内容？考虑下面程序ProcedureQ(B,C)BeginB:=B+2;B:=B*C;End;BeginY:=2;Q(Y,2*Y);Print(Y);End;当参数传递方式分别采取传值和传地址方式时，程序执行后输出Y的值是什么？综合题（每小题10分，共30分）将下列四元式序列划分为基本块。B1:(ASSIG,10,-,1)B2:(WHILE,-,-,-)(>,i,0,t1)(DO,t1,-,-)B3:(>,x,y,t2)(THEN,-,-,-)B4:(SUBI,x,y,t3)(ASSIG,t3,-,x)(ELSE,-,-,-)B5:(SUBI,y,x,t4)(ASSIG,t4,-,x)B6:(endif,-,-,-)(SUBI,i,1,t5)(ASSIG,t5,-,i)(ENDWHILE,-,-,-)B7:(ASSIG,0,-,z)已知文法G7，写出它的递归下降分析程序。有如下的变量声明和过程声明，写出对应的符号表的内容。变量标识符和过程标识符的属性信息同教材一致。设当前层数为L,当前偏移为Off，整数类型占1个单元，且形参的起始偏移为Off（），类型at表示包含10个整数元素的数组，内部表示的指针为atptr。varx,y:at;procedurep(vara:at;b:at;varx:at;functionf():integer)