编译原理习题与答案详解.ppt

第二章;2.5 证明下面的文法是二义性的。 S→iSeS | iS | i 答：对句子iiiei对应两棵不同的语法树;2.9 设有文法G[T]: T→T*F|F F→ F?P|P P→(T)|i 分析句型T*P ?(T*F)的短语、直接短语和句柄 答：句型T*P ?(T*F)的语法树：;第三章;第三章;第三章;3.4 给出文法G[S]，构造相应最小的DFA。 G：S→aS | bA | b A→aS 解：由文法到NFA的转换有两种方法： ① 由文法到正规式，再由正规式到NFA 先由产生式得: A = aS 将A代入S中得: S = aS|bA|b = aS|baS|b = (a|ba)S|b 利用规则（A-xA|y）得: S= (a|ba)*b 文法G对应的正规式为(a|ba)*b ，其对应的NFA的状态转换图为：;第三章;第三章;第三章;第三章;第三章;第三章;第三章;第三章;第三章; 上图所对应的DFA如下所示。 ;对上图的DFA进行最小化。首先将状态分为非终态集和终态集两部分：{0,1,2,5}和{3,4,6,7}。 由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其化为分{0,1,2,5}, {4}, {3,6,7};第三章;;6.设有L(G)={a2n+1b2ma2p+1|?n≥0,p≥0,m≥1}。 (1) 给出描述该语言的正规表达式； (2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。 解： (1) 该语言对应的正规式为a(aa)*bb(bb)*a(aa)*。 (2) a(aa)*bb(bb)*a(aa)*正规表达式对应的NFA如下图所示。;第三章;I; 重新命名后的状态转换矩阵可化简为(可由最小化方法得到) {X,2} {1} {3,5} {4}{6} {Y} 按顺序重新命名为0、1、2、3、4、5后得到最简的DFA，如下图所示。 ;第三章; 7.有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放≥3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。 (1) 写出售货机售糖的正规表达式； (2) 构造识别上述正规式的最简DFA。 解：(1) 设a=1，b=2，则售货机售糖的正规表达式为 a (b|a(a|b))|b(a|b)。 (2) 画出与正规表达式a(b|a(a|b))|b(a|b)对应的NFA，如图所示。;第三章;I;由转换矩阵可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态 即最简状态{0}、{1}、{2，3}、{4}。 按顺序重新命名为0、1、2、3，则得到最简DFA，如下图所示。;0;第四章;第四章;第四章;第四章;;第四章;第四章;第四章;第四章;0: S?→·E E→·aA E→·bB ;LR(0)分析表为:;(0) S?→E (1) E→aА (2) E→bB (3) A→cА (4) A→d (5) B→cB (6) B→d 输入串bccd$的分析过程;第四章;(1) 将文法G[S]拓广为文法G[S]： (0) S→P (1) P→m,r (2) P→m,i (3) P→r,r (4) P→r,i (5) P→r,m;文法G[S]的DFA;;(0) S→P (1) P→m,r (2) P→m,i (3) P→r,r (4) P→r,i (5) P→r,m 输入串m,i$的分析过程;;我们知道，LR(0)、SLR(1)和LR(1)分析表构造的主要差别是构造算法。其区别如下： (1) 对LR(0)分析表来说，若项目A→α·属于Ik(状态)，则对任何终结符a(包括$)，置ACTION[k,a]为“用产生式A→α进行归约(A→α为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则是每个归约状态所在的行全部填满“rj”；并且，同一行的“rj”其下标j相同，而不同行的“rj”其下标j是不一样的。 ;(2) 对SLR(1)分析表来说，若项目A→α·属于Ik，则对任何输入符号a，仅当a∈FOLLOW(A)时置ACTION[k,a]为“用产生式A→α进行归约(A→α为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则存在某个归约状态所在的行并不全部填满rj，并且不同行的“rj”其下标j不同。;(3) 对LR(1)来说，若项目[A→α·,a]属于Ik(状态)，则置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”。LR(1)是在SLR(1)状态(项目集)的基础上，通过状态分裂的办法(即分裂成更多的项目集)，使得L