《编译原理教学-华南理工》第三章作业.pptVIP

第三章 词法分析 构造一个正规表达式，使它定义的正规集为∑={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。然后将其分别转换为DFA和正规文法 1）正规表达式为： (0 | 10)* 0*(100*)* 正确 0*(10)*0* 不正确 0* | (10)* 不正确 2）将正规表达式 (0 | 10)*转换为DFA 由正规表达式构造相应的DFA，共分三步： 由正规表达式构造一个相应的NFA 将NFA转换成等价的DFA DFA的最小化 （1）构造与(0 | 10)*等价的 NFA (0 | 10)* 0|10 ε ε 0 ε ε 10 0 ε ε 0 1 （2）将NFA转换成DFA 采用子集法，即DFA的每个状态对应NFA的一个状态集合 DFA的初始状态T0= ε-closure(1) 对于任何a∈Σ ，求 Tia= ε-closure(Move(Ti,a)) 0 1 4 2 ε ε 3 0 1 φ {2,4 }=T1 {3 } {3} {2,4 }=T1 {2,4} {3} { 2,4} {1,2,4} Ti1 Ti0 Ti T0 T1 T2 0 1 4 2 ε ε 3 0 1 1 1 0 DFA的状态转换图 φ {2,4 }=T1 {3 } {3} {2,4 }=T1 {2,4} {3} { 2,4} {1,2,4} Ti1 Ti0 Ti T0 T1 T2 1 1 0 T2 0 1 0 T0 T1 0 1 首先，将状态分成两个子集：一个由终态组成，一个由非终态组成：{ { T0,T1} { T2 } } （3）化简DFA：分割法，把DFA的状态集分成一些不相交的子集，使得不同的两子集的状态是可区别的，同一子集的状态是等价的。 T2 0 1 0 T0 T1 0 1 在等价状态子集 { T0,T1}中选状态T0做代表，消去其他状态T1，把从消去状态T1射出和射入的弧都引到代表状态T0上 得到化简后的DFA： T2 0 1 0 T0 T1 0 1 T2 0 1 T0 0 作业中的问题： 只给出了NFA，没有转换成DFA，或者没有进行DFA的化简 按课本上的方法构造的NFA，这种方法引进的状态个数和标记为ε的边较多，给转换成DFA带来了麻烦，容易出错 区分NFA和DFA： NFA有标记为ε的边而DFA没有 DFA中的一个状态对于一个输入符，最多只有一个转向状态，而NFA中的一个状态对于一个输入符，可能转向一个状态集合。 0 1 1 3 1 0 4 5 1 2 1 不是DFA 3）将正规表达式 (0 | 10)*转换为正规文法 S- (0 | 10)* 依据规则2：A-x*y = A-xA A-y，转换为： S-ε S- (0 | 10) S 等价于： S-ε S- 0S S- 10S 依据规则1：A-xy = A-xB B-y ，转换为： S-ε S- 0S S-1S’ S’-0S