编译原理习题与答案

1、第二章 2.2 设有文法设有文法GN: N-D | NDD-0|1|9 (1) GN定义的语言是什么？定义的语言是什么？ (2) 请给出句子请给出句子0123的最左推导和最右推导。的最左推导和最右推导。 N ND NDD NDDDDDDD 0DDD 01DD 012D 0123 N ND N3ND3 N23 ND23 N123 D123 0123 2.5 证明下面的文法是二义性的。证明下面的文法是二义性的。 SiSeS | iS | i 答：对句子答：对句子iiiei对应两棵不同的语法树对应两棵不同的语法树 第二章 S iS SeiS ii S iS SeiS i i 2.9 设有文法设有文法

2、GT: TT*F|F F FP|PP(T)|i 分析句型分析句型T*P (T*F)的短语、直接短语和句柄的短语、直接短语和句柄 答：句型答：句型T*P (T*F)的语法树：的语法树：T TF * ()T 五棵子树对应五个短语五棵子树对应五个短语T*P (T*F), P (T*F), P, (T*F), T*F 两层子树两层子树( (简单子树简单子树) )的末端结点构成直接短语的末端结点构成直接短语 两棵两层子树对应两个直接短语：两棵两层子树对应两个直接短语： P , T*F 位于最左边的两层子树的末端结点构成句柄：位于最左边的两层子树的末端结点构成句柄： P 第二章 PF P TF * 第三章

3、 3.1 构造正规式构造正规式1(0|1)*101相应的相应的NFA X 1 B 1 C 10 D Y A (0|1)* X 1 B 1 C 10 D Y A E 0|1 X 1 B 1 C 10 D Y A E 0,1 第三章 3.1 构造正规式构造正规式1(0|1)*101相应的相应的NFA X 11 B 10 C Y A (0|1)* 0,1 X 11 B 10 C Y A X 1 B 1 C 10 D Y A E 0,1 第三章 3.5 给出下述文法所对应的正规式。给出下述文法所对应的正规式。 G：SaA AbA | aB | b B aA 解：先由产生式得解：先由产生式得: B=aA

4、 将将B代入代入A中得中得:A=bA|aaA|b =(b|aa)A|b 利用规则利用规则（A-xA|y）得得: A= (b|aa) * b 将将A代入代入S中得中得:S=a (b|aa) * b 即为所求正规式即为所求正规式 3.4 给出文法给出文法GS，构造相应最小的，构造相应最小的DFA。 G：SaS | bA | b AaS 解解：由文法到由文法到NFA的转换有两种方法：的转换有两种方法： 由文法到正规式，再由正规式到由文法到正规式，再由正规式到NFA 先由产生式得先由产生式得:A = aS 将将A代入代入S中得中得:S = aS|bA|b = aS|baS|b = (a|ba)S|b

5、利用规则利用规则（A-xA|y）得得: S= (a|ba)*b 文法文法G对应的正规式为对应的正规式为(a|ba)*b ，其对应的，其对应的NFA的的 状态转换图为状态转换图为： 第三章 3.4 给出文法给出文法GS，构造相，构造相 应最小的应最小的DFA。 G：SaS | bA | b AaS 解解： 由文法直接到由文法直接到NFA 文法对应的有自动文法对应的有自动 M=(S,A, T, a,b, f, S, T) 其对应的状态转换图为：其对应的状态转换图为： 产生式产生式转换函数转换函数 SaSf(S,a)=Sf(S,a)=S SbAf(S,b)=Af(S,b)=A Sbf(S,b)=Tf

6、(S,b)=T AaSf(A,a)=Sf(A,a)=S 第三章 正规式：正规式：(a|ba)*b T b SA a b a 产生式产生式转换函数转换函数 SaSf(S,a)=Sf(S,a)=S SbAf(S,b)=Af(S,b)=A Sbf(S,b)=Tf(S,b)=T AaSf(A,a)=Sf(A,a)=S 第三章 将将NFA确定化为确定化为DFA 如右图所示如右图所示 最小化：此状态图已经为最简了。最小化：此状态图已经为最简了。 T b SA a b a S SA,T A,TS IbIaI 0 1 01 0 01 a b a - 第三章 1.指出与正规式匹配的串。指出与正规式匹配的串。 a

