《编译原理》模拟试题六

1、编译原理模拟试题六、是非题(请在括号，正确的划V,错误的划 为(每个2分，共20分)1设r和s分别是正规式，则有 L(r|s)=L(r)L(s)。( >)2确定的自动机以及不确定的自动机都能正确地识别正规集。(V)3词法分析作为单独的一遍来处理较好。( > )4构造 LR 分析器的任务就是产生 LR 分析表。 (V)5规归约和规推导是互逆的两个过程。(>)6同心集的合并有可能产生新的“移进” /归“约”冲突。(>)7 LR 分析技术无法适用二义文法。( > )8树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。9程序中的表达式语句在语义翻译时不需要回填技

2、术。(V)10对中间代码的优化依赖于具体的计算机。(>)二、选择题 (请在前括号选择最确切的一项作为答案划一个勾，多划按错论40 分)( >)(每个 4 分，共1编译程序绝大多数时间花在 上。A( ) 出错处理C ( ) 目标代码生成2 编译程序是对 B ( ) 词法分析D ( ) 表格管理A( ) 汇编程序的翻译C( ) 机器语言的执行B( ) 高级语言程序的解释执行D( ) 高级语言的翻译3采用自上而下分析，必须 。A( ) 消除左递归B( ) 消除右递归C( ) 消除回溯D( ) 提取公共左因子4在规归约中，用 来刻画可归约串。A( )直接短语B( )句柄C( )最左素短语D

3、( )素短语5. 若a为终结符，则A-> a B为项目。A( )归约B( ) 移进C( )6. 间接三元式表示法的优点为 A.( ) 采用间接码表，便于优化处理C.( ) 便于优化处理，节省存储空间7. 基本块的优化为 。A. ( ) 代码外提，删除归纳变量C.( ) 强度削弱，代码外提8. 在目标代码生成阶段，符号表用接受 D.( ) 待约B.( ) 节省存储空间，不便于表的修改D.( ) 节省存储空间，不便于优化处理B.( ) 删除多余运算，删除无用赋值D.( ) 循环展开，循环合并A.( ) 目标代码生成B.( ) 语义检查C.( ) 语法检查D.( ) 地址分配9.若项目集Ik含

4、有A->a 则在状态k时，仅当面临的输入符号a FOLLOW(A)时，才采取“A->a ”动作的一定是 。A. ( ) LALR 文法C.( ) LR(1) 文法B . ( ) LR(0)文法D. ( ) SLR(1)文法A. ( ) 先请先放B ( ) 先请后放C( ) 后请先放D. ( ) 任意三、填空题 (每空 1 分，共 10 分 )1词法分析基于 _正则 _文法进行，即识别的单词是该类文法的句子。2语法分析基于 _上下文无关 _文法进行， 即识别的是该类文法的句子。 语法分析的有效 工具是 _语法树 _。3分析句型时， 应用算符优先分析技术时，每步被直接归约的是_最左素短

5、语 _，而应用LR 分析技术时，每步被直接归约的是 _句柄 _。4语义分析阶段所生成的与源程序等价的中间表示形式可以有_逆波兰 _、 _四无式表示_与 _三元式表示 _等。5按 Chomsky 分类法，文法按照 _规则定义的形式 _进行分类。6一个文法能用有穷多个规则描述无穷的符号串集合(语言) 是因为文法中存在有 _递归_定义的规则。四、简答题( 20 分)1. 文法 GS 为：S->Ac|aBA->abB->bc写出 L(GS) 的全部元素。解： S=>Ac=>abc或 S=>aB=>abc所以 L(GS)=abc2. 构造正规式 1(0|1)*1

6、01 相应的 DFA 。 解：先构造 NFA ：确定化:01XAAAABABACABACAABYABY徐AB重新命名，令 AB为B、AC为C、ABY为D得:01AA直BBCBC直DDr.cB3. 文法S->aF|(T)T->T,S|S对(a,(a,a)和(a,a),A,(a),a)的最左推导。解：对(a,(a,a )的最左推导为：S=>(T) =>(T,S) =>(S,S) =>(a,S)=>(a,(T) =>(a,(T,S) =>(a,(S,S)=>(a,(a,S) =>(a,(a,a)对(a,a),A,(a),a)的最左推导

7、为：S=>(T) =>(T,S) =>(S,S) =>(T),S)=>(T,S),S) =>(T,S,S),S) =>(S,S,S),S)=>(T),S,S),S) =>(T,S),S,S),S) =>(S,S),S,S),S) =>(a,S),S,S),S) =>(a,a),S,S),S) =>(a,a),A,S),S) =>(a,a),(T),S) =>(a,a)f,(S),S) =>(a,a),A,(a),S) =>(a,a), (a) ),a)4. 文法：S->MH|aH->

8、;LSo| &K->dML| £L->eHfM->K|bLM判断G是否为LL(1)文法，如果是，构造 LL(1)分析表。解：各符号的FIRST集和FOLLOW集为：FIRSTFOLLOWSgdh E i伽何讣H宀LK预测分析表为:adefV#S"MHM->K->K->K->bLMQKH-!> £L->eHfK-> E_n E由于预测分析表中无多重入口，所以可判定文法是LL(1)的。五. 计算题(10分) 已知文法GS为:S->aF|(T)T-> T,S|S(1) 计算 GS的 FIRS

