资源描述：
《《编译原理》期末复习资料汇总》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《编译原理》期末复习资料【题1】1.（a
2、b）*（aa
3、bb）（a
4、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
5、,6,7}Aa={2,4}×（2）A={1,3}，B={2}，C={4,5,6,7}Aa={2}B，Ab={3,5}×（3）A={1}，B={2}，C={3},D={4,5,6,7}（单元素可以不用看，必有，古先看D）Da={4,7}D，Db={5,6}D，Aa={2}B，Ab={3}C，Ba={4}D，Bb={3}C，Ca={2}B，Cb={5}C，则有abABCBDCCBDDDD2.（a*
6、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,
7、4,5,6,7,86,83,4,5,6,7,8⑥76,8---⑦6,8---7IaIb1232243---54---657567---7---6新的状态转换图如下：化简：（用终结状态与非终结状态，然后输出状态一致分一类）。（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}
8、Aa={2}B，Ab={3}D，Ba={2}B，Bb={4}E，Ca={7}E，Db={5}F，Eb={6}C，Fa={7}E，Fb={5}FabABDBBECE---D---FE---CFEF[注意事项]：[知识要点]：u正则表达式：；；；；是最左边一个字母一定是，其余字母为的任意组合，不包括。{a和若干个a（包括0的情形）后跟一个b构成的符号串集合}{a和a后跟若干个（包括0的情形）b构成的符号串集合}u状态转换图（有穷状态自动机）：【题2】1.求如下简单算术表达式文法中语法变量的FOLLOW集。[解答]：（1）求表达式文法的语法符号的FIRST集：FIRST(F)
9、={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(（)={（}FIRST(）)={）}FIRST(id)={id}（2）求表达式文法的语法变量的FOLLOW集：FOLLOW(E)={#,)}FOLLOW(E')=FOLLOW(E)={#,)}FOLLOW(T)={FIRST(E')-{ε}}∪FOLLOW(E)∪FOLLOW(E')={+,),#}FOLLOW(T')=FOLLOW(T)={
10、+,),#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T')={*,+,),#}6[知识点]First集合的求法：First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合1.直接收取：对形如U->a…的产生式（其中a是终结符），把a收入到First(U)中2.反复传送：对形入U->P1P2P3…Pn的产生式（其中P是非终结符），应先把First(P1)中的全部内容传送到First(U)中,如果
11、P1中有ε，把First(P2)中的内容传送到First(U)中,类推直到Pi中无ε。Follow集合的求法：Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“$”是识别符号的后随符,先直接加入到S中。1.直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。2.直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)中非ε收入到Follow(U)中。3.反复传送：对形如U－>aP的产生式（其中P是非终结符）或U->
