蒋立源《编译原理》第3版桂电期末复习作业答案概论Word格式.docx

1、G（S） = （S,W,R,0,1,#, SW#, W0W0|1W1|# ,S）（5）任何不是以0打头的所有奇整数所组成的集合G（S） = （S,A,B,I,J,-,0,1,2,3,4,5,6,7,8,9,SJ|IBJ,B0B|IB|e, IJ|2|4|6|8, J1|3|5|7|9,S）（6）所有偶数个0和偶数个1所组成的符号串集合对应文法为 S0A|1B|e，A0S|1C B0C|1S C1A|0B7.解：aacb是文法GS中的句子，相应语法树是：最右推导：S=aAcB=aAcb=aacb最左推导：aacB=（2）aabacbadcd不是文法GS中的句子因为文法中的句子不可能以非终结符d结

2、尾（3）aacbccb不是文法GS中的句子可知，aacbccb仅是文法GS的一个句型的一部分，而不是一个句子。（4）aacabcbcccaacdca不是文法GS中的句子因为终结符d后必然要跟终结符a，所以不可能出现dc这样的句子。（5）aacabcbcccaacbca不是文法GS中的句子由（1）可知：aacb可归约为S，由文法的产生式规则可知，终结符c后不可能跟非终结符S，所以不可能出现caacb这样的句子。8.证明：用归纳法于n，n=1时，结论显然成立。设n=k时，对于12.kT*b,存在i：i=1,2,.,k，iT*bi成立，现在设12. kk+1T*b，因文法是前后文无关的，所以12.

3、k可推导出b的一个前缀b，k+1可推导出b的一个后缀=b（不妨称为b k+1）。由归纳假设，对于b，存在i ：i=1,2,.,k，b=12.k,使得iT*bi成立，另外,我们有k+1T*b（=b k+1）。即n=k+1时亦成立。证毕。9.证明：（1）用反证法。假设首符号为终结符时，的首符号为非终结符。即设：=a；=A且 =*。由题意可知：=aT T A=，由于文法是CFG，终结符a不可能被替换空串或非终结符，因此假设有误。得证；（2）同（1），假设：的首符号为非终结符时，首符号为终结符。=A且=aT T A=，与（1）同理，得证。10.证明：因为存在句子：abc，它对应有两个语法树（或最右推导

4、）：STABTAbcTabcSTDCTDcTabc所以，本文法具有二义性。11.解：（1） STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推导中，下划线部分为当前句型的句柄。对应的语法树为：全部的短语：第一个a （a1）是句子bbaacb相对于非终结符A （A1） （产生式A?a）的短语（直接短语）；b1a1是句子bbaacb相对于非终结符A2的短语；b2b1a1是句子bbaacb相对于非终结符A3的短语；c是句子bbaacb相对于非终结符S1（产生式S?c）的短语（直接短语）；a2cb3是句子bbaacb相对于非终结符B的短语；b2b1a1a2cb3是句子bbaac

5、b相对于非终结符S2的短语；注：符号的下标是为了描述方便加上去的。（2）句子（b）a（a）（b）的最右推导：ST（AS）T（A（b）T（SaA）（b）T（Sa（a）（b）T（b）a（a）（b）相应的语法树是：（3）解：iii*i+对应的语法树略。E TT=F=FPT FET FET+T FEF+T FEP+T FEi+TFTi+T FTF*i+TFTP*i+T FTi*i+TFFi*i+T FPi*i+TFii*i+T Pii*i+Tiii*i+13.化简下列各个文法（1）解：SbCACdAcSA| cCCCcS | c（2）解：SaAB | fA | gAe | dDADeABfSac第三章

6、7 （1） 其对应的右线性文法是:A 0D, B0A,B1C,C1|1F,C1|0A,F0|0E|1A,D0B|1C,E1C|0B（2） 最短输入串011（3） 任意接受的四个串011,0110,0011,000011（4） 任意以1打头的串.11将右线性文法化为左线性文法的算法：o（1）对于G中每一个形如AaB的产生式且A是开始符，将其变为Ba,否则若A不是开始符，BAa;o（2）对于G中每一个形如Aa的产生式,将其变为SAa 12 （1）状态矩阵是：记S=q0 B=q1 A B=q2 S A=q3 ,最小化和确定化后如图（2）记 S=q0, A=q1,B S=q2 最小化和确定化后的状态转

7、换图如下13 （1）将具有动作的NFA确定化后，其状态转换图如图：记 S0,S1,S3=q0 S1=q1 S2 S3=q2 S3=q3 （2） 记S=q0 Z=q1 U R=q2 S X=q3 Y U R=q4 X S U=q5 Y U R Z=q6 Z S=q714（1）从略（2）化简后S0和S1作为一个状态，S5和S6作为一个状态。状态转换图如图22 构造NFA其余从略。第四章（1）S（S）Z21|（）Z21|SZ31|Z31A（S）Z22|（）Z22|SZ32|Z32B（S）Z23|（）Z23|SZ33|Z33Z11|AZ11|BZ21Z12AZ12|BZ22Z13AZ13|BZ23Z2

