《编译原理》考试题

《编译原理》考试题 一、选择题:(每题2分,共20分) 1.文法G所描述的语言是 的集合。 A)文法G的字汇表V中所有符号组成的符号串 B)文法G的字汇表V的闭包V*中的所有符号串 C)由文法的识别符号推出的所有符号串 D)由文法的识别符号推出的所有终结符号串 2.设有文法G[S]=({b},{S,B},S,{S→b|bB,B→bS}),试问该文法所描述的语言是 。 A)L(G[S])={bi|i≥0} B)L(G[S])={b2i|i≥0} C)L(G[S])={b2i+1|i≥0} D)L(G[S])={b2i+1|i≥1} 3.一个句型中的最左 称为该句型的句柄。 A)短语 B)简单短语 C)素短语 D)终结符号 4. 正则文法能产生下面的语言:L={anbn|n≥1}。 A)存在一个 B)存在多个 C)不存在 D)无法判断 5.编译程序中的语法分析器接受以 为单位的输入,并产生有关信息供以后各阶段使用。 A)表达式 B)产生式 C)单词 D)语句 6.编译方法中,自顶向下的语法分析方法有 。 word文档 可自由复制编辑

A)简单优先分析方法 B)算符优先分析方法 C)SLR方法 D)LL(1)分析方法 7.简单优先分析法每次都是对 进行归约。 A)最左短语 B)简单短语 C)句柄 D)最左素短语 8.LR语法分析栈中存放的状态是识别 的DFA状态。 A)前缀 B)可归前缀 C)项目 D)句柄 9.表达式-(a+b)/(c-d)-(a+b*c)的逆波兰表示是 (@代表单目运算-)。 A)ab+cd-/@bc*a+- B)ab+/cd@bc*a+-- C)ab+@cd-/abc*+- D)ab+cd-/abc*+@- 10.乔姆斯基(Chomsky)把文法分成四种类型,即0型、1型、2型和3型。其中,3型文法是 。 A)上下文无关文法 B)上下文有关文法 C)正则文法 D)短语文法 二、填空题:(每空1分,共20分) 1.假设G是一个文法,S是文法的开始符号,如果S?*x,则称x是 。 2.已知文法G[E]:E→E+T|T,T→T*F|F,F→(E)|i;该文法的开始符号是 ,终结符号集合VT是 ,非终结符号集合VN是 ,句型T+T*F+i的短语有T+T*F+i,第一个T,T*F和 。 3.确定的有限自动机DFA是一个 ,通常表示为 。 4.LL(1)分析法中,第一个L的含义是 ,第二个L的含义是 ,“1”的含义是 。 5.自底向上语法分析方法的基本思想是:从待输入的符号串开始,利用文法的规则步步向上进行 ,试图 到文法的 。 6.在编译程序中安排中间代码生成的目的是 和 。 7.文法符号的属性有两种,一种称为 ,另一种称为 。 8.一个程序是正确的,包含两层含义:一是 ;二是 。 9.文法G产生的 全体是该文法描述的语言。 三、判断题:(每题2分,共20分) 1.符号就是字符。 2.移进—归约法是一种语法分析方法。 3.每一个NFA都对应有唯一的一个最小化的DFA。 4.编译程序的输入是高级语言程序,输出是机器语言程序。 5.编译程序与解释程序的区别在于编译程序对源程序进行了翻译,而解释程序则没有。 6.有的编译程序可以没有目标代码生成部分。 7.一个语言的文法是唯一的。 8.每一个DFA都对应有唯一的一个NFA。 9.所有的LL(K)文法都是二义性的。 10.回填就是稍后填写转移指令的地址。 四、应用题:(每题5分,共40分) 1.请消除文法G[S]:S→a|(T)|? T→T;S|S的左递归。 2.请构造语言L={anbnci|n≥1,i≥0}的文法。 3.已知文法G[S]:S→aB|bA,A→aS|bAA|a,B→bS|aBB|b,请给出串aabb的最左和最右推导。 4.为正规式(a|b)*a(a|b)构造一个非确定的有限自动机(NFA)。 5.请将图中的DFA最小化(写明过程)。 a Z a,b A a word文档 可自由复制编辑 b C b 题5图 6.考虑文法G[A]:A→A∨B|B, B→B∧C|C, C→﹁D|D,D→(A)|i,请求出该文法中各非终结符的FIRST集和FOLLOW集,并判断该文法是否是LL(1)文法。 7.请给出算术表达式-(a+b)*(c+d)-(a+b+c)的四元式序列。 8.已知某文法以LR(0)项目集为状态的识别活前缀的DFA如图所示,请构造它的LR(0)分析表。 I1:A’→A· A I0:A’→·A I2:A→(·A) A A→·(A) ( A→·(A) I4:A→(A·) A→·a A→·a ( ) a a I5:A→(A)· I3:A→a· 题8图

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4