搜索
合肥工业大学试卷（A、B√）20～20学年第学期课程代码课程名称学分课程性质:必修×选修、限修考试形式:开卷、闭卷专业班级（教学班）考试日期命题教师系（所或教研室）主任审批签名张炳武命题教师注意事项:1、主考教师必须于考试一周前将“试卷A”、“试卷B”经教研室主任审批签字后送教务科印刷。2、请命题教师用黑色水笔工整地书写题目或用A4纸横式打印贴在试卷版芯中。、××××（1）构造识别正规式10|（0|11）0*1的极小化DFAM（需写过程）。（10分）（2）（a）给出接受可被5整除的二进制串集（不含空串）的极小化DFAN；（5分）（b）给出产生可被5整除的二进制串集（不含空串）的上下文无关文法G0；（5分）（c）针对你写的文法G0，写一个翻译方案，输出文法所生成的二进制串的十进制数值。（10分）（3）（a）针对文法G1，写一个语法制导定义，统计输入串中字符a、b的个数；（10分）（b）删除文法G1中的左递归；（5分）（c）给出递归下降分析程序。（10分）（4）文法G2和G3中有一个是二义性文法，另一个是非二义性文法。（a）针对其中的二义性文法，用串aabbab证明其二义性；（5分）（b）针对其中的文法G3，给出读过活前缀aabbab所经过的所有LR（1）项目集簇（状态）。（10分）（5）给出以下C程序片段的三地址代码（假设相关名字均为整型变量或整型数组）；（15分）文法G1，L为开始符号。L→Ra|TbaR→aba|caba|RbcT→bbc|bc文法G2，S为开始符号。S→aBS|bASS→注：此为空产生式A→a|bAAB→b|aBB文法G3，S为开始符号。S→aB|bAS→注：此为空产生式A→aS|bAAB→bS|aBBfor(i=2;in;i++){r=k;while(D[J[r]]D[j]&&D[J[r]]r)r=r-1;if(D[J[r]]=D[i]&&D[i]r){for(m=k;mr+1;m--)J[m+1]=J[m];J[r+1]=i;k=k+1;}}//第（5）题C程序片段#includestdio.hintf(intx,int*y,int**z){**z+=1;*y+=2;x+=3;returnx+*y+**z;}intmain(){int**a,*b,c=4;a=&b;b=&c;printf(%d\n,f(c,b,a));return0;}//第（6）题C程序.filec5.c.text.globlf.typef,@functionf:pushl%ebpmovl%esp,%ebpmovl16(%ebp),%eaxmovl(%eax),%edxmovl16(%ebp),%eaxmovl(%eax),%eaxmovl(%eax),%eaxincl%eaxmovl%eax,(%edx)movl12(%ebp),%edxmovl12(%ebp),%eaxmovl(%eax),%eaxaddl$2,%eaxmovl%eax,(%edx)addl$3,8(%ebp)movl12(%ebp),%eaxmovl○1,%eaxaddl○2,%eaxmovl○3,%edxmovl○4,%edxaddl○5,%eaxleaveret//第（6）题函数f的汇编代码.section.rodata.LC0:.string%d\n.text.globlmain.typemain,@functionmain:pushl%ebpmovl%esp,%ebpsubl$24,%espandl$-16,%espmovl$0,%eaxsubl%eax,%espmovl$4,-12(%ebp)leal○6,%eaxmovl%eax,○7leal○8,%eaxmovl%eax,○9subl$8,%espsubl$12,%esppushl○10pushl○11pushl○12callfaddl$24,%esppushl%eaxpushl$.LC0callprintfaddl$16,%espmovl$0,%eaxleaveret//第（6）题//函数main的汇编代码（6）仔细阅读所给C程序。问：（a）C程序输出结果如何？（3分）（b）补全12个下划线处的空白汇编代码。（12分）合肥工业大学试卷（A、B√）20～20学年第学期课程代码课程名称学分课程性质:必修×选修、限修考试形式:开卷、闭卷专业班级（教学班）考试日期命题教师系（所或教研室）主任审批签名张炳武命题教师注意事项:1、主考教师必须于考试一周前将“试卷A”、“试卷B”经教研室主任审批签字后送教务科印刷。2、请命题教师用黑色水笔工整地书写题目或用A4纸横式打印贴在试卷版芯中。、××××参考解答：(1)首先，构造识别正规式10|（0|11）0*1的NFA，如下：然后，由子集构造法得到DFA：输入状态子集01{0}{3}{1,2}{3}{3}{4}{1,2}{4}{3}{4}――――最后，通过极小化，得到最终DFA：(2)（a）构造的DFA为：（b）识别同样串集的CFGG0，如下：设状态S对应非终结符S，状态0～4，分别对应非终结符A～E。S→0A|1BA→0A|1BA→注：此为空产生式B→0C|1DC→0E|1AD→0B|1CE→0D|1E（c）针对文法G0，翻译方案如下：继承属性i表示在读新串前、已读入的二进制串的（十进制）值；综合属性s表示读入新串后、所有读入的二进制串的（十进制）值。S→0{A.i=0;}A{print(A.s);}|1{B.i=1;}B{print(B.s);}A→0{A1.i=2*A.i;}A1{A.s=A1.s;}|1{B.i=2*A.i+1;}B{A.s=B.s}A→{A.s=A.i;}注：此为空产生式B→0{C.i=2*B.i;}C{B.s=C.s;}|1{D.i=2*B.i+1;}D{B.s=D.s;}C→0{E.i=2*C.i;}E{C.s=E.s;}|1{A.i=2*C.i+1;}A{C.s=A.s;}D→0{B.i=2*D.i}B{D.s=B.s;}|1{C.i=2*D.i+1;}C{D.s=C.s;}E→0{D.i=2*E.i;}D{E.s=D.s;}|1{E1.i=2*E.i+1;}E1{E.s=E1.s;}（3）（a）语法制导定义如下：产生式语法制导定义S→LPrint(L.a,L.b)L→RaL.a=R.a+1;L.b=R.bL→TbaL.a=T.a+1;L.b=T.b+1R→abaR.a=2;R.b=1R→cabaR.a=2;R.b=1R→R1bcR.a=R1.a;R.b=R1.b+1;T→bbcT.a=0;T.b=2T→bcT.a=0;T.b=111001031241010010231011S0123401010101001合肥工业大学试卷（A、B√）20～20学年第学期课程代码课程名称学分课程性质:必修×选修、限修考试形式:开卷、闭卷专业班级（教学班）考试日期命题教师系（所或教研室）主任审批签名张炳武命题教师注意事项:1、主考教师必须于考试一周前将“试卷A”、“试卷B”经教研室主任审批签字后送教务科印刷。2、请命题教师用黑色水笔工整地书写题目或用A4纸横式打印贴在试卷版芯中。、××××（b）删除左递归产生式R中含有直接左递归，删除之：R→abaY|cabaYY→bcYY→注：此为空产生式此外，产生式T中含有左因子，也必须提出，如下：T→bZZ→bc|c（c）递归下降分析程序如下：voidL(){if(lookhead==’a’||lookhead==’c’){//L→RaR();match(’a’);}elseif(lookhead==’b’){//L→TbaT();match(’b’);match(’a’);}elseerror();}voidR(){if(lookhead==’a’){//R→abaYmatch(’a’);match(’b’);match(’a’);Y();}elseif(lookhead==’c’){//R→cabaYmatch(’c’);match(’a’);match(’b’);match(’a’);Y();}elseerror();}voidY(){if(lookhead==’b’){//Y→bcYmatch(’b’);match(’c’);Y();}elseif(lookhead==’a’)return;elseerror();}voidT(){if(lookhead==’b’){//T→bZmatch(’b’);Z();}elseerror();}voidZ(){if(lookhead==’b’){//Z→bcmatch(’b’);match(’c’);}elseif(lookhead==’c’){//Z→cmatch(’c’);}elseerror();}（4）（a）文法G3为二义性文法。文法G3，S为开始符号。S→aB|bAS→注：此为空产生式A→aS|bAAB→bS|aBB输入串为aabbab推导1：S＝aB=aaBB=aabSB=aabB=aabbS=aabbaB=aabbabS=aabbab推导2：S＝aB=aaBB=aabSB=aabbAB=aabbaSB=aabbaB=aabbabS=aabbab（b）G2为非二义性文法。S→aBS|bASS→注：此为空产生式A→a|bAAB→b|aBB合肥工业大学试卷（A、B√）20～20学年第学期课程代码课程名称学分课程性质:必修×选修、限修考试形式:开卷、闭卷专业班级（教学班）考试日期命题教师系（所或教研室）主任审批签名张炳武命题教师注意事项:1、主考教师必须于考试一周前将“试卷A”、“试卷B”经教研室主任审批签字后送教务科印刷。2、请命题教师用黑色水笔工整地书写题目或用A4纸横式打印贴在试卷版芯中。、××××