词法分析与有限状态自动机.ppt

第三章词法分析与有限状态自动机词法分析程序的主要功能是识别单词,这将涉及3型文法、正则表达式和有限状态自动机。本章将讨论这三者间的关系。(Finite-stateAutomate machineFA): ⑴一根输入带:输入带可以理解成由一系列带块组成,每个带块上只含有一个输入符号(终结符号),其全体构成集合VT,特殊符号“”表示输入符号串的结束,VT。 ⑵一个输入头:初始时,输入头指向第一个带块(即指向输入带最左端的带块),输入头每次将输入头下方带块上的输入符号读入,然后输入头向右移动一个带块。Date2基本概念⑶一个有限状态控制器:有限状态控制器所能处于的状态的全体组成状态集合Q,Q中有若干特殊状态:一个初始状态q0和若干最终状态qf。开始时有限状态控制器处于初始状态,以后有限状态控制器所处状态由状态转换函数决定。Date3基本概念例1令VT={0,1,2,3} Q={S,A,B}2030S是初态用‘-’表示A是终态用‘+’表示有向弧表示转换Date4FA的工作过程初始时,FA处于初态,输入头指向第一个输入符,随着带上符号的读入,FA从一个状态转向另一个状态。若遇到如下情况,FA结束工作:输入头指向‘’、FA处于终态。称输入串被FA接受。(如2030)输入头指向‘’、FA不在终态。称输入串不被FA接受。(如203)FA无法转换。称输入串不被FA接受。(如1031)Date5FA的形式描述定义1:有限状态自动机M是一个五元组: M=(VT,Q,,q0,Qf),其中: VT:有限非空终结符集合 Q:有限非空状态集合:从Q×VT到Q的幂集2Q上的状态转换函数 q0:初始状态,q0Q Qf:最终状态集,QfQ|Qf|≥1Date6FA的形式描述对q,q1Q aVT(q,a)={q1}的含义为:当前状态为q,若输入头所指符号为a,则转向下一状态q1,输入头右移。∵是Q×VT 2Q上的一个单射 一般地(q,a)={q1,q2,……qn}qiQi=1,2,…n 因此称FAM为不确定的FA,记为NFA。若映射是Q×VT Q,即对任何qQ,aiVT,(q,ai)至多只有一个元素q’,称FAM是确定性的FA,记为DFA。Date7FA的形式描述对FA的拓展Q0Q|Q0|≥1即初态可以是一个集合:从Q×VT*到2Q上的单值映射,即输入符可以是一个串,包括称M为一个传递图或转换系统或NFA。例1:M1=(VT,Q,,q0,F)VT={a,b}, Q={q0,q1,q2} F={q2}:(q0,a)=q1 (q0,b)=q2(q1,a)=q1(q1,b)=q1 (q2,a)=q2 (q2,b)=q1M1是一个DFA。:qQ若q,q’Q,aVT,且q’(q,a),初态用‘-’标记、终态用‘+’标记qqq’aDate9状态转换图例2:例1的DFAM1可表示为:—+q0q2q1abbaa,bDate10