词法分析程序的设计原则,单词的描述技术,识别机制及词法

词法分析程序的设计原则,单词的描述技术,识别机制及词法内容摘要：

)(0|1)* 确定有限自动机和不确定有限自动机 DFA是 NFA的特例 .对每个 NFA N一定存在一个 DFA Ｍ ，使得 L(M)=L(N)。 对每个NFA N存在着与之等价的 DFA M。 有一种算法，将 NFA转换成接受同样语言的 子集法 . 与某一 NFA等价的 DFA不唯一 . NFA确定化算法 : 假设 NFA N=(K, ,f,K0,Kt)按如下办法构造一个 DFA M=(S, ,d,S0,St)， 使得L(M)=L(N)： 1. M的状态集 S由 K的一些子集 组成。 用 [S1 S2... Sj]表示 S的元素，其中 S1, S2,... Sj是 K的状态。 并且约定，状态 S1, S2,... Sj是按某种规则排列的，即对于子集 {S1, S2}={ S2, S1,}来说， S的状态就是 [S1 S2]； 2 M和 N的输入字母表是相同的，即是 ； 3 转换函数是这样定义的： d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = closure(move({S1, S2,... Sj},a)) 4 S0=closure(K0)为 M的开始状态； 5 St={[Si Sk... Se]，其中 [Si Sk... Se]S且 {Si , Sk,... Se}Kt} 定义对状态集合 I的几个有关运算： 1. 状态集合 I的 ε 闭包 ， 表示为 εclosure(I)， 定义为一状态集，是状态集 I中的任何状态 S经任意条 ε弧而能到达的状态的集合。 状态集合 I的任何状态 S都属于 εclosure(I)。 2. 状态集合 I的 a弧转换 ， 表示为 move(I,a)定义为状态集合 J，其中 J是所有那些可从 I中的某一状态经过一条 a弧而到达的状态的全体。 状态集合 I的有关运算的例子 I={1}, closure(I)={1,2}； I={5}, closure(I)={5,6,2}； move({1,2},a)={5,3,4} closure({5,3,4})={2,3,4,5,6,7,8}； 1 2 5 3 4 6 8 7 a a      a 构造 NFA N的 状态 K的子集 的算法： 假定所构造的子集族为 C， 即 C= (T1, T2,... TI),其中 T1, T2,... TI为状态 K的子集。 1 开始，令 closure(K0)为 C中唯一成员，并且它是未被标记的。 2 while （ C中存在尚未被标记的子集 T） do { 标记 T； for 每个输入字母 a do { U:= closure(move(T,a))； if U不在 C中 then 将 U作为未标记的子集加在 C中 } } NFA的确定化 例子 4 f 3 5 6 2 1 i     a a a a b b b b Ia Ib{i,1,2} {1,2 , 3} {1,2 , 4}{1,2 , 3} {1,2 , 3,5 , 6,f} {1,2 , 4}{1,2 , 4} {1,2 , 3} {1,2 , 4,5 , 6,f}{1,2 , 3,5 , 6,f} {1,2 , 3,5 , 6,f} {1,2 , 4,6 ,f}{1,2 , 4,5 , 6,f} {1,2 , 3,6 ,f} {1,2 , 4,5 , 6,f}{1,2 , 4,6 ,f} {1,2 , 3,6 ,f} {1,2 , 4,5 , 6,f}{1,2 , 3,6 ,f} {1,2 , 3,5 , 6,f} {1,2 , 4,6 ,f}S A BA C BB A DC C ED F DE F DF C E4 f 3 5 6 2 1 i     a a a a b b b b 等价的 DFA a C D B A E F S b a a a a a b b b b b a b 确定有穷自动机的化简 说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。 DFA的最小化就是寻求最小状态 DFA 最小状态 DFA的含义 :。