6.第三章词法分析.ppt

* NFA确定化：练习1 设有NFA M=({x,y},{a,b},δ,x,{y}), 其中δ定义如下: δ(x,a)={x,y} δ(x,b)={y} δ(y,a)=φ δ(y,b)={x,y} 试构造相应的 DFA M’。 I Ia Ib {x} 0 {X,y} 1 {y} 2 {x,y} 1 {x,y} 1 {x,y} 1 {y} 2 {x,y} 1 a x b y a b b NFA a,b a 0 2 1 b b DFA * 给出接受在字母表{0,1}上所有以00结束的串的DFA: NFA确定化：练习2 1 0 2 0 1 0 1 0 1 DFA I I0 I1 {1} 0 {1,3} 1 {1} 0 {1,3} 1 {1,3,4}2 {1} 0 {1,3,4}2 {1,3,4}2 {1} 0 确定化 1 4 3 0 0 0 1 NFA Ch3.词法分析 Ch3.词法分析 第3章 词法分析 词法分析(Lexical Analysis) 词法的表示 词法分析器的设计与实现 * 回顾: 词法分析 任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词符号。 逻辑上紧密相连的一组字符，这些字符具有集体含义。 单词：标识符，保留字，常数，算符，界符 词法分析阶段的工作所依循的是语言的词法规则。描述词法规则的有效工具是正规式和有限自动机。 * 有限自动机(FA) 自动机是一种能进行运算并能实现自我控制的装置。一台储存有程序的传统计算机，在有合适电源的条件下不仅具有进行运算的能力，而且具有自我控制的能力，所以，计算机是一部自动机。 所有实际的计算装置均以某种方式受限于它所能储存的信息量，因此是有限的。 自动机是描述符号串处理的强有力的工具，因而自动机成为研究词法分析器的重要基础。有限自动机(FA)分为确定有限自动机(DFA) 和不确定有限自动机(NFA) 。 本节介绍有限自动机的基本概念，以及有限自动机与正规式、正规文法之间的等价关系。 * 3.3.2 确定有限自动机(DFA) 一个确定有限自动机(DFA) M是一个五元式 M= (S, Σ, δ, s0, F) (1) S 是一个有限集，它的每个元素称为一个状态。 (2) ? 是一个有穷字母表，它的每个元素称为一个输入字符。 (3) δ是一个从 S × ? 至 S 的单值部分映射。 δ(s, a)=s’ 意味着：当现行状态为s, 输入字符为a时，将转换到下一个状态s’。我们称s’为s的后继状态。后继状态是唯一确定的, 故称确定有限自动机。 (4) s0 ? S，是唯一的初态。 (5) F ? S，是一个终态集(可空)。 * Ch3.词法分析 * 参见P47~48. 例1 设有DFA： M=({0,1,2,3},{a,b}, δ,0,{3}) 其中 δ 为: δ(0,a)=1 δ(0,b)=2 δ(1,a)=3 δ(1,b)=2 δ(2,a)=1 δ(2,b)=3 δ(3,a)=3 δ(3,b)=3 注意: 后继状态不一定是按顺序的下一个，只要是状态集合的一个状态即可。 DFA：例1 * 显然， DFA可以用一个矩阵表示 该矩阵的行表示状态 列表示输入字符，矩阵元素表示δ(s,a)的值 该矩阵称为状态转换矩阵或状态转换表 如例1 的 DFA M=({0,1,2,3},{a,b}, δ,0,{3}) 所对应的状态转换矩阵如 P48.表3.2 DFA表示为 --- 状态转换矩阵 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3 * DFA也可以表示成一张确定的状态转换图。 假定DFA M含有m个状态n个输入字符，那末这张图： 含有m个状态结点 每个结点顶多有n条箭弧射出和别的结点相连接 每条箭弧用?上的一个不同字符作标记 整张图含有唯一的初态和若干个(可以是0个)终态结点。 某个结点可以既是初态同时又是终态。 DFA表示为 --- 状态转换图 * 例1的DFA M=({0,1,2,3},{a,b}, δ,0,{3}) δ 所对应的状态转换图如 P48.图3.5 DFA表示为状态转换图：例 a,b a 0 1 2 3