9、TVT 和 LASTVT 。(2) 构造GS的算符优先关系表并说明GS是否未算符优先文法。计算GS的优先函数。(4)给出输入串(a,a)#的算符优先分析过程。解：(1)各符号的 FIRSTVT和LASTVT :FIRSTVTLASTVTTas、( 八SK化(* Ss 户 )(2)算符优先关系表:a()FA#a>>(=3<>>><>>><<(3)对应的算符优先函数为:a(A#s212221T33113（4）句子（a,a）#分析过程如下:歩骤栈当前符号剩入串移进或归约1非1(33卅移甚2(<aa移iff33日）痒归约4枫

10、F7宜)#:移5A冲移进6b归约7做ftnp#归约8做Fp移谨9#归约10#一、选择题（每个选择题2分，共20分）1 .文法G产生的 的全体是该文法描述的语言。A .句型B.终结符集C.非终结符集D.句子2 .若文法G定义的语言是无限集，则文法必然是：A .递归的B前后文无关的C二义性的D无二义性的3 . Chomsky定义的四种形式语言文法中，0型文法又称为 文法；1 型文法又称为 文法；2型语言可由 识别。A .短语结构文法B前后文无关文法C前后文有关文法D正规文法E图灵机F有限自动机G下推自动机4 .一个文法所描述的语言是 ；描述一个语言的文法是 。A .唯一的B不唯一的C可能唯一，好可

11、能不唯一5 .数组的情向量中肯定不含有数组的 的信息A.维数B.类型C.维上下界D.各维的界差6.在下述的编译方法中，自底向上的方法有 ，自顶向下的分析方法有 。简单优先分析算符优先分析递归下降分析预测分析技术LR （K）分析SLR ( k)分析LL ( k)分析LALR( K分析A.B.C.D.E.F.二、简答题(每小题 5 分，共 20 分)1 LL ( 1 )分析法对文法有哪些要求？2 常见的存储分配策略有几种？它们都适合于什么性质的语言？3 常见循环优化都有哪些项目？4 什么是活动记录？它主要由哪些容构成？三、( 8 分)化简文法 GS ：S ASe | BCaD | aD | ACA

12、 Cb|DBSC bC | dB AcD aD四、(12分)设L a,b,c*是满足下述条件的符号串构成的语言：(1) 若出现 a ，则其后至少紧跟两个 c ；(2) 若出现 b ，其后至少紧跟一个 c 。试构造识别 L 的最小化的 DFA ，并给出描述 L 的正规表达式。五、( 12 分)已给文法 GS ： S SaP | Sf | P P qbP | q 将 GS 改造成 LL ( 1 )文法，并给出 LL ( 1 )分析表。六、( 12 分)给定文法 GS ： S Aa|dAb|Bb|dBa A c B c 构造文法 GS 的 LR ( 1 )分析表。七、( 8 分)将下面的条件语句表示

13、成逆波兰式和四元式序列：if a>b then x:=a+b*c else x:=b-a;八、( 8 分)给定基本块：A:=3*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+F假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后 的代码序列。参考答案：一、DA A CG.A BA (9) FA二、1 对于G中的每个产生式A -Y 1 | 丫 2 | 丫 m ,其各 候选式均应满足：( 1 )不同的候选式不能推出以同一终结符号打头的符号串,即FIRST( 丫 i) n FIRST( 丫 j )=©( 1 < i ,

14、j < m ; i j )(2)若有丫 j £,则其余候选式丫 i所能推出的符号串不能以FOLLOW(A) 中的终结符号开始,即有FIRST( 丫 i) n FOLLOW(A)=©( i < 1,2,，m ; i j )2 有三种分配存储空间的方式：( 1 )静态分配若在编译阶段就能确 定源程序中各个数据实体的存储空间大小,则可以采用较简单的静态存储管 理。适合静态管理的语言应具备条件： 数组上下界是常数、过程调用不 允许递归、不允许动态建立数据实体。 ( 2)栈式分配适用于允许递归 调用的程序设计语言 ；( 3 )堆式分配对于允许程序在运行时为变量 动 态申请

15、和释放存储空间 的语言,采用堆式分配是最有效的解决方案 。3 不变运算外提；运算强度削弱；消除归纳变量；下标变量地址计算优化。4 . 一个过程的一次执行所需信息的管理，是通过称为活动记录的连续存储块来实现的。活动记录的主要容有：（1）临时变量域 存放目标程序 临时变量的值；（2 ）局部数据域存放过程本次执行时的局部数据、简单 变量及数组情向量等；（3）机器状态域保存在调用过程前有关机器状态 的信息，包括各寄存器的当前值及返回地址等；（4 ）存取链 为访问其它活动记录中所存放的非局部数据所提供的链地址；（5）控制链指向主调过程的活动记录；（6 ）实参存放主调过程为被调用过程所提供的实参信 息；（

16、6 ）返回值为主调过程存放被调过程的返回值、化简后：S f ASe|AC A f Cb C f bC | d四、DFA如图所示。相应的正规式为（c|acc|bc）*五、改造后的文法：S f PS' S' f aPS'l fS' | e P f qP' P' f bP | e各候选式的FIRST集，各非终结符的FOLLOW集为产生式FIRST 集FOLLOWS f PS'q#S' f aPS'a#f fS'ff e e P f qP'qa,f,#P' f bPba,f,#f e e LL（1）分析表为tQft5tS'EFzE*E六、分析表如下图所示GOTO1bc