编译原理课后习题答案.doc

第一章1解答：程序设计语言：程序设计语言是遵守一定规范的、描述“计算”（Computing）过程的形式语言。一般可以划分为低级语言和高级语言两大类。低级语言是面向机器的语言，它是为特定的计算机系统设计的语言，机器指令、汇编语言是低级语言。高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示，例如FORTRAN、Pascal、C等等我们熟悉的语言是高级语言。语言处理程序：由于目前的计算机只能理解和执行机器语言，因此必须有一个程序将用程序设计语言书写的程序等价（执行效果完全一致）地转换为计算机能直接执行的形式，完成这一工作的程序称为“语言处理程序”。它一般可分为解释程序和翻译程序两大类。翻译程序：翻译程序(Translator)是一种语言处理程序，它将输入的用程序设计语言书写的程序（称为源程序）转换为等价的用另一种语言书写的程序（称为目标程序）。若源语言是汇编语言，目标程序是机器语言，称这种翻译程序为汇编程序。若源语言是高级语言，目标程序是低级语言，称这种翻译程序为编译程序。解释程序：解释程序（Interpreter）是一种语言处理程序，它对源程序逐个语句地进行分析，根据每个语句的含义执行语句指定的功能。2解答：编译程序的总框图见图1.2。其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号。 语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。 语义分析及中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。 优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。 目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种机器无关的表示形式，只有把它再翻译成与机器硬件直接相关的机器能识别的语言，即目标程序，才能在机器上运行。 表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格打交道。出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户 Chapter 21 试写出VT0，1上下述集合的正则表达式： 所有以1开始和结束的符号串。 恰含有3个1的所有符号所组成的集合。 集合01，1。 所有以111结束的符号串。解答： 1(0|1)*1|1 0*10*10*10* 01|1 (0|1)*1112 试写出非负整数集的正则表达式。 试写出以非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|5|6|7|8|9)* 3试将2.8中所示的有限状态自动机M最小化。分析：只能对确定的有限状态自动机进行最小化，本题的自动机已经是确定的。最小化采用状态分离法，具体做法如下： 进行0等价类的划分：Q划分为Qf与QQf 若已进行了k等价划分，即Q已被划分成（Q1，Q2，Qn），再进行k1划分，对Qi（i1n），若q、qQi，使得对某一个aVT，d（q，a）Qj和d（q，a）Ql，jl或d（q，a）存在而d（q，a）不存在或反之。则将Qi划分为二个子集Qi1，Qi2，使qQi1，q Qi2。 重复直至无法进一步划分为止。对最后划分得到的状态子集中每一个子集，选择该子集中任何一个状态作为该状态子集的代表，然后修改原来的有限状态自动机的状态转换函数d，凡在d作用下转向某状态子集中任何一个状态的一律改成转向该状态子集的代表。若一个状态子集中某一状态是原来的开始状态，则该状态子集的代表就是新的有限状态自动机的开始状态。同理，若一个状态子集中的状态均是最终状态，则该状态子集的代表就是新的有限状态自动机的最终状态。 抹去可能存在的无用状态与不可及状态。解答：此有限状态自动机的状态转换表如表3.1所示：表2.1 M的状态转换表abABCBDCCBEDDFAcceptEGEAcceptFGEAcceptGDFAccept由此看出：此有限状态自动机是确定的。最小化：初始划分由2个子集组成，即：（A,B,C,D,E,F,G）集合D,E,F,G不需要进一步划分，考察子集A,B,C。由于d（B,a）=DD,E,F,G，而d（A,a）d（C,a）BA,BC，因此Q可进一步划分为：（A,C,B,D,E,F,G）。由于d（A,b）CA,C，而d（C，b）ED,E,F,G。因此Q可进一步划分为：（A,C,B,D,E,F,G）。这时不能再划分了，得到的最小化的有限状态自动机如表3.2所示：表2.2 最小化的有限状态自动机abABCCBEBDCDDDAccept4某程序语言的无（正负）符号常数可以用下面正则表达式R来表示：（D+E|D+.D+E|E|.D+E）(+|-)D|D)D*|D+|D*.D+ 试把它转换成确定性有限状态自动机。 把上述有限状态自动机最小化。 在上述有限状态自动机中添加相应动作，取出无（正负）符号常数。分析：从正则表达式构造有限状态自动机可以分两步进行。 画一条从结点X到结点Y的有向弧，有向弧上标以正则表达式R。结点X为标以“”的初始状态，结点Y为标以“”的最终状态。从这一有向图出发反复应用图3.2所示的替代规则，直至所有有向弧都以VT中的符号或标记e为止。 图2.2 3条替代规则 消除应用所得到的传递图中的弧，可以分为两步：首先消除环路，其次消除其他弧。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|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）。解答： 图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,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，计算：-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.3 M的状态转换表DE+-A1A2A4A3A2A2A4A5AcceptA3A6A4A7A8A8A5A9A6A6A4AcceptA7A7AcceptA8A7A9A9A4Accept图2.5 M的状态转换图采用状态分离法：初始时分成2个子集，即：(A1,A3,A4,A5,A8,A2,A6,A7,A9)考察子集 A2,A6,A7,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,A4A2#3,A2#2,A3#2,A4#10,AcceptA3#4,A6A4#5,A7#6,A8#7,A8A6#4,A6#2,A4#11,AcceptA7#8,A7#12,AcceptA8#9,A7矩阵中元素A1，A2，.，A7表示应该转换的下一个状态。1，2，.，12表示应该执行的语义子程序。各语义子程序的代码归结如下：1：number:=value（char）;getchar;2：getchar;3：number:=number*10+value（char）;getchar;4：n:=n+1; number:=number*10+value（char）;getchar;5：expsign:=1;exp:=value（char）;getchar;6：expsign:=1;getchar;7：expsign=-1;getchar;8：exp:=exp*10+value（char）;getchar;9：exp:=value（char）;getchar;10：按硬件要求构造无（正负）符号数；11：exp:=-n; 按硬件要求构造无（正负）符号数；12：if expsign=-1 then exp:=-exp;exp=exp-n; 按硬件要求构造无（正负）符号数；5.设要识别的单词有限集是STEP,SWITCH,STRING，相应正则表达式是STEP|SWITCH|STRING，试把它转换成确定性有限状态自动机。解答：6设VTa,b，试构造下述正则表达式的确定性有限状态自动机： a(a|b)*baa (a|b)*bbb*解答： 由此正则表达式构造的有限状态自动机M1的状态转换图如图2.7所示：图2.7 有限状态自动机M1的转换图确定化（表3.5）：表3.5 M1的确定化Qdadb12222,32,32,42,32,42,52,32,522,3A对应的状态转换图如图3.8所示：图2.8 DFA M1的状态转换图 由正则表达式构造的有限状态自动机M2的状态转换图如图2.9所示：图2.9 M2的状态图确定化（表2.6）：表2.6 M2的确定化Qdadb111,21,211,2,31,2,311,2,3对应的状态转换图如图2.10所示：图2.10 DFA M2的状态转换图9对于下列的状态转换矩阵：abSASAABBBBZabSASABAZBBB 分别画出相应的状态转换图。 用自然语言分别描述它们所识别的输入串的特征。解答： 表1所对应的状态转换图如图2.11所示：图2.11 表3.6对应的状态转换图表2所对应的状态转换图如图2.12所示：图2.12 表3.7对应的状态转换图 表1所识别的输入串是：以b*aa*b开头的后接任意多个a或b的a,b上的字符串。表2所识别的输入串是：仅含有一个a的a,b上的字符串。10. 将习题图2.1所示的非确定的有限状态自动机确定化和最小化。习题图2.1 非确定的有限状态自动机M解答：确定化（表2.8）：表2.8 M的确定化abSAAB,CAB,CAZ令BB,C对应的状态转换图如图2.14所示：图2.14 DFA M的状态转换图确定化的M已是最小化的。11.消除传递图T（习题图2.2）中的 e 弧。习题图2.2传递图T解答：i）先消除e环路，合并状态2和3，得到的传递图T如图3.16所示：图2.16 消除?环路的传递图Tii）采用逐步消除法去除其他e弧，最终得到的传递图T如图2.17所示：图2.17 消除所有e弧的传递图Chapter 32设有文法G1：|D0|1|2|9试写出028和4321的最左推导和最右推导过程。分析：在每一步的推导中，都是对最左的那个非终结符用相应的产生式的右部来替换，这样的推导称为最左推导。类似地，如果每一步的推导中都是对最右的那个非终结符用相应的产生式的右部来替换，这样的推导称为最右推导，最右推导又称规范推导。解答：028的最左推导：002028028的最右推导：8828280284321的最左推导：44343243214321的最右推导：11212132132143213证明文法G是二义性文法：ifthenelse|ifthen|s0|1分析：只要找出该文法的一个二义性句子即可证明。解答：句子if 0 then if 1 then s else s 对应如下两棵不同的推导树：图3.1 句子if 0 then if 1 then s else s的推导树（1）图3.1 句子if 0 then if 1 then s else s的推导树（2）4设有文法G：-|/|i|() 试写出i/(i-i-i)的推导树。 试写出（-i）/的短语、简单短语和句柄。分析：只要给出句型（句子）对应的推导树就容易求出短语、简单短语和句柄。解答： i/(i-i-i)的推导树如下：图3.3 句子i/(i-i-i)的推导树（-i）/的推导树如下：图3.4 句子（-i）/的推导树短语：，i，-i，（-i），（-i）/简单短语：，i句柄：5对布尔矩阵求B+。解答：利用Warshall算法求解的结果如下：7对表结构语言G：a|(),| 试给出(a,(a,a)的最左和最右推导。 指出(a,a),(a),a)的最右推导，以及规约的每一步的句柄。 给出(a,a),(a),a)的推导树自下而上的构造过程。分析：本题是要让读者明确，自下而上构造推导树的过程是最右推导(规范推导)的逆过程，这一过程正是自底向上句法分析的过程，其要点是找句柄、归约。解答： 句子(a,(a,a)的最左推导为：()(,)(,)(a,)(a,()(a,(,)(a,(,)(a,(a ,)(a,(a,a)最右推导为：()(,)(,()(,(,)(,(,a)(,(,a)(, (a,a)(,(a,a)(a,(a,a) 句子(a,a),(a),a)的最右推导及归约的每一步句柄如表3.1所示：表3.1 句子(a,a),(a),a)的最右推导过程最右推导每一步归约时的句柄()()(,),(,a)a(,a) (),a)()(,),a),(,(),a)()(,(),a)(,(a),a)a(,(a),a),(,(a),a)(,(a),a)(),(a),a)()(,),(a),a),(,a),(a),a)a(,a),(a),a)(a,a),(a),a)a 句子(a,a),(a),a)的推导树如图3.5所示:图3.5 句子(a,a),(a),a)的推导树构造过程如图3.6所示:图3.6 句子(a,a),(a),a)的推导树自下而上的构造过程Chapter 4（略）Chapter 51. 考察算术表达式翻译文法T1：T1=(+,*,(,),C,C,ADD,MUL,R,)其中R由下面规则组成：+,ADD,*,MUL,(),C,C其相应输入文法是LR(1)。试对该输入文法的下推自动机控制表作适当改动，构造翻译下推自动机的控制表，使该翻译下推自动机把任何一个由C,+,*组成的中缀表达式翻译成后缀表达式。分析：设翻译文法中的翻译规则形如：x，y把自底向上的下推自动机改造成相应的下推翻译自动机的方法很简单：只需规定，当下推自动机应用产生式i进行规约的同时，输出y中的输出符号。解答：输入文法的LR(1)状态集如表5.1。表5.1 输入文法的LR(1)状态集状态T项目集文法符号BGOTO（T，B）0*, 1+, /+1, /+2*, /+/*2, /+/*3(), /+/*(4C, /+/*C51*Accept*+, /+62*, /+/+#2*, /+/*73*, /+/*/+/*#44*(), /+/*8+, )/+8, )/+9*, )/+/*9, )/+/*10(), )/+/*(11C, )/+/*C125*C, /+/*/+/*#66*+, /+13*, /+/*13, /+/*3(), /+/*(4C, /+/*C57*, /+/*14(), /+/*(4C, /+/*C58*(), /+/*)15*+, )/+169*, )/+)/+#2*, )/+/*1710*, )/+/*)/+/*#411*(), )/+/*18+, )/+18, )/+9*, )/+/*9, )/+/*10(), )/+/*(11C, )/+/*C1212*C, )/+/*)/+/*#613*+, /+/+#1*, /+/*714*, /+/*/+/*#315*(), /+/*/+/*#516*+, )/+19*, )/+/*19, )/+/*10(), )/+/*(11C, )/+/*C1217*, )/+/*20(), )/+/*(11C, )/+/*C1218*(), )/+/*)21*+, )/+1619*+, )/+)/+#1*, )/+/*1720*, )/+/*)/+/*#321*(), )/+/*)/+/*#5翻译下推自动机的控制表如表5.2所示：表5.2 翻译下推自动机的控制表状态T动作表（Action）转向表（Goto）+*()C0S4S51231S6Acc2R#2S7R#23R#4R#4R#44S11S1289105R#6, GEN(C)R#6, GEN(C)R#6,GEN(C)6S4S51337S4S5148S16S159R#2S17R#210R#4R#4R#411S11S121891012R#6, GEN(C)R#6, GEN(C)R#6, GEN(C)13R#1,GEN(ADD)S7R#1,GEN(ADD)14R#3,GEN(MUL)R#3,GEN(MUL)R#3,GEN(MUL)15R#5R#5R#516S11S12191017S11S122018S16S2119R#1,GEN(ADD)S17R#1,GEN(ADD)20R#3,GEN(MUL)R#3,GEN(MUL)R#3,GEN(MUL)21R#5R#5R#52. 考察下述文法G：i:=+*()i试写出各产生式的语义子程序。解答：让非终结符带有属性.type指出数据类型，属性.val存放运算结果。 i:=if i.type=.type then GEN(:=,.val,i.val);else if i.type=real AND .type=int then begin T:=NEWTEMP; GEN(float,.val,T); GEN(:=,T,i.val); end.else if i.type=int AND .type=real then begin T:=NEWTEMP; GEN(int,.val,T); GEN(:=,T,i.val); end.else error. E1+.val:=NEWTEMP;if .type=int AND .type=int then begin .type:=int; GEN(int+,.val, .val,.val); end.else if .type=real AND .type=real then begin .type:=real; GEN(real+,.val, .val,.val); end.else if .type=int AND .type=real then begin .type:=real; T:=NEWTEMP; GEN(float, .val,T); GEN(real+,T, .val,.val); end.else if .type=real AND .type=int then begin .type:=real; T:=NEWTEMP; GEN(float, .val,T); GEN(real+, .val,T,.val); end.else error.*.val:=NEWTEMP;if .type=int AND .type=int then begin .type:=int; GEN(int*,.val, .val,.val); end.else if .type=real AND .type=real then begin .type:=real; GEN(real*,.val, .val,.val); end.else if .type=int AND .type=real then begin .type:=real; T:=NEWTEMP; GEN(float, .val,T); GEN(real*,T, .val,.val); end.else if .type=real AND .type=int then begin .type:=real; T:=NEWTEMP; GEN(float, .val,T); GEN(real*, .val,T,.val); end.else error.().val:= .val;.type:= .type;i.val:= i.val;.type:=i.type;Chapter 6（略）Chapter 71.考察下面程序段：procedure p(x,y,z)beginy:=y+1;z:=z+x;end;begina:=2;b:=3;p(a+b,a,a);write(a);end;若参数通信分别是： 按名 按值方式，上述程序执行后，输出a的值分别是多少？解答：按名调用的特点是：在被调用过程执行时，用实参替换形参，然后执行替换后的程序，因此本程序相当于执行如下程序段：a:=2；b:=3；a:=a+1；a:=a+a+b；输出a的值是9。按值调用的特点是：传送的是实在参数的当时值，该值成为形参的初值，是一种单向