北大编译原理讲义Chapter3.ppt

第三章 词法分析 3. 1 词法分析程序的设计：词法分析器的功能，输出，把它组织成单独程序 3 . 2 词法分析器的手工构造：用DFA 能识别单词，构造DFA并用程序实现它 3 . 3 有限自动机：有限自动机的等价性， 一个FA m ,? min( DFA m’) L(m)=L(m’) 3 . 4 正规表达式：单词能用正规表达式描述，能用DFA识别 3 . 5 正规文法与有限自动机的等价性 3 . 6词法分析程序自动构造工具LEX简介 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 编写词法分析程序 2. DFA的转移函数 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标识的弧。 算法3,2 从一个NFA构造一个DFA t?d 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; ? 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 3.3.2 确定的有限自动机的化简 一. 何谓确定的有限自动机的化简 所谓一个DFA m=(?, Q, q0, F, ?)的化简是指寻找一个状态数比较少的DFA m’,使 L(m)=L(m’)。而且可以证明， 存在一个最 少状态的DFA m’, 使L(m)=L(m’)。 二.等价状态的定义 设p,q ?Q ，若对任何w? ?* , ?(p,w) ?F 当且仅当 ?(q,w) ?F ，则称p和q是等价状态。否则，称p和q是可区别的。 q1 q2 q3 q4 q1 q2 q3 q6 q4 q5 q7 b a a a a a a a a a a a b b b ,b b b b b b b 1.等价状态定义了状态集合上的等价关系。因此，状态集合能被划分成等价类； 2 .两个状态p和q等价应满足如下条件： （a）一致性条件， p和q必须同时或为接受 状态或为非接受状态； （b）蔓延性条件，对于?a ?? ， ?（p,a)=r, ?（q,a)=s, r和s必须等价; 相反, r和s不等价, p和q不等价。 判定两个状态p和q不等价，只要找到一个w??*， 使?（p,w)?F 且?（q,w) ? F，或者相反。 W称为判别序列。 三. 方法： 构造一张表，对每一个状态对（qi,qj）（ij）有一表项，每当发现一对状态不等价时，就放一个x到相应表项中。 1 . 根据一致性条件，在每一个对应于终结状态和非终结状态的表项中放上一个x。 2 .根据蔓延性性条件，对每一个状态对（p,q），若?a??，?（p,a）=r， ?（q,a）=s，r和