您好,欢迎访问三七文档
1编译原理试题一、单项选择题1.将编译程序分成若干个“遍”是为了(B)A.提高程序的执行效率B.使程序的结构更加清晰C.利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率2.不可能是目标代码的是(D)A.汇编指令代码B.可重定位指令代码C.绝对指令代码D.中间代码3.词法分析器的输入是(B)A.单词符号串B.源程序C.语法单位D.目标程序4.中间代码生成时所遵循的是(C)A.语法规则B.词法规则C.语义规则D.等价变换规则5.编译程序是对(D)A.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译6.词法分析应遵循(C)A.语义规则B.语法规则C.构词规则D.等价变换规则7.词法分析器的输出结果是(C)A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和属性值D.单词属性值8.正规式M1和M2等价是指(C)A.M1和M2的状态数相等B.M1和M2的有向弧条数相等C.M1和M2所识别的语言集相等D.M1和M2状态数和有向弧条数相等9.词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确,因此,(B)A.词法分析器应作为独立的一遍B.词法分析器作为子程序较好C.词法分析器分解为多个过程,由语法分析器选择使用.D.词法分析器并不作为一个独立的阶段10.如果L(M1)=L(M2),则M1与M2(A)A.等价B.都是二义的2C.都是无二义的D.它们的状态数相等11.文法G:S→xSx|y所识别的语言是(C)A.xyxB.(xyx)*c.xnyxn(n≥0)d.x*yx*12.文法G描述的语言L(G)是指(A)A.*,|)(TVSGLB.*)(,|)(NTVVSGLC.**,|)(TVSGLD.**)(,|)(NTVVSGL13.有限状态自动机能识别(C)A.上下文无关文法B.上下文有关文法C.正规文法D.短语文法14.如果文法G是无二义的,则它的任何句子(A)A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导,但它们对应的语法树相同15.由文法的开始符经0步或多步推导产生的文法符号序列是(C)A.短语B.句柄C.句型D.句子16.文法G:E→E+T|TT→T*P|PP→(E)|i则句型P+T+i的句柄为(B)A.P+TB.PC.P+T+iD.i17.文法G:S→b|∧|(T)T→T∨S|S则FIRSTVT(T)=(C)A.{b,∧,(}B.{b,∧,)}C.{b,∧,(,∨}D.{b,∧,),∨}18.产生正规语言的文法为(D)A.0型B.1型C.2型D.3型19.任何算符优先文法(D)优先函数。A.有一个B.没有C.有若干个D.可能有若干个20.采用自上而下分析,必须(A)A.消除左递归B.消除右递归C.消除回溯D.提取公共左因子321.在规范归约中,用(B)来刻画可归约串。A.直接短语B.句柄C.最左素短语D.素短语22.有文法G:E→E*T|TT→T+i|i句子1+2*8+6按该文法G归约,其值为(B)A.23B.42C.30D.1723.如果文法是无二义的,那么规范归约是指(B)A.最左推导的逆过程B.最右推导的逆过程C.规范推导D.最左归约的逆过程24.文法G:S→S+T|TT→T*P|PP→(S)|i句型P+T+i的短语有(B)A.i,P+TB.P,P+T,i,P+T+iC.P+T+iD.P,P+T,i25.四元式之间的联系是通过(B)实现的。A.指示器B.临时变量C.符号表D.程序变量26.后缀式ab+cd+/可用表达式(B)来表示。A.a+b/c+dB.(a+b)/(c+d)C.a+b/(c+d)D.a+b+c/d27.使用间接三元式表示法的主要目的(A)A.便于优化处理B.便于表的修改C.节省存储空间D.生成中间代码更容易28.表达式(┐A∨B)∧(C∨D)的逆波兰表示为(B)A.┐AB∨∧CD∨B.A┐B∨CD∨∧C.AB∨┐CD∨∧D.A┐B∨∧CD∨二、判断题1.一个确定有限状态自动机中,有且仅有一个唯一的终态。(╳)2.设R和S分别是字母表∑上的正规式,则有L(R|S)=L(R)∪L(S)。(√)3.自动机M1和M2的状态数不同,则二者必不等价。(╳)4.确定有限自动机以及非确定有限自动机都能正确地识别正规集。(√)5.对任意一个右线性正规文法G,都存在一个NFAM,满足L(G)=L(M)。(√)6.对任意一个右线性正规文法G,都存在一个DFAM,满足L(G)=L(M)。(√)7.对任何正规式e,都存在一个NFAM,满足L(M)=L(e)。(√)8.对任何正规式e,都存在一个DFAM,满足L(M)=L(e)。(√)9.从一个句型到另一个句型的推导过程是唯一的。(╳)10.词法分析作为单独的一遍来处理较好。(╳)411.一张转换图只包含有限个状态,其中有一个被认为是初态,最多只有一个终态。(╳)12.二义文法不是上下文无关文法。(╳)13.自上而下分析法是一种“移进—归约”法。(╳)14.文法是描述语言的语法结构的形式规则。(√)15.产生式是定义语法范畴的一种书写规则。(√)16.要构造行之有效的自上而下的分析器,则必须消除左递归。(╳)17.如果文法G是无二义的,那么规范归约和规范推导是互逆的两个过程。(√)18.自下而上的分析法是一种“移进—归约”法。(√)19.如果文法G是二义的,那么规范归约和规范推导是互逆的两个过程。(╳)三、填空题1.解释程序和编译程序的区别在于(是否生成目标代码)。2.编译过程通常可分为5个阶段,分别是(词法分析)、(语法分析)、语义分析与中间代码产生、代码优化和目标代码生成。3.编译程序工作过程中,第一阶段输入是(源程序),最后阶段的输出为(目标代码)程序。4.把语法范畴翻译成中间代码所依据的是(语义规则)。5.目标代码可以是(汇编)指令代码或(可重定位)指令代码或绝对机器指令代码。6.词法分析的任务是:输入源程序,对构成源程序的(字符串)进行扫描和分解。7.源程序中的错误通常分为(语法错误)和(语义错误)两大类。8.(编译程序)是将源程序翻译成目标程序的程序。9.一个上下文无关文法G包括四个部分:(终结符号)、(非终结符号)、(开始符号)和一组(产生式)。10.若n21,则称这个序列是从1到n的一个(推导)。11.设文法G的开始符号为S,如果*S则称是L(G)的一个(句型)。12.文法G所产生的句子的全体是文法G所定义的(语言)。13.若一个文法存在某个句子对应的两棵不同的语法树,则称这个文法是(二义文法)。14.程序语言的单词符号一般可分为五种:(关键字)、(标识符)、常数、(运算符)和界符。15.(确定有限自动机DFA)是非确定有限自动机NFA的一个特例。16.对于正规文法G和有限自动机M,若L(G)=L(M),则称G和M是(等价)的。17.若两个正规式所表示的正规集相等,则认为二者是(等价)的。18.按照语法分析树的建立方法,语法分析可分为两类:(自上而下分析)和(自下而上分析)。18.规范归约中的可归约串是指(句柄)。519.算符优先分析中的可归约串是指(最左素短语)。20.(自下而上)语法分析的关键问题是精确定义可归约串的概念。四、简答1.给出上下文无关文法的定义。一个上下文无关文法G是一个四元式(VT,VN,S,P),其中:VT是一个非空有限集,它的每个元素称为终结符号;VN是一个非空有限集,它的每个元素称为非终结符号,VT∪VN=Φ;S是一个非终结符号,称为开始符号;P是一个产生式集合(有限),每个产生式的形式是P→α,其中,P∈VN,α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。2.给出正规式与正规集的递归定义。(1)ε和Φ都是∑上的正规式,它们所表示的正规集分别为{ε}和Φ;(2)任何a∈∑,a是∑上的一个正规式,它所表示的正规集为{a};(3)假定U和V都是∑上的正规式,它们所表示的正规集分别记为L(U)和L(V),那么,(U|V)、(U·V)和(U)*也都是正规式,它们所表示的正规集分别为L(U)∪L(V)、L(U)L(V)(连接积)和(L(U))*(闭包)。仅由有限次使用上述三步骤而得到的表达式才是∑上的正规式。仅由这些正规式所表示的字集才是∑上的正规集。3.设文法G为:S→aAcB|BdSA→BaB|aBc|aB→aScA|cAB|b对于输入串aacabccb,给出最左推导。S=aAcB=aaBccB=aacABccB=aacaBccB=aacabccB=aacabccb4.设文法G为:S→BAA→BS|dB→aA|bS|c对于输入串adccd,给出最左推导。S=BA=aAA=adA=adBS=adcS=adcBA=adccA=adccd65.证明:文法G:P→PaP|PbP|cP|Pe|f为二义文法。对于文法G定义的句子fbfbf,有两棵不同的语法树:所以该文法是二义文法。6.证明:文法G:P→S+S|S*S|i|(S)为二义文法。对于文法G定义的句子i+i*i,有两棵不同的语法树:所以该文法是二义文法。7.给定正规文法G:S→aS|bA|bA→aS请构造与之等价的有限自动机。PPPbPPbfffPPPbPPfffbSSS*SS+iiiSSS+SSiii*SfAabab78.给定正规文法G:S→aAA→bA|aB|bB→aA请构造与之等价的有限自动机。9.对下面给出的NFA确定化。10.对下面给出的NFA确定化。ABDFbbaaSaSFDAababaSBDAaaaab24D3abaa1aa8或11.对下面给出的DFA最小化。a24D3aaa1bb13D2abaabaADDBabaSabCbbaa23D1aaabb912.对下面给出的DFA最小化。13.有如下布尔表达式:aband(cdoref)假定整个表达式的真假出口分别为Ltrue和Lfalse,请翻译成三地址语句。ifabgotoL1gotoLfalseL1:ifcdgotoLtruegotoL2L2:ifefgotoLtruegotoLfalse14.有如下语句:ifabthenifcdthenp:=a+1elsep:=b+1elsep:=c+1请翻译成三地址语句。ifabgotoL1gotoL2L1:ifcdgotoL3gotoL4L3:T1:=a+1p:=T1bADDBbaaSaCbababb24D3baa1abba10gotoL5L4:T2:=b+1p:=T2L5:gotoLnextL2:T3:=c+1p:=T3Lnext:…五、语法分析1.设有文法G:S→a|b|(A)A→SdA|S⑴完成下列算符优先关系表,并判断是否为算符优先文法(请说明理由)。ab()d#a·>·>·>b·>·>·>(<·<·<·=<·)·>·>·>d<·<·<··><··>#<·<·<·=由于该文法的任何产生的右部都不含两个相继的非终结符,故属于算符文法。从上表可以看出,任何两个终结符之间至多满足=、<·、·>三种关系之一,故G为算符优先文法。⑵给出句型(SdSdS)对应的语法树,指出该句型的短语、句柄S()ASAdSSAd11短语:(SdSdS)SdSdSSdSS句柄:S2.设有文法G:S→S*F|FF→F↑P|PP→(S)|i⑴完成下列算符优先关系表,并判断是否为算符优先文法(请说明理由)。*↑()i#*·><·<··><··>↑·>·><··><··>(<·<·<·=<·)·>·>·>·>i·>·>·>·>#<·<·<·<·=由于该文法的任何产生的右部都不含两个相继的非终结符,故属于算符文法。从上表可以看出,任何两个终结符之间至多满足=、<·、·>三种关系之一,故G为算符优先文法。⑵给出句型S*P↑(S)对应的语法树,指出该句型的短
本文标题:编译原理试题
链接地址:https://www.777doc.com/doc-1502128 .html