8、1Z11Z22|Z12Z23Z13Z31Z21Z32Z22Z33|Z23（2）SbZ11|aZ21AbZ12|aZ22Z11| AZ21Z12AZ22Z21SZ21Z22|SZ22（3）S（T）Z11 | aZ11 | Z11S（T）Z12 | aZ12 | Z12Z11| Z21Z12Z22Z21,SZ21Z22|,SZ224.解：5.证：因为是左递归文法，所以必存在左递归的非终结符A，及形如A|的产生式,且T* Ad. 则first（Ad） first（）,从而first（） first（），即文法不满足LL（1）文法条件。得证。6.证：LL（1）文法的分析句子过程的每一步，永远只有唯一的

9、分析动作可进行。现在，假设LL（1）文法G是二义性文法，则存在句子，它有两个不同的语法树。即存在着句子有两个不同的最左推导。从而可知，用LL（1）方法进行句子的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即LL（1）分析动作存在不确定性。与LL（1）性质矛盾。所以，G不是LL（1）文法。7.解：（1）D产生式两个候选式fD和f的first集交集不为空，所以不是LL（1）的。（2）此文法具有左递归性，据第5题结论，不是LL（1）的。12.解：（1）SA（a）b=不是简单优先文法。（2）RT,是简单优先文法。（3） o首先消去无用产生式ZE, ZE+T Z#iI化简后的文

10、法是简单优先文法；31.（1）算符优先矩阵：+*（2）用Floyd方法将优先矩阵线性化得到得的优先函数为：F3517G24635解：（1）识别全部活前缀的DFA如下：（以表格的形式来表示，很容易可以转化为图的形式，本章中其余的题目也是采用这种形式表示。状态项目集经过的符号到达的状态I0S SaSbaScabI1I2S SSaSbScI3I4SaScI5I6SabSaSbSaSc（2）识别全部活前缀的DFA如下：cAccBSccBAScASccBAcBI7I8AaSccBBcCI9I10BbBccI11AcABccB所求的LR（0）项目规范族C=I0,I1,I11（3）aSSbaSSSSSbSS

11、SSSSaSSSaSSbSaSSS（4）AbSASAb38解：SabbR（冲突项目）SSaccSbRSSaSbRr2RSRaSSab项目I1,I5同时具有移进和归约项目，对于I5= RS, SSab ,follow（R）=a,follow（R） a=a,所以SLR（1）规则不能解决冲突，从而该文法不是SLR（1）文法。aSABBASSSABSBaAr5ABSBAABr4SaSAAaAr3SaSABr1不存在冲突项目，故该文法是LR（0）文法，也是SLR（1）文法。SLR（1）分析表如下：ACTIONGOTOS2S4ACCS78R59R210R411R3R140解：求LR（1）项目集和状态转换表

12、：S#A#BA#aB#,a,bb#,a,bBaB#,a,b#,a,bABABaB相应的LR（1）分析表为：STATES5用 LR（1）分析表对输入符号串abab的分析过程：步骤栈中符号余留符号分析动作下一状态abab#04#abab#045#abab#047#aB03#B034#Bab#0345#Bab0347#BaB033#BB0336#BBA036#BA1201#A第五章5.4 解：A-BC+*DE- ad*c+d/e+f*g+ ax+4 = cd3*/ de*c+b/a/f s0=; i1=; i100 = BZ s s ii*+=;ii1+=;BR S2 5.5 解：a+b*c a*（

13、b-c）-（c+d）/e 有误 if（ab） x=（a-b）c ;else g=h;5.8 解：（+,B,C,T1） （*,A,T1,T2）（+,T2,D,T3）（=,T3,0,X）2）如下所示：当前句型（方框括起来部分为句柄）A/（BV（CVD/?F）用产生式Expriden归约，得 （1）Expr.TC（jnz,A,0,0）;（2）Expr.FC（j,0,0,0）;当前句型Expr /（BV（CVD/?F）用产生式ExprExpr /归约，得 （1）（jnz,A,0,3）;（2）Expr.FC（j,0,0,0）;当前句型Expr （BV（CVD/?（1）（jnz,A,0,0）;（3）Expr.TC（jnz,B,0,0）;（4）Expr.FC（j,0,0,0）;当前句型Expr （ExprV（CVD/?F）用产生式ExprvExpr V归约，得 （3）Exprv.TC（jnz,A,0,0）;（4）（j,0,0,5）;当前句型Expr （Exprv （CVD/?（5）Expr.TC（jnz,C,0,0）;（6）Expr.FC（j,0,0,0）;当前句型Expr （Exprv （ExprVD/?F）,用产生式ExprvExprV归约，得 （5）Exprv.TC（jnz,C,0,0）;（6）（j,0,0,7）;