成都理工大学2012-2013软件代码开发技术(编译原理)考试试卷(最终修改版)详解

《成都理工大学2012-2013软件代码开发技术(编译原理)考试试卷(最终修改版)详解》由会员分享，可在线阅读，更多相关《成都理工大学2012-2013软件代码开发技术(编译原理)考试试卷(最终修改版)详解（7页珍藏版）》请在装配图网上搜索。

1、成都理工大学2012-2013学年第一学期软件代码开发技术考试试卷一，填空题（每题 2分，共30分）1 .源程序的动态错误是源程序中的逻辑错误，它们发生在程序运行的时候，也被成为亚态语义错误。2 .设计一个编译器,除了具有中间代码生成、代码生成和出错处理功能之外，还应具有哪些功能：它们分别为 一词法分析、语法分析、语义分析、中间代码优化、符号表管理 3 .设汇=0,1 上的正规集S由倒数第二个字符为 0的所有字符串组成，则该正规集对应的正规式表示为（0|1）* 0（0|1） 4 .假设G是一个文法，S是文法的开始符号，如果S =x,则称x是该文法的一个句型5 .中间代码生成器对语法树进行遍历，

2、生成可顺序执行的中间的代码序列，最常用的中间 代码形式是四元式6 .最右推导也成为规范 推导,推导出的句型称为 右 句型。7 . LR（k）文法所识别的语言称为 LR（k）语言，其中L表示 从左到右扫描输入序列,R表示 逆 序的最右推导，k表示 确定下一动作向前看的终结符个数8 .将栈顶的符号和文法产生式的右部符号串进行比较，若相等，则用左部符号去替换栈顶符号串，这种操作称为规约9 .自上而下语法分析方法遇到的主要问题是回溯 和无限循环（死循环）10 .正规文法，正规表达式和有限自动机三者在某种意义下是等价的11 .若为文法G构造的预测分析表中不含多重定义的条目，则称 G为 回溯文法。12 .

3、文法符号的属性有两种，一种称为综合属性,另一种称为几成属性。13 . 一个句型中的最左 直接短语 称为该句型的句柄。14 .如果一个问发的同一个句子存在两棵分析树，则该文法是 二义性的15.不管任何类型的文法都包括四个组成部分，它们分别是非终结符、终结符、产生式、开始符号二、判断题（每题1分，共10分）1,确定的和不确定的有限自动机都能识别正规集。（，）2,有些语言能被确定的有限自动机识别，但不能用正规表达式表示。（X）3,设 L = a, b, c , M = b, c, d , LUM = b , c.（ x ）4,在预测分析器的转换图中，其箭弧上的标识必须是终结符。（X ）5, 一个项目

4、集中既可以有移进项目，又有可规约项目，使得分析无法进行，这种冲突称为移进/规约冲突。（，）6,在使用自上而下分析法时，文法应该没有左递归。（，）7,正规集都可以由一个状态数最少的DFA识别，这个DFA是唯一的。（，）8,二义文法是SLR（l）文法。（X ）9,正规表达式的运算操作不具有优先级运算。（X）10,文法G的产生式为S -（L） | aL- L , S | S是一个直接左递归文法。（V）三、选择题（每题 1分，共10分）1,文法G所描述的语言是_D_的集合。A.文法G的字汇表V中所有符号组成的符号串B.文法G的字汇表V的闭包V*中的所有符号串C.由文法的开始符号推出的所有符号串D.由文

