编译原理习题与答案ppt课件.ppt-淘文阁

资源描述

《编译原理习题与答案ppt课件.ppt》由会员分享，可在线阅读，更多相关《编译原理习题与答案ppt课件.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第二章2.2 设有文法设有文法GN:N-D | NDD-0|1|9(1) GN定义的语言是什么？定义的语言是什么？(2) 请给出句子请给出句子0123的最左推导和最右推导。的最左推导和最右推导。N ND NDD NDDDDDDD 0DDD01DD 012D0123N ND N3ND3 N23ND23N123 D1230123我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物2

2、.5 证明下面的文法是二义性的。证明下面的文法是二义性的。SiSeS | iS | i答：对句子答：对句子iiiei对应两棵不同的语法树对应两棵不同的语法树第二章SiSSeiSiiSiSSeiSii我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物2.9 设有文法设有文法GT: TT*F|F F FP|PP(T)|i 分析句型分析句型T*P (T*F)的短语、直接短语和句柄的短语、直接短语和句柄答：句型答：句型T*P (T*F)的语法树：的语法树：TTF*()T五棵子树对应五个短语五棵子树对应五个短语T*P

3、(T*F), P (T*F),P, (T*F), T*F两层子树两层子树( (简单子树简单子树) )的末端结点构成直接短语的末端结点构成直接短语两棵两层子树对应两个直接短语：两棵两层子树对应两个直接短语： P , T*F位于最左边的两层子树的末端结点构成句柄：位于最左边的两层子树的末端结点构成句柄： P第二章PFPTF*我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章3.1 构造正规式构造正规式1(0|1)*101相应的相应的NFAX 1B1C10D YA (0|1)*X 1B1C10D YAE 0

4、|1X 1B1C10D YAE 0,1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章3.1 构造正规式构造正规式1(0|1)*101相应的相应的NFAX 11B10C YA (0|1)* 0,1X 11B10C YAX 1B1C10D YAE 0,1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章3.5 给出下述文法所对应的正规式。给出下述文法所对应的正规式。G：SaA AbA | aB | b B aA解

6、到正规式，再由正规式到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的的状态转换图为状态转换图为：我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章3.4 给出文法给出文法GS，构造相，构造相应最小的应最小的DFA。G：SaS | bA | b AaS解解：由文法直接

7、到由文法直接到NFA文法对应的有自动文法对应的有自动M=(S,A, T, a,b, f, S, T)其对应的状态转换图为：其对应的状态转换图为：产生式产生式转换函数转换函数SaSf(S,a)=Sf(S,a)=SSbAf(S,b)=Af(S,b)=ASbf(S,b)=Tf(S,b)=TAaSf(A,a)=Sf(A,a)=S我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章正规式：正规式：(a|ba)*bTbSAaba产生式产生式转换函数转换函数SaSf(S,a)=Sf(S,a)=SSbAf(S,b)=Af

8、(S,b)=ASbf(S,b)=Tf(S,b)=TAaSf(A,a)=Sf(A,a)=S我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章将将NFA确定化为确定化为DFA如右图所示如右图所示最小化：此状态图已经为最简了。最小化：此状态图已经为最简了。TbSAabaSSA,TA,TSIbIaI0101001aba-我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章1.指出与正规式匹配的串。指出与正规式匹配的串。a)

9、 (ab|b)*c 与后面的那些串匹配？与后面的那些串匹配？ababbcababcbabcaaabcb) ab*c*(a|b)c 与后面的那些串匹配？与后面的那些串匹配？acacacbbcabbcacabcaccc) (a|b)aa*(ba)* 与后面的那些串匹配与后面的那些串匹配? ?babbabaaaaababa我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章2. 为下边所描述的串写正规式，字母表是为下边所描述的串写正规式，字母表是 0, 1.a) 以以01 结尾的所有串结尾的所有串b) 只包含一

10、个只包含一个0的所有串的所有串 c) 包含偶数个包含偶数个1但不含但不含0的所有串的所有串d) 包含偶数个包含偶数个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

