编译原理课后习题答案资料

《编译原理课后习题答案资料》由会员分享，可在线阅读，更多相关《编译原理课后习题答案资料（27页珍藏版）》请在金锄头文库上搜索。

1、ChapterChapterChapterChapter1 1 1 1 1解答： 程序设计语言：程序设计语言是遵守一定规范的、描述“计算”（Computing）过程的形式语言。一般可以划分为低级 语言和高级语言两大类。低级语言是面向机器的语言，它是为特定的计算机系统设计的语言，机器指令、汇编语言是低级语 言。高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示，例如 FORTRAN、Pascal、C 等 等我们熟悉的语言是高级语言。 语言处理程序： 由于目前的计算机只能理解和执行机器语言， 因此必须有一个程序将用程序设计语言书写的程序等价 （执 行效果完全一致）地转换为

2、计算机能直接执行的形式，完成这一工作的程序称为“语言处理程序”。它一般可分为解释程序 和翻译程序两大类。 翻译程序：翻译程序(Translator)是一种语言处理程序，它将输入的用程序设计语言书写的程序（称为源程序）转换 为等价的用另一种语言书写的程序（称为目标程序）。若源语言是汇编语言，目标程序是机器语言，称这种翻译程序为汇编 程序。若源语言是高级语言，目标程序是低级语言，称这种翻译程序为编译程序。 解释程序：解释程序（Interpreter）是一种语言处理程序，它对源程序逐个语句地进行分析，根据每个语句的含义执 行语句指定的功能。 2解答： 编译程序的总框图见图 1.2。其中词法分析器，又

3、称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一 个个的单词符号，其输出结果是单词符号。 语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断 输入串是否构成语法上正确的“程序”。 语义分析及中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成 一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直 接生成目标代码。 优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际 上是对中间代码

4、进行等价替换，使程序在执行时能更快，并占用更小的空间。 目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种机器无关的表示形式，只有把它再翻译成与机器硬件 直接相关的机器能识别的语言，即目标程序，才能在机器上运行。 表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结 果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格打交道。 出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告 给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理

5、、记录，并反映给用户 ChapterChapterChapterChapter2 2 2 2 1 试写出 VT0，1上下述集合的正则表达式： 所有以 1 开始和结束的符号串。 恰含有 3 个 1 的所有符号所组成的集合。 集合01，1。 所有以 111 结束的符号串。 解答： 1(0|1)*1|1 0*10*10*10* 01|1 (0|1)*111 2 试写出非负整数集的正则表达式。 试写出以非 5 数字为头的所有非负整数集的正则表达式。 解答： 0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 0|(1|2|3|4|6|7|8|9)(0|1|2|3|4

6、|5|6|7|8|9)* 3试将 2.8 中所示的有限状态自动机 M 最小化。 分析：只能对确定的有限状态自动机进行最小化，本题的自动机已经是确定的。 最小化采用状态分离法，具体做法如下： 进行 0 等价类的划分：Q 划分为 Qf与 QQf 若已进行了 k 等价划分，即 Q 已被划分成（Q1，Q2，Qn），再进行 k1 划分，对 Qi（i1n），若 q、qQi，使得 对某一个 aVT，（q，a）Qj和（q，a）Ql，jl 或（q，a）存在而（q，a）不存在或反之。则将 Qi划分为二个 子集 Qi1，Qi2，使 qQi1，q Qi2。 重复直至无法进一步划分为止。对最后划分得到的状态子集中每一个

7、子集，选择该子集中任何一个状态作为该状态子 集的代表，然后修改原来的有限状态自动机的状态转换函数，凡在作用下转向某状态子集中任何一个状态的一律改成转向 该状态子集的代表。若一个状态子集中某一状态是原来的开始状态，则该状态子集的代表就是新的有限状态自动机的开始状 态。同理，若一个状态子集中的状态均是最终状态，则该状态子集的代表就是新的有限状态自动机的最终状态。 抹去可能存在的无用状态与不可及状态。 解答：此有限状态自动机的状态转换表如表 3.1 所示： 表 2.1 M 的状态转换表 ab ABC BDC CBE DDFAccept EGEAccept FGEAccept GDFAccept 由此

8、看出：此有限状态自动机是确定的。 最小化： 初始划分由 2 个子集组成，即：（A,B,C,D,E,F,G） 集合D,E,F,G不需要进一步划分，考察子集A,B,C。由于 （B,a）=DD,E,F,G，而（A,a）（C,a）BA,BC， 因此 Q 可进一步划分为：（A,C,B,D,E,F,G）。由于 （A,b）CA,C，而（C，b）ED,E,F,G。 因此 Q 可进一步划分为：（A,C,B,D,E,F,G）。 这时不能再划分了，得到的最小化的有限状态自动机如表 3.2 所示： 表 2.2 最小化的有限状态自动机 ab ABC CBE BDC DDDAccept 4某程序语言的无（正负）符号常数可

