资源描述：
《编译原理-练习.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理——练习1王金伟计算机与信息工程学院天津师范大学练习1.1基本概念编译程序的结构上下文无关文法的一些概念词法分析语法分析自上而下自下而上1.填充下面编译程序总框图源程序目标程序(字符串)词法分析器语法分析器语义分析和中间代码生成器代码优化器目标代码生成器表格管理出错处理对于∑上的每一个正规式V，存在一个∑上的DFAM，使得L(M)=L(V)问题：如何由一个正规式V，构造一个DFAM思路：分两步走1.根据V，构造一个NFAM’，使得L(M’)=L(V)2.将M’确定化，变为DFAM第一步，在∑上构造一个NFAM’(1)构造一个拓广的转换图练习1.2词法分析(2)使用分裂
2、规则对V进行分裂，加进新结点，直到把图转换成每条弧上标识为∑上的一个字符或ε最后得到一个NFAM’且L(M’)=L(V)第二步，把M’确定化(1)两个概念定义1：假定I是M’的状态集的子集，定义I的ε闭包ε_CLOSURE(I)为：(a)若q∈I，则q∈ε_CLOSURE(I)(b)若q∈I，那么从q出发经任意条ε弧而能到达的任何状态q’都属于ε_CLOSURE(I)；定义2：假定I是M’的状态集的子集，定义Ia=ε_CLOSURE(J)其中，J是所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体例：有如下一个状态转换图假定I={1,2}，求Ia=？解：Ia
3、=ε_CLOSURE(J)J={}ε_CLOSURE(J)={}Ia={5,6,2,4,7,3,8}1a5438εε267εεεaa4,5,35,6,2,4,7,3,8aaa543ε6ε2ε7ε8(2)用子集法把M’确定化设∑={a，b}①构造一张表IIa=ε_CLOSURE(J)Ib=ε_CLOSURE(J)集合1集合1集合1集合2集合2集合2集合3集合3集合3集合4集合4集合4ε_CLOSURE(X)……IIa=ε_CLOSURE(J)Ib=ε_CLOSURE(J)ε_CLOSURE(X)集合1集合2集合3集合4集合1集合3集合4集合2…集合2集合4集合3集合1…Sab0
4、12341342…2431…②把得到的每个集合看成一个状态，得到一张状态转换表，该表的初态就是ε_CLOSURE(X)，它的终态是那些含有终态Y的子集，这样就得到一个DFAM且L(M)=L(M’)1.构造下列正规式相应的DFA。(1)1(0
5、1)*101(2)0*10*10*10*①②(1)1(0
6、1)*101③④⑤得到一个NFAM’且L(M’)=L(V)用子集法对M’进行确定化①构造一张表II0=ε_CLOSURE(J)I1=ε_CLOSURE(J)--J={1}{X}{1,2,3}--{2,3}{2,3}{2,3,4}{1,2,3}{2,3}{2,3,4}{2,3,5}{
7、2,3,4}{2,3,4}J={2}J={2,4}J={2}J={2,4}J={2,5}J={2,4}{2,3,5}{2,3}{2,3,4,Y}{2,3,4,Y}{2,3,5}{2,3,4}J={2}J={2,4,Y}J={2,5}J={2,4}II0=ε_CLOSURE(J)I1=ε_CLOSURE(J){X}{1,2,3}{2,3}{2,3,4}{2,3,5}{2,3,4,Y}--{2,3}{2,3}{2,3,5}{2,3}{2,3,5}{1,2,3}{2,3,4}{2,3,4}{2,3,4}{2,3,4,Y}{2,3,4}②把每个子集看成一个状态，得到一个DFAM，且L
8、(M)=L(M’)s01012345--2242413335301232332434515324s01012345--22424133353把DFAM’进行化简解:①把M状态集分为两组:终态结点{5}非终态结点{0，1，2，3，4}②考察{0，1，2，3，4}因为，{0，1，2，3，4}0={0，1，2，3，4}1=所以，{0，1，2，3，4}可再分，分成{0,1,2,3}和{4}③考察{0，1，2,3}因为，{0,1,2,3}0=所以，{0,1,2,3}必可再分看图，把{0,1,2,3}分割为{0,1,2}和{3}{2,4}{1,3,5}{0,1,2,3,4}{0,1,2,
9、3,4}J={2,4}J={1,3,5}{2，4}{0，1，2，3}J={2,4}④考察{0,1,2}因为，{0,1,2}0={0,1,2}1=所以，{0,1,2}必可再分看图，把{0,1,2}分割为{0}，{1,2}⑤考察{1,2}因为，{1,2}0={1,2}1=所以{1,2}不可再分J={2}J={1,3}{2}{0,1,2}{1,3}{0,1,2}J={2}J={3}{2}{1,2}{3}{3}所以，最终把M分割为{0}，{1,2}，{3}，{4}，{5}⑥用状态2代替状态1，把引向状态1的箭弧