11、)*x 必须以必须以 x 开头和开头和x结尾的串结尾的串 b) x*(yx+)*x* 每个每个 y 至少有一个至少有一个 x 跟在后边的串跟在后边的串 c) (x|y)*(xx|yy) (x|y)* 所有含两个相继的所有含两个相继的x或两个相继的或两个相继的y的串的串我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章4.指出哪些串是自动机可接受的指出哪些串是自动机可接受的xy xyxxy yyyx xyyxyxyxxy我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我

12、也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章5.将下图所示的将下图所示的非确定有限自非确定有限自动机动机(NFA)变换变换成等价的确定成等价的确定有限自动机有限自动机(DFA)。XY1342abaabbabab我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章解解: :用子集法将用子集法将NFA确定化，确定化，如下图所示。如下图所示。 IIaIbX132,3,Y3,Y13,432,3,4,Y2,3,Y2,3,Y2,3,Y3,43,Y3

13、,4,Y3,43,42,3,4,Y2,3,4,Y2,3,4,Y2,3,4,Y3,4,Y3,4,Yba01213425336435557666767重新命名重新命名XY1342abaabbabab我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物上上图所对应的图所对应的DFA如下所示。如下所示。 345aabba2bb01a7bb6babaa第三章ba01213425336435557666767我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错

14、：表里边有一个活的生物对上图的对上图的DFA进行最小化。首先将进行最小化。首先将状态分为非终态集和终态集两部分：状态分为非终态集和终态集两部分：0,1,2,5和和3,4,6,7。由终态集可知，对于状态由终态集可知，对于状态3、6、7，无论输入字符是无论输入字符是a还是还是b的下一状态的下一状态均为终态集，而状态均为终态集，而状态4在输入字符在输入字符b的下一状态落入非终态集，故将其的下一状态落入非终态集，故将其化为分化为分0,1,2,5, 4, 3,6,7第三章ba01213425336435557666767我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我

15、也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章对于非终态集，在输入字符对于非终态集，在输入字符a a、b b后按其下一状态落入的状态集后按其下一状态落入的状态集不同而最终划分为不同而最终划分为0, 1, 2, 5, 4, 3,6,7按顺序重新命名为按顺序重新命名为0、1、2、3、4、5，得到最简得到最简DFADFA如下图所示。如下图所示。0,1,2,5, 4, 3,6,7ba01213425336435557666767我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物012ab435aabbbb

16、baa345aabba2bb01a7bb6babaa我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物6.设有设有L(G)=a2n+1b2ma2p+1| n0,p0,m1。(1) 给出描述该语言的正规表达式；给出描述该语言的正规表达式；(2) 构造识别该语言的确定有限自动机构造识别该语言的确定有限自动机(可直接用状可直接用状态图形式给出态图形式给出)。解：解：(1) 该语言对应的正规式为该语言对应的正规式为a(aa)*bb(bb)*a(aa)*。(2) a(aa)*bb(bb)*a(aa)*正规表达式对应的正

17、规表达式对应的NFA如如下下图所示。图所示。第三章我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章正规表达式：正规表达式：a(aa)a(aa)* *bb(bb)bb(bb)* *a(aa)a(aa)* *Y1Xba345bbab6aa2aa我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物IIaIb用子集法将上图确定化，如图所示。用子集法将上图确定化，如图所示。X121123456YY3454重命名重命名X1234Y

18、561231Y6Y454abY6Y1Xba345bbab6aa2aa我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物重新命名后的状态转换矩阵重新命名后的状态转换矩阵可化简为可化简为( (可由最小化方法得到可由最小化方法得到) )X,2 1 3,5 46 Y按顺序重新命名为按顺序重新命名为0、1、2、3、4、5后得到最简的后得到最简的DFA，如，如下图所示。下图所示。 X1234Y561231Y6Y454abY1Xba345bbab6aa2aa我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽

