《郑州大学编译原理试卷及复习资料往年试题整合.docx》由会员分享，可在线阅读，更多相关《郑州大学编译原理试卷及复习资料往年试题整合.docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、二填空题1.不同的编译程序关于数据空间的存储分配策略可能不同，但大局部编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为1和2。2.标准规约是最3规约。3.编译程序的工作过程一般划分为5个阶段：词法分析、4、语义分析及中间代码生成，代码优化及5。另外还有6和出错处理。4表达式x+y*z/(a+b)的后缀式为7。5文法符号的属性有综合属性和8。6假设二位数组按行存放，而且每个元素占用一个存储单元，那么数组a1.15,1.20某个元素ai，j的地址计算公式为9。7局部优化是局限于一个10范围内的一种优化。答案(1)栈式动态存储分配 (2)堆式动态存储分配 (3)左 (4)语法
2、分析 (5)目标代码生成 (6)表格管理 (7)xyz*ab+/+ (8)继承属性(9)a+(i-1)*20+j-1(10)根本块8 词法规那么通常可以用_正规式_，正规文法、_自动机_描述；语法规那么通常用_2型文法_来描述；语义规那么通常用_属性文法_来描述。9 编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段。1.()称为标准推导。，和五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，那么称这个文法是。4.从功能上说，程序语言的语句大体可分为语句和语句两大类。5.语法分析器的输入是，其输出是。6.扫描器的任务是从中识别出一个个。7.符号表中
3、的信息栏中登记了每个名字的有关的性质，如等等。8.一个过程相应的DISPLAY表的内容为。9.一个句型的最左直接短语称为句型的。10.常用的两种动态存贮分配方法是动态分配和动态分配。11.一个名字的属性包括()和()。12.常用的参数传递方式有，和。13.根据优化所涉及的程序范围，可将优化分成为，和三个级别。14.语法分析的方法大致可分为两类，一类是分析法，另一类是分析法。15.预测分析程序是使用一张和一个进展联合控制的。16.常用的参数传递方式有，和。17.一张转换图只包含有限个状态,其中有一个被认为是态;而且实际上至少要有一个态。18.根据优化所涉及的程序范围，可将优化分成为，和三个级别。
4、19.语法分析是依据语言的规那么进展。中间代码产生是依据语言的规那么进展的。20.一个句型的最左直接短语称为句型的。21.一个文法G，假设它的预测分析表M不含多重定义，那么该文法是文法。22.对于数据空间的存贮分配，FORTRAN采用()策略，PASCAL采用()策略。23.如果一个文法存在某个句子对应两棵不同的语法树，那么称这个文法是()。24.最右推导亦称为，由此得到的句型称为句型。25.语法分析的方法大致可分为两类，一类是分析法，另一类是分析法。26.对于文法G，仅含终结符号的句型称为()。27.所谓自上而下分析法是指。28.语法分析器的输入是，其输出是。29.局限于根本块范围的优化称。
5、30.预测分析程序是使用一张和一个进展联合控制的。31.2型文法又称为文法；3型文法又称为文法。32.每条指令的执行代价定义为。33.算符优先分析法每次都是对进展归约。答案参考答案：1.(最右推导2.(词法分析，语法分析，中间代码生成，代码优化，目标代码生成3.(二义性的4.(执行性，说明性5.(单词符号，语法单位。6.(源程序，单词符号7.(类型、种属、所占单元大小、地址8.(现行活动记录地址和所有外层最新活动记录的地址)9.(句柄10.(栈式)，堆式11.(类型)，作用域12.(传地址，传值，传名13.(局部优化，循环优化，全局优化14.(自上而下，自下而上15.(分析表，符号栈16.(传
6、地址，传值，传名17.(初，终18.(局部优化，循环优化，全局优化19.(语法，语义20.(句柄21.(LL(1)文法22.(静态，动态23.(二义性文法24.(标准推导，标准25.(自上而下，自下而上26.(句子)27.(从开场符号出发，向下推导，推出句子28.(单词符号，语法单位29.(局部优化30.(分析表，符号栈31.(上下文无关文法，正规32.(指令访问主存次数加133.(最左素短语三解答题共60分1共15分文法GE:EETE|E|iT*|+1将文法G改造成LL1文法；5分2构造文法G中每个非终结符的FIRST集合及FOLLOW集合；5分3构造LL1分析表。5分2共12分给定文法GS
7、：SS(S)|1给出句子()()()()的标准推导过程；4分2指出每步推导所得句型的句柄；4分3画出该句子的语法推导树。4分答案11文法存在左递归，消除左递归后的文法为：E(E)E|iE2分ETEE|2分T*|+1分FIRST(E)=(,i FIRST(E)=*,+,FIRST(T)=*,+FOLLOW(E)=),*,+,# FOWLLOW(E)=),*,+,# FOLLOW(T)=(,i1.写一个文法G,使其语言为不以0开头的偶数集。2.文法G(S)及相应翻译方案SaAbprint“1Saprint“2AASprint“3Acprint“4输入acab,输出是什么？3.文法G(S)SbAaA
8、(B|aBAa)写出句子b(aa)b的标准归约过程。4.考虑下面的程序：procedurep(x,y,z)；beginy:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A,A,B);PrintA,Bend.试问，假设参数传递的方式分别采用传地址和传值时，程序执行后输出A,B的值是什么?5.文法G(S)SdABAaA|aBBb|描述的语言是什么？6.证明文法G(S)SSaS|是二义性的。7.文法G(S)SBAABS|dBaA|bS|c的预测分析表如下abcd#SSBASBASBAAABSABSABSAdBBaABbSBc给出句子adccd的分析过程。8.写一个文法G,使其语
9、言为L(G)=albmclanbn|l=0,m=1,n=29.文法G(S):Sa|(T)TT,S|S的优先关系表如下：关系a(),a-.(.=.,.请计算出该优先关系表所对应的优先函数表。10.何谓优化？按所涉及的程序范围可分为哪几级优化？11.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？=a,b，试写出上所有以a为首的字组成的正规集相对应的正规式13.根本的优化方法有哪几种？14.写一个文法G,使其语言为L(G)=abncn|n015.考虑下面的程序：procedurep(x,y,z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b,b
10、,a);printaend.试问，假设参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么?16.写出表达式ab*(c-d)/e的逆波兰式和三元序列。17.证明文法G(A)AAA|(A)|是二义性的。=a,b，那么正规式a*b|b*a表示的正规集是什么？19.何谓DISPLAY表？其作用是什么？20.考虑下面的程序：procedurep(x,y,z)；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b,a-b,a);printaend.试问，假设参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么?21.写一个文法G,使其语言为L(G)
11、=anbncm|n0为奇数，m0为偶数22.写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。23.一个文法G别是LL(1)文法的充要条件是什么？24.文法GSSS*aF|aF|*aFF+aF|+a消除文法左递归和提公共左因子。25.符号表的作用是什么？符号表查找和整理技术有哪几种？答案：.1所求文法是GS:SAB|BA0AAD|CB2|4|6|8C1|3|5|7|9|BD0|CA=6,B=16传值A=2,B=45.L(G)=danbm|n0,m06.证明：因为文法GS存在句子aa有两个不同的最左推导，所以文法GS是是二义性的。S=SaS=SaSaS=aSaS=aaS=aaS
12、=SaS=aS=aSaS=aaS=aa8.所求文法是GS:SABAaAc|DDbD|bBaBb|aabb10.优化：对程序进展各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用存放器，以减少访问内存次数；(3)如何充分利用指令系统的特点。a(a|b)*。13.删除多余运算，代码外提，强度削弱，变换循环控制条件，合并量，复写传播和删除无用赋值。14.文法GS:SaB|aBbc|bBca=2传地址a=1516.
13、逆波兰式:abcd-*e/+三元序列:oparg1arg2(1)-cd(2)*b(1)(3)/(2)e(4)+a(3)17.证明：因为文法GS存在句子()有两个不同的最左推导，所以文法GS是是二义性的。A=AA=(A)A=()A=()A=AA=A=(A)=()18.(a*b|b*a)=a,b,ab,ba,aab,bba19.Display表:嵌套层次显示表由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，display表就是用于登记每个外层过程的最新活动记录起始地址。a=12传值a=521.所求文法是GS:SACAaaAbb|
14、abCccC|cc23.一个文法G别是LL(1)文法的充要条件是:(1)FIRST()FIRST()=(2)如果=*,FIRST()FOLLOW(A)=SaFS|*aFSS*aFS|F+aF|+a提公共左因子,文法G(S)SaFS|*aFSS*aFS|F+aFFF|25.作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。主要技术：线性表，对折查找，杂奏技术。三、简答题：每题7分，共28分说明：将答案写在试卷后面的答题纸上1、文法GEE-E+T|E-T|TT-T*F|T/F|FF-(E)|i证明F+T-T*(E-T)是文法的句型，并给出该句型的短语、直接短语和句柄。2、给出语句WhileABDoIf(CAa|bA-Ac|Sd4、文法G：S-aBc|bABA-aAb|bB-b|e判断该文法是否是LL1文法，并说明理由。四、综合题：共27分说明：将答案写在试卷后面的答题纸上1、正规式10|1*101构造一个最小化的DFA。15分2、文法GA:A(A)|a,构造该文法的LR0分析表。12分第 5 页