Chapt3_词法分析.ppt

第3章 词法分析 Never look down on yourself. 永远不要小看自己。 第3章 词法分析 （P28） 学习重点 3.1词法分析的功能（P28） 3.1词法分析的功能 3.2 程序语言的单词符号种类及词法分析输出（P29） 3.2 程序语言的单词符号种类及词法分析输出 3.2 程序语言的单词符号种类及词法分析输出 3.2 程序语言的单词符号种类及词法分析输出 3.3 正则文法及状态图(P30) 3.3 正则文法及状态图 3.3 正则文法及状态图 3.3 正则文法及状态图 3.3 正则文法及状态图 3.3 正则文法及状态图 3.4 词法分析程序的设计与实现（P32） TEST语言的词法规则 TEST语言的各类单词符号的正则文法 TEST语言的各条词法规则的状态图 TEST语言的词法规则的状态图 3.5 正则表达式(P37) 3.5 正则表达式 3.5 正则表达式 3.5 正则表达式 3.5 正则表达式 3.5 正则表达式 3.5 正则表达式 3.5 正则表达式 3.5 正则表达式 3.6 有穷自动机（P39） 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.6 有穷自动机 3.7 词法分析程序的自动生成器LEX(P52) 小 结 习 题(P60) 习 题 第一次作业 第二次作业(任选一题) 多余状态：一是从初始状态到该状态之间没有通路； 二是从该状态到终止状态之间没有通路。 例3-15 (P49) 判断如下的状态图中，哪些状态是多余状态。 0 1 2 3 4 5 b b a 0 2 3 4 b b 有多余状态的状态图 删除多余状态的状态图 多余状态是无用的，应该删除。删除多余状态的方法是直接将多余状态结点以及相关的弧线删除，即可得到等价的自动机。 a a b 设DFA M=(Q,∑,δ,q0,F)，最小化（或化简）DFA的算法(P49) : 1）先将自动机的状态划分成非结束状态集S1和结束状态集S2。 2）对各状态集按下面方法划分，直到所有状态集不再产生新的划分为止。设第m次划分将Q分成n个状态集，即Q= S1∪S2∪…∪Sn 。 对状态集合Si（i=1，2，…，n）中的各个状态逐一检查，设状态q1和q2是状态集合Si中的两个状态，对于输入符号a（a∈∑），有δ(q1,a)= S′、δ(q2,a)=S〞,若状态S ′和S〞属于同一状态集合，则将状态q1和q2放在同一状态集合中；否则，将状态q1和q2分为两个集合。 3）重复第2步，直到所有状态集合都不能划分。此时，每个状态集合中的状态都是等价的。 4）将每个状态集合中的等价状态合并成一个等价代表状态。将状态函数中的所有状态用相应的等价代表状态表示。从状态图上看，要将一个状态集合中的等价状态结点合并成一个结点。 5）删除多余状态。 例 将DFA（见右图）最小化。 解：将状态集分成非结束状态集S1={q0,q1,q2}和结束状态集S2={q3} 。 在S1中，由于状态q0无输入1，而状态q1和状态q2有输入1，所以将S1分割成S11={q0}和S12={q1,q2}。 又因为δ (q1,0)=q2∈S12，δ (q2,0)=q2∈S12，δ (q1,1)=q3∈S2，δ (q2,1)=q3∈S2，所以状态q1和状态q2等价。 将原状态集合分割成以下子集： {q0}，{q1,q2}，{q3} 例3-16(P50) 对如图所示的有穷自动机化简。 0 1 2 3 4 b b b a a a b a a b 待化简的有穷自动机 解：将状态集分成非结束状态集S1={0,1,2}和结束状态集S2 ={3，4} 。 对S1={0，1，2}的划分: ∵δ(0,a)=1,δ(1,a) =3,δ(2,a) =1, δ(0,b)=2,δ(1,b) =2,δ(2,b) =4 ∴将S1分成S4={0}，S5={1}, S6=