19、的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第三章a(aa)*bb(bb)*a(aa)*Y1Xba345bbab6aa2aa510ba23abab4aa我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物7.7.有一台自动售货机，接收有一台自动售货机，接收1 1分和分和2 2分硬币，出售分硬币，出售3 3分分钱一块的硬糖。顾客每次向机器中投放钱一块的硬糖。顾客每次向机器中投放3 3分的硬币，分的硬币，便可得到一块糖便可得到一块糖( (注意：只给一块并且不找钱注意：只给一块并且不找钱)

20、)。(1) (1) 写出售货机售糖的正规表达式；写出售货机售糖的正规表达式；(2) (2) 构造识别上述正规式的最简构造识别上述正规式的最简DFADFA。解解：(1) (1) 设设a=1a=1，b=2b=2，则售货机售糖的正规表达式为，则售货机售糖的正规表达式为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，如图所示。，如图所示。第三章我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快

21、，证实我的猜测没有错：表里边有一个活的生物XY123ababbaba第三章正规表达式：正规表达式：a(b|a(a|b)|b(a|b)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物IIaIb第三章用子集法将用子集法将NFA确定化。确定化。重新命名Y3YY2YY13YX12XY123ababbaba4344244134012ab我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物由转换矩阵可看出，非终态由转换矩阵可看出，非终

22、态2 2和非终态和非终态3 3面对输入符号面对输入符号a a或或b b的下一状态相同，故的下一状态相同，故合并为一个状态合并为一个状态即最简状态即最简状态00、11、22，33、44。按顺序重新命名为按顺序重新命名为0 0、1 1、2 2、3 3，则得到，则得到最简最简DFADFA，如下图所示。，如下图所示。第三章4344244134012ab我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物0312abbbaa3233123012ab第三章我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的

23、世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第四章作业作业4.3 设有文法设有文法GS:SA AB|AiBBC|B+C C)A*|( 1）将文法）将文法GS改写为改写为LL(1)文法。文法。2）求经改写后的文法的每个非终结符的）求经改写后的文法的每个非终结符的FIRST集和集和FOLLOW集。集。3）构造相应的预测分析表。）构造相应的预测分析表。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第四章1）将文法）将文法GS改写为改写为LL(1)文法。文法。文法文法GS为左递归文法，削去

24、文法左递归为左递归文法，削去文法左递归后的文法为：后的文法为：SAABAA iBA|BCBB +CB|C)A*|( SA AB|AiBBC|B+C C)A*|( 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第四章1）将文法）将文法GS改写为改写为LL(1)文法。文法。FIRST(C)=(,) FIRST(B)=+, FIRST(B)=(,) FIRST(A)=i, FIRST(A)=(,) FIRST(S)=(,)FOLLOW(S)=$ FOLLOW(A)=$,*FOLLOW(A)=$,* FOLLOW

25、(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) =iSELECT(A)= FOLLOW(A)= $,*SELECT(BCB)=(,)SELECT(B +CB) =+ SELECT(B)= i, $,*SELECT(C)A*)=) SELECT(C( )

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

27、LLOW(C)=+,i,$,*我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3）构造相应的预测分析表。）构造相应的预测分析表。C)A*B +CBC(BBCBBCBB AiBAAABAABAA S $*)+i (终极符号终极符号语法语法变量变量SELECT(SA) = (,) SELECT(ABA)=(,) SELECT(AiBA) =i SELECT(A)= $,*SELECT(BCB)=(,) SELECT(B +CB) =+ SELECT(B)= i, $,* SELECT(C)A*)=) SELEC

