1 / 67
文档名称:

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

格式:ppt   大小:335KB   页数:67页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

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

上传人:xiang1982071 2020/8/4 文件大小:335 KB

下载得到文件列表

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

文档介绍

文档介绍:*华东师大计算机科学技术系*: ⑴一根输入带:输入带可以理解成由一系列带块组成,每个带块上只含有一个输入符号(终结符号),其全体构成集合VT,特殊符号“”表示输入符号串的结束,VT。 ⑵一个输入头:初始时,输入头指向第一个带块(即指向输入带最左端的带块),输入头每次将输入头下方带块上的输入符号读入,然后输入头向右移动一个带块。*华东师大计算机科学技术系*基本概念⑶一个有限状态控制器:有限状态控制器所能处于的状态的全体组成状态集合Q,Q中有若干特殊状态:一个初始状态q0和若干最终状态qf。开始时有限状态控制器处于初始状态,以后有限状态控制器所处状态由状态转换函数决定。*华东师大计算机科学技术系*基本概念例1令VT={0,1,2,3} Q={S,A,B}2030S是初态用‘-’表示A是终态用‘+’表示有向弧表示转换*华东师大计算机科学技术系*FA的工作过程初始时,FA处于初态,输入头指向第一个输入符,随着带上符号的读入,FA从一个状态转向另一个状态。若遇到如下情况,FA结束工作:输入头指向‘’、FA处于终态。称输入串被FA接受。(如2030)输入头指向‘’、FA不在终态。称输入串不被FA接受。(如203)FA无法转换。称输入串不被FA接受。(如1031)*华东师大计算机科学技术系*FA的形式描述定义1:有限状态自动机M是一个五元组: M=(VT,Q,,q0,Qf),其中: VT:有限非空终结符集合 Q:有限非空状态集合:从Q×VT到Q的幂集2Q上的状态转换函数 q0:初始状态,q0Q Qf:最终状态集,QfQ|Qf|≥1*华东师大计算机科学技术系*FA的形式描述对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。*华东师大计算机科学技术系*FA的形式描述对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’a*华东师大计算机科学技术系*状态转换图例2:例1的DFAM1可表示为:—+q0q2q1abbaa,b*华东师大计算机科学技术系*状态转换表状态转换表(矩阵)表的列对应输入符号及特殊符号‘’,行和M的状态q相对应。状态转换表的qi行aj列中填以(qi,aj)中的状态。表的第一行和M的初始状态q0相对应;‘’这一列和最终状态qf行的元素标以A,以表示该状态是最终状态。