华东交通大学编译原理试题库-试卷四

一:已知文法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│└─────┘