《编译原理》期末复习资料【题 1】1.（a|b）*（aa|bb）（a|b）*画出状态转换图。IaIb 1,2,3①2,3,42,3,5 2,3,4②2,3,4,6,7,82,3,5 2,3,5③2,3,42,,3,5,6,7,8 2,3,4,6,7,8④2,3,4,6,7,82,3,5,7,8 2,3,5,6,7,8⑤2,3,4,7,82,3,5,6,7,8 2,3,5,7,8⑥2,3,4,7,82,3,5,6,7,8 2,3,4,7,8⑦2,3,4,6,7,82,3,5,7,8IaIb123243325446575675746 新的状态转换图如下： （1）A={1,2,3}，B={4,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，则有ab ABC BDCCBDDDD2.（a*|b*）b（ba）*的状态转换图。IaIb 1,2,3,4①2,43,4,5,6,8 2,4②2,45,6,8 3,4,5,6,8③---3,4,5,6,7,8 5,6,8④---7 3,4,5,6,7,8⑤6,83,4,5,6,7,8 7⑥6,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} 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}Fab ABD BBECE---D---FE---CFEF[注意事项]：[知识要点]：正则表达式：；；；；是最左边一个字母一定是，其余字母为的任意组合，不包括。{a 和若干个 a（包括 0 的情形）后跟一个 b 构成的符号串集合}{a 和 a 后跟若干个（包括 0的情形）b 构成的符号串集合}状态转换图（有穷状态自动机）： 【题 2】中语法变量的 FOLLOW 集。[解答]：（1）求表达式文法的语法符号的 FIRST 集：FIRST(F)={（, 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)= {+,),#}FOLLOW(F) =...
