编译原理chpt3词法及其自动构造剖析.ppt

过程PP: Construction of ∏new For each group G of ∏ do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to states in the same group of ∏;/*at worst, a state will be in a subgroup by itself*/ 2.replace G in ∏new by the set of all subgroups formed end DFA的最小化—例子 ∏0:{S,A,B} {C,D,E,F} ∏1:{S,A,B} {C,D,E,F} ∏2: C D B A E F S b a a a a a a b b b b b b a } { } {A S, B b B { { S } } D B A S a a a b b b b a a 图 跳过或识别C风格注释的有穷自动机 3.3 DFA的实现 可为状态赋予有意义的名字： start(1)、entering_comment(2)、in_comment(3)、exiting_comment(4)和finish(5) 方法之一： 这种实现方式是将DFA“硬连”进代码之中。 另一种实现方式是将DFA表示为数据结构并基于该数据结构实现DFA的行为。 方法之二---表驱动 Accept[ ] T[ ][ ] state = 1; ch = next input character; while not Accept[state] and not error(state) do newstate = T[state][ch]; if Advance[state][ch] then ch = next input char; state = newstate; end while; if Accept[state] then accept ; 这种方法被称作表驱动(table driven)。其优点是代码的长度缩短了，并通用。缺点是表格大，占用空间大。 能否往前走 3.4 词法分析程序的自动构造 基于有穷自动机和正规表达式的等价性可给出词法分析程序的自动构造方法 从Σ上的一个正规式R构造Σ上的一个NFA M，使得L(M)=L(R)，可采用“语法制导”的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下： 正规式R=〉NFA M (1) R=?,构造任一具有空终态集的NFA M (2) R= ? ，构造的NFA M=({k0}, ∑,f,k0.{k0}): f(k0,a)对于 所有a?∑都没定义。 (3)R=a,构造的NFA M=({k0,,k1},∑,f,k0.{k1}): f(k0,a) = k1 (4) R =R1 | R2, 将步骤(1)、(2)、(3) 分别应用到R1,R2 ，产生M1=(K1,∑,f1,k1,F1), M2=(K2,∑,f2,k2,F2),其中K1,K2不相交.构造的NFA M= (K1?K2?{k},∑,f,k,F) : k是新增加的状态符号，f包含f1和f2,且f(k,a)=f1(k1,a)?f2(k2,a). 若k1?F1且k2?F2则 F=F1 ? F2，否则F=F1 ? F2 ?{k} (5) R=R1.R2 将步骤(1)、(2)、(3)分别应用到R1,R2 产生M1==(K1,∑,f1,k1,F1), M2=(K2,∑,f2,k2,F2),其中K1,K2不相交.构造的NFA M= (K1?K2,∑,f,k1,F2) : f包含f1和f2,且f(k1, ?)=k2, f(k,a)=f1(k,a),当 k?F1时;