9、以用下面正则表达式 R 来表示： （D+E|D+.D+E|E|.D+E）(+|-)D|D)D*|D+|D*.D+ 试把它转换成确定性有限状态自动机。 把上述有限状态自动机最小化。 在上述有限状态自动机中添加相应动作，取出无（正负）符号常数。 分析：从正则表达式构造有限状态自动机可以分两步进行。 画一条从结点 X 到结点 Y 的有向弧，有向弧上标以正则表达式R。结点 X 为标以“”的初始状态，结点 Y 为标以“”的 最终状态。从这一有向图出发反复应用图 3.2 所示的替代规则，直至所有有向弧都以 VT中的符号或标记为止。 图2.23 条替代规则 消除应用所得到的传递图中的弧，可以分为两步：首先消

10、除环路，其次消除其他弧。 a)环路的消除方法： i将环路的诸项合并为一个顶点。 ii修改各个相关的有向弧。 iii若环路中某一状态是最终（或初始）状态，则新顶点是最终（或初始）状态。 b)其它弧的消除有两种方法： 1）子集法：即计算-Closure（T） ，其表示从状态集 T 中任何一状态沿弧可以到达的状态全体。 其要点是：从初始状态 q0的 X=-Closure（q0）开始，按如下方法构造状态集： i令 SetX； ii若 Set 中还有未考察过的状态子集 Xi，则对于每一输入符号 aVT，求 T=-Closure（move（Xi,a） ） ，Set=SetT（其中 move(Xi,a)=q

11、|q(p,a),pXi） 。重复执行（2） ，直至不存在这样的 Xi。这样得到的 Set 即为消除弧后的确定的有限状态机 （DFA） 。DFA 的初始状态就是-Closure（q0） ，最终状态由那些至少含有一个最终状态的状态子集组成。 2）逐步消除法： 其要点是找到类似于图2.3 所示，但从 B 再无弧引出的弧。 图2.3逐步消除法 删除状态 A 到状态 B 的弧，对每一条从状态 B 到状态 C 标记为 ai的弧，增加 1 条从状态 A 到状态 C 标记为 ai的弧。若B 是最终状态，则让 A 为最终状态。重复上述过程直至消除全部的弧，这样得到的一般是不确定的有限状态自动机（NFA）。 解答

12、： 图 3.4 给出了从正则表达式 R 构造有限状态自动机 M 的过程。 图2.4 替代规则的应用过程 应用子集法消除?弧： -Closure（x）=x,2，令 A1x,2，计算： -Closure（move（A1，D） ）-Closure（7,10,2,1）=7,10,2,1,y -Closure（move（A1， ） ）=-Closure（5,3）=5,3 -Closure（move（A1，E） ）-Closure（4）=4 令 A27,10,2,1,y，A35,3，A44，计算： -Closure（move（A2，D） ）7,10,2,1,y -Closure（move（A2， ） ）8

13、,3 -Closure（move（A2，E） ）4 -Closure（move（A3，D） ）5,6,3,y -Closure（move（A4，D） ）12,y -Closure（move（A4，） ）11 -Closure（move（A4，） ）11 令 A58,3，A65,6,3,y，A7=12,y，A811，计算： -Closure（move（A5，D）8,9,3,y -Closure（move（A6，D）5,6,3,y -Closure（move（A6，E）4 -Closure（move（A7，D）12,y -Closure（move（A8，D）12,y 令 A98,9,3,y，计算：

14、 -Closure（move（A9，D）8,9,3,y -Closure（move（A9，E）4 得到的 DFA M的初始状态是 A1，最终状态集由 A2，A6，A7，A9组成。 图2.5 是 M的状态转换图，M的状态转换表如表2.3 所示。 表2.3M的状态转换表 DE+- A1A2A4A3 A2A2A4A5Accept A3A6 A4A7A8A8 A5A9 A6A6A4Accept A7A7Accept A8A7 A9A9A4Accept 图2.5M的状态转换图 采用状态分离法： 初始时分成 2 个子集，即：(A1,A3,A4,A5,A8,A2,A6,A7,A9) 考察子集 A2,A6,A

15、7,A9，它进一步可分成： （A6,A9,A2,A7） 考察子集 A1,A3,A4,A5,A8，它进一步分成： （A4,A1,A8,A3,A5） 不能再进一步划分了，得到的最小化的有限状态自动机如图2.6 所示： 图2.6最小化的有限状态自动机 由于数的表示和具体的机器有着内在联系，这里仅将此无（正负）符号常数的十进制数部分和指数部分分别存入 2 个工作 单元。设立下述工作单元： 此常数的十进制数部分number 此常数的指数部分exp 小数点位数n 此常数指数部分正负号expsign 这 4 个工作单元进入有限状态自动机的模拟程序时被初始化为 0。 函数过程 getchar，其功能是读入下一个字符到工作单元 char 中。 函数过程 value，其功能是求出存放在工作单元 char 中数字字符的值。 经过加工后的状态矩阵如表 2.4所示： 表2.4加工后的状态矩阵 DE+- A1#1,A2#2,A3#2,A4 A2#3,A2#2,A3#2,A4#10,Accept A3#4,A6 A4#5,A7#6,A8#7,A8 A6#4,A6#2,A4#11,Accept A7#8,A7#12,