7、) (ab|b)*c 与后面的那些串匹配？与后面的那些串匹配？ ababbcababcbabcaaabc b) ab*c*(a|b)c 与后面的那些串匹配？与后面的那些串匹配？ acacacbbcabbcacabcacc c) (a|b)aa*(ba)* 与后面的那些串匹配与后面的那些串匹配? ? ba bba baaaaababa 第三章 2. 为下边所描述的串写正规式，字母表是为下边所描述的串写正规式，字母表是 0, 1. a) 以以01 结尾的所有串结尾的所有串 b) 只包含一个只包含一个0的所有串的所有串 c) 包含偶数个包含偶数个1但不含但不含0的所有串的所有串 d) 包含偶数个包含

8、偶数个1且含任意数目且含任意数目0的所有串的所有串 e) 包含包含01子串的所有串子串的所有串 f) 不包含不包含01子串的所有串子串的所有串 (0|1)*01 1*01* (11)* (0*10*10*)* (0|1)*01(0|1)* 1*0* 第三章 3. 请描述下面正规式定义的串请描述下面正规式定义的串. 字母表字母表S = x, y。 a) x(x|y)*x 必须以必须以 x 开头和开头和x结尾的串结尾的串 b) x*(yx+)*x* 每个每个 y 至少有一个至少有一个 x 跟在后边的串跟在后边的串 c) (x|y)*(xx|yy) (x|y)* 所有含两个相继的所有含两个相继的x或

9、两个相继的或两个相继的y的串的串 第三章 4.指出哪些串是自动机可接受的指出哪些串是自动机可接受的 xy xyxxy yyyx xyyxyxyxxy 第三章 5.将下图所示的将下图所示的 非 确 定 有 限 自非 确 定 有 限 自 动机动机(NFA)变换变换 成 等 价 的 确 定成 等 价 的 确 定 有 限 自 动 机有 限 自 动 机 (DFA)。 X Y 1 34 2 a b a a b b a b a b 第三章 解解: :用子集法将用子集法将NFA确定化，确定化， 如下图所示。如下图所示。 IIaIb X13 2,3,Y3,Y1 3,43 2,3,4,Y2,3,Y2,3,Y 2,

10、3,Y3,43,Y 3,4,Y3,43,4 2,3,4,Y 2,3,4,Y2,3,4,Y 2,3,4,Y3,4,Y3,4,Y ba 012 134 25 336 435 557 666 767 重新命名重新命名 X Y 1 34 2 a b a a b b a b a b 上上图所对应的图所对应的DFA如下所示。如下所示。 3 4 5 a a b b a 2 b b 0 1 a 7 b b 6 b a b a a 第三章 ba 012 134 25 336 435 557 666 767 对上图的对上图的DFA进行最小化。首先将进行最小化。首先将 状态分为非终态集和终态集两部分：状态分为非终态

11、集和终态集两部分： 0,1,2,5和和3,4,6,7。 由终态集可知，对于状态由终态集可知，对于状态3、6、7， 无论输入字符是无论输入字符是a还是还是b的下一状态的下一状态 均为终态集，而状态均为终态集，而状态4在输入字符在输入字符b 的下一状态落入非终态集，故将其的下一状态落入非终态集，故将其 化为分化为分0,1,2,5, 4, 3,6,7 第三章 ba 012 134 25 336 435 557 666 767 第三章 对于非终态集，在输入字符对于非终态集，在输入字符a a、 b b后按其下一状态落入的状态集后按其下一状态落入的状态集 不同而最终划分为不同而最终划分为 0, 1, 2,

12、 5, 4, 3,6,7 按顺序重新命名为按顺序重新命名为0、1、2、3、 4、5，得到最简得到最简DFADFA如下图所示。如下图所示。 0,1,2,5, 4, 3,6,7 ba 012 134 25 336 435 557 666 767 0 1 2 a b 4 3 5 a a b b b b b a a 3 4 5 a a b b a 2 b b 0 1 a 7 b b 6 b a b a a 6.设有设有L(G)=a2n+1b2ma2p+1| n0,p0,m1。 (1) 给出描述该语言的正规表达式；给出描述该语言的正规表达式； (2) 构造识别该语言的确定有限自动机构造识别该语言的确定有

