编译原理习题答案课件.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
显示全部