《编译原理》考试题 一、选择题：（每题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图