第三编译原理模拟试卷

编译原理模拟试卷（三）一、单项选择题%151、编译程序是对。a．汇编程序的翻译b．高级语言程序的解释执行c．机器语言的执行d．高级语言的翻译2、语法分析应遵循。a．语义规则b．语法规则c．构词规则d．等价变换规则3、设文法为：S→SA|AA→a|b则对句子aba，下面是规范推导。a.SSASAAAAAaAAabAabab.SSASAAAAAAAaAbaabac.SSASAASAaSbaAbaabad.SSASaSAaSbaAbaaba4、文法G：S→b|∧(T)T→T,S|S则FIRSTVT(T)。a.{b,∧,(}b.{b,∧,)}c.{b,∧,(,，}d.{b,∧,),，}5、产生正规语言的文法为。6、一个A指明了在分析过程中的某时刻所能看到产生式多大一部分。a.活前缀b.前缀c.项目d.项目集7、中间代码生成所依据的是C。a.语法规则b.词法规则c.语义规则d.等价变换规则8、四元式之间的联系是通过B实现的。a.指示器b.临时变量c.符号表d.程序变量9、后缀式ab+cd+/可用表达式B来表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d10、表达式（┓A∨B）∧（C∨D）的逆波兰表示为ERB。a.┓AB∨∧CD∨b.A┓B∨CD∨∧c.AB∨┓CD∨∧d.A┓B∨∧CD∨11、在编译时有传名功能的高级程序语言是。a.Fortranb.Basicc.Pascald.ALGOL12、栈式动态分配与管理在过程返回时应做的工作有。a.保护SPb.恢复SPc.保护TOPd.恢复TOP13、优化可生成DD的目标代码。a．运行时间较短b．占用存储空间较小c．运行时间短但占用内存空间大d．运行时间短且占用存储空间小14、下列A优化方法不是针对循优化进行的。a．强度削弱b．删除归纳变量c．删除多余运算d．代码外提15、基本块内的优化为B。a．代码外提，删除归纳变量b．删除多余运算，删除无用赋值c．强度削弱，代码外提d．循环展开，循环合并二、多项选择题%161、下面哪些说法是错误的。a.有向图是一个状态转换图b.状态转换图是一个有向图c.有向图是一个DFAd.DFA可以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了。a.多种推导过程b.多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最左推导过程3、如果文法G存在一个句子，满足下列条件之一时，则称该文法是二义文法。a.该句子的最左推导与最右推导相同b.该句子有两个不同的最左推导c.该句子有两棵不同的最右推导d.该句子有两棵不同的语法树e.该句子的语法树只有一个4、有一文法G：S→ABA→aAb|εB→cBd|ε它不产生下面集合。a.{anbmcndm|n,m≥0}b.{anbncmdm|n,m0}c.{anbmcmdn|n,m≥0}d.{anbncmdm|n,m≥0}e.{anbncndn|n≥0}5、自下而上的语法分析中，应从开始分析。a.句型b.句子c.以单词为单位的程序d.文法的开始符e.句柄6、对正规文法描述的语言，以下有能力描述它。a.0型文法b.1型文法c.上下文无关文法d.右线性文法e.左线性文法7、在词法分析中，能识别出。a.基本字b.四元式c.运算符d.逆波兰式e.常数8、令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为。a.b(ab)*b.b(ab)+c.(ba)*bd.(ba)+be.b(a|b)9、一个LR分析器包括。a.一个总控程序b.一个项目集c.一个活前缀d.一张分析表e.一个分析栈10、LR分析器核心部分是一张分析表，该表包括等子表。a.LL(1)分析b.优先关系c.GOTOd.LRe.ACTION11、每一项ACTION[S，a]所规定的动作包括。a.移进b.比较c.接受d.归约e.报错12、对LR分析表的构造，有可能存在动作冲突。a.移进b.归约c.移进/归约d.移进/移进e.归约/归约13、中间代码主要有。a．四元式b．二元式c．三元式d．后缀式e．间接三元式++cab+a+bc14、下面中间代码形式中，能正确表示算术表达式a+b+c的有。a．ab+c+b．abc++c．d．e．a+b+c15、在下面的语法制导翻译中，采用拉链-回填技术。a．赋值语句b．goto语句c．条件语句d．循环语句16、下列中间代码形式有益于优化处理。a．三元式b．四元式c．间接三元式d．逆波兰表示法e．树形表示法三、填空题%241、FORTRAN语言采用了静态存储空间分配方案，其程序所需的存储空间在编译时确定。2、一个函数的活动记录体积在时确定，数组内情向量表的体积在时确定。3、目标程序运行的动态分配策略中，含有和分配策略4、在Pascal中，由于允许用户动态地申请与释放内存空间，所以必须采用存储分配技术。5、如果两个临时变量名不相交，则它们可分配在同一单元中。6、堆式动态分配策略允许用户动态的和存储空间。7、符号表中名字栏内容有两种填写方式，它们是填写和填写。8、词法分析阶段的错误主要是，可通过的办法纠正错误。9、符号表中名字的有关信息在和过程中陆续填入。10、在目标代码生成阶段，符号表是的依据。11、中间代码有等形式，生成中间代码主要是为了使。12、语法制导翻译既可以用来产生代码，也可以用来产生指令，甚至可用来对输入串进行。13、当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持时才能确定，因而要进行。四、判断题%81、一个有限状态自动机中，有且仅有一个唯一终态。（）2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。（）3、自动机M和M′的状态数不同，则二者必不等价。（）4、确定的自动机以及不确定的自动机都能正确地识别正规集。（）5、对任意一个右线性文法G，都存在一个NFAM，满足L(G)=L(M)。（）6、对任意一个右线性文法G，都存在一个DFAM，满足L(G)=L(M)。（）7、对任何正规表达式e，都存在一个NFAM，满足L(G)=L(e)。（）8、对任何正规表达式e，都存在一个DFAM，满足L(G)=L(e)。（）五、综合题%371、下面文法G[S]是否为LL（1）文法？说明理由。%10S→AB|PQxA→xyB→bcP→dP|εQ→aQ|ε2、设有文法G[S]为：S→a|b|(A)A→SdA|S（1）给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。（2）用自下而上分析法给出输入串（adb）#的分析过程。%103、请写出在∑=（a,b）上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状态最少的DFA。%104、写出下面算术表达式E值的语义描述%7⑴E→E1+E2⑵E→0⑶E→1[解答3]根据题意，不以a开头就意味着以b开头，且以aa结尾的正规式为：b(a|b)*aa根将图2.30所示的NFA确定化，如图2.31所示。从图2.31可知已为最简状态，由于开始状态0只能输入字符b而不能与状态1合并，而状态2和状态3面对输入符号的下一状态相同，但两者一为非终态、一为终态，故也不有合并，故图2.31所示的状态转换矩阵已是最简的DFA，如图2.32所示据正规式画出NFA，如图2.30所示。图2.31状态转换矩阵abaab图3-6-8NFA将图2.30所示的NFA确定化，如图。X12Ybbbaaba图2.32最简DFA0321重新命名IIaIb{x}—{1}{1}{1,2}{1}{1,2}{1,2,Y}{1}{1,2,Y}{1,2,Y}{1}SaB0—1121231331