成都理工大学20122013软件代码开发技术(编译原理)考试试卷(最终修改版)汇编.docx

成都理工大学2012-2013学年第一学期《软件代码开发技术》考试试卷填空题（每题2分，共30分）源程序的动态错误是源程序中的逻辑错误，它们发生在程序运行的时候，也被成为动态语义错误。设计一个编译器，除了具有中间代码生成、代码生成和出错处理功能之外，还应具有哪些功能：它们分别为_词法分析、语法分析、语义分析、中间代码优化、符号表管理_ 设∑=｛0,1｝上的正规集S由倒数第二个字符为0的所有字符串组成，则该正规集对应的正规式表示为(0|1)*0(0|1)假设G是一个文法，S是文法的开始符号，如果S=x,则称x是该文法的一个句型中间代码生成器对语法树进行遍历，生成可顺序执行的中间的代码序列，最常用的中间代码形式是四元式最右推导也成为规范推导，推导出的句型称为右 句型。LR(k)文法所识别的语言称为LR(k)语言，其中L表示从左到右扫描输入序列，R表示逆序的最右推导，k表示确定下一动作向前看的终结符个数将栈顶的符号和文法产生式的右部符号串进行比较，若相等，则用左部符号去替换栈顶符号串，这种操作称为规约自上而下语法分析方法遇到的主要问题是回溯和无限循环（死循环）正规文法，正规表达式和有限自动机三者在某种意义下是 等价的若为文法G构造的预测分析表中不含多重定义的条目，则称G为回溯文法。文法符号的属性有两种，一种称为 综合属性，另一种称为几成属性。一个句型中的最左 直接短语称为该句型的句柄。如果一个问发的同一个句子存在两棵分析树，则该文法是二义性的不管任何类型的文法都包括四个组成部分，它们分别是 非终结符、终结符、产生式、开始符号二、判断题（每题1分，共10分）1，确定的和不确定的有限自动机都能识别正规集。（√）2，有些语言能被确定的有限自动机识别，但不能用正规表达式表示。（×）3，设L = {a, b, c},M = {b, c, d} , LM = {b , c}.（×）4，在预测分析器的转换图中，其箭弧上的标识必须是终结符。（×）5，一个项目集中既可以有移进项目，又有可规约项目，使得分析无法进行，这种冲突称为移进/规约冲突。（√）6，在使用自上而下分析法时，文法应该没有左递归。（√）7，正规集都可以由一个状态数最少的DFA识别，这个DFA是唯一的。（√）8，二义文法是SLR(l)文法。（×）9，正规表达式的运算操作不具有优先级运算。（×）10，文法G的产生式为 S-（L）|aL-L，S|S是一个直接左递归文法。（√）三、选择题（每题1分，共10分）1，文法G所描述的语言是D的集合。A．文法G的字汇表V中所有符号组成的符号串B．文法G的字汇表V的闭包V*中的所有符号串C．由文法的开始符号推出的所有符号串D．由文法的开始符号推出的所有终结符号串2，一个语言的文法是 B 。A．唯一的B. 不唯一的 C. 个数有限的3，若一个文法是递归的，则它所产生的句子个数 A 。必定是无穷的B. 是有限个的C. 根据具体情况而定4，文法的二义性和语言的二义性是两个 A 的概念。不同B. 相同C. 无法判断D. 等价5，巴克斯范式（BNF）是一种广泛采用的 C 的工具。描述规则B. 描述语言C. 描述文法D. 描述句子6， B 是两类程序语言处理程序。高级语言程序和低级语言程序解释程序和编译程序编译程序和操作系统系统程序和应用程序7，乔姆斯基把文法分为四种类型：0型、1型、2型和3型，其中2型文法指的是 C 。A．短语文法B.上下文有关文法C. 上下文无关文法D. 正规文法8，语法分析常用的方法是 A 。自顶向下、自底向上自顶向下、自底向上、自左向右自顶向下、自底向上、自左向右、自右向左自左向右、自右向左9.编译程序中的语法分析器接受以 C 为单位的输入，并产生以有关信息供以后各阶段使用。A. 表达式B. 产生式 C. 单词D. 语句10.LR语法分析栈中存放的状态是识别 B 的DFA状态。A. 前缀B. 可规约前缀C. 项目D. 句柄四，综合题（5小题，共50分）设文法G具有下列产生式：E - E Or T|TT - T and F|FF - not F | (E) | true | false请指出文法G的终结符号、非终结符号和开始符号。（4分）解答：终结符：｛or,and,not,(,),true,false｝ 非终结符：｛E,T,F｝ 开始符号：｛E｝根据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)由分析树：可知句柄为：true有NFA定