编译原理模拟试卷及答案集.doc

1由文法开始符号经0步或多步推导产生的文法符号序列是_句型_。2编译器通常经历_词法分析_、_语法分析_、_语义分析和中间代码生成_、_优化_、_目标代码生成_等几个阶段；其中第一个阶段是以_源程序_为输入，_单词符号_为输出；最后一阶段是以_中间代码_为输入，_机器语言程序或汇编语言程序_为输出。同时_表格管理_和_出错处理_贯穿编译器的各个阶段。3解释器与编译器的主要区别是：_编译程序生成目标代码，而解释程序不生成目标代码_。4高级语言到低级语言的翻译过程称为_编译_。汇编语言到机器语言的翻译过程称为_汇编_。二、单项选择题（20分，每小题2分）1正规表达式(|a|b)2表示的集合是（ D ）。A，ab，ba，aa，bb Bab，ba，aa，bbCa，b，ab，aa，ba，bbD，a，b，aa，bb，ab，ba2分析树的内部结点仅由（ C ）组成。A开始符号和非终结符号B终结符号和非终结符号C非终结符号 D终结符号3文法S(L)|aLL，S|S 的终结符号是（C）。ASBS LC a , ( )Da , ( ) |4NFA M所识别的语言是（ D ）。A0型语言 B上下文有关语言C上下文无关语言 D正规语言5同正规式a*b*等价的文法是（ C ）。ASaS|bS| B SaSb|CSaS|Sb| DSabS|6对LR分析表的构造，不可能存在( C )动作冲突。A移进/归约B归约/归约 C移进/移进 D.以上都不对7LR分析模式中，改变格局变化的动作不包括（ B ）。A移进 B匹配终结符 C归约 D接受8如果一个文法G是二义文法，则必存在某个句子XL（G），该句子（ ）。 A存在两个不同的最右推导和一个最左推导B存在两个不同的最左推导和一个最右推导 C最左推导和最右推导不同 D存在两个不同的最左推导和两个不同的最右推导9一个句型的最左直接短语称为（ D ）。A句型B句子C语言D句柄三、判断题（10分，每小题1分）（ T ）1一个LL（1）文法是一个无二义性和无回溯文法。（ F ）2每个非终结符产生的终结符号串都是该语言的子集。（ F ）3正规式所描述的语言结构均可以用CFG描述，反之也成立。（ T ）4一个非确定的有限自动机NFA，可以通过多条路识别一个符号串（ F ）5自动机M和M的状态数不同，则二者必不等价。（ F ）6最小化的DFA所识别接受的正规集最小。（ F ）7一个状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（ F ）8语法分析时必须先消除文法中的左递归。（ T ）9确定的自动机和不确定的自动机都能正确的识别正规集。 （ T ）10规范归约是最右推导的逆过程。文法G如下：SaBcD|cdBBb|bDd|dD1改写G为等价的LL(1)文法G；（5分）2求G中每个非终结符的FIRST集合和FOLLOW集合；（5分）3构造预测分析表。（5分）答：1、SaBCD|cd BbB B bB|空 DdD D空|D2、FIRST(S)=a,c FOLLOW(S)=# FIRST(B)=b FOLLOW(B)=c FIRST(B)=b,空 FOLLOW(B)=c FIRST(D)=d FOLLOW(D)=# FIRST(D)=d,空 FOLLOW(D)=#3、预测分析表abcd#SSaBcDScdBBbBBB bBB 空DDdDDD DD 空证明文法SAaAb|BbBa A B 是LL（1）文法，但不是SLR（1）文法（5分）。证明：非终结符S产生的2个不同的产生式 S1 AaAb S2BbBa 得FIRST(S1)=空,a FIRST(S2)=空,b 且FIRST(S1)FIRST(S2)=空集 又因为S为无左递归，无公共左因子S是LL(1)文法GS的拓广文法S S SAaAb SBbBa A 空 B空 其DFA中 其中：FLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A) FOLLOW(B)空集S文法有规约-规约冲突，不能由SLR（1）解决S不是SLR（1）文法1、符号表项的组织常采用线性法、二分法和（ ）。2、整个编译过程可以划分成五个阶段：（ ）、语法分析阶段、（ ）、（ ）和目标代码生成阶段。5、语言翻译常用的两种形式是（ ）和（ ）。6、词法分析器输出的是单词符号，语法分析器输出的是（ ）。二、选择题：（每空2分，共10分）1、3型文法是（ ），（ ）是语法分析使用的文法。A短语文法 B.上下文有关文法 C.上下文无关文法 D.正规文法2、语法分析是依据语言的（ ）规则进行的，中间代码产生是依据语言的（ ）规则进行的。 A语法， 推导 B语义，产生式 C语法， 语义 D推导， 产生式3、错误“变量类型声明不一致”将在（ ）阶段发现。A词法分析 B.语法分析 C.语义分析 D.目标代码生成4、下列（ ）不是数据空间的使用方法和管理方法A静态存储分配 B.栈式动态存储分配 C.堆式动态存储分配 D.段页式存储分配一、是非题（请在括号内，正确的划，错误的划）（每个2分，共20分）1设r和s分别是正规式，则有L(r|s)=L(r)L(s)。()2确定的自动机以及不确定的自动机都能正确地识别正规集。()3词法分析作为单独的一遍来处理较好。 ( )4构造LR分析器的任务就是产生LR分析表。 ()5规范归约和规范推导是互逆的两个过程。 ( )6同心集的合并有可能产生新的“移进”/“归约”冲突。 ( )7LR分析技术无法适用二义文法。 ( )8树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。 ()9程序中的表达式语句在语义翻译时不需要回填技术。 ()10对中间代码的优化依赖于具体的计算机。 ( )二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1编译程序绝大多数时间花在_d_ 上。A( ) 出错处理 B( ) 词法分析 C( ) 目标代码生成 D( ) 表格管理2 编译程序是对_d_。 A( ) 汇编程序的翻译 B( ) 高级语言程序的解释执行C( ) 机器语言的执行 D( ) 高级语言的翻译 3 采用自上而下分析，必须_c_。A( ) 消除左递归 B( ) 消除右递归C( ) 消除回溯 D( ) 提取公共左因子 4在规范归约中，用_b_来刻画可归约串。A( )直接短语 B( )句柄 C( )最左素短语 D( )素短语 5 若a为终结符，则A- a为_b_项目。A( )归约B( ) 移进 C( ) 接受 D( ) 待约 6间接三元式表示法的优点为_a_。 A( ) 采用间接码表，便于优化处理 B( ) 节省存储空间，不便于表的修改 C( ) 便于优化处理，节省存储空间 D( ) 节省存储空间，不便于优化处理 D( ) 循环展开，循环合并 8. 在目标代码生成阶段，符号表用_d_。A( ) 目标代码生成 B( ) 语义检查C( ) 语法检查 D( ) 地址分配9若项目集Ik含有A- ，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“A- ”动作的一定是_d_。A. ( ) LALR文法 B( ) LR(0)文法 C( ) LR(1)文法D( ) SLR(1)文法三、填空题(每空1分，共10分)1词法分析基于_正则_文法进行，即识别的单词是该类文法的句子。 2语法分析基于_上下文无关_文法进行，即识别的是该类文法的句子。语法分析的有效工具是_语法树_。3分析句型时，应用算符优先分析技术时，每步被直接归约的是_最左素短语_，而应用LR分析技术时，每步被直接归约的是_句柄_。4语义分析阶段所生成的与源程序等价的中间表示形式可以有_逆波兰_、_四无式表示_与_三元式表示_等。5按Chomsky分类法，文法按照_规则定义的形式_进行分类。 6一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有_递归_定义的规则。 四、简答题（20分）1. 文法 GS 为： S-Ac|aB A-ab B-bc 写出 L(GS) 的全部元素。解：S=Ac=abc 或S=aB=abc 所以L(GS)=abc文法G的产生式为：（12%） + | * | I | ()a)给出（I+I）* I的最左推导、最右推导