编译原理习题.doc

一、单项选择题1、将编译程序分成若干个“遍”是为了 。 a提高程序的执行效率 b使程序的结构更加清晰 c利用有限的机器内存并提高机器的执行效率 d利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握 。 a源程序b目标语言 c编译方法d以上三项都是3、编译程序绝大多数时间花在 上。 a出错处理b词法分析 c目标代码生成d管理表格4、词法分析器的输入是 。 a单词符号串b源程序 c语法单位d目标程序5、中间代码生成时所遵循的是- 。 a语法规则b词法规则 c语义规则d等价变换规则6、编译程序是对 。 a汇编程序的翻译b高级语言程序的解释执行 c机器语言的执行d高级语言的翻译7、语法分析应遵循 。 a语义规则b语法规则 c构词规则d等价变换规则二、多项选择题1、编译程序各阶段的工作都涉及到 。 a语法分析b表格管理c出错处理 d语义分析e词法分析2、编译程序工作时，通常有 阶段。 a词法分析b语法分析c中间代码生成 d语义检查e目标代码生成三、填空题 1、解释程序和编译程序的区别在于 。2、编译过程通常可分为5个阶段，分别是 、语法分析 、代码优化和目标代码生成。3、编译程序工作过程中，第一段输入是 ，最后阶段的输出为 程序。4、编译程序是指将 程序翻译成 程序的程序。一、单项选择题1、文法G：SxSx|y所识别的语言是 。a. xyxb. (xyx)*c. xnyxn(n0)d. x*yx*2、文法G描述的语言L(G)是指 。a. L(G)=|S , VT*b. L(G)=|S, VT*c. L(G)=|S,(VTVN*)d. L(G)=|S, (VTVN*)3、有限状态自动机能识别 。a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立 。a. 若f(a)g(b)，则abb.若f(a)g(b)，则a0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbncndn|n05、自下而上的语法分析中，应从 开始分析。a. 句型b. 句子c. 以单词为单位的程序d. 文法的开始符e. 句柄6、对正规文法描述的语言，以下 有能力描述它。a.0型文法b.1型文法 c.上下文无关文法 d.右线性文法 e.左线性文法 三、填空题1、文法中的终结符和非终结符的交集是 。词法分析器交给语法分析器的文法符号一定是 ，它一定只出现在产生式的 部。2、最左推导是指每次都对句型中的 非终结符进行扩展。3、在语法分析中，最常见的两种方法一定是 分析法，另一是 分析法。4、采用 语法分析时，必须消除文法的左递归。5、 树代表推导过程， 树代表归约过程。6、自下而上分析法采用 、归约、错误处理、 等四种操作。 7、Chomsky把文法分为 种类型，编译器构造中采用 和 文法，它们分别产生 和 语言，并分别用 和 自动机识别所产生的语言。四、判断题1、文法 SaS|bR|描述的语言是(a|bc)* ( ) RcS2、在自下而上的语法分析中，语法树与分析树一定相同。 （ ）3、二义文法不是上下文无关文法。 （ ）4、语法分析时必须先消除文法中的左递归。（ ）5、规范归约和规范推导是互逆的两个过程。（ ）6、一个文法所有句型的集合形成该文法所能接受的语言。（ ）五、综合题1、有文法G：SaAcB|BdAAaB|cBbScA|b（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）写出句子acabcbbdcc的最左推导过程。2、对于文法GS： S（L）|aS|a LL, S|S3、考虑文法GT：TT*F|FFFP|PP（T）|i证明T*P（T*F）是该文法的一个句型，并指出直接短语和句柄。一、单项选择题1、词法分析所依据的是 。a. 语义规则b. 构词规则c. 语法规则d. 等价变换规则2、词法分析器的输出结果是 。a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值3、正规式M1和M2等价是指 。a. M1和M2的状态数相等b. M1和M2的有向弧条数相等c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等4、状态转换图（见图3-6-1）接受的字集为 。 0 1 0图3-6-1YXa. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好c. 词法分析器分解为多个过程，由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段二、多项选择题1、在词法分析中，能识别出 。a. 基本字b. 四元式c. 运算符d. 逆波兰式e. 常数2、令=a,b，则上所有以b开头，后跟若干个ab的字的全体对应的正规式为 。a. b(ab)*b. b(ab)+c.(ba)*bd. (ba)+be. b(a|b)三、填空题1、确定有限自动机DFA是 的一个特例。2、若二个正规式所表示的 相同，则认为二者是等价的。3、一个字集是正规的，当且仅当它可由 所 。四、判断题1、一个有限状态自动机中，有且仅有一个唯一终态。（ ）2、设r和s分别是正规式，则有L（r|s）=L(r)|L(s)。（ ）3、自动机M和M的状态数不同，则二者必不等价。（ ）4、确定的自动机以及不确定的自动机都能正确地识别正规集。（ ）5、对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。（ ）6、对任意一个右线性文法G，都存在一个DFA M，满足L(G)=L(M)。（ ）7、对任何正规表达式e，都存在一个NFA M，满足L(G)=L(e)。（ ）8、对任何正规表达式e，都存在一个DFA M，满足L(G)=L(e)。（ ）五、基本题1、设M（x,y, a,b, f,x,y）为一非确定的有限自动机，其中f定义如下：f（x,a）x,y f（x,b）yf（y,a） f（y,b）x,y 试构造相应的确定有限自动机M。即得到M=（0,1,2, a,b, f,0, 1,2），其状态转换图如图3-6-5所示。2、对给定正规式b*（d|ad）（b|ab）+，构造其NFA M； 1、 构造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | 2、 下面文法GS是否为LL（1）文法？说明理由。S A B | P Q x A x y B b cP d P | Q a Q | 3、 设有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| （1）求出该文法的每一个非终结符U的FOLLOW集。（2）该文法是LL（1）文法吗？（3）构造CS的LL（1）分析表。4、 将文法GV改造成为LL(1)的。 GV：VN|NE EV|V+E Ni5、已知文法：GA：AaAa|（1）该文法是LL（1）文法吗？为什么？（2）若采用LL（1）方法进行语法分析，如何得到该文法的LL（1）分析表？（3）若输入符号串“aaaa”，请给出语法分析过程。第七节 习题1、设有文法GS为：Sa|b|(A)ASdA|S（1） 完成算符优先关系表，并判断GS是否为算符优先文法。（2）给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。（3）给出输入串（adb）#的分析过程。第四节 习题一、单项选择题1、若a为终结符，则Aa为 项目 a.归约b.移进c.接受d.待约2、若项目集Ik含有A，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“A”动作的一定是 。 a.LALR文法b.LR（0）文法c.LR（1）文法d.SLR（1）文法3、就文法的描述能力来说，有 。 a. SLR（1）LR（0） b. LR（1）LR（0）c. SLR（1）LR（1）d.无二义文法LR（1）4、在LR（0）的ACTION子表中，如果某一行中存在标记“rj”的栏，则 。 a.该行必定填满rjb.该行未填满rjc.其他行也有rjd.goto子表中也有rj5、一个 指明了在分析过程中的某时刻所能看到产生式多大一部分。二、多项选择题1、一个LR分析器包括 。 a.一个总控程序b.一个项目集c.一个活前缀d.一张分析表e.一个分析栈2、LR分析器核心部分是一张分析表，该表包括 等子表。 a.LL(1)分析b.优先关系c.GOTO d.LRe.ACTION3、每一项ACTIONS，a所规定的动作包括 。a.移进b.比较c.接受d.归约e.报错4、对LR分析表的构造，有可能存在 动作冲突。a.移进b.归约c.移进/归约d.移进/移进e.归约/归约5、就文法的描述能力来说，有 。 a. SLR（1）LR（1）b. LR（1）SLR（1）c. LR（0）LR（1）d. LR（1）无二义文法 e. SLR（1）无二义文法6、对LR分析器来说，存在 等分析表的构造方法。 a.LALRb.LR（0）c.SLR（1）d.SLR（0）e.LR（1）7、自上而下的语法分析方法有 。 a.算符优先分析法b.LL（1）分析法c.SLR（1）分析法三、填空题1、对于一个文法，如果能够构造 。使得它的 均是唯一确定的，则称该文法为LR文法。2、字的前缀是指该字的 。3、活前缀是指 的一个前缀，这种前缀不含 之后的任何符号。4、在LR分析过程中，只要 的已扫描部分保持可归约成一个 ，则扫描过的部分正确。5、将识别 的NFA确定化，使其成为以 为状态的DFA，这个DFA就是建立 的基础。6、A称为 项目；对文法开始符S为 项目；若a为终结符，则称Aa为 项目；若B为非终结符，则称Aa为 项目。四、综合题1、设文法GS为：SrDDD,i | i（1） 构造识别文法活前缀的DFA（3分）。（2） 该文法是LR(0)文法吗（1分）？请说明理由（2分）。（3） 该文法是SLR(1)文法吗？若是，构造它的SLR(1)分析表（4分）。第八节 习题一、单项选择题1、中间代码生成所依据的是 。a.语法规则b.词法规则c.语义规则d.等价变换规则2、四元式之间的联系是通过 实现的。 a.指示器b.临时变量c.符号表d.程序变量3、后缀式ab+cd+/可用表达式 来表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d4、表达式（AB）（CD）的逆波兰表示为 。 a. ABCDb. ABCDc. ABCDd. ABCD5、中间代码的树型表示+ABCD+ 所对应的表达式为 。 a.A+B+C+Db.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)6、四元式表示法的优点为 。a.不便于优化处理，但便于表的更动b.不便于优化处理，但节省存储空间c.便于优化处理，也便于表的更动d.便于表的更动，也节省存储空间7、终结符具有 属性。 二、多顶选择题1、中间代码主要有。a四元式b二元式c三元式d后缀式e间接三元式2、下面中间代码形式中，能正确表示算术表达式a+b+c的有。+a +b c+ ca baab+c+babc+c d ea+b+c3、在下面的语法制导翻译中，采用拉链-回填技术。a赋值语句bgoto语句 c条件语句d循环语句4、下列中间代码形式有益于优化处理。a三元式b四元式c间接三元式d逆波兰表示法e树形表示法5、在编译程序中安排中间代码生成的目的是。a便于进行存储空间的组织b利于目标代码的优化c利于编译程序的移植d利于目标代码的移植e利于提高目标代码的质量+a *a b*+ ca b6、下面的中间代码形式中，能正确表示算术表达式a+b*c。题）aab+c*babc*+ca+b*cd e7、三地址代码语句具体实现通常有表示方法。a逆波兰表示b三元式c间接三元式d树形表示e四元式三、填空题1、中间代码有 等形式，生成中间代码主要是为了使 。2、语法制导翻译既可以用来产生 代码，也可以用来产生 指令，甚至可用来对输入串进行 。3、当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须持 时才能确定，因而要进行 。4、文法符号的属性有两种，一种称为 ，另一种称为 。5、后缀式abc-/所代表的表达式是 ，表达式(a-b)*c可用后缀式 表示。6、用一张 辅以 的办法来表示中间代码，这种表示法称为间接三元式。四、综合题1、给出下列表达式的逆波兰表示（后缀式）： a*(-b+c) (AB)(CDE) 2、写出算术表达式：A+B*(C-D)+E/(C-D)N的四元式序列；三元式序列；间接三元式序列第三节 习题一、单项选择题1、编译程序使用 区别标识符的作用域。 a. 说明标识符的过程或函数名 b. 说明标识符的过程或函数的静态层次c. 说明标识符的过程或函数的动态层次 d. 标识符的行号2、在目标代码生成阶段，符号表用于 。 a. 目标代码生成b. 语义检查c. 语法检查d. 地址分配3、过程信息表不包含 。 a. 过程入口地址 b. 过程的静态层次 c. 过程名 d. 过程参数信息4、下列关于标识符和名字叙述中，正确的是 。 a. 标识符有一定的含义b. 名字是一个没有意义的字符序列c. 名字有确切的属性d. ac都不正确二、多项选择题1、符号表的每一项均包含 。 a. 名字栏b. 类型栏c. 信息栏d. 值栏e. ad均包含2、对编译程序所用到的符号表，涉及的操作有 。 a. 填写或更新信息栏内容b. 填入新名c.给定名字，访问它的有关信息d. 杂凑技术e.线性表和排序二叉树3、源程序中的错误一般有 。 a. 词法错误b. 语法错误c. 语义错误d. 编译错误e. 违反环境限制的错误三、填空题1、符号表中名字栏内容有两种填写方式，它们是 填写和 填写。2、词法分析阶段的错误主要是 ，可通过 的办法纠正错误。3、符号表中名字的有关信息在 和 过程中陆续填入。4、在目标代码生成阶段，符号表是 的依据。第五节 习题一、单项选择题1、优化可生成的目标代码。a运行时间较短b占用存储空间较小c运行时间短但占用内存空间大d运行时间短且占用存储空间小2、对一个基本块来说，是正确的。a只有一个入口语句和一个出口语句b有一个入口语句和多个出口语句c有多个入口语句和一个出口语句d有多个入口语句和多个出口语句二、多项选择题1、根据优化所涉及的范围，可将优化分为。a局部优化b过程优化c全局优化d循环优化e四元式优化2、下列优化中，属于循环优化的有。a强度削弱b合并已知量c删除无用赋值d删除归纳变量e代码外提三、填空题1、局部优化是范围内进行的一种优化。2、在一个基本块内，可实行3种优化方法，即合并已知量、。3、优化就是对程序进行各种变换，使之能生成更有效的。4、在优化中，可把循环中的提到循环外面去，这种方法称为。