编译原理作业20150515(答案)

1、第3章作业【编辑人：陈芳芳】1. 写一文法，使其语言是偶正整数的集合。要求：（1）允许0打头；（2）不允许0打头。 【解】：(1) 允许0打头且含0的偶正整数集合的文法为： N>(0|D|E)N|(E|0) D>1|3|5|7|9 E>2|4|6|8(2) 不允许0打头的偶正整数集合的文法为： R>(D|E)N|E N>(0|D|E)N|(E|0) D>1|3|5|7|9 E>2|4|6|8(3) 允许0打头的偶正整数集合的文法为： S>0S|RR>(D|E)N|E N>(0|D|E)N|(E|0) D>1|3|5|7|9 E&

2、gt;2|4|6|82.一个上下文无关文法生成句子abbaa的推导树如下：S A B S a S 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

3、) 产生式集合P：S>ABS | Aa| A>aB>SBB | b(3) 短语：a , , b , bb , aa , abbaa 直接短语：a , , b 句柄：a3、给出生成下述语言的上下文无关文法：(1)anbnambm | n, m >= 0(2)1n0m1m0n | n, m >= 0【解】：（1）S>AA A>aAb | （2）S>1S0 | A A>0A1 | 第4章课后作业1. 构造一个状态数最小的DFA，它接受=0,1上所有倒数第二个字符为1的字符串。（编辑：张超）解： 构造正规式：（01）* 1（01） 由正规式构造NF

4、A： 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,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为终态。状态c

5、losure（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 30，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 AB

6、bS|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 由上表可知：该文法中，所有相同左部不同右部的产生式SELECT集两两相交均为空集，所以该文法为LL(1)文法。 构造预测分析表fbedg#SABfABfABfABbSeBbSBdAg3、已知文法GS：S(A)ab AAcSS 构造文法的算符优先矩阵，并判断该文法是否是算符优先文法。【解】：拓展该文法：S#S# S(A)ab

7、 AAcSS计算FIRSTVT与LASTVT:FIRSTVTLASTVTS#S( a b) a bAc ( a bc ) a b计算算符优先关系：# = # ( = ) # < FIRSTVT(S) ( < FIRSTVT(A) c< FIRSTVT(A) LASTVT(S) > # LASTVT(A) > ) LASTVT(A) > c构造算符优先矩阵（注：按终结符出现顺序列表）:()abc#(< = < < < )>>>a>>>b>> >c< > < <

8、 >#<<<= 因为该文法G为2型文法，且不含空产生式，没有形如 U®VW的产生式，其中V,WVN，所以 G 为算符文法；又因为G 中任意两个终结符间至多有一种算符优先关系存在(算符优先矩阵无冲突，见上表)，所以G 为算符优先文法。4、课后习题 P122：4(2) 已知文法：S S;G|G G G(T)|H H a|(S) T T+S|S求句型a(T+S);H;(S) 的短语、直接短语、句柄、素短语与最左素短语。【解】：该句型的对应的语法树如下：短语： a T+S H (S) a(T+S) a(T+S);H a(T+S);H;(S)直接短语： a T+S H

9、(S)句柄： a素短语： a T+S (S)最左素短语：a5. 给定文法GA：A(A)a，构造出该文法的LR(1)分析表。【解】对该文法拓广，得其拓广文法GS： (0) SA (1) A(A) (2) Aa 计算其LR(1)项目集规范族如下： I0 = S.A,#， A.(A),#， A.a,# I1 = GOTO(I0，A) = SA.,# I2 = GOTO(I0，() = A(.A),#，A.(A),)，A.a,) I3 = GOTO(I0，a) = Aa.,# I4 = GOTO(I2，A) = A(A.),# I5 = GOTO(I2，() = A(.A),)，A.(A),)，A.a

10、,) I6 = GOTO(I2，a) = Aa.,) I7 = GOTO(I4，) = A(A).,# I8 = GOTO(I5，A) = A(A.),) GOTO(I5，() = I5 ; GOTO(I5，a) = I6I9 = GOTO(I8，) = A(A).,) 构造LR(1)分析表： 状态Action表Goto表（）a#A0S2S311acc2S5S643r24S75S5S686r27r18S99r16、证明文法 S ® bB B® B*a B ® a不是LR(0)文法，而是 SLR(1)文法。【解】对该文法拓广，得其拓广文法GS： (0) SS (1)

11、 S ® bB (2) B® B*a (3) B ® a 计算其LR(0)项目集规范族如下： I0 = closure S.S = S.S , S. bB I1 = GOTO(I0，S) = SS.I2 = GOTO(I0，b) = Sb.B，B® .B*a，B ® .a I3 = GOTO(I2，B) = SbB.，B® B.*a I4 = GOTO(I2，a) = B ® a. I5 = GOTO(I3，*) = B® B*.a I6 = GOTO(I5，a) = B® B*a. 因为该文法的LR(0

12、)项目集规范族中有一个项目集I3同时存在移进项目与归约项目，即“移进-归约”冲突，所以不是LR(0)文法。 I3 = SbB.，B® B.*a 而，FOLLOW（S）= # Follow(S) * = 即可采用Follow集能解决其冲突，所以该文法是SLR(1)文法。7. 给出下面赋值语句的逆波兰式： x := a*(b+c)-d/e【解】 x a b c + * d e / :=8. 把下列语句翻译成四元式(四元式的编号从100开始）。 while ABCD do if a > 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 ， ， ， 10