编译原理chapter3

《编译原理chapter3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.4从正规式到词法分析器构造词法分析器的一般方法和步骤：<1>用正规式对模式进行描述；<2>为每个正规式构造一个NFA，它识别正规式所表示的正规集；<3>将构造出的NFA转换成等价的DFA，这一过程也被称为确定化；问题<4>：优化DFA，使其状态数最少，这一过程也被称为最小化；<5>从优化后的DFA构造词法分析器。我们是从DFA构造词法分析器，为何不直接从正规式构造DFA，而要先构造NFA，然后转换为DFA？原因：<1>机器构造需要规范的算法；<2>正规式→NFA：有规范的一对一的构造算法<3>DFA→分析器：有便于记号的识别的算法12.4.1从正规式到NFA<4>对于正规

2、式(p)，使用p本身的算法2.2Thompson算法NFA，不再构造新的NFA。■输入字母表∑上的正规式r输出接受L(r)的NFAN方法首先分解r，然后根据下述步骤构造NFA：<1>对ε，构造NFA如右。其中，s0为初εs0f态，f为终态，此NFA接受{ε}；a<2>对∑上的每一个字符a，构造NFA如右s0f<3>若N(p)和N(q)是正规式p和q的NFA，则εN(P)ε（a）对正规式p

3、q，构造NFA如右。其s0εεf中，s0为初态，f为终态，此NFA接受N(Q)L(p)（b∪）L(q对正规式)；pq，构造NFA如右。其中，s0为初态，f为终态，此NFA接受s0N(P)N(

4、Q)fL(p)L(q)；ε（c）对正规式p*，构造NFA如右。其εεs0N(P)f中，s0为初态，f为终态，此NFA接受L(p*)；ε22.4.1从正规式到NFA（续1）正规式NFA定义2.2令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定εεs0f义如下:1.ε是正规式，它表示集合L(ε)={ε}aa2.若a是Σ上的字符，则a是正规式s0f，它表示集合L(a)={a}3.若正规式r和s分别表示集合L(r)N(P)P

5、Q和L(s)，则s0f（a）r

6、s是正规式，表示集合N(Q)L(r)∪L(s)，（b）rs是正规式，表示集合L(r)L(s)，PQ（c）r*是正规式，表

7、示集合s0N(P)N(Q)f(L(r))*，ε（d）(r)是正规式，表示的集合*s0εN(P)εf仍然是L(r)。（加括弧改变优先级、P结合性）ε可用正规式描述的语言称为正规语言或正规集。■32.4.1从正规式到NFA（续2）εaεε23εεabb01εε678910b45εr11例2.11用Thompson算法构造正规式r9r10r=(a

8、b)*abb的NFAN(r)r7r8b<1>分解正规式<2>自下而上构造NFAr5r6b强调：r4*a<1>算法的构造与正规式一一(r3)对应<2>构造一个新的NFA最多增加r1

9、r2两个状态ab4c1c乙2.4.2从NFA到DFAcb甲

10、3<1>NFA识别记号的“并行”方法cb例2.12从甲地到乙地，可以乘小轿车也可以骑自行车2，具体路线如上。其中c表示乘车，b表示骑自行车。现在要求从甲地到乙地，只许乘车而不许骑自行车，该如何走？（即识别是否有从甲到乙标记为cc的路径）试探（串行方式）：甲c2无路可走，退回甲c1c3无路可走，退回甲c1c乙到达乙地，成功并行(假设有足够的小汽车，每次都是到达小汽车可能到达的全体)甲c{1,2}c{3,乙}到达乙地，成功由于并行的方法在每试探一步时，考虑了所有的下一状态转移，因此所走的每一步都是确定的。用NFA识别记号，并不采用串行的方法（算法不易构造，复杂度高且回溯），而是采

11、用并行的方法，核心思想是将不确定的下一状态确定化。5NFA上识别记号的确定化方法2.4.2从NFA到DFA（续1）εεas2s4s5确定化的两个步骤（回顾DFA定义）s1计算下一状态转移时：<1>消除ε状态转移：ε-闭包(T)as3<2>消除多于一个的下一状态转移：smove(S,a)smove(S,a)：从状态集S出发，标记为a的下一状态全体。与move(s,a)的唯一区别：用状态集取代状态ε-闭包(T)：从状态T出发，不经任何字符达到的状态全体。定义2.6状态集T的ε-闭包(T)是一个状态集，且满足：（1）T中所有状态属于ε-闭包(T)；（2）任何smove(ε-闭包(T

12、)，ε)属于ε-闭包(T)；（3）再无其他状态属于ε-闭包(T)。■根据定义，上图中ε-闭包({s2})应该包括：1.s2自身{s2}（1）2.s4{s2,s4}（2）3.s5{s2,s4,s5}（2）算法6算法2.3模拟NFA2.4.2从NFA到DFA（续2）输入NFAN，x（eof），s0，F输出若N接受x，回答“yes”，否则“no”方法用下边的过程对x进行识别。S是一个状态的集合S:=ε-闭包({s0});--所有可能初态的集合a:=nextchar;whilea≠eofloopS:=ε-闭包(