13、限自动机(可直接用状可直接用状 态图形式给出态图形式给出)。 解：解： (1) 该语言对应的正规式为该语言对应的正规式为a(aa)*bb(bb)*a(aa)*。 (2) a(aa)*bb(bb)*a(aa)*正规表达式对应的正规表达式对应的NFA如如下下 图所示。图所示。 第三章 第三章 正规表达式：正规表达式：a(aa)a(aa)* *bb(bb)bb(bb)* *a(aa)a(aa)* * Y1X ba 34 5 bb ab 6 aa 2 aa II a I b 用子集法将上图确定化，如图所示。用子集法将上图确定化，如图所示。 X1 2 1 1 2 3 4 5 6 Y Y 3 4 5 4

14、重命名重命名 X 1 2 3 4 Y 5 6 1 2 3 1 Y 6 Y 4 5 4 ab Y6 Y1X ba 34 5 bb ab 6 aa 2 aa 重新命名后的状态转换矩阵重新命名后的状态转换矩阵 可化简为可化简为( (可由最小化方法得到可由最小化方法得到) ) X,2 1 3,5 46 Y 按顺序重新命名为按顺序重新命名为0、1、2、 3、4、5后得到最简的后得到最简的DFA，如，如 下图所示。下图所示。 X 1 2 3 4 Y 5 6 1 2 3 1 Y 6 Y 4 5 4 ab Y1X ba 34 5 bb ab 6 aa 2 aa 第三章 a(aa)*bb(bb)*a(aa)*

15、Y1X ba 34 5 bb ab 6 aa 2 aa 510 ba 23 ab ab 4 aa 7.7.有一台自动售货机，接收有一台自动售货机，接收1 1分和分和2 2分硬币，出售分硬币，出售3 3分分 钱一块的硬糖。顾客每次向机器中投放钱一块的硬糖。顾客每次向机器中投放3 3分的硬币，分的硬币， 便可得到一块糖便可得到一块糖( (注意：只给一块并且不找钱注意：只给一块并且不找钱) )。 (1) (1) 写出售货机售糖的正规表达式；写出售货机售糖的正规表达式； (2) (2) 构造识别上述正规式的最简构造识别上述正规式的最简DFADFA。 解解：(1) (1) 设设a=1a=1，b=2b=2

