东南大学1997编译原理试题

东南大学1997编译原理试题一:文法G1:E→ET+|TT→TF*|FF→FP↑|PP→E|i1.试证明符号串TET+*i↑是G1的一个句型(要求画出语法树).2.写出该句型的所有短语,简单短句和句柄.二:1.给出下图FA的正规式.ab──→──→②→○①a↑↓ε←──←──③εb2.已知正规文法G2:S→aS|AA→bBB→aB|ε试构造一确定有限自动机DFA(要求化简),使得它接受的语言正是该文法产生的语言,要求画出状态图.三:1.试写出一个上下文无关文法G3,它能产生配对的圆括号串(例如,(),(()),()(())等,甚至包含0对括号).2.使用文法G3给出输入串(())()#的自上而下分析过程.四:已知文法G4:S→aAb|Sc|εA→aAb|ε1.给出G4文法的LR(0)项目集规范族;2.构造SLR分析表;3.G4文法所定义的语言;4.已知有如下文法及相应的LR分析表,试给出语句01001#的LR分析过程(填写下表).S→AAAA→1AA→0LR分析表:───┬──┬──┬──┰──┬──状态│1│0│#┃S│A───┼──┼──┼──╂──┼──0│S3│S4│┃1│2───┼──┼──┼──╂──┼──1│││acc┃│───┼──┼──┼──╂──┼──2│S3│S4│┃│5───┼──┼──┼──╂──┼──3│S3│S4│┃│6───┼──┼──┼──╂──┼──4│r3│r3│r3┃│───┼──┼──┼──╂──┼──5│S3│S4│┃│7───┼──┼──┼──╂──┼──6│r2│r2│r2┃│───┼──┼──┼──╂──┼──7│││r1┃│───┴──┴──┴──┸──┴──分析过程:──────┬──────┬──────状态栈│符号栈│输入串──────┼──────┼──────││││││││││││││──────┴──────┴──────五:1.翻译下面语句成四元式中间代码序列和后缀式(逆波兰式);whilex+yadoifa10thena:=a+1elsex:=x-1;2.翻译布尔表达式(ab)or(c=d)andnot(e成转移四元式序列(即四元式中仅包含(zθ,-,-,-)和(j,-,-,-)两类语句,其中θ为关系运算符.)六:1.有如下Fortran说明语句,试借助符号表登记等价环链EQ和相对数OFFSET,即填写下表的EQ栏和OFFSET栏.设每个整型量占1子编址.integera,b,c(10,10),d(10)equivalence(a,d(8),c(5,5))equivalence(b,c(5,8))符号表┌───┬─────┬───┬───┐│name│...│EQ│OFFSET│├───┼─────┼───┼───┤1│a│...│││├───┼─────┼───┼───┤2│b│...│││├───┼─────┼───┼───┤3│c│...│││├───┼─────┼───┼───┤4│d│...│││└───┴─────┴───┴───┘2.有如下pascal语言的程序轮廓,当运行该程序且第一次递归调用Q过程(即在过程Q中又调用了Q)时,数据区建立情况.假定各数据区首址用SP(i)(i=0,1,……)表示,试给出P,Q数据区的display表.┌main│┌P││┌Q│││CallQ││└││CallQ│└│┌R││CallP│└│┌S││CallR│└│CallS└七:已知如下流图,试给出回边与循环.↓┌─→①←┐│/\/│↓↓/\②③\\/↑\↓↓/┌→④──┐││↓││┌→⑤│↓/│└─⑥←─┘东南大学1998编译原理试题一:已知文法G1:S→aB|εB→bC|bDC→cB|cD→d1.试构造一个最小DFA,画出状态转换图.2.由该DFA给出它所识别的语言(用正规式表示).二:已知正规式α=ab*c*d,1.试构造一个DFAM,其接受的语言为此α(画出图);2.由该DFAM写出对应的正规文法(古线性).三:文法G3:S→A[B]A→[B]|AaB→a1.求出各非终结符N的Firstvt(N)和Lastvt(N),构造包括语句括号'#'在内的算符优先表;2.给出语句#[a][a]#的算符优先分析过程,即填写如下格式的表:步骤│栈内│输入串│动作────┼───┼────┼─────0│#│[a][a]#│...│││四:已知文法G4:T→T*F|FF→(T)|i1.试给出语句(i*i)#的自上而下分析过程(填下表);2.画出对应的语法树,指出每一步归纳的句柄.步骤│栈内│输入│动作────┼───┼────┼─────0│#T│(i*i)#│...│││五:已知文法G5:0.E'→E1.E→E+T2.E→T3.T→i列出LR(0)项目集规范族,求出各非终结符N的Follow集合,构造SLR分析表.六:翻译如下语句成四元式序列(由语法制导生成).whileabandaifa=5thenb:=b+1elserepeata:=a+1untila=d;七:按语法制导翻译下段程序成四元式序列(不要优化),设数组A:array[1..10,1..10]ofint;每个下标变量占1字编址,数组按行存放,Z为函数名.beginA[i,j]:=A[i,j]+2;B:=Z(A[i,j])*5end八:将如下一段四元式序列进行块内优化和循环优化(强度减弱及删除基本归纳变量),写出优化后的四元式序列.(要求先划分基本块)(1)i:=1(2)ifi100goto(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单元开始编址.┌─────┐programfactoral;│函数返回值│varnum,fact:int;├─────┤functionf(n:int):int│变量单元│ifn0thenf:=n*f(n-1)├─────┤elsef:=1;│display表│begin├─────┤read(num);│形参单元│fact:=f(num)├─────┤end│返回地址│├─────┤│基SP│└─────┘东南大学1999编译原理试题一:已知正规文法中的左线性文法G1:S→Sa|Sb|c试构造无ε产生式的等价右线性文法,并构造相应的确定有限自动机DFA,画出状态转换图即可.二:已知正规文法(X为开始符号)G2:X→0Y|1Z|0Y→0X|1Y|1Z→1X1.该文法产生语言是什么?请用正规式表示.2.构造最简的确定有限自动机DFA,并画出状态转换图.三:已知上下文无关文法(E为开始符号)G3:E→ET+|TT→TF*|FF→E|i1.消除文法左递归,并给出改写后的文法产生式;2.给出文法改写以后的各非终结符X的First(X)与Follow(X)集合,并由此判定它是否是LL(1)文法(按下表填).V(N)│First(X)│Follow(X)───┼─────┼───────X││───┼─────┼───────...││───┼─────┼───────││四:已知表达式文法(已拓广)G4:E'→EE→E+E|i1.试构造文法G4的LR(0)项目集规范族;2.若'+'服从右结合率,请给出LR分析表.五:已知文法(Z为开始符号)G5:Z→bMbM→(Ma)|a1.试构造算符优先分析表(即填下表);│a│b│(│)│#│──┼──┼──┼──┼──┼──┼a││││││──┼──┼──┼──┼──┼──┼b││││││──┼──┼──┼──┼──┼──┼(││││││──┼──┼──┼──┼──┼──┼)││││││──┼──┼──┼──┼──┼──┼#││││││──┼──┼──┼──┼──┼──┼2.若某相邻的终结符a,b间存在a=b两种关系,那么在进行算符优先分析做归约动作时,在寻找栈顶的素短语符号串时要察看它与哪个产生式右部的符号串匹配.例如栈顶串...aAbα(a,b∈VT,A∈(VA∪ε),a=b,α∈V*)为已知可归约,而现有产生式X→aAbα,则取素短语aAbα,若只有产生式Y→Abα,那么就取Abα进行归约.试按此规定的算法给出语句b((aa)a)b的算符优先分析过程.六:翻译成中间代码.1.将如下程序段翻译成后缀式(逆波兰式),填在一维数组POST[i]中,设i初值=1.t:=15;b:=20;whiletbdoiftbthent:=t-belseb:=b-t;2.翻译布尔表达式成转移四元式序列,并指出待填真假链序号.(ab+1)andnot(c+2注:f(x)为布尔函数.七:有如下一个计算m*2^n的C语言程序,试给出运行时整个栈或数据区的结构.数据区的活动记录结构如图所示.┌──────┐┌─────┐│函数f返回值││返回结果值│├──────┤├─────┤│局部变量区││局部变量区│├──────┤├─────┤│全程变量区││形参单元区│├──────┤├─────┤│主程序main││返回地址││数据区│├─────┤└──────┘│基SP│├─────┤│函数数据区│└─────┘intm;f(n)intn;{intc;if(n==0)c=m;elsec=f(n-1)*2;return(c);}main(){intn=2;m=5;printf(%d\n,f(n));}八:已知如下程序段a:=1;whilea=10dobeginifabthenA[a,b]:=A[a,b]+2;a:=a+1;end;1.按语法制导生成四元式中间代码序列;2.将中间代码序列划分成基本块,画出程序流图,并指出循环结点集;3.执行循环中代码外提,强度减弱优化和基本块内删除公共子表达式优化,最后画出包含优化后的中间代码的程序流图.注:数组A:array[1..10,1..10]ofint;按行存放,每个下标变量占1字编址,首地址为addrA上海交通大学1998年编译原理试题一、生成语言l={albmclanbnl=0,m=1,n=2}的文法是什么？它是chomsky那一型文法？二、文法G1：PaPQRabRRQQRBQbbbRbccRcc它是chomsky哪一型文法？请证aaabbbccc是G1的一个句子。三、文法G2:PaPbQQbQcbScSSaa1、请构造它的SLR分析表以说明它是不是SLR文法。２、在消除左递归、提取公共因子后可得等价文法Ｇ２，它是不是ll(1)文法。四、求与正规R=(ab)*a(ab)*a(ba)*等价的minＤＦＡ五、文法Ｇ3及相应翻译方案为pbQb{print:”1”}QcR{print:”2”}Qa{print:”3”}RQab{print:”4”}1、该文法是不是算符优先文法，请构造算符优先关系表证实之。2、输入串为bcccaadadb时，该翻译方案的输出是什么？六、三维数组a[2:5,-2:2,5:7]首址为100,每个数组元素占４个存储单元，2、求数组元素a(3,1,6)的地址。七、下列程序段若以Ｂ表示循环体，Ａ表示初始化，Ｉ表示增量，Ｔ表示测试。I:=1;WhileI=ndoBeginSun:=sun+a[I];I:=I+1End请用正规表达式表示这个程序段可能的执行序列。（５分）清华大学1997编译原理试题1．已知正规式：(8分)（1）(（a|b）*|aa)*b和正规式（2）（a|b）*b,试用有限自动机的等价性证明正规式（1）和（2）是等价的,给出相应的正规文法。2．已知文法G[A]为：(8分)A→aABl|aB→Bb|d①试给出与G[A]等价的LL（1）文法G[A]②构造G'[A]的预测分析表给出输入串aade#的分析过程。3．有文法G[S]为：(8分)S→a|b|（A）A→SdA|S完成下列算符优先关系表，并判断G[S]是否为