第三章_词法分析(4).ppt

编译原理,2020/6/14,1,对于加括号的正规式(s)，使用N(s)本身作为它的NFA。,编译原理,2020/6/14,2,Thompson方法构造的NFA有下列性质：,N(r)的状态数最多是r中符号和运算符个数的两倍。N(r)只有一个开始状态和一个接受状态，接受状态没有向外的转换。作为构成成分的每个NFA也具有这一性质。N(r)的每个状态或者有一个用中的符号标记的指向其它结点的转换，或者至多有两个指向其它结点的转换。,编译原理,2020/6/14,3,r9,r7,r8,r4,r3,r5,r6,*,),(,r2,r1,a,|,b,a,b,(a|b)*ab的分解,例3.26构造r=(a|b)*ab的NFA(r),编译原理,2020/6/14,4,r9,r7,r8,r4,r3,r5,r6,*,),(,r2,r1,a,|,b,a,b,(a|b)*ab的分解,a,2,3,start,b,4,5,start,编译原理,2020/6/14,5,r9,r7,r8,r4,r3,r5,r6,*,),(,r2,r1,a,|,b,a,b,r3=r1|r2,a,2,3,start,b,4,5,1,6,编译原理,2020/6/14,6,r9,r7,r8,r4,r3,r5,r6,*,),(,r2,r1,a,|,b,a,b,r4=(r3),a,2,3,start,b,4,5,1,6,编译原理,2020/6/14,7,r9,r7,r8,r4,r3,r5,r6,*,),(,r2,r1,a,|,b,a,b,r5=(r3)*,a,2,3,b,4,5,1,6,7,start,0,编译原理,2020/6/14,8,r9,r7,r8,r4,r3,r5,r6,*,),(,r2,r1,a,|,b,a,b,r6=a,a,2,3,start,b,4,5,1,6,0,7,a,8,start,7,编译原理,2020/6/14,9,r9,r7,r8,r4,r3,r5,r6,*,),(,r2,r1,a,|,b,a,b,r7=r5r6,a,2,3,start,b,4,5,1,6,0,7,a,8,编译原理,2020/6/14,10,r9,r7,r8,r4,r3,r5,r6,*,),(,r2,r1,a,|,b,a,b,编译原理,2020/6/14,11,(a|b)*ab的两个NFA的比较,手工构造的NFA,语法制导的算法构造的NFA,编译原理,2020/6/14,12,补充例子,ThompsonsKeyideaNFApatternforeachsymbolwhileceofdoS-closure(move(s,c);cnextcharend;ifSFthenreturn“yes”elsereturn“no”,编译原理,2020/6/14,17,NFA和DFA的权衡,例，识别正则表达式(a|b)*a(a|b)n-1的DFA的状态数不少于2n。而相应的NFA的状态数为n+1。识别字符串x是否属于正则表达式r的语言,编译原理,2020/6/14,18,3.6.2最小化DFA的状态数(DFAMinimization),对于同一个语言，可以存在多个识别该语言的DFA。每个正则表达式都可以由唯一（不计同构）的状态数最少的DFA识别(minimalDFA)。方法：划分等价状态集合,编译原理,2020/6/14,19,可区分状态,如果DFAM分别从状态s和状态t出发，经过x路径到达的两个状态只有一个是接受状态，则字符串x区分状态s和状态t。例如，区分任何接受状态和非接受状态；b区分状态A和状态B；b区分状态B和状态C；,编译原理,2020/6/14,20,B,start,a,A,a,b,b,a,a,b,D,C,b,b,a,bb区分状态A和状态B,(a|b)*abb对应的DFA,编译原理,2020/6/14,21,算法3.23DFA最小化算法(Hopcroft算法),DFA最小化的方法是将DFA的状态划分为不相交的组，同一个组中的状态是不可区分的，不同组的状态则可以由某个输入串区分。当划分不能再进行时，得到了状态最少的DFA。初始划分包括两个组：接受状态组和非接受状态组构造新的划分new，使得划分后的每个子集在任意输入字符a上的转换能落入到当前划分的同一个组中。,编译原理,2020/6/14,22,DFA最小化算法(Hopcroft算法),重复划分组的过程，直至不需要继续划分。把一个组并为一个代表状态r（每组任取一个状态做“代表”，删去其余状态），并把到达这些状态的箭弧都改作到达r；类似地，从这个组中的每个状态出发的弧，都改作从r出发。这样得到的状态转换图所对应的DFAM就是与M等价的具有最少状态的DFA。删除M中的“陷阱”状态，删除从初始状态出发不可达的状态；取消某个状态到“陷阱”状态的转移。,编译原理,2020/6/14,23,编译原理,2020/6/14,24,final:(AC)(B)(D)(E),编译原理,2020/6/14,25,另一个例子：从a(b|c)*构造NFA,编译原理,2020/6/14,26,用子集构造法从NFA得到DFA,编译原理,2020/6/14,27,构造最小化DFA,编译原理,2020/6/14,28,例：考虑正规表达式(a|b)*(aa|bb)(a|b)*,编译原理,2020/6/14,29,用子集构造法得到的DFA：,编译原理,2020/6/14,30,Finalpartition,构造最小状态的DFA：,编译原理,2020/6/14,31,正规表达式和NFA等价,任何一个正规表达式表示的语言，存在一个NFA识别（Thompson构造法）任何一个NFA识别的语言，可以表示为一个正规表达式拓广状态转换图的概念，转移符号可以用一个正规表达式标记,编译原理,2020/6/14,32,补充内容：由-NFA构造正规表达式,在M的状态转换图上增加状态X,Y，从X到初始状态q0用弧连接，从M的所有终态到Y用弧连接，得到的新的NFA为M，它只有一个初始状态X和一个终止状态Y。反复应用以下三条规则，消去-NFAM中的状态结点和弧，直至只剩下状态结点X、Y及连接二者的弧。在消去的过程中，用正规表达式标记弧。连接X、Y结点边的标记r即为所求的正规表达式：,编译原理,2020/6/14,33,q1,q2,q3,q1,q3,r1,r2,r1r2,q1,q2,r1,r2,q1,q2,r1|r2,q1,q2,q3,r1,r3,r2,q1,q3,r1(r2)*r3,编译原理,2020/6/14,34,X,Y,r,start,编译原理,2020/6/14,35,每次减少一个中间状态,编译原理,2020/6/14,36,最后的正规表达式,r1*r2(r4|r3r1*r2)*,编译原理,2020/6/14,37,编译原理,2020/6/14,38,例：给出下图对应的正规表达式。,编译原理,2020/6/14,39,第1步，增加状态q和f，构造-NFA：,q0,q2,q1,1,2,2,1,2,0,q,f,编译原理,2020/6/14,40,q0,q2,2,0,q,f,2|11*2,11*,消除状态q1得到：,编译原理,2020/6/14,41,消除状态q2得到：,q0,0,q,f,(11*)|(2|11*2)2*),编译原理,2020/6/14,42,消除状态q0得到：,q,f,|0*(11*)|(2|11*2)2*),化简得：0*1*2*,编译原理,2020/6/14,43,给出偶数个0和偶数个1的字符串的正规表达式,编译原理,2020/6/14,44,消除状态1：,编译原理,2020/6/14,45,消除状态2：,编译原理,2020/6/14,46,消除状态3：,编译原理,2020/6/14,47,3.7词法分析器生成工具,编译原理,2020/6