16、，则售货机售糖的正规表达式为，则售货机售糖的正规表达式为 a (b|a(a|b)|b(a|b)a (b|a(a|b)|b(a|b)。 (2) (2) 画出与正规表达式画出与正规表达式a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)对应的对应的 NFANFA，如图所示。，如图所示。 第三章 X Y 1 2 3 a b a b b a b a 第三章 正规表达式：正规表达式：a(b|a(a|b)|b(a|b) II a I b 第三章 用子集法将用子集法将NFA确定化。确定化。 重新命名 Y 3YY 2YY 13Y X12 X Y 1 2 3 a b a b b a b a 4

17、 344 244 134 012 ab 由转换矩阵可看出，非终态由转换矩阵可看出，非终态2 2和非终态和非终态3 3 面对输入符号面对输入符号a a或或b b的下一状态相同，故的下一状态相同，故 合并为一个状态合并为一个状态 即最简状态即最简状态00、11、22，33、44。 按顺序重新命名为按顺序重新命名为0 0、1 1、2 2、3 3，则得到，则得到 最简最简DFADFA，如下图所示。，如下图所示。 第三章 4 344 244 134 012 ab 0 3 1 2 a b b b a a 3 233 123 012 ab 第三章 第四章 作业作业4.3 设有文法设有文法GS: SA AB|

18、AiB BC|B+C C)A*|( 1）将文法）将文法GS改写为改写为LL(1)文法。文法。 2）求经改写后的文法的每个非终结符的）求经改写后的文法的每个非终结符的 FIRST集和集和FOLLOW集。集。 3）构造相应的预测分析表。）构造相应的预测分析表。 第四章 1）将文法）将文法GS改写为改写为LL(1)文法。文法。 文法文法GS为左递归文法，削去文法左递归为左递归文法，削去文法左递归 后的文法为：后的文法为： SA ABA A iBA| BCB B +CB| C)A*|( SA AB|AiB BC|B+C C)A*|( 第四章 1）将文法）将文法GS改写为改写为LL(1)文法。文法。 F

19、IRST(C)=(,) FIRST(B)=+, FIRST(B)=(,) FIRST(A)=i, FIRST(A)=(,) FIRST(S)=(,) FOLLOW(S)=$ FOLLOW(A)=$,* FOLLOW(A)=$,* FOLLOW(B)=i,$,* FOLLOW(B)=i,$,* FOLLOW(C)=+,i,$,* SA ABA A iBA| BCB B +CB| C)A*|( 第四章 SELECT(SA) =FIRST(A)=(,) SELECT(ABA)=(,) SELECT(AiBA) =i SELECT(A)= FOLLOW(A)= $,* SELECT(BCB)=(,)

20、SELECT(B +CB) =+ SELECT(B)= i, $,* SELECT(C)A*)=) SELECT(C( )= ( 因为因为同一非终结符的不同产生式的同一非终结符的不同产生式的Select集交集为空集交集为空，所以，所以 改写后的文法是改写后的文法是LL(1)文法。文法。 2）求经改写后的文法的每个非终结符的）求经改写后的文法的每个非终结符的FIRST集和集和 FOLLOW集。集。 在上步中已经求出。在上步中已经求出。 FIRST(C)=(,) FIRST(B)=+, FIRST(B)=(,) FIRST(A)=i, FIRST(A)=(,) FIRST(S)=(,) FOLLO

21、W(S)=$ FOLLOW(A)=$,* FOLLOW(A)=$,* FOLLOW(B)=i,$,* FOLLOW(B)=i,$,* FOLLOW(C)=+,i,$,* 3）构造相应的预测分析表。）构造相应的预测分析表。 C)A* B +CB C( B BCBBCBB AiBAA ABAABAA S $*)+i ( 终极符号终极符号 语法语法 变量变量 SELECT(SA) = (,) SELECT(ABA)=(,) SELECT(AiBA) =i SELECT(A)= $,* SELECT(BCB)=(,) SELECT(B +CB) =+ SELECT(B)= i, $,* SELECT(

22、C)A*)=) SELECT(C( )= ( C 第四章 作业作业4.5 设有表格结构文法设有表格结构文法GS: Sa|(T) TT,S|S 1）计算文法的）计算文法的FIRSTVT集和集和LASTVT集。集。 2）构造其优先关系表，并判断其是否为算）构造其优先关系表，并判断其是否为算 符优先文法。符优先文法。 3）计算其优先函数。）计算其优先函数。 第四章 1）计算文法的）计算文法的FIRSTVT集和集和 LASTVT集。集。 FIRSTVT(S)=a, , ( FIRSTVT(T)=, a, , ( LASTVT(S)=a, , ) LASTVT(T)=, a, ,) 2）构造其优先关系表

23、，并判）构造其优先关系表，并判 断其是否为算符优先文法。断其是否为算符优先文法。 Sa|(T) TT,S|S = = =( $,) 11111 11111 迭代函迭代函 数数 函数函数a,() f g 0(初初 值值) f g 1 22213 23331 33313 44241 f g 2 , 第四章 例文法例文法GS S E EaA|bB AcA|d BcB|d 1）构造识别文法活前缀的）构造识别文法活前缀的DFA 2）构造其）构造其LR(0)分析表分析表 3）输入串）输入串aabab是否为文法是否为文法G定义的句子定义的句子 0: S E EaA EbB 4: AcA AcA Ad c 5

24、: BcB BcB Bd c 3: EbB BcB Bd b 1: S E E 2: EaA AcA Ad a 11: Bd d 8: AcA A c c d 10: Ad d d 9: BcB B 6: EaA A 7: EbB B LR(0)分析表为分析表为: s2s31 acc s4s106 s5s117 s4s108 s5s11 r1r1r1r1r1 9 r2r2r2r2r2 r3r3r3r3r3 r5r5r5r5r5 r4r4r4r4r4 r6r6r6r6r6 状态状态 ACTIONGOTO abcd#EAB 0 1 2 3 4 5 6 7 8 9 10 11 S E EaA|bB

25、AcA|d BcB|d (0) S E(1) Ea(2) EbB(3) Ac (4) Ad(5) BcB(6) Bd 输入串输入串bccd$的分析过程的分析过程 步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONGOTO 1 2 3 4 5 6 7 8 9 0$bccd$S3 03$b ccd$S8 038$bccd$ S8 0388$bccd$ S9 03889$bccd$ $ $ $ $ r611 0388$bccr511 038$bcr57 03 $br21 0$acc B(11) B (11) B 7 E1 第四章 8086/8088汇编语言对操作数域的检查可汇编语言对操作数域

26、的检查可 以用以用LR分析表实现。设分析表实现。设m代表存储器，代表存储器，r 代表寄存器，代表寄存器，i代表立即数；并且为了简代表立即数；并且为了简 单起见，省去了关于单起见，省去了关于m、r和和i的产生式，的产生式， 暂且认为暂且认为m、r、i为终结符，则操作数域为终结符，则操作数域 P的文法的文法GP为为 GP: Pm,r m,i r,r r,i r,m 试构造能够正确识别操作数域的试构造能够正确识别操作数域的LR分析表。分析表。 (1) 将文法将文法GS拓广为文法拓广为文法GS： (0) SP (1) Pm,r (2) Pm,i (3) Pr,r (4) Pr,i (5) Pr,m 第

27、四章 GP: Pm,r m,i r,r r,i r,m 文法GS的DFA 0: S P Pm,r Pm,i Pr,r Pr,i Pr,m (0) SP (1) Pm,r(2) Pm,i (3) Pr,r (4) Pr,i(5) Pr,m 1: S P P 2: Pm,r Pm,i 3: Pr,r Pr,i Pr,m 5: Pm, r Pm, i 4: Pr, r Pr, i Pr, m , m r , r 6: Pm, r i 7: Pm, i r 8: Pr, r i 9: Pr, i m 10: Pr, m LR(0)分析表分析表 状态状态 ACTIONGOTO mri，$P 0 s2s3

28、 1 1 acc 2 s5 3 s4 4 s10s8s9 5 s6s7 6 r1r1r1r1r1 7 r2r2r2r2r2 8 r3r3r3r3r3 9 r4r4r4r4r4 10 r5r5r5r5r5 r1 (0) SP (1) Pm,r(2) Pm,i (3) Pr,r (4) Pr,i(5) Pr,m 输入串输入串m,i$的分析过程的分析过程 步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONGOTO 1 2 3 4 5 0$m,i$S2 02$m,i$ S5 025$m, i$ S7 0257$m,i$ r2 0$acc 1P1 例：请指出下图中的例：请指出下图中的LRLR分析

29、表分析表(a)(a)、(b)(b)、(c)(c)分属分属 LR(0)LR(0)、SLR(1)SLR(1)和和LR(1)LR(1)中的哪一种，并说明理由。中的哪一种，并说明理由。 (a)(b )(c) 5r 1 4r 2 3r 2 2s 4 5 1acc 0s 3 12 状态 ACTION GOTO b#SB 4r 1 r 1 r 1 3r 2 r 2 r 2 2s 2 s 3 0s 3 s 2 1 1accg 状态 ACTIONGOTO ab#T 4r 1 3r 2 2acc 1s 1 s 3 0s 1 2s 3 状态 ACTIONGOTO ik#P 我们知道，我们知道，LR(0)、SLR(1

30、)和和LR(1)分析表分析表 构造的主要差别是构造算法。其区别如下：构造的主要差别是构造算法。其区别如下： (1) 对对LR(0)分析表来说，若项目分析表来说，若项目A属属 于于Ik(状态状态)，则对，则对任何终结符任何终结符a(包括包括$)，置，置 ACTIONk,a为为“用产生式用产生式A进行归约进行归约 (A为第为第j个产生式个产生式)”，简记为，简记为“rj”。表。表 现在现在ACTION子表中，则是每个归约状态子表中，则是每个归约状态 所在的行全部填满所在的行全部填满“rj”；并且，；并且，同一行的同一行的 “rj”其下标其下标j相同，而不同行的相同，而不同行的“rj”其下其下 标标

31、j是不一样的。是不一样的。 (2) (2) 对对SLR(1)SLR(1)分析表来说，若项目分析表来说，若项目A A属于属于I Ik k， 则对任何输入符号则对任何输入符号a a，仅当，仅当a aFOLLOW(A)FOLLOW(A)时置时置 ACTIONk,aACTIONk,a为为“用产生式用产生式A A进行归约进行归约(A(A 为第为第j j个产生式个产生式) )”，简记为，简记为“r r j j ”。表现在。表现在 ACTIONACTION子表中，则存在某个归约状态所在的行并子表中，则存在某个归约状态所在的行并 不全部填满不全部填满r rj j，并且不同行的，并且不同行的“r rj j”其下

32、标其下标j j不同。不同。 第四章 (3) (3) 对对LR(1)LR(1)来说，若项目来说，若项目AA,a,a属于属于I Ik k( (状态状态) )， 则置则置ACTIONk,aACTIONk,a为为“用产生式用产生式A A进行归约进行归约”， 简记为简记为“r rj j”。LR(1)LR(1)是在是在SLR(1)SLR(1)状态状态( (项目集项目集) )的基的基 础上，通过状态分裂的办法础上，通过状态分裂的办法( (即分裂成更多的项目即分裂成更多的项目 集集) )，使得，使得LRLR分析器的每个状态能够确切地指出当分析器的每个状态能够确切地指出当 后跟哪些终结符时才容许把后跟哪些终结符

33、时才容许把归约为归约为A A。例如，假定。例如，假定 AA,a,a属于属于I Ik k( (状态状态) )，则置，则置ACTIONk,aACTIONk,a栏目栏目 为为r rj j(A(A为第为第j j个产生式个产生式) )；而；而AA,b,b属于属于 I Im m( (状态状态) )，则同样置，则同样置ACTIONm,bACTIONm,b栏目为栏目为r rj j。表现在。表现在 ACTIONACTION子表中，则在不同的行子表中，则在不同的行( (即不同的状态即不同的状态) )里有里有 相同的相同的r rj j存在。存在。 因此，图因此，图3-12(a)3-12(a)的分析表为的分析表为LR

34、(1)LR(1)分析表分析表 ( (在不同行有相同的在不同行有相同的r r2 2存在存在) )；图；图3-12(b)3-12(b)为为 LR(0)LR(0)分析表分析表( (有有r rj j的行是每行都填满了的行是每行都填满了r rj j 且同一行且同一行r rj j的的j j相同，不同行相同，不同行r rj j的的j j不同不同) )； 而图而图3-12(c)3-12(c)为为LR(0)LR(0)分析表分析表( (存在并不全存在并不全 部填满部填满r rj j的行，且不同行的行，且不同行r rj j的的j j不同不同) )。 第四章 第五章 1 1、表达式表达式( (A AB)B)(C(CD

35、)D)的逆波兰表示为的逆波兰表示为 。 2 2、有一语法制导翻译如下所示：、有一语法制导翻译如下所示： S SbAb printbAb print1 1 A A(B print(B print2 2 A Aa printa print3 3 B BAa) printAa) print4 4 若输入序列为若输入序列为b(aa)a)a)bb(aa)a)a)b，且采用自下而上，且采用自下而上 的分析方法，则输出序列为的分析方法，则输出序列为 。34242421 ABCD 3 3、给出文法、给出文法GS: GS: S SSaA|ASaA|AA AAbB|BAbB|BB BcSd|ecSd|e 请证实请证实AacAbcBaAdbedAacAbcBaAdbed是文法是文法GSGS的一个句型；的一个句型； 请写出该句型的所有短语、素短语以及句柄；请写出该句型的所有短语、素短语以及句柄； 为文法为文法GSGS的每个产生式写出相应的翻译子程的每个产生式写出相应的翻译子程 序，使句型序，使句型AacAbcBaAdbedAacAbcBaAdbed经该翻译方案经该翻译方案归约归约 后，输出为后，输出为131042521430131042521430。 第五章 第五章