编译原理第1234章复习期末

1、页眉编译原理第1、2章复习10 / 71、选择题1、词法分析所依据的是BA.语义规则B.构词规则C.语法规则D.等价变换规2、词法分析器的输出结果是A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值D.单词自身值3、正规式M1和M2等价是指A.M1和M2的状态数相等B.M1和M2的有向弧条数相等C.M1和M2所识别的语言集相等D.M1和M2状态数和有向弧条数相等4、A.5 B. 6 C. 7 D. 8C语言中表达式a+=1词法分析后，能识别的单词个数是A 个。5、 将识别各类单词的有限自动机合并后得到的有限自动机是丄AA. 可能是NFA也可能是DFAB. 定是 DFAC. 定

2、是 NFAD. 是最小的DFA6、 中间代码生成时所遵循的是_D。A 语法规则B.词法规则C 语义规则D.等价变换规则7、语法分析应遵循 BA 语义规则C 构词规则B. 语法规则D.等价变换规则8、编译程序各阶段的工作都涉及到BC 。A 语法分析B表格管理C.出错处理D 语义分析E 词法分析9、 编译过程中扫描器的任务包括ABCDE (多选)：A. 按词法规则分割单词，识别出其属性，并转换成token串输出；B. 删除注释、空格C. 行计数、列计数D. 发现并定位词法错误E. 建立符号表10、 令刀=a,b，则刀上所有以 b开头，后跟若干个 ab的字的全体对应的正规式为_ABCD 多选)。A.

3、 b(ab)*B. b(ab)+C. (ba)*bD. (ba)+bE. b(a|b)11、将编译程序分成若干个“遍”是为了 _B。A .提高程序的执行效率B 使程序的结构更加清晰C .利用有限的机器内存并提高机器的执行效率D 利用有限的机器内存但降低了机器的执行效率12、D不可能是目标代码。A .汇编指令代码B.可重定位指令代码C .绝对指令代码D.中间代码13、 使用A可以定义一个程序的意义。A.语义规则B.词法规则C.产生规则D.词法规则14、词法分析器的输入是_B。A.单词符号串B.源程序C.语法单位D.目标程序15、 状态转换图(见图)接受的字集为_D_。A.以0开头的二进制数组成的

4、集合B.以0结尾的二进制数组成的集合C.含奇数个0的二进制数组成的集合D.含偶数个0的二进制数组成的集合二、填空题1确定有限自动机 DFA是NFA的一个特例。2、 若二个正规式所表示的正规集相同，则认为二者是等价的。3、 一个字集是正规的，当且仅当它可由_FA所识别。4、 编译过程通常可分为5个阶段，分别是 词法分析、语法分析中间代码生成、代码优化和目标代码生成。5、 确定有穷自动机 DFA的化简，是将多余状态消除而形成一个最小的等价的DFA化 简包括：消除多余状态、合并等价状态。三、判断题1 一个有限状态自动机中，有且仅有一个唯一终态。(错)2、设r和s分别是正规式，则有 L( r|s )=

5、L(r)|L(s)。(对)3、 自动机M和M'的状态数不同，则二者必不等价。(错)4、确定的自动机以及不确定的自动机都能正确地识别正规集。(对)5、对任何正规表达式 e,都存在一个 NFA M满足L(G)=L(e)。(对)编译原理第3、 4章复习一、选择题1文法G:A xyxStxSx|y所识别的语言是 C。B. (xyx)*C. x nyxn(n > 0)D. x*yx2、设G为算符优先文法，G的任意终结符对a、b有以下关系成立CA 若 f(a)>g(b)，则 a>b B.若 f(a)<g(b)，则 a<bC. ab都不一定成立D. ab 一定成立3、如

