东南大学历年编译原理考研试卷3.doc

窗体顶端东南大学历年编译原理考研试卷3返回其他资料 关闭窗口 窗体底端ID: 09758519TIMEX 发表于：2006-7-19 23:12:31 试题编号:553试题名称:编译原理一:文法G1:EET+|TTTF*|FFFP|PPE|i1.试证明符号串TET+*i是G1的一个句型(要求画出语法树).2.写出该句型的所有短语,简单短句和句柄.二:1.给出下图FA的正规式. a b a b2.已知正规文法G2:SaS|AAbBBaB|试构造一确定有限自动机DFA(要求化简),使得它接受的语言正是该文法产生的语言,要求画出状态图.三:1.试写出一个上下文无关文法G3,它能产生配对的圆括号串(例如,(),(),()()等,甚至包含0对括号).2.使用文法G3给出输入串()()#的自上而下分析过程.四:已知文法G4:SaAb|Sc|AaAb|1.给出G4文法的LR(0)项目集规范族;2.构造SLR分析表;3.G4文法所定义的语言;4.已知有如下文法及相应的LR分析表,试给出语句01001#的LR分析过程(填写下表).SAAAA1AA0LR分析表:状态 1 0 # S A0 S3 S4 1 21 acc 2 S3 S4 53 S3 S4 64 r3 r3 r3 5 S3 S4 76 r2 r2 r2 7 r1 分析过程: 状态栈 符号栈 输入串五:1.翻译下面语句成四元式中间代码序列和后缀式(逆波兰式);while x+ya doif ab) or (c=d) and not (eb and a=d;七:按语法制导翻译下段程序成四元式序列(不要优化),设数组A: array1.10,1.10 of int;每个下标变量占1字编址,数组按行存放,Z为函数名.beginAi,j:=Ai,j+2;B:=Z(Ai,j)*5end八:将如下一段四元式序列进行块内优化和循环优化(强度减弱及删除基本归纳变量),写出优化后的四元式序列.(要求先划分基本块)(1) i:=1(2) if i100 goto (10)(3) T1:=20*i(4) M:=J+T1(5) T2:=20*i(6) N:=K+T2(7) O:=M+N(8) i:=i+1(9) goto (2)(10) .九:已知如下一段程序,试给出运行时整个数据区结构.假定num初值为2,每个数据区的活动记录包含内容如下图所示,数据区从k单元开始编址. program factoral;函数返回值 var num,fact:int; function f(n:int):int 变量单元 if n0 then f:=n*f(n-1) else f:=1;display 表 begin read(num); 形参单元 fact:=f(num) end 返回地址 基SP 试题编号:553试题名称:编译原理一:已知正规文法中的左线性文法G1:SSa|Sb|c试构造无产生式的等价右线性文法,并构造相应的确定有限自动机DFA,画出状态转换图即可.二:已知正规文法(X为开始符号)G2: X0Y|1Z|0 Y0X|1Y|1 Z1X1.该文法产生语言是什么?请用正规式表示.2.构造最简的确定有限自动机DFA,并画出状态转换图.三:已知上下文无关文法(E为开始符号)G3: EET+|T TTF*|F FE|i1.消除文法左递归,并给出改写后的文法产生式;2.给出文法改写以后的各非终结符X的First(X)与Follow(X)集合,并由此判定它是否是LL(1)文法(按下表填). V(N) First(X) Follow(X)X .四:已知表达式文法(已拓广)G4: EE EE+E|i1.试构造文法G4的LR(0)项目集规范族;2.若+服从右结合率,请给出LR分析表.五:已知文法(Z为开始符号)G5: ZbMb M(Ma)|a1.试构造算符优先分析表(即填下表);a b ( ) # a b ( ) # 2.若某相邻的终结符a,b间存在a=b两种关系,那么在进行算符优先分析做归约动作时,在寻找栈顶的素短语符号串时要察看它与哪个产生式右部的符号串匹配.例如栈顶串.aAb(a,bVT,A(VA),a=b,V*)为已知可归约,而现有产生式XaAb,则取素短语aAb,若只有产生式YAb,那么就取Ab进行归约.试按此规定的算法给出语句b(aa)a)b的算符优先分析过程.六:翻译成中间代码.1.将如下程序段翻译成后缀式(逆波兰式),填在一维数组POST中,设i初值=1.t:=15;b:=20;while tb doif tb then t:=t-belse b:=b-t;2.翻译布尔表达式成转移四元式序列,并指出待填真假链序号.(ab+1) and not (c+2d) or f(x)注:f(x)为布尔函数.七:有如下一个计算m*2n的C语言程序,试给出运行时整个栈或数据区的结构.数据区的活动记录结构如图所示.函数f返回值返回结果值 局部变量区 局部变量区 全程变量区 形参单元区主程序main 返回地址 数据区 基SP 函数数据区 int m;f(n)int n; int c;if (n=0) c=m;else c=f(n-1)*2;return (c);main() int n=2;m=5;printf(%dn,f(n);八:已知如下程序段a:=1;while a=10 dobegin if ab then Aa,b:=Aa,b+2; a:=a+1;end;1.按语法制导生成四元式中间代码序列;2.将中间代码序列划分成基本块,画出程序流