编译原理复习题答案

二、概念问题1，有语法：PP Q|QQQ*R|RR(P)|i(1)证明q * r q是句型。(3点)(2)给出了q * r q的所有球、直球和句柄。(4点)(3)给出了句子I * I的最右侧推导。(4点)(4)给出了句子I * I最左边的推导。(4点)2，有语法：e e t | t t * f | f (e) | I(1)证明E T*F是句型。(3点)回答：(2)给出了E T*F的所有球体、直线球和句柄。(4点): E T*F、T*F、直接语法： T*F句柄： T*F(3)给出了句子I * I的最右侧推导。(4点)3，创建与表达式a b*(c-d)对应的逆波兰和三元序列。答案：反向波兰式：(abcd-*)三元序列：OP ARG1 ARG2(1)-c d(2) * b (1)(3) a (2)三、词汇分离问题给出了以下语言的相应语法L1=anbnambm|n，m0答案：s ab | a | b | 8721AaAb|abBaBb|ab给出了以下语言的相应语法L2=anbnci|n1，i0答案：SAB|BAa|aABbBc|bc给出了以下语言的相应语法L3=anbncm| m，n1，n为奇数，m为偶数。答案：语法G(S):SACAaaAbb/abC CCC/cc四、词汇分离问题1，以下常规相应的DFA配置(0|1)*|(11)*)*(要求：首先将正则表达式转换为NFA，然后最小化NFA)2，以下常规相应的DFA配置1(0 | 1)x 101回答：I0 i1 a，b，cA，B，C B，CB，C，DB，C B，CB，C，DB，C，DB，C，E B，C，DB，C，EB，CB，C，D，yB，C，D，yB，C，EB，C，D3，S=a，b配置接受包含ab的所有字符串的DFA。(要求：首先将正则表达式转换为NFA，然后最小化NFA)答案：(a)相应的正则表达式为(a|b)*ab(a|b)*(b) 对应于这个正则表达式的NFA是状态转换矩阵如下：最小化：0，1，2 3，4，50，2，1，3，4，5baa01b3ba因此，等效的DFA包括启动状态0、关闭状态集3、状态集0，1，3、输入字母表的状态转换图如上所示。4，构造等于正则表达式b(a|b)*ba的DFA五、语法分析问题1，下一语法G:Expr- ExprExpr(Expr)|Var ExprTailExpr tail expr | Varid VarTailVarTail(Expr) |(1) LL(1)配置分析表。(12分)回答：(1) first (expr)=_，(，id first (expr tail)=_， first (var)=idFollow (expr)=#，) follow (expr tail)=#，)Follow (var)=_，#，) follow (vartail)=_，#，)(2)提供句子id-id (id)的分析过程。(8点)步骤符号堆叠输入字串中使用的建立0 # expr id _ _ id(id)% #1 # expr tail var id _ _ id(id)# exprvar expr tail2 # expr vartail idid _ _ id(id)# varid vartail3 # expr vartail _ _ id (id) )#4 # expr tail _ _ id (id) # vartail 5 # expr _ _ id (id) # expr tail expr6 # expr _ id(id)% #7 # expr _ _ id (id) # expr expr8 # expr id (id) #9 # expr tail varid(id)# exprvar expr tail10 # expr vartail idid(id)# varid vartail11 # ExprTail vart ail(id)#(id)#12 # expr)expr(id)# vartail(expr)13 # expr tail)expr(id)#14 # expr tail)expr(id)# expr(expr)15 # expr tail)expr id(#16 # expr tail)expr tail varid(# expvar expr tail)17# ExprTail)expr tail vartail idid)# varid vartail18# ExprTail)Expr tail vartail)19# ExprTail)Expr tail) # vartail 20 # expr tail)# expr tail21 # expr tail)#22# ExprTail #ExprTail23# #分析成功2，下一语法G:ETE E E|TFT TT|FPF F *F|p(e)| a | b | |(1)计算此语法中每个终止元的FIRST和FOLLOW。(8点)答案：first (e)=(，a，b，FIRST(E)=，First (t)=(，a，b，First (t)=(，a，b，)First (f)=(，a，b，FIRST(F)=*，First (p)=(，a，b，FOLLOW(E)=#，)FOLLOW(E)=#，)Follow (t)=，#Follow (t)=，#Follow (f)=(，a，b，)，#Follow (f)=(，a，b，)，#Follow (p)=*，(，a，b，)，#(2)证明这个语法是LL(1)。(6分)回答：考虑以下生产：first(e)first(e)-follow(e)= - #，)=first(t)first()=(，a，b， =first(t)-follow(t)=(，a，b，-，)，#=first(* f)first()= * =first(* f)-follow(f)= * -(，a，b，)，#=first(e)-first(a)-first(b)-first()=因此语法LL(1)语法。(3)配置预测分析表。(6分)3，已知语法GS为：S-a|(T)T-T、S|S在语法GS中去掉左边递归需要语法GS。语法GS是LL(1)吗？如果是，则提供预测分析表。4，下一语法G:S S a T | a T | a TT a T | a(1)去掉语法的左递归，提取左公共元素。(2)构造每个非终结器的FIRST和FOLLOW集。(3)构造语法的LL(1)分析表，确保语法为LL(1)。回答：5，语法G(S)LR分析表显示了baba#系列的分析过程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTION加藤bda#sbd0R3S3121Acc2S43R24R6S5R665R4R46S7R17S88R5R5回答：阶段状态符号输入字符串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246 # DbBba #502467 # DbBba #6024678 # DbBba #70246#DbB#801#S#acc六、语法分析问题考虑语法：SAS|b ASA|a(1)列出该语法的所有LR(0)项。(5分)答案0.1.2.3。4.5.6.7。8.9.10.11。(2)给出了标识语法所有活动前缀的DFA。(5分)(3)查找所有非终结器的FOLLOW集。(5分)(4)语法是SLR语法吗？配置SLR分析表。否则，说明原因。(5分)不是SLR语法状态3，6，7存在移动协议冲突状态3: follow (s)=#排除a，b状态6: follow (s)=#，a，b包含a、b、不能解决移动协议冲突状态7: follow (a)=a，b包含a，b；解决返回冲突所以不是SLR语法。七、证明问题1，证明下面的语法是LL(1)，但不是SLR(1)。SAaAb|BbBaAB第一，语法没有左边递归，没有共同的左边因子。其次，对于：saaab | bbba first(aaab)= a first(bbba)= b first(aaab)first(bbba)=所以语法是LL(1)语法。(2)证明语法不是SLR。语法的LR(0)项目集规范族为：I0=s 。s aaab s bbba a b I1= S S.I2= SA.aAbI3= SB.bBaI4=I4= SAa。Ab A。I5=s bb。ba I6= SAaA.bI7= SBbB.aI8= SAaAb .I9= SBbBa .调查I0:Follow (a)=a，b follow (b)=a，b follow(a)follow(b)= a，b 法令生成-法令冲突。所以语法不是SLR(1)语法。2，证明下面的语法是SLR(1)，但不是LR(0)。SAAAb|bBaBaAc|a|aAb解决方案：语法GS:0: s a1: a ab2: a BBA3: b AAC4: b a5: b aab配置LR(0)项目集规范族。状态专案集转换函数0SAAAbAbBaGO0，a=1GO0，a=1GO0，b=21SAAAbACCEPTGO1，b=32AbBaBaAcBaBaAbGO2，b=4GO2，a=5GO2，a=5GO2，a=53AAbR14AbBaGO4，a=65BaAcBaBaAbAAbAbBaGO5，a=7R4GO5，a=7GO5，a=7GO5，b=26AbBaR27BaAcBaAbAAbGO7，c=8GO7，b=9GO7，b=98BaAcR39BaAbAAbR5R1状态5有“