《习题及解答》由会员分享，可在线阅读，更多相关《习题及解答（17页珍藏版）》请在金锄头文库上搜索。
1、第3章 文法和语言3.8 练习（P44）2. 文法GN为：N D|NDD 0|1|2|3|4|5|6|7|8|9|GN的语言是什么?=*解: N NDn-1=*.Dn =*.0,1,3,4,5,6,7,8,9+L(GN)= 0,1,3,4,5,6,7,8,9+5.写一文法，使其语言是偶正数的集合。要求：(1)允许0打头(2)不允许0打头解：(1)允许0打头0是正偶数：SABB0|2|4|6|8AAC|CC0|1|2|3|4|5|6|7|8|9|0不是正偶数：SFABC|FEA1|2|3|4|5|6|7|8|9BBD|DD0|1|2|3|4|5|6|7|8|9|C0|EE2|4|6|8FF0|(
2、2) 不允许0打头SABC|EA1|2|3|4|5|6|7|8|9BBD|DD0|1|2|3|4|5|6|7|8|9|C0|EE2|4|6|89.考虑下面上下文无关文法：SSS*|SS+|a(1) 表明通过此文法如何生成串aa+a*，并为该串构造推导树。(2) 该文法生成的语言是什么？解：(1) S=SS*=SS+S*=*.aa+a*该串的推导树如下：S*SSS+Saaa(2) 该文法生成的语言是只含+、*的算术表达式的逆波兰表示。11.令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：E=E+T=E+T
3、*FE+T*F是文法GE的一个句型句型E+T*F的语法树如下：ET+EF*TE+T*F是句型E+T*F相对于非终结符E的短语T*F是句型E+T*F相对于非终结符T的短语T*F是句型E+T*F相对于规则TT*F的直接短语T*F是句型E+T*F的句柄13.一个上下文无关文法生成句子abbaa的推导树如下：(1) 给出该句子相应的最左推导，最右推导。(2) 该文法的产生式集合P可能有哪些元素?(3) 找出该句子的所有短语，简单短语、句柄。BSSBABBSAabbaa解：(1) 最左推导如下：S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa最右推导如下：S=ABS=
4、ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa(2) 该文法的产生式集合P可能有以下元素：SABS|Aa|BSBB|bAa(3)为方便叙述将句型abbaa写作a1b1b2a2a3该句子的短语有：a1, , b1, b2, a2, b1b2, a2 a3, a1b1b2a2a3该句子的直接短语有：a1, , b1, b2, a2该句子的句柄为：a116.给出生成下述语言的三型文法：(2)anbm|n,m1解：该语言的三型文法为：GS： SaB BaB|CCbC|b或GS： SaS|aA BbA|b第4章 词法分析4.7练习（P66）1构造下列正规式相应的DF
5、A：(4) b(ab)*|bb)*ab解：先将正规式转换为NFA，转换过程如下：12b(ab)*|bb)*ab3=123(ab)*|bbabb4=a123(ab)*bbbb4=以下为最终所得的NFA图：a1266bb73bb45ba=然后，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0=1T1=2,4T1=2,4T2=5,6T3=3T2=5,6T4=2,4,7T3=3T1=2,4T4=2,4,7T2=5,6T3=3aT0bbT4=T1T3T2abbb所得DFA图如下：aT0bbT4=T1T2bba 最后，将此DFA化简后如下：ZUSQV0，10110，10110图 4.163将图4
6、.16确定化：解：首先，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0=ST1=V,QT2=U,QT1=V,QT3=Z,VT2=U,QT2=U,QT4=VT5=Z,Q,UT3=Z,VT6=ZT6=ZT4=VT6=ZT5=Z,Q,UT3=Z,VT5=Z,Q,UT6=ZT6=ZT6=Z所得DFA图如下：T0=T1T3T2T5T6T4000011110，100，1T4T0=T1T2T3T400001110，1最后，将此DFA化简后如下：7给文法GS：SaA|bQAaA|bB|bBbD|aQQaQ|bD|bDbB|aAEaB|bFFbD|aE|b构造相应的最小的DFA。S=ATQBDEFa
7、bbabbbabaabbaba解：首先，将正规式转换成NFA如下：a然后，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0=ST1=AT2=QT1=AT1=AT3=Z,BT2=QT2=QT4=Z.DT3=Z,BT2=QT5=D T4=Z.DT1=AT6=BT5=D T1=AT6=BT0=T1T5T6T4T3T2aaabbabbbaabbT6=BT2=QT5=D 所得DFA图如下：最后，将此DFA化简后如下：bT3T0T0T5aa，babba=8给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0解：由题意得：A=1S|1，B=0S|0 ，S0A|1B，将A，B右端代入S的产生
8、式得：S0(1S|1)|1(0S|0)=01S|01|10S|10=(01|10)| (01|10)SS(01|10)| (01|10)SS=(01|10)| (01|10)*该文法所对应的正规式为：(01|10)| (01|10)*11构造下述文法GS的确定自动机，并给出该文法的语言的正规式。S=Aa|A= Aa|Sb|a解：由左线型正规文法到NFA的转换规则可得该文法的NFA状态转换图为：ASQbaaa=转换关系矩阵如下表：CTaTbT0=Q,ST1=AT1=AT1=AT2=A,ST2=A,ST2=A,ST1=AT2T1T0baaa，b=所得DFA图如下：第5 章 自顶向下语法分析方法5.
9、6 练习（P90）2对下面的文法G：ETEE+E|TFTTT|FPFF* F|P(E)|a|b|(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2) 证明这个文法是LL(1)的。(3) 构造它的预测分析表。解：(1)由题意分析得可推导出的非终结符表为：EETTFFP否是否是否是否各非终结符的FIRST集为：FIRST(E)= FIRST(T)=(，a，b，FIRST(E)=+ =+，FIRST(T)= FIRST(F)=(，a，b，FIRST(T)= FIRST(T) =(，a，b，FIRST(F)= FIRST(P)=(，a，b，FIRST(F)=* =*，FIRST(P)=(，a，b，最终求得各非终结符的FIRST集为：FIRST(E)=(，a，b，FIRST(E)=+，FIRST(T)=(，a，b，FIRST(T)= (，a，b，FIRST(F)=(，a，b，FIRST(F)=*，FIRST(P)