5、法的开始符号推出的所有终结符号串2, 一个语言的文法是 B。A.唯一的B.不唯一白C.个数有限的3,若一个文法是递归的，则它所产生的句子个数A 。A.必定是无穷的B.是有限个的C.根据具体情况而定4,文法的二义性和语言的二义性是两个A 的概念。A.不同 B.相同 C.无法判断D.等价5,巴克斯范式(BNH是一种广?采用的 C的工具。A.描述规则B.描述语言C.描述文法 D.描述句子6, B 是两类程序语言处理程序。A.高级语言程序和低级语言程序B.解释程序和编译程序C.编译程序和操作系统D.系统程序和应用程序7,乔姆斯基把文法分为四种类型：0型、1型、2型和3型，其中2型文法指的是 CA.短语

6、文法 B.上下文有关文法C.上下文无关文法 D.正规文法8,语法分析常用的方法是 A。A.自顶向下、自底向上8 .自顶向下、自底向上、自左向右C.自顶向下、自底向上、自左向右、自右向左D.自左向右、自右向左9 .编译程序中的语法分析器接受以C 为单位的输入,并产生以有关信息供以后各阶段使用。A.表达式B.产生式C.单词 D.语句10 .LR语法分析栈中存放的状态是识别B 的DFA状态。A.前缀 B.可规约前缀C.项目 D.句柄四，综合题(5小题，共50分)1,设文法G具有下列产生式：E - E Or T | TT - T and F | FF - not F | (E) | true | fa

7、lse请指出文法G的终结符号、非终结符号和开始符号。(4分)解答：终结符：or,and,not,(,),true,false 非终结符：E,T,F开始符号：E2,根据1中文法G写出句子not(true and false)的规范推导并确定句柄。(6分)解答：规范推导为：E =T =F =not F =not (E) =not (T) =not (T and F) =not (T and false)=not (F and false) =not (true and false)由分析树：可知句柄为:3,有NFA定义如下:timetrueN = (S=0,1 , E= a,bMOVE = mov

8、e(0,a) = 0,s0 = 0 , F = 0,move(0,a) = 1, move(1,a) = 0（1）画出N的状态转换图（4分） 解答：（2）构造N的最小DFA D （ 7分）解答：确定DFAe_闭包（0）=0 *Ae 闭包(smove(0 ,a)=0,1 *Be 闭包(smove(0, b)=1 *Ce 闭包(smove(0, 1 ,a)=0,1 Be 闭包(smove(0, 1 ,b)=1 Ce 闭包(smove(1 ,a):0 Ae 闭包(smove(1 ,b)=二 DFA 为:n =A, B , Cmove(A,a尸 Bmove(A,b尸cmove(B,a尸 Bmove(B

9、,b尸 c故A,B不可分，将A为A,B编号0, C编号1,为c代表最小DFA为a(3)给出串aaba,baa的识别过程(4分) 解答：a a b a4,设文法G具有下列产生式：E - E + T | TT - T * F | F F - id | (E)(1)消除文法的直接左递归：(4分) 解答：消除左递归后的文法为：E -T E E -+T E / eT -F T T -*F T / eF -id/(E)(2)求消除左递归后文法的FIRST和FOLLOW数：(6分)解答：First(F) =id,( First(T ) =*, First(T) =id,( First(E )= + , Fi

10、rst(E) = First(T) = First(F) =id,( Follow(E) =#,) Follow(E ) = Follow(E) =#,) Follow(T) = +,#,) Follow(T ) = Follow(T) =+,#,) Follow(F) =*,+,# (4分)(3)构造其预测分析表。解答：first(TE 尸id , ( first(+TE ) =+, e first(FT ) =id , (first(*FT )=*,( first(id) = idfirst(E) =(*+)(id#ETE，TE，E，+TETFTFT*FTF(E)id5,已知文法 G3:S

11、- EE - aA | bBA - cA | dB - cB | d(4分)(1)写出句型bccB的所有短语、直接短语和句柄。 解答：S =E =bB =bcB =bccB短语： bccB(S E) ccB(B i) cB(B2)直接短语：cB(B2)句柄：cB(B2)(2)列出4个项目集II、12、13、I4 (如下图)，请将这4个项目集补充完整。(7分)I2:E-a.A附加资料：编译：高级语言可以直接转换成机器语言，也可以翻译成汇编语言，这两个过程称为编译。解释器与编译器的主要区别：运行目标程序的控制权在解释器而不在目标程序。解释器优点：(1)其具有较好的动态特性。(2)具有较好的可移植性

12、。缺点：在时间和空间上的损失较大，运行效率低。文法的分类：文法产生式语后自动机0型文法(短语)a - B0型语言(短语结构语言，递归可枚举集)图灵机1型文法(CSG限制11型语言(CSL)线性界线自动机2型文法(CFG限制22型语言(CFL)下推自动机3型文法(正规)限制33型语言(正规语言，正规集)有限自动机LR(1)与LALR(1)的关系：LR(1)与LALR(1)对于移进/规约冲突的解决二者是等价的， 而对于 规约/规约冲突，由于 LALR(1)项目中合并了 lookaheads可能会减弱它对规约/规约冲突的 解决能力，具体有下述两个结论：(1) LR(1) DFA中不发生的移进/规约冲突，LALR(1)DFA中也一定不会发生。(2)合并后的lookaheads可能会引起LALR项目集中的规约/规约冲突。