编译原理作业20150515(答案)

1、第3章作业【编辑人：陈芳芳】1. 写一文法，使其语言是偶正整数的集合。要求：（1）允许0打头；（2）不允许0打头。 【解】：(1) 允许0打头且含0的偶正整数集合的文法为： N(0|D|E)N|(E|0) D1|3|5|7|9 E2|4|6|8(2) 不允许0打头的偶正整数集合的文法为： R(D|E)N|E N(0|D|E)N|(E|0) D1|3|5|7|9 E2|4|6|8(3) 允许0打头的偶正整数集合的文法为： S0S|RR(D|E)N|E N(0|D|E)N|(E|0) D1|3|5|7|9 E2|4|6|82.一个上下文无关文法生成句子abbaa的推导树如下：S A B S a S

2、 B B A a b b a（1）给出该句子的相应的最左推导，最右推导。（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有短语，简单短语，句柄。【解】：（1）最左推导：S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa最右推导：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa(2) 产生式集合P：SABS | Aa| AaBSBB | b(3) 短语：a , , b , bb , aa , abbaa 直接短语：a , , b 句柄：a3、给出生成下述语言的上下文无关文法：(1)anbnambm |

3、 n, m = 0(2)1n0m1m0n | n, m = 0【解】：（1）SAA AaAb | （2）S1S0 | A A0A1 | 第4章课后作业1. 构造一个状态数最小的DFA，它接受=0,1上所有倒数第二个字符为1的字符串。（编辑：张超）解： 构造正规式：（01）* 1（01） 由正规式构造NFA： NFA转化为DFA ：T0=closure（0）=0用子集构造法求DFA状态，T0为初态，T2，T3为终态。状态closure（move（Ti，0）closure（move（Ti，1）T0=000,1T1=0,10,20,1,2T2=0,200,1T3=0,1,20,20,1,2用0,1,

4、2,3代表T0，T1，T2，T3，得到如下DFA ：最小化DFA ：P0=（0,1，2,3）P1=（0，1，2，3）无等价状态。 没有找到多余状态， 无多余状态。 上图为最小化的DFA。2、将下图的NFA确定化为DFA，并最小化。（编辑：张超）解：用子集构造法求DFA状态，T0为初态，T3为终态。状态closure（move（Ti，a）closure（move（Ti，b）T0=X，1，21，21，2，3T1=1，21，21，2，3T2=1，2，31，2，Y1，2，3T3=1，2，Y1，21，2，3用0,1,2,3代表T0，T1，T2，T3，得到如下DFA ：最小化：0，1，2 30，1 2 3

5、0，1 2 30和1是等价的， 得到最小化的DFA 如下 ：第5-7章课后作业（含答案）1、将文法GS 改写为等价的GS，使GS不含左递归和左公共因子。GS： SbSAe|bA AAbd | dc | a【解】：GS：SbS SSAe|A A(dc|a)A A bd A |2、有文法GS：SABf ABbS|e BdAg| 证明文法G是LL(1)文法，并构造预测分析表【解】：计算FIRST、FOLLOW、SELECT集产生式FIRSTFOLLOWSELECT左部右部SABfd b e# g d fd b eABbS d bg d fd beeeBdAgd b fd b f 由上表可知：该文法中

6、，所有相同左部不同右部的产生式SELECT集两两相交均为空集，所以该文法为LL(1)文法。 构造预测分析表fbedg#SABfABfABfABbSeBbSBdAg3、已知文法GS：S(A)ab AAcSS 构造文法的算符优先矩阵，并判断该文法是否是算符优先文法。【解】：拓展该文法：S#S# S(A)ab AAcSS计算FIRSTVT与LASTVT:FIRSTVTLASTVTS#S( a b) a bAc ( a bc ) a b计算算符优先关系：# = # ( = ) # FIRSTVT(S) ( FIRSTVT(A) c # LASTVT(A) ) LASTVT(A) c构造算符优先矩阵（注：按终结符出现顺序列表）:()abc#( = ab c # b then x := m - k else y := m + k;【解】 对应的四元式序列为： 100（Jnz， A， ， 108 ） 101（J ， ， ， 102 ） 102（Jnz， B， ， 104 ） 103（J ， ， ， 106 ） 104（Jnz， C， ， 106 ） 105（J ， ， ， 108 ） 106（Jnz， D， ， 108 ） 107（J ， ， ， 116 ） 108（J，a ，b ， 110 ） 109（J ， ， ， 113 ） 110