第3章词法案例.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 3、确定化为DFA M’ * * 4、写出实现其功能的程序 PROGRAM LEX(input,output) BEGIN TOKEN:=’’; getchar; CASE char OF ‘0’..’9’:[while char IN[‘0’..’9’]DO BEGIN TOKEN:=TOKEN+char; getchar END; retract; IF VAL(token,value) THEN return(4,value)]; ‘A’..’Z’:[while char IN[‘A’..’Z’,’0’..’9’]DO BEGIN TOKEN:=TOKEN+char; getchar END; retract; Return(5,token)]; ‘*’:[getchar; IF char=’*’ THEN Return(7,-) ELSE [retract;Return(6,-)] ELSE:ERROR; END{of case}; END; * * 本章小结 词法分析概况 状态转换图 确定型有穷状态自动机 非确定型有穷状态自动机 正则表达式 词法分析程序的实现 词法分析器的自动生成 * * 基本要求 了解词法分析程序的功能和实质。 明确DFA与NFA的区别，掌握把NFA变为DFA的方法； 熟练掌握把正则文法变为状态转换图以及写出有穷状态自动机的方法。 掌握词法分析程序的基本实现方法。 * * 习题课 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 举例 例：正则表达式(A|B){A|B|0|1}的转换系统的构造过程如下： S Z (A|B){A|B|0|1} S Z (A|B) {A|B|0|1} S Z A B ? ? A|B|0|1 S Z A B ? ? 1 0 A B * * 概念1. 假设I是NFA M’的状态集的一个子集，我们定义ε-CLOSURE(I)为（I的ε-闭包）。 （1）若S∈I，则S∈ε-CLOSURE(I) （2）若S∈I ，则从s出发经过任意条ε弧而达到的状态s’，有s’∈ε-CLOSURE(I) 例1. 五、正规式和有限自动机的等价性 若I={1, 3}，则ε-CLOSURE(I) ={1, 3, 2, 8} * * 概念2. 假定I是M’的状态子集，a是Σ中的字符，定义Ia= ε-CLOSURE(J),其中J是I中任意状态出发（跳过前面任意多条ε弧），经过一条a弧而能达到的状态结的全体。 例2．同例1 DFA， Ia={5,6,2} 利用概念1和概念2，便可把NFA确定化。 五、正规式和有限自动机的等价性 * * 五、正规式和有限自动机的等价性 令 ，构造一张如下的表，此表第0列为状态子集I，第1至m列分别为状态子集 ，设第一行第0列为ε-CLOSURE(X),，其中X为NFA M’的初态，求出第一个的 ，如果某个Iai(i=1,…,m)未曾在第0列中列出，则把Iai补入状态子集集合I中，即列于第0列新的一行。 重复上述各步，直至所有行的Iai(i=1,…,m)均在第0列I中出现过为止。这种循环必将在有限步内中止。（因为S是有限状态集，所以S中状态的组合数也是有限的） * * 显然，这张表可以看成一个状态转换表，也就是说可把I中每个子集看成一个状态，而状态转换表唯一地刻划了一个DFA M，其初态为该表的第1行第0列，含有原NFA M’终态的子集为新的终态。（证毕） 推论：一个子集是正规的，当且仅当它可由一个DFA（或NFA）所识别。 五、正规式和有限自动机的等价性 * * 例：设计一个DFA M，它识别二进制偶数（不以0开头的无符号数） 解： 1． 写出正规式 1（1|0）* 0 2． 画出NFA M’ 细化为： 3. 确定化为DFA M 五、正规式和有限自动机的等价性 * * 五、正规式和有限自动机的等价性 或： * * 举例 正则表达式{a}|{(a|b)a}的相应转换系统与状态转换图的构造过程。 A B {