6、果文法 G是无二义的，则它的任何句子aAA 最左推导和最右推导对应的语法树必定相同B. 最左推导和最右推导对应的语法树可能不同C. 最左推导和最右推导必定相同D. 可能存在两个不同的最左推导，但它们对应的语法树相同A 短语B.句柄C.句型D.句子5、文法 G: E- E+T|TT- T*P|PP- (E)|i贝恂型P+T+i的句柄和最左素短语为B。4、由文法的开始符经 0步或多步推导产生的文法符号序列是CA P+T 和 i B . P 和 P+TC. i 和 P+T+iE/IE +TIP#< + 句型P+T+iEI + FiT PIi卜< >#的语法及优先关系6 、设文法为：

7、S- SA|AAt a|bASSASAAAAAaAAabAabaB.SSASAAAAAAAaAbaabaC.SSASAASAaSbaAbaabaD.SSASaSAaSbaAbaaba7、文法G:S b| A (T)TT,S|S则对句子aba,下面D 是规范推导。贝U FIRSTVT(T) _C。A b, A ,(B. b, A ,)C. b, A ,(, , D .b,A ,), , 8、产生正规语言的文法为_D_。A.0型B.1型C. 2型D. 3型9、米用自上而下分析，必须 _A。A.消除左递归、消除回溯B.消除右递归C.提取公共左因子10、 在规范归约中，用 _B来刻画可归约串。A.直接

8、短语B.句柄C.最左素短语D.素短语11、规范归约指巴_A.最左推导的逆过程B.最右推导的逆过程C.规范推导D.最左归约的逆过程12、若a为终结符，则Aaa B为B项目A.归约B.移进C.接受D.待约13、 若项目集Ik含有Aa，则在状态k时，仅当面临的输入符号 a FOLLOW(A寸，才采 取“ Aa ”动作的一定是卫_。A . LALR文法B. LR ( 0)文法 C. LR (1)文法 D. SLR (1)文法14、 在LR( 0)的ACTION子表中，如果某一行中存在标记“j 的栏，贝U上_。A .该行必定填满rjB.该行未填满rjC.其他行也有rjD. goto子表中也有门15、 一

9、个 A指明了在分析过程中的某时刻所能看到产生式多大一部分。A . n ABVA CDVC. ABVn CDVA21、四元式表示法的优点为 C。A.不便于优化处理，但便于表的更动C.便于优化处理，也便于表的更动B. An BVCDVAD. An BVA CDVB.不便于优化处理，但节省存储空间D. 便于表的更动，也节省存储空间A .活前缀B.前缀C.项目D.项目集16、自上而下的语法分析方法是B。A .算符优先分析法B.LL (1)分析法C. SLR( 1)分析法D. LR ( 0)分析法E.LALR (1)分析法17、中间代码生成所依据的是D。)A.语法规则B.词法规则C.语义规则D.等价变换

10、规则18、四兀式之间的联系是通过B实现的。A .指示器B.临时变量C.符号表D.程序变量19、后缀式ab+cd+/可用表达式B来表示。A.a+b/c+dB. (a+b)/(c+d)C. a+b/(c+d)D. a+b+c/d20、表达式鬥 AV B)A( CVD)的逆波兰表示为B。22、终结符具有_D_属性。A.传递B.继承C.抽象D.综合二、填空题1 对于一个文法，如果能够构造LR分析表。使得它的 每个入口均是唯一确定的，则称该文法为 LR文法。2、字的前缀是指该字的 任意首部 。3、 每一项 ACTIONS, a所规定的动作包括 移进 、归约 、接收 、出错 。4、 对LR分析器来说，存在

11、 LR(O)、SLR、LR、LALR表的构造方法。5、 将识别 活前缀 的NFA确定化，使其成为以项目集 为状态的DFA这个DFA就 是建立LR分析表 的基础。6、Aa称为归约项目;对文法开始符S'fa为 接收 项目;若a为终结符， 则称Aaa B为 移进 项目；若B为非终结符，则称 AaB B为待约 项目。7、 LR (1)分析法的名字中“ L”表示 自左到右扫描输入串，“ R'表示最右推导的逆 过程,“ 1”表示向前展望1个字符。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