《编译原理 第1、2、3、4章复习(期末).pdf》由会员分享，可在线阅读，更多相关《编译原理 第1、2、3、4章复习(期末).pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理 第 1、2 章复习一、选择题1、词法分析所依据的是 B。A.语义规则则2、词法分析器的输出结果是C。A.单词的种别编码B.单词在符号表中的位置D.单词自身值B.构词规则C.语法规则D.等价变换规C.单词的种别编码和自身值3、正规式 M1 和 M2 等价是指 C。A.M1 和 M2 的状态数相等B.M1 和 M2 的有向弧条数相等C.M1 和 M2 所识别的语言集相等D.M1 和 M2 状态数和有向弧条数相等4、C 语言中表达式 a+=1 词法分析后，能识别的单词个数是 A个。A.5 B.6 C.7 D.85、将识别各类单词的有限自动机合并后得到的有限自动机是 A。A.可能是 NFA
2、也可能是 DFAB.一定是 DFAC.一定是 NFAD.是最小的 DFA6、中间代码生成时所遵循的是 D。A语法规则 C语义规则B词法规则D等价变换规则7、语法分析应遵循 B。A语义规则 C构词规则B语法规则D等价变换规则8、编译程序各阶段的工作都涉及到 BC。A语法分析 D语义分析B表格管理E词法分析C出错处理9、编译过程中扫描器的任务包括 ABCDE (多选)：A.按词法规则分割单词，识别出其属性，并转换成token 串输出；B.删除注释、空格C.行计数、列计数D.发现并定位词法错误E.建立符号表10、令=a,b，则上所有以 b 开头，后跟若干个 ab 的字的全体对应的正规式为_ABCD_
3、(多选)。A.b(ab)*D.(ba)+bB.b(ab)+E.b(a|b)C.(ba)*b11、将编译程序分成若干个“遍”是为了 B。A提高程序的执行效率 B使程序的结构更加清晰 C利用有限的机器内存并提高机器的执行效率 D利用有限的机器内存但降低了机器的执行效率12、D不可能是目标代码。A汇编指令代码 C绝对指令代码B可重定位指令代码D中间代码13、使用 A可以定义一个程序的意义。A语义规则 C产生规则B词法规则D词法规则14、词法分析器的输入是 B。A单词符号串 C语法单位B源程序D目标程序15、状态转换图（见图）接受的字集为 D。00YX B.?1以 0 结尾的二进制数组成的集合A.以
4、0 开头的二进制数组成的集合C.含奇数个 0 的二进制数组成的集合 D.含偶数个 0 的二进制数组成的集合二、填空题1、确定有限自动机 DFA 是 NFA的一个特例。2、若二个正规式所表示的 正规集相同，则认为二者是等价的。3、一个字集是正规的，当且仅当它可由 FA所识别。4、编译过程通常可分为5 个阶段，分别是 词法分析、语法分析中间代码生成、代码优化和目标代码生成。5、确定有穷自动机 DFA 的化简，是将多余状态消除而形成一个最小的等价的DFA。化简包括：消除多余状态、合并等价状态。三、判断题1、一个有限状态自动机中，有且仅有一个唯一终态。（错）2、设 r 和 s 分别是正规式，则有L（r
5、|s）=L(r)|L(s)。（对）3、自动机 M 和 M的状态数不同，则二者必不等价。（错）（对）4、确定的自动机以及不确定的自动机都能正确地识别正规集。5、对任何正规表达式 e，都存在一个 NFA M，满足 L(G)=L(e)。编译原理 第 3、4 章复习一、选择题1、文法 G：SxSx|y 所识别的语言是 C。A xyxB(xyx)*nn（对）D x*yx*C x yx(n0)2、设 G 为算符优先文法，G 的任意终结符对 a、b 有以下关系成立 C。A 若 f(a)g(b)，则 abC ab 都不一定成立B若 f(a)g(b)，则 abD ab 一定成立3、如果文法 G 是无二义的，则它
6、的任何句子 A。A 最左推导和最右推导对应的语法树必定相同B 最左推导和最右推导对应的语法树可能不同C 最左推导和最右推导必定相同D 可能存在两个不同的最左推导，但它们对应的语法树相同4、由文法的开始符经 0 步或多步推导产生的文法符号序列是 C。A 短语B句柄C 句型D 句子EE+FE+TPTiP#+#句型 P+T+i 的语法及优先关系5、文法 G：EE+T|TTT*P|PP(E)|i则句型 P+T+i 的句柄和最左素短语为 B。AP+T 和 i B P 和 P+TC i 和 P+T+i DP 和 T 6、设文法为：SSA|AAa|b则对句子 aba，下面 D是规范推导。A SSASAAAA
7、AaAAabAabaB SSASAAAAAAAaAbaabaC SSASAASAaSbaAbaabaD SSASaSAaSbaAbaaba7、文法 G：Sb|(T)TT,S|S则 FIRSTVT(T)C。A b,(B b,)Cb,(,，Db,),，8、产生正规语言的文法为 D。A 0 型B 1 型C 2 型D 3 型9、采用自上而下分析，必须 A。A 消除左递归、消除回溯B 消除右递归C 提取公共左因子10、在规范归约中，用 B来刻画可归约串。A 直接短语B 句柄C 最左素短语D 素短语11、规范归约指 B。A 最左推导的逆过程B 最右推导的逆过程C 规范推导 D 最左归约的逆过程12、若 a
8、 为终结符，则 Aa为 B项目 A归约B移进C接受D待约13、若项目集 Ik含有 A，则在状态 k 时，仅当面临的输入符号aFOLLOW(A)时，才采取“A”动作的一定是 D。ALALR 文法BLR（0）文法CLR（1）文法DSLR（1）文法14、在 LR（0）的 ACTION 子表中，如果某一行中存在标记“rj”的栏，则 A。A该行必定填满 rjC其他行也有 rjB该行未填满 rjDgoto 子表中也有 rj15、一个 A指明了在分析过程中的某时刻所能看到产生式多大一部分。A活前缀B前缀C项目D项目集16、自上而下的语法分析方法是 B。A算符优先分析法DLR（0）分析法BLL（1）分析法E.
9、LALR（1）分析法CSLR（1）分析法17、中间代码生成所依据的是 D。A语法规则B词法规则C语义规则D等价变换规则18、四元式之间的联系是通过 B实现的。A指示器B临时变量C符号表D程序变量19、后缀式 ab+cd+/可用表达式 B来表示。Aa+b/c+dB(a+b)/(c+d)Ca+b/(c+d)Da+b+c/d20、表达式（AB）（CD）的逆波兰表示为 B。A ABCDC ABCDB ABCDD ABCD21、四元式表示法的优点为 C。A不便于优化处理，但便于表的更动B不便于优化处理，但节省存储空间C便于优化处理，也便于表的更动D便于表的更动，也节省存储空间22、终结符具有 D属性。A
10、传递二、填空题1、对于一个文法，如果能够构造 LR 分析表。使得它的 每个入口均是唯一确定的，则称该文法为 LR 文法。2、字的前缀是指该字的任意首部。3、每一项ACTIONS，a所规定的动作包括 移进、归约、接收、出错。4、对 LR 分析器来说，存在 LR(0)、SLR(1)、LR(1)、LALR(1)表的构造方法。5、将识别活前缀的 NFA 确定化，使其成为以 项目集为状态的 DFA，这个DFA 就是建立 LR 分析表的基础。6、A称为 归约 项目；对文法开始符 S为接收项目；若 a 为终结符，则称 Aa为移进项目；若 B 为非终结符，则称 AB为 待约项目。7、LR（1）分析法的名字中“
11、L”表示 自左到右扫描输入串，“R”表示最右推导的逆过程，“1”表示 向前展望 1 个字符。B继承C抽象D综合8、在条件、循环 结构的语法制导翻译中，采用拉链-回填技术。9、中间代码有逆波兰记号、树形表示、三元式、四元式等形式，生成中间代码主要是为了使目标代码的优化容易实现。10、语法制导翻译既可以用来产生中间代码代码，也可以用来产生 机器指令，甚至可用来对输入串进行解释执行。11、文法符号的属性有两种，一种称为综合，另一种称为继承。12、后缀式 abc-/所代表的表达式是 a/(b-c)，表达式(a-b)*c 可用后缀式 ab-c*表示。13、在语法分析中，最常见的两种方法是 top-down分析法，另一是 bottom-up分析法。14、采用 top-down语法分析时，必须消除文法的左递归。15、Chomsky 把文法分为 4种类型，编译器构造中采用 2 型和 3 型文法，它们分别产生 上下无关语言和正规语言，并分别用 PDA和 DFA自动机识别所产生的语言。三、判断题1、在自下而上的语法分析中，语法树与分析树一定相同。2、二义文法不是上下文无关文法。3、语法分析时必须先消除文法中的左递归。4、规范归约和规范推导是互逆的两个过程。（错）（错）（错）（对）（错）5、一个文法所有句型的集合形成该文法所能接受的语言。