发布时间 : 星期二 文章哈工大编译原理习题及答案更新完毕开始阅读68851b05bed5b9f3f90f1ca1
所以，本文法具有二义性。 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是句子bbaacb相对于非终结符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=>FP↑T FE↑T 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+↑ 12.证明：
充分性：当前文法下的每一符号串仅有一个句柄和一个句柄产生式T对当前符号串有唯一的最左归约T对每一步推导都有唯一的最右推导T有唯一的语法树。
必要性：有唯一的语法树T对每一步推导都有唯一的最右推导T对当前符号串有唯一的最左归约T当前文法下的每一符号串仅有一个句柄和一个句柄产生式
13.化简下列各个文法
（1）解：S→bCACdA→cSA| cCCC→cS | c （2）解：S→aAB | fA | gA→e | dDAD→eAB→f （3）解：S→ac
14.消除下列文法中的ε产生式 （1）解：S→aAS | aS | bA→cS
（2）解：S→aAA | aA | aA→bAc| bc | dAe| de 15.消除下列文法中的无用产生式和单产生式 （1）消除后的产生式如下： S→aB | BC B→DB | b C→b D→b | DB
（2）消除后的产生式如下： S→SA | SB |（）|（S）|[] |[S] A→() |（S）|[]|[S] Bà[] |[S]
（3）消除后的产生式如下： E→E+T | T*F | (E) | P↑F | i T→T*F | (E) | P↑F | i F→P↑F | (E) | i P→(E) | i
第三章 词法分析及词法分析程序
3.1试用某种高级语言编写一个FORTRAN源程序的预处理子程序，其功能是： 每调用它一次，即把源程序中的一个完整语句送入扫描缓冲区。要求删去语句中的注释行；删去续行标记字符，把语句中的各行连接起来，并在语句的末端加上语句结束符。此外，还要求此程序具有组织源程序列表输出的功能。
3.2画出用来识别如下三个关键字的状态转移图。 STEP STRING SWITCH
3.3假定有一个猎人带着一只狼、一头山羊和一棵白菜来到一条河的左岸，拟摆渡过河，而岸边只有一条小船，其 大小仅能装载人和其余三件东西中的一件，也就是说，每一次猎人只能将随行者中的一件带到彼岸。若猎人将狼和山羊留在同一岸上而无人照管，那么，狼就会将羊吃掉；如果猎人把山羊和白菜留在同一岸，山羊也会把白菜吃掉。现在，请你用状态转换图作为工具，描述猎人可能采取的种种摆渡方案，并从中找出可将上述三件东西安全地带到右岸的方案来。
3.4设已给文法G=(VN,VT,P,S)，其中，P仅含形如 A→αBA→αα∈V*T，B∈VN
的产生式，试证明： 由此种文法所产生的语言是一正规语言。 3.5试证明： 任何有限个符号串所组成的集合 L={x1,x3,?,xn}xi∈Σ+ 都是3型语言。
3.6试构造一右线性文法，使得它与如下的文法等价 S→ABA→UTU→a|aU T→b|bTB→c|cB
并根据所得的右线性文法，构造出相应的状态转换图。 3.7对于如题图37所示的状态转换图 (1) 写出相应的右线性文法； (2) 指出它接受的最短输入串；
(3) 任意列出它接受的另外四个输入串； (4) 任意列出它拒绝接受的四个输入串。 题图37
3.8对于有限自动机 M=(K,Σ,f,S0,Z)
其中，K={S0,S1,S2,S3,S4,S5},Σ={a,b},Z={S1,S4,S5}。 f由如下的状态转移矩阵给出：