28、T(C( )= (C 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第四章作业作业4.5 设有表格结构文法设有表格结构文法GS: Sa|(T) TT,S|S 1）计算文法的）计算文法的FIRSTVT集和集和LASTVT集。集。2）构造其优先关系表，并判断其是否为算）构造其优先关系表，并判断其是否为算符优先文法。符优先文法。3）计算其优先函数。）计算其优先函数。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第四章1）计

29、算文法的）计算文法的FIRSTVT集和集和LASTVT集。集。FIRSTVT(S)=a, , (FIRSTVT(T)=, a, , (LASTVT(S)=a, , )LASTVT(T)=, a, ,)2）构造其优先关系表，并判）构造其优先关系表，并判断其是否为算符优先文法。断其是否为算符优先文法。Sa|(T) TT,S|S= = =($,)1111111111迭代函迭代函数数函数函数a,()fg0(初初值值)fg122213233313331344241fg2, 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的

30、生物第四章例文法例文法GS S E EaA|bB AcA|d BcB|d 1）构造识别文法活前缀的）构造识别文法活前缀的DFA2）构造其）构造其LR(0)分析表分析表3）输入串）输入串aabab是否为文法是否为文法G定义的句子定义的句子我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物0: S E EaA EbB 4: AcA AcA Adc5: BcB BcB Bd c3: EbB BcB Bdb1: S EE2: EaA AcA Ada11: Bdd8: AcAAccd10: Addd9: BcBB6:

31、EaA A7: EbBBLR(0)分析表为分析表为:s2s31accs4s106s5s117s4s108s5s11r1r1r1r1r19r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r6状态状态ACTIONGOTOabcd#EAB01234567891011S E EaA|bBAcA|d BcB|d我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物(0) S E(1) Ea(2) EbB(3) Ac(4) Ad(5) BcB(6) Bd输入串输入串bccd$的

32、分析过程的分析过程步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONGOTO1 2 3 4 56789 0$bccd$S303$bccd$S8038$bccd$S80388$bccd$S903889$bccd$r6110388$bccr511038$bcr5703$br210$accB(11)B(11)B7E1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第四章8086/8088汇编语言对操作数域的检查可汇编语言对操作数域的检查可以用以用LR分析表实现。设分析表实现。设m代表存储器，代表存储器，r

33、代表寄存器，代表寄存器，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

34、) Pr,i(5) Pr,m第四章GP: Pm,r m,i r,r r,i r,m我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物文法GS的DFA0: 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,m1: S PP2: Pm,r Pm,i3: Pr,r Pr,i Pr,m5: Pm, r Pm, i4: Pr, r Pr, i Pr, m,mr,r6: Pm, r i7: Pm, i r8: Pr, r

35、i9: Pr, i m10: Pr, m我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物LR(0)分析表分析表状态状态ACTIONGOTOmri，$P0s2s3 1 1 acc 2 s5 3 s4 4s10s8s9 5 s6s7 6r1r1r1r1r1 7r2r2r2r2r2 8r3r3r3r3r3 9r4r4r4r4r4 10r5r5r5r5r5r1我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物(0) SP (1)

36、Pm,r(2) Pm,i(3) Pr,r (4) Pr,i(5) Pr,m输入串输入串m,i$的分析过程的分析过程步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONGOTO1 2 3 4 5 0$m,i$S202$m,i$S5025$m,i$S70257$m,i$r20$acc1P1例：请指出下图中的例：请指出下图中的LRLR分析表分析表(a)(a)、(b)(b)、(c)(c)分属分属LR(0)LR(0)、SLR(1)SLR(1)和和LR(1)LR(1)中的哪一种，并说明理由。中的哪一种，并说明理由。 (a)(b )(c)5r14r23r22s451acc0s312状态ACTION G

37、OTOb#SB4r1r1r13r2r2r22s2s30s3s211accg状态ACTIONGOTOab#T4r13r22acc1s1s30s12s3状态ACTIONGOTOik#P我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我们知道，我们知道，LR(0)、SLR(1)和和LR(1)分析表分析表构造的主要差别是构造算法。其区别如下：构造的主要差别是构造算法。其区别如下：(1) 对对LR(0)分析表来说，若项目分析表来说，若项目A属属于于Ik(状态状态)，则对，则对任何终结符任何终结符a(包括包括$)，置，

38、置ACTIONk,a为为“用产生式用产生式A进行归约进行归约(A为第为第j个产生式个产生式)”，简记为，简记为“rj”。表。表现在现在ACTION子表中，则是每个归约状态子表中，则是每个归约状态所在的行全部填满所在的行全部填满“rj”；并且，；并且，同一行的同一行的“rj”其下标其下标j相同，而不同行的相同，而不同行的“rj”其下其下标标j是不一样的。是不一样的。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物(2) (2) 对对SLR(1)SLR(1)分析表来说，若项目分析表来说，若项目A A属于属于I

39、 Ik k，则对任何输入符号则对任何输入符号a a，仅当，仅当a aFOLLOW(A)FOLLOW(A)时置时置ACTIONk,aACTIONk,a为为“用产生式用产生式A A进行归约进行归约(A(A为第为第j j个产生式个产生式) )”，简记为，简记为“r rj j”。表现在。表现在ACTIONACTION子表中，则存在某个归约状态所在的行并子表中，则存在某个归约状态所在的行并不全部填满不全部填满r rj j，并且不同行的，并且不同行的“r rj j”其下标其下标j j不同。不同。第四章我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜

40、测没有错：表里边有一个活的生物(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分析器的每个状态能够确切地指出当分析器的每个状态能够确切地指出当后跟哪些终结符时才容许把后跟哪些终结符时才容许把归约为

41、归约为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存在。存在。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，

42、证实我的猜测没有错：表里边有一个活的生物因此，图因此，图3-12(a)3-12(a)的分析表为的分析表为LR(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

43、 j的的j j不同不同) )。第四章我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第五章1 1、表达式表达式( (A AB)B)(C(CD)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，且采用自下而上

44、，且采用自下而上的分析方法，则输出序列为的分析方法，则输出序列为。34242421ABCD我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3 3、给出文法、给出文法GS: GS: S SSaA|ASaA|AA AAbB|BAbB|BB BcSd|ecSd|e请证实请证实AacAbcBaAdbedAacAbcBaAdbed是文法是文法GSGS的一个句型；的一个句型；请写出该句型的所有短语、素短语以及句柄；请写出该句型的所有短语、素短语以及句柄；为文法为文法GSGS的每个产生式写出相应的翻译子程的每个产生式写

45、出相应的翻译子程序，使句型序，使句型AacAbcBaAdbedAacAbcBaAdbed经该翻译方案经该翻译方案归约归约后，输出为后，输出为131042521430131042521430。第五章我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第五章(1) (1) 根据文法根据文法GSGS画出画出AacAbcBaAdbedAacAbcBaAdbed对应的对应的语法树如图所示。语法树如图所示。由图可知由图可知AacAbcBaAdbedAacAbcBaAdbed是文法是文法GSGS的一个句型。的一个句型。AaS

46、SBAdScABbABbAedScAaSAB图图 AacAbcBaAdbed对应的语法树对应的语法树我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第五章( 2 )( 2 ) 由图可知，句型由图可知，句型AacAbcBaAdbedAacAbcBaAdbed中的短语为：中的短语为： B, BaA, cBaAd, AbcBaAd, e, B, BaA, cBaAd, AbcBaAd, e, AbcBaAdbe, cAbcBaAdbed, A, AbcBaAdbe, cAbcBaAdbed

47、, A, AacAbcBaAdbedAacAbcBaAdbedAaSSBAdScABbABbAedScAaSAB我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第五章从图可看出，句型从图可看出，句型AacAbcBaAdbedAacAbcBaAdbed的的素短语为：素短语为：BaABaA和和e e。句柄句柄( (最左直接短语最左直接短语) )为：为：A A。AaSSBAdScABbABbAedScAaSAB我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢

48、？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物(3) (3) 采用修剪语法树的办法，按句柄方式自下而上采用修剪语法树的办法，按句柄方式自下而上归约，每当一个产生式得到匹配时，则按归约的归约，每当一个产生式得到匹配时，则按归约的先后顺序与所给的输出先后顺序与所给的输出131042521430131042521430顺序进行对顺序进行对应。应。如：第一个句柄为如：第一个句柄为A A，它所对应的产生式为，它所对应的产生式为S SA A，所以它的语义动作应为所以它的语义动作应为print(print(1 1) )；修剪后第；修剪后第二次找到的句柄为二次找到的句柄为B,B,它所对应的产生式

49、为它所对应的产生式为A AB B，此时它对应输出序列中的此时它对应输出序列中的“3 3”，即它的语义动作，即它的语义动作为为print(print(3 3) )，依此类推，得到每个产生式相，依此类推，得到每个产生式相应的语义动作如下：应的语义动作如下：第五章我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第五章SSaA print(0)SA print(1)AAbB print(2)AB print(3)BcSd print(4)Be print(5)AaSSBAdScABbABbAedScAaSAB句型句型AacAbcBaAdbed经该翻译方经该翻译方案归约后，输出为案归约后，输出为131042521430

展开阅读全文