[编译原理第三章.ppt

3.1 词法分析程序的设计 3.1.1 词法分析程序的功能 源程序 单词序列 3.1.2 单词的词类和属性 （词类符号，单词的属性值） 3.1.3 词法分析程序作为一个独立子程序 (1) 语法分析程序的子程序； （2）组织成一遍扫描。 3?2 词法分析器的手工构造 为了构造词法分析器，要研究构词法，每种词类的结构模式以及识别它的数学模型——有限自动机。它的模拟程序可以作为词法分析器的控制程序。 3?2 ?1 确定的有限自动机（DFA） 3?2 ?2 构造识别单词的DFA 3?2 ?3 编写词法分析程序 三、DFA的三种表示 1. 像上面，用转换函数； 2. 转移矩阵； 3. 状态转换图。 1. ?_closure(S) 的定义和算法 从S中任一状态出发，仅沿?弧到达的状态集合。 T=S ? ( ? edge(t, ?)) 如下计算T： T:=S; REPEAT T ?:=T ; T:=T ? ? ( ? edge(t, ?)) (t?T ?) UNTIL T=T ? t?T 四、从NFA构造DFA的算法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2. DFA的转移函数 edge(t, a)是NFA中从状态t出发，仅沿a弧到达的状态集合。 DFAedge(d, a)= ?—closure( ? edge(t, a)) 其中， d是NFA的状态集， a ??。 从NFA构造DFA，对于NFA的所有输入,，用DFA模拟NFA的动作，令t1是NFA的初态，DFA的初态d1= ?—closure(t1) ，若dj= DFAedge(di, a),那么，从di到dj存在一条用a标识的弧。 t?d Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. States[1] :=ε-closure({t1}); p:=1; j:=1; WHILE j=p DO ? for each a∈Σ ? e:=DFAedge(states[j],a); IF e=states[i] for some i=p THEN trans[j,a]=i ELSE ? p:= p+1; states[p]:=e; trans[j,a]:=p; ? ; ? ; j:=j+1; ? 算法3.2 从一个NFA构造一个DFA Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 0 1 4 3 6 5 7 8 9 10 ? ? ? ? ? ? ? a b b b 2 ? a 3,8,6,1,2,4,7 0,1,2,4,7 2 5,6,1,2,4,7 3 2 5,9,6,1,2,4,7 4 2 3 2 5,10,6,1,2,4,7 5 2 3 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 一、何谓确定的有限自动机的化简 所谓一个DFA M=(?, Q, q0, F, ?)的化简是指寻找一个状态数比较少