编译原测验题要点讲解.doc

第1-2章测试题 一、选择题 1． 文法 G 产生的_____的全体是该文法描述的语言。 　A．句型 　　 B． 终结符集 　　C．非终结符集 　　D． 句子 2． 若文法 G 定义的语言是无限集，则文法必然是 _____。? 　A．递归的 ? 　 　B．前后文无关的　? C．二义性的 　　 D． 无二义性的 ． 一个文法所描述的语言是_____。 A． 唯一的 　 ? 　　 ? 　 ? 　　?B． 不唯一的 　??C．可能唯一，好可能不唯一 ? 　　D．都不对 ．_____是两类程序语言处理程序。 　A． 高级语言程序和低级语言程序 ??????? 　　B． 解释程序和编译程序 　C． 编译程序和操作系统 ??????????????? 　　D． 系统程序和应用程序 . 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 　A．句子 　 　　 B．句型　C． 单词 　　　 D． 产生式 已知文法G(E) 　　 E→T|E＋T 　　 T→F|T *F 　　 F→(E)|i 句型(T F)*i+T (1)画出句型的语法树；  (2)给出句型的短语、。→ S＋ | S*S | i |（S） （1）对于输入串i+i*i给出一个最左推导； （2）该文法是否是二义性文法？请证明你的结论。 第3章测试题 一、选择题 1．词法分析器用于识别_____。?A． 字符串 ? B．语句C． 单词　　D．标识符 ．词法分析器的输出结果是_____。A．单词的种别编码 B．单词在符号表中的位置 C．单词的种别编码和自身值 D． 单词自身值．_____。A．B．C．D．构造正规式 1(0|1)*101 相应的DFA构造正规式 1(0|1)*101 相应的DFA解：先构造NFA： 确定化： 重新命名，令AB为B、AC为C、ABY为D得： 所以，可得DFA为： 已知 NFA=（ {x,y,z},{0,1},M,{x},{z} ），其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)= φ ,M(z,1)={y}, 构造相应的DFA并最小化。NFA图: 下表由子集法将NFA转换为DFA： 下面将该DFA最小化： (1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F} (2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。 (3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。 (5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下： 1．在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_____。 A.非终符集 ????? B．终符集 ?????? C．字母表 ????? D.状态集 ． 在自向的语法分析方法中，分析的关键是_____。 A.寻找句柄 ??????? B.寻找句型 ????? C. 消除递归 ????? D.选择候选式 分析器用于识别_____。?A．字符串 ? B．语句C．单词　　D．标识符 ．_____。A．B．C．D．．在规范归约中，用_____来刻画可归约串。 A．直接短语 B．句柄 C．最左素短语 ? 　D．素短语 ?设文法G(S)： S→(L) | a S | a L→L，S | S (1) 消除左递归和回溯； (2) 计算每个非终结符的和 解：(1) 　　　　　　　　　S→(L)|aS 　　　　　　　　　 S→S|ε 　　　　　　　　　 L→SL 　　　　　　　　　 L→SL|ε 　　 　　 　 (2) 　　　　　　　　FIRST)S)＝{(，a}　　　　FOLLOW(S)＝{#，，，)} 　　　　　　　　 FIRST(S)＝{，a,ε}　　FOLLOW(S)＝{#，，，)} 　　　　　　　　　 FIRST(L)＝{(，a}　　　FOLLOW(L)＝{ )} 　　　　　　　　FIRST(L)＝{，，ε}　　FOLLOW(L〕＝{ )}FIRST)S)＝{(，a}　　　　FOLLOW(S)＝{#，，，)} 　　　　　　　　 FIRST(S)＝