编译原理张晶版第三章词法分析讲义.ppt

中国科大 第三章 词法分析 第三章 词法分析 第一节 正规文法和有限自动机 一、正规文法、正规集与正规式 一、正规文法、正规集与正规式 一、正规文法、正规集与正规式 一、正规文法、正规集与正规式 假设正规文法G是右线性的，每个产生式的右部只含一个终结符，从文法G的产生式获得相应正规式方程式的规则如下： （1）若有A→a，则有A=a；若有A→ε，则A= ε； （2）若有A→aA，则有A=a*A； （3）若有A→aB且B≠A，则有A=aB； （4）若有A→a1|a2|…|an|aA，则有 A=a*(a1|a2|…|an)； 二、有限自动机（Finite automation FA) 2、有限自动机模型 二、有限自动机（Finite automation -FA) 二、有限自动机（Finite automation FA) 二、有限自动机（Finite automation FA) 二、有限自动机（Finite automation FA) 例： DFA M=({0,1,2,3},{a,b},f,0,{3})--f:f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2-- f(2,a)=1 f(2,b)=3 f(3,a)=3 f(3,b)=3 二、有限自动机（Finite automation FA) (2)算法 由NFA M=（S,∑,f,S0,Z ）构造一个等价的DFA M‘=（ Q,∑,δ,I0,F） 1.取I0=S0， 2.若状态集Q中有状态Ii={S0，S1……Sj}，SK∈S，0≤K≤j； 而且M中有f（{S0，S1,…..SJ},a) =f(s0,a) ∪f(s1,a) ∪….. ∪f(sj,a)= ∪f(sk,a) =(s0,s1,….st)=It, 若It不在Q中，则将It加入Q (2)、算法（续） 3.重复步骤2，直到Q中无新状态加入为止。 4.取终态F={I|I∈Q，且I∩Z Φ} 注：1）上述过程可在有限步内完成，因为M机状态的幂集是有限的； 2）上述过程也可用表格法来描述，其中列是字符集∑中的字符；行是Q中的各状态，开始仅包含I0状态，随着算法的执行，Q的状态逐渐增多直至不再增加为止；表格元素就是δ映射函数。 二、有限自动机（Finite automation FA) 注：3）NFA确定化的实质是以原有状态集的覆盖片（COVER）作为DFA的一个状态。将原状态间的转换改为覆盖片间的转换，从而将不确定问题确定化。 4）通常，经确定化后，状态数增加，而且可能出现一些等价状态，这时需要化简。 二、有限自动机（Finite automation FA) 例：设NFA M=（{q0,q1},{0,1},f,{q0},{q1}) 映射为 将其确定化 M‘的状态：I0={q0},则Q中就有了I0状态。 由Q中的状态I0 ={q0},查看M机，有f({q0},0)={q0}= I0 f({q0},1)={q1}= I1 此时，Q={I0， I1} 由Q中的状态I1={q1},查看M机。 有：f({q1},0)= {q0, q1}= I2, f({q1},1)={q0}= I0 此时，Q={I0, I1, I2} 由Q中的状态I2={q0, q1}，查看M机， 有： f({q0, q1},0)= {q0, q1}= I2, f({q0, q1},1)= {q0, q1}= I2， 此时,Q={I0，I1，I2} F={I1， I2} 二、有限自动机（Finite automation FA) (4) 化简(最小化)算法（续） 3.重复步骤2，直到所含的子集数不再增加为止。 4.对每个子集任取一状态为代表，若该子集包含原有的初态，则相应代表状态就是最小化后的M的初态；同样，若该子集包含原有的终态，则相应代表状态就是最小化后M的终态。 二、有限自动机（Finite automation FA) 注：1）当一个自动机没有任何多余的状态，并且它的状态中没有两个是互相等价的时候，我们说这个有限自动机是化简了的。 2）可以通过消除多余状态，合并等价状态而转化成一个最小化的、与之等价的有限自动机。 例：设有一DFA的状态转换图如下，试化简之 解： 1.把M的状态集分为两组：终态集、非终态集 —∏0={{0,1,2},{3,4,5,6}} 2.1考察非终态集: f({0,1,2},a)={1,3},不属于∏0的任何一个子集,所以{0,1,2}要分开. —得到： ∏1‘={{1}}，{0,2},{3,4,5,6}} 再