计算机编译原理课后习题及答案详细解析

资源描述

《计算机编译原理课后习题及答案详细解析》由会员分享，可在线阅读，更多相关《计算机编译原理课后习题及答案详细解析（60页珍藏版）》请在金锄头文库上搜索。

1、在此深情而热烈的感谢沈仲秋同学的大力支持和帮助，同时希望本文档对各位有些帮助。一1、画出编译程序的总体结构图，简述其部分的主要功能。答案编译程序的总框图见下图。图编译程序的总体结构图其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果上单词符号。语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不

2、同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能识别的语言，即目标程序，才能在机器上运行。表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中，所需要的信息也大多从表格中获取，整个编译过

3、程都在不断地和表格打交道。出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。 2、计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么? 答案计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。像Basic之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，

4、再执行，如此反复。总而言之，是边翻译边执行。像C，Pascal之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上看，编译型的高级语言比解释型的高级语言更快。1.文法GS为： S-Ac|aBA-ab B-bc 写出L(GS)的全部元素。答案 S=Ac=abc 或S=aB=abc 所以L(GS)=abc 2. 文法GN为： N-D|ND D-0|1|2|3|4|5|6|7|8|9 GN的语言是什么？答案 GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD. =NDDDD.D=D

6、法的基本定义是：A-,AVn，（VnVt）*，注意关键问题是保证anbn的成立，即“a与b的个数要相等”，为此，可以用一条形如A-aAb|ab的产生式即可解决。答案构造上下文无关文法如下： S-AB|A A-aAb|ab B-Bc|c 扩展凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路是这样的：要求符合anbncm，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而cm做为另一个单位，初步产生式就应写为S-AB，其中A推出anbn，B推出cm。因为m可为0，故上式进一步改写为S-AB|A。接下来考虑A,凡是要求两个终结符个数相等的问题，都应写为A-aAb|

7、ab形式，对于B就很容易写成B-Bc|c了。6.写一文法，使其语言是偶正整数集合。要求： (1)允许0开头； (2)不允许0开头。答案 (1)允许0开头的偶正整数集合的文法，注意：0不是正数。E-NT|G|SFMT-NT|GN-0|1|2|3|4|5|6|7|8|9D-0|2|4|6|8G-2|4|6|8S-NS|F-1|2|3|4|5|6|7|8|9M-M0|0 (2)不允许0开头的偶正整数集合的文法 E-NT|DT-FT|GN-D|1|3|5|7|9D-2|4|6|8F-N|0G-D|0 答案| 返回 | 上一题 | 下一题 |7.已知文法G： E-E+T|E-T|T T-T*F|T/

8、F|F F-(E)|i 试给出下述表达式的推导及语法树 (1)i; (2)i*i+i (3)i+i*i (4)i+(i+i)答案 (1) E=T=F=i(2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i(3)E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i(4)E=E+T=T+T=F+T=i+T=i+F=i+(E)=i+(E+T)=i+(T+T)=i+(F+T) =i+(i+T)=i+(i+F)=i+(i+i) 8.为句子i+i*i构造两棵语法树，从而证明下述文法G是二义的。表达式-表达式运算符表达式|(表达式)|

9、i 运算符-+|-|*|/答案可为句子i+i*i构造两个不同的最右推导: 最右推导1 表达式=表达式运算符表达式=表达式运算符i=表达式* i=表达式运算符表达式* i=表达式运算符i * i=表达式+ i * i= i + i * i 最右推导2 表达式=表达式运算符表达式=表达式运算符表达式运算符表达式=表达式运算符表达式运算符 i=表达式运算符表达式 * i= 表达式运算符i * i=表达式+ i * i= i + i * i所以，该文法是二义的。9. 文法GS为： S-Ac|aB A-ab B-bc 该文法是否为二义的？为什么？答案对于串abc(1)S=Ac=abc(2)S=aB

10、=abc即存在两不同的最右推导所以，该文法是二义的。 10.考虑下面上下文无关文法： S-SS*|SS+|a (1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 (2) GS的语言是什么？答案 (1)此文法生成串aa+a*的最右推导如下:S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*(2)该文法生成的语言是即加法和乘法的逆波兰式, 11. 令文法GE为: E-E+T|E-T T-T*F|T/F|F F-(E)|I 证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序列: E=E+

11、T=E+T*F，所以 E+T*F句型。此句型相对于E的短语有:E+T*F；相对于T的短语有T*F,直接短语为：T*F。句柄为：T*F 。 12.已知文法GE:EET+|T TTF* | F FF | a试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄。答案该句型对应的语法树如下：该句型相对于E的短语有FF*；相对于T的短语有FF*,F;相对于F的短语有F;F;简单短语有F;F;句柄为F.13.一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。答案

展开阅读全文

计算机编译原理课后习题及答案详细解析

最新文档