资源描述：
《编译原理自测题附答案(有错).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章一．填空题1．编译程序的工作过程一般可以划分为词法分析、语法分析、语义分析与中间代码产生、优化和生成目标程序等几个基本阶段，同时还伴有符号表管理和出错处理。2．若源程序是用高级语言编写的，目标程序是汇编或机器语言，则其翻译程序称为编译程序。3．编译方式与解释方式的根本区别在于运行目标程序时的控制权在解释器而不是目标程序。4．翻译程序是这样一种程序，它能将用甲种语言书写的程序转换成与其等价的乙种语言书写的程序。5．对编译程序而言，输入数据是高级语言（源）程序，输出结果是低级语言（目标）程序。6．运行编译程序的计算机称宿主机
2、，运行编译程序所产生目标代码的计算机称目标机。7．当把编译程序划分成编译前端和编译后端时，前端主要由与源语言有关但与目标机无关的部分组成，编译后端包括编译程序中与目标机有关的部分，编译后端不依赖于源语言而仅仅依赖于中间语言。8．描述词法规则的有效工具是词法分析器，通常使用语法分析器来描述语法规则，使用语义分析（与中间代码产生）器描述语义规则。二．综合题（该答案仅供参考）1、给出C语言编译程序对下面语句进行编译时从词法分析到目标代码生成5个分析阶段的分析过程。c=a+b*30;（1）给出每个阶段的输入和输出代码或其它数据形式。（
3、2）给出符号表，说明在哪些阶段会对符号表进行填写或查找。（3）编译过程是否进行了代码优化？若有，请指出优化之处，并给出属于哪种优化？答：词法分析：出入源程序；输出识别出的记号流。c=a+b*30id1=id2+id3*30语法分析器：输入记号流，构造句子结构；输出语法树。=id1+id2*id330语义分析与中间代码生成：出入语法树，输出中间代码变量地址数值注：赋值阶段会对符号表进行填写或查找1.id10c（itr，30，，t1）2.id24x（*，id3，t1，t2）3.id38y（+，id2，t2，t3）4.t11230（
4、=，t3，，id1）优化：1.（*，id3，30.0，t1）2.（+，id2，t1，id1）精简掉多余的复写传播目标代码：movid3，r29mulf#30.0，r2movid2，r1subr1，r2movr2，id1第二章一．填空题1．上下文无关文法包括以下四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。2．如果一个文法存在某个句子对应两棵不同的语法树，则这个文法是二义文法。3．消除文法的二义性的方法主要有：改写二义文法为非二义文法；为文法符号规定优先顺序和结合规则。二简答题1．有文法G：E→E+E
5、│E*E│(E)│id（1）给出(id*id)+id的最左推导；E（E）（E+E）（E*E+E）（id*E+E）（id*id+E）（id*id+id）（2）并给出该推导过程中的所有句型；见（1）,把箭头去掉即可（3）给出该文法的2个句子。1*1+12*2+2第三章一综合题31．给出书中P48图3.5中所示有限自动机的状态转换矩阵和五元式，并说明该有限自动机可识别哪一类字符串。状态abay6x541012空空aa空a空1322213bbb333b(5,3,1,2,6,y）(5,4,1,2,6,y)可识别相继两个a或相继两个b的字
6、2．构造与正规式（a｜b）*a(a｜b)或(0
7、1)*0(0
8、1)等价的状态最少的确定有限自动机。（1）构造转换系统如下图所示。9aaZCaBεεSAbb正则式（a｜b）*a(a｜b)的转换系统（2）NFA确定化为DFA的过程如下表所示：IIaIb①[S,A,B]②[A,B,C]③[A,B]②[A,B,C]④[A,B,C,Z]⑤[A,B,Z]③[A,B]②[A,B,C]③[A,B]④[A,B,C,Z]④[A,B,C,Z]⑤[A,B,Z]⑤[A,B,Z]②[A,B,C]③[A,B]相应DFA的状态图如下所示a4a2aa1bab5
9、bb3b正则式（a｜b）*a(a｜b)的DFA将DFA最小化：首先得到两个子集K1={1,2,3}和K2={4，5}由于状态1和状态3输入a都到达状态2，输入b都到达状态3，而状态2输入a到达状态4，输入b到达状态5，所以将K1分割成K11={1,3}和K12={2}9又由于状态4输入b到达K2，而状态5输入b到达K11,所以状态4、5是可分的。这样，将原状态集合分割成以下子集：{1，3}，{2}，{4}，{5}所以最小化DFA的状态图如下所示，2aaaba41bbb5正则式（a｜b）*a(a｜b)的最小化DFA1．构造与正规
10、式(a
11、ba)*等价的状态最少的确定有限自动机。iab31b(x,1)(1,y)(1,2)y1x空a(1,y)----aa(1,2)(1,y)--22ba4、P64:习题8（1）以01结尾的二进制数串（2）能被5整除的十进制整数第四章&第五章&第七章一．填空题1．自上而下语法
