编译原理习题答案课件.ppt

习题及解答：;2、叙述编译程序的逻辑结构和实现机制 根据语言和环境的不同，编译程序实现时是把 图中的各阶段划分成若干遍；典型的情况是两遍的编译程序： 第一遍 :词法分析 、语法分析和语义分析。即前端完成分析，一般与机器无关。 第二遍 :目标代码生成和目标代码优化。即后端完成综合，一般与机器有关。 每遍中的各阶段的工作是穿插进行的， 例如： 使语法分析器处于核心位置,而把词法分析器作为子程序；当语法分析需要下一个单词时，就调用词法分析器，识别一个单词。 ;第二章;;2、试构造下述语言L的文法： L={ ambn |m≥0,n≥1}; S - AB A - Aa |ε B - Bb | b or S - AB A - aA |ε B - bB | b ;3、试求下述文法G(Z)所定义的语言： G(Z): Z-b|bB , B-bZ Z = b Z = bB = bbZ = bbb Z = bB = bbZ = bbbB = bbbbZ = bbbbb Z = b2n-1 , n≥1 ;第三章;（3）包含奇数个1或奇数个0的二进制数串。 本题求二进制串，并且要求包含奇数个0或奇数个1，由于0和1都可以在二进制串中任何地方出现，所以本题只需要考虑一种情况，另外一种情况也可以类似求得。考虑包含奇数个0的字符串:由于只关心0的个数的奇偶数，我们可以把二进制串分成多段来考虑，第1段为二进制串的开始到第1个0为止，这一段包含1个0，并且0的前面有0个或多个1，对于剩下的二进制串按照每段包含两个0的方式去划分，即以0开始，以0结尾，中间可以有0个或多个1，和果一个二进制串被这样划分完后，剩下的部分如果全部是全1串(这些全1串在前面划分的串之间或最后)，则该二进制串就具有奇数个0，所以该二进制串可以这样描述:以第1段(1*0)开始，后面由全1串(1*)以及包含两个0的串(01*0)组成，所以包含奇数个0的正规表达式为:1*0(1|01*0)*，本题的解答则是:1*0(1|01*0)*|0*1(0|10*1)*。 ;2.给定正规式(a|b)*a(a|b)，构造其最小DFA M。(参见书图 3.7) 首先将其分为终态集{3,4}和非终态集{0,1,2}，由于｛0} a={1}，｛0｝b=｛2｝，{2}a={1}，｛2｝b={2}都是集合｛0,1,2｝的子集，但｛1｝a={3}，｛1｝b={4}，属于｛3,4｝的子集，故将其划分为｛0,2｝，｛1｝。对｛3｝、｛4｝也是如此，即最后划分为：{0,2｝、｛1｝、{3｝、{4｝，按顺序重新命名为1、2、3、4。(见书p57页) ;第四章;?;2.P82，第4题。 对文法S ?-S S ?(S)|AB B ?-S|? A ?aC C ?(S)|? (1)构造LL(1)分析表 (2)给出对句子a--a((a))的分析过程。 ;(1) First(S)={- ( a} First(A)={a} First(B)={- ?} First(C)={( ?} Follow(S)={) #} Follow(B)={) #} Follow(A)={- ) #} Follow(C)={- ) #} LL(1)分析表 ;步骤;12;P133.1 令文法G1为： E-E+T | T T-T*F | F F-(E) | I 证明E+T*F是它的一个句型，指出这个句型的所有短语，直接短语和句柄 答案： 因为E=E+T=E+T*F 所以E+T*F是该文法的一个句型。 短语:E+T*F, T*F, 直接短语:T*F 句柄:T*F ;P133.3 S-a | ∧ | (T) T-T, S | S (1)计算FIRSTVT和LASTVT. (2)计算优先关系。以上文法是一个优先文法吗？ (3)给出输入串(a,(a,a))的算符优先分析过程。 答案： (1) FIRSTVT(S)={a ^ (} FIRSTVT(T)={, A ^ (} LASTVT(S)={A ^ )} LASTVT(T)={, A ^ )} (2);(3);第七章;三元式表 间接码表 (+,a,b) (1) (,(1),-) (2) (+,c,d) (3) (*,(2),(3)) (4) (+,(1),c) (1) (-,(4),(5)) (5) (6) 四元式序列： (1)（+,a,b,T1） (2) (,T1,-,T2) (3) (+,c,d,T3