《《编译原理》模拟试题六.doc》由会员分享，可在线阅读，更多相关《《编译原理》模拟试题六.doc（12页珍藏版）》请在三一文库上搜索。
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程序中的表达式语句在语义翻译时不需要回填技术。(V)10对中间代码的优化依赖于具体的计
2、算机。()二、选择题 (请在前括号选择最确切的一项作为答案划一个勾，多划按错论40 分)( )(每个 4 分，共1编译程序绝大多数时间花在 上。A( ) 出错处理C ( ) 目标代码生成2 编译程序是对 B ( ) 词法分析D ( ) 表格管理A( ) 汇编程序的翻译C( ) 机器语言的执行B( ) 高级语言程序的解释执行D( ) 高级语言的翻译3采用自上而下分析，必须 。A( ) 消除左递归B( ) 消除右递归C( ) 消除回溯D( ) 提取公共左因子4在规归约中，用 来刻画可归约串。A( )直接短语B( )句柄C( )最左素短语D( )素短语5. 若a为终结符，则A- a B为项目。A(
3、)归约B( ) 移进C( )6. 间接三元式表示法的优点为 A.( ) 采用间接码表，便于优化处理C.( ) 便于优化处理，节省存储空间7. 基本块的优化为 。A. ( ) 代码外提，删除归纳变量C.( ) 强度削弱，代码外提8. 在目标代码生成阶段，符号表用接受 D.( ) 待约B.( ) 节省存储空间，不便于表的修改D.( ) 节省存储空间，不便于优化处理B.( ) 删除多余运算，删除无用赋值D.( ) 循环展开，循环合并A.( ) 目标代码生成B.( ) 语义检查C.( ) 语法检查D.( ) 地址分配9.若项目集Ik含有A-a 则在状态k时，仅当面临的输入符号a FOLLOW(A)时，
4、才采取“A-a ”动作的一定是 。A. ( ) LALR 文法C.( ) LR(1) 文法B . ( ) LR(0)文法D. ( ) SLR(1)文法A. ( ) 先请先放B ( ) 先请后放C( ) 后请先放D. ( ) 任意三、填空题 (每空 1 分，共 10 分 )1词法分析基于 _正则 _文法进行，即识别的单词是该类文法的句子。2语法分析基于 _上下文无关 _文法进行， 即识别的是该类文法的句子。 语法分析的有效 工具是 _语法树 _。3分析句型时， 应用算符优先分析技术时，每步被直接归约的是_最左素短语 _，而应用LR 分析技术时，每步被直接归约的是 _句柄 _。4语义分析阶段所生成
5、的与源程序等价的中间表示形式可以有_逆波兰 _、 _四无式表示_与 _三元式表示 _等。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)*101 相应的 DFA 。 解：先构造 NFA ：确定化:01XAAAABABACABACAABYABY徐AB重新命名，令 AB为B、AC为C
6、、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)的最左推导为：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,
7、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-LSo| &K-dML| L-eHfM-K|bLM判断G是否为LL(1)文法，如果是，构造 LL(1)分析表。解：各符号的FIRST集和FOLLOW集为：FIRSTFOLLOWSgdh E i伽何讣H宀LK预测分析表为:adefV#SMHM-K-K-K-bLMQKH-! L-eHfK- E_n E由于预测分析表中无多重入口，所以可判定文法是LL(1)的。五. 计算题(10分)
8、 已知文法GS为:S-aF|(T)T- T,S|S(1) 计算 GS的 FIRSTVT 和 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(b then x:=a+b*c else x:=b-a
9、;八、( 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 , j m ; i j )(2)若有丫 j ,则其余候选式丫 i所能推出的符号串不能以FOLLOW(A) 中的终结符号开始,即有FIRST( 丫 i) n FOLLOW(A)=( i , a, b,)(j,)(*, b, c, T1)(+, a, T1, T2)(:=,T2, , x)(j, , , (9)(-,b, a, T3)(8) (:=, T3, , x)(9) ()八、化简后的的四元式序列为A :=D+12E :=E+FC :=28