《《编译原理》期末复习资料完整版》由会员分享，可在线阅读，更多相关《《编译原理》期末复习资料完整版（15页珍藏版）》请在金锄头文库上搜索。
1、编译原理期末复习资料【题 1】1. （a|b）*（aa|bb）（a|b）*画出状态转换图。IaIb 1,2,32,3,42,3,5 2,3,42,3,4,6,7,82,3,5 2,3,52,3,42,3,5,6,7,8 2,3,4,6,7,82,3,4,6,7,82,3,5,7,8 2,3,5,6,7,82,3,4,7,82,3,5,6,7,8 2,3,5,7,82,3,4,7,82,3,5,6,7,8 2,3,4,7,82,3,4,6,7,82,3,5,7,8IaIb123243325446575675746 新的状态转换图如下： （1）A=1,2,3，B=4,5,6,7 Aa=2,4 （2
2、）A=1,3，B=2，C=4,5,6,7 Aa=2B，Ab=3,5 （3）A=1，B=2，C=3,D=4,5,6,7（单元素可以不用看，必有，古先看D） Da=4,7D，Db=5,6D，Aa=2B，Ab=3C，Ba=4D，Bb=3C，Ca=2B，Cb=5C，则有ab ABC BDCCBDDDD2. （a*|b*）b（ba）*的状态转换图。IaIb 1,2,3,42,43,4,5,6,8 2,42,45,6,8 3,4,5,6,8-3,4,5,6,7,8 5,6,8-7 3,4,5,6,7,86,83,4,5,6,7,8 76,8- 6,8-7IaIb1232243-54-657567-7-6新
3、的状态转换图如下：化简：（用终结状态与非终结状态，然后输出状态一致分一类）。（1）A=1,2,6，B=3,4,5,7 Aa=2 （2）A=1,2，B=6，C=3,4,7，D=5 Cb=5,6 （只要有一个不属于任何一个集合，就不行）（3）A=1,2，B=6，C=3，D=4,7，E=5 Ab=3,4 （4） A=1，B=2，C=6，D=3，E=4,7，F=5 Aa=2B，Ab=3D，Ba=2B，Bb=4E，Ca=7E，Db=5F，Eb=6C，Fa=7E，Fb=5Fab ABD BBECE-D-FE-CFEF注意事项：知识要点：u 正则表达式：；是最左边一个字母一定是，其余字母为的任意组合，不包括
4、。a和若干个a（包括0的情形）后跟一个b构成的符号串集合a和a后跟若干个（包括0的情形）b构成的符号串集合u 状态转换图（有穷状态自动机）： 【题 2】1.求如下简单算术表达式文法中语法变量的FOLLOW集。解答：（1）求表达式文法的语法符号的FIRST集：FIRST(F)=（, idFIRST(T)=FIRST(F)=（, id FIRST(E)=FIRST(T)=（, id FIRST(E)=+，FIRST(T)=*, FIRST(+)=+, FIRST(*)=*FIRST(（)=（FIRST(）)=）FIRST(id)=id（2）求表达式文法的语法变量的 FOLLOW集：FOLLOW(E
5、) = #, ) FOLLOW(E)= FOLLOW( E ) = #, ) FOLLOW(T) = FIRST(E)-FOLLOW(E)FOLLOW(E)= +,),#FOLLOW(T)= FOLLOW(T)= +,),#FOLLOW(F) = FIRST(T)FOLLOW(T)FOLLOW(T) =*,+,),# 6知识点First集合的求法： First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合1. 直接收取：对形如U-a的产生式（其中a
6、是终结符），把a收入到First(U)中2. 反复传送：对形入U-P1P2P3Pn的产生式（其中P是非终结符），应先把First(P1)中的全部内容传送到First(U)中,如果P1中有，把First(P2)中的内容传送到First(U)中,类推直到Pi中无。Follow集合的求法： Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“$”是识别符号的后随符,先直接加入到S中。1. 直接收取：注意产生式右部的每一个形如“Ua”的组合，把a直接收入到Follow(U)中。2. 直接收取：对形如“UP”(P是非终结符)的组合，把
7、First(P)中非收入到Follow(U)中。3. 反复传送：对形如UaP的产生式（其中P是非终结符）或U-aPQ(P,Q为非终结符且Q中含)，应把Follow(U)中的全部内容传送到Follow(P)中。例 文法：SABc Aa| Bb|First集合求法:能由非终结符号推出的所有的开头符号或可能的，但要求这个开头符号是终结符号。如此题A可以推导出a和，所以FIRST（A）=a，；同理 FIRST（B）=b,;S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S）=a，b，cFollow集合的求法:紧跟随其后面的终结符号或。但文法的识别符号包含，在求的时候还要考虑到。
8、具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。 Follow（S）=如求A的，产生式：SABc Aa| ，但只有SABc 有用。跟随在A后面的终结符号是FIRST（B）=b，当FIRST（B）的元素为时，跟随在A后的符号就是c，所以 Follow（A）=b，c同理Follow（B）=c2.对下面的文法 G ： (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。(2) 证明这个方法是 LL(1) 的。(3) 构造它的预测分析表。解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。 FIRST集合有： FIRST(E)=FIRST(T)=FI
9、RST(F)=FIRST(P)=(,a,b,; FIRST(E)=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(T)=FIRST(T)=(,a,b,; FIRST(F)=FIRST(P)=(,a,b,; FIRST(F)=FIRST(P)=*,; FIRST(P)=(,a,b,; FOLLOW集合有： FOLLOW(E)=),#; FOLLOW(E)=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#; FOL
10、LOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#; FOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 (2)证明这个方法是LL(1)的。 各产生式的SELECT集合有： SELECT(E-TE)=FIRST(T)=(,a,b,; SELECT(E-+E)=+; SELECT(E-)=FOLLOW(E/)=),# SELECT(T-FT)=FIRST(F)=(,a,b,; SELECT(T-T)=FIRST(T)=(,a
11、,b,; SELECT(T-)=FOLLOW(T/)=+,),#; SELECT(F-PF)=FIRST(P)=(,a,b,; SELECT(F-*F)=*; SELECT(F-)=FOLLOW(F)=(,a,b,+,),#; SELECT(P-(E)=( SELECT(P-a)=a SELECT(P-b)=b SELECT(P-)= 可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是LL(1)文法。 (3)构造它的预测分析表。 文法GE的预测分析表如下： 【题 3】考虑下面的文法：（1） 求出所有语法变量的FIRSTOP集合和LASTOP集合。（2） 构造文法的算符优先关系表，并判断是否为算符优先文法。（3） 计算文法的算符优先函数。（4） 给出表达式和id*(id+id)的算符优先分析过程。解答：（1） 所有语法变量的FIRSTOP集合和LASTOP集合如下：（2）文法的算符优先关系表算符关 系算 符+-*/()id+-
