第3章--词法分析

编译原理 第三章 词法分析 制作人 李明新 共 41 页第 1 页 20 3 27 第三章第三章 词法分析词法分析 知识结构 知识结构 功能功能 词法分析器的要求词法分析器的要求 单词符号分类单词符号分类 词法分析词法分析 单词内部形式单词内部形式 器的设计器的设计 设计方发设计方发 词法分析器的设计词法分析器的设计 状态图状态图 词法分析器组成词法分析器组成 正规表达式正规表达式 单词描述工具单词描述工具 正规集正规集 词法分析器词法分析器 正规文法正规文法 确定有限自动机 确定有限自动机 DFADFA 单词识别工具单词识别工具 非确定有限自动机 非确定有限自动机 NFANFA DFADFA 的最小化的最小化 正规式与正规式与 FAFA 的等价转换的等价转换 等价转换等价转换 正规文法与正规文法与 FAFA 的等价转换的等价转换 第一节第一节 对词法分析器的要求对词法分析器的要求 一 词法分析器的功能一 词法分析器的功能 输入源程序 输出单词符号 二元式表示 输入源程序 输出单词符号 二元式表示 输入输入 输出输出 二 单词符号的分类二 单词符号的分类 词法分析器源程序 字符流 二元式 单词流 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 2 页 20 3 27 关键字 关键字 是由程序语言定义的具有固定意义的标识符 是由程序语言定义的具有固定意义的标识符 标识符 标识符 用来表示各种名字 如变量等 用来表示各种名字 如变量等 常数 常数 常数的类型有整型 实型等 常数的类型有整型 实型等 运算符 运算符 算术运算符 关系运算符 逻辑运算符 算术运算符 关系运算符 逻辑运算符 界限符 界限符 逗号 分号等 逗号 分号等 三 单词符号内部的表示形式三 单词符号内部的表示形式 内部的单词符号内部的单词符号 TOKENTOKEN 字 二元式 字 二元式 TOKENTOKEN 字占用机器字的字占用机器字的 长度 依据信息量的多少而定 长度 依据信息量的多少而定 1 1 TOKENTOKEN 字结构字结构 CLASSCLASS 用整数表示 用整数表示 VALUEVALUE 表示单词符号的属性 符号表指针 表示单词符号的属性 符号表指针 2 2 TOKENTOKEN 的作用的作用 CLASSCLASS 用于语法分析器对源程序结构的分析 用于语法分析器对源程序结构的分析 VALUEVALUE 用于语义分析器对源程序具体操作的分析 用于语义分析器对源程序具体操作的分析 3 3 单词种别码划分原则 单词种别码划分原则 CLASSCLASS 关键字 运算符 界限符 编译程序定义的符号 关键字 运算符 界限符 编译程序定义的符号 使用一字一种编码 使用一字一种编码 VALUEVALUE 值省略 值省略 VALUEVALUE 标识符 常数 用户定义的符号 标识符 常数 用户定义的符号 存放符号表 存放符号表 常数表的指针 标识符 常数每一类为一种编常数表的指针 标识符 常数每一类为一种编 码 码 例 例 BEGINBEGIN A A B B ENDEND CLASS 单词种别码 VALUE 单词符号得属性 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 3 页 20 3 27 词法分析结果 词法分析结果 符号表符号表 BEGINBEGIN A A K1K1 K1K1 B B K3K3 K3K3 ENDEND 四 词法分析器的结构四 词法分析器的结构 1 1 一遍扫描 交互式结构 一遍扫描 交互式结构 2 2 多遍扫描 独立式结构 多遍扫描 独立式结构 第二节第二节 词法分析器的设计词法分析器的设计 一 设计步骤一 设计步骤 1 1 确定词法分析器的接口关系 确定词法分析器的接口关系 2 2 确定单词分类和 确定单词分类和 TOKENTOKEN 字的结构 字的结构 3 3 对每一类单词构造状态转换图 对每一类单词构造状态转换图 4 4 根据状态转换图设计算法 根据状态转换图设计算法 二 功能描述二 功能描述 1 1 组织源程序输入 组织源程序输入 2 2 按词法规则拼读单词符号 并转换成二元式 按词法规则拼读单词符号 并转换成二元式 3 3 删除注解行 空格和无用符号 删除注解行 空格和无用符号 4 4 检查词法错误 检查词法错误 三 设计方法三 设计方法 1 1 输入 输入 读取原文件读取原文件 原文件存储方式 原文件存储方式 名字 属性 A B 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 4 页 20 3 27 一种方式将原文件一次读入内存 另一种方式利用缓冲区技一种方式将原文件一次读入内存 另一种方式利用缓冲区技 术将原文件分批读入内存 术将原文件分批读入内存 缓冲区的设置 缓冲区的设置 输入 扫描 缓冲区 存放输入的原文件 双缓冲区 输入 扫描 缓冲区 存放输入的原文件 双缓冲区 起点指针起点指针 扫描指针扫描指针 2 2 预处理 预处理 功能描述 功能描述 删除无用符号 出错信息的列表打印 删除无用符号 出错信息的列表打印 单词符号的识别 单词符号的识别 语句格式语句格式 标识符不能被无效字符隔开 标识符不能被无效字符隔开 标识符与关键字 关键字与关键字之间用空格符隔开 标识符与关键字 关键字与关键字之间用空格符隔开 标识符的个数不能超过限定的个数 标识符的个数不能超过限定的个数 单词符号的格式单词符号的格式 标识符 关键字的首字符必须是字母 标识符 关键字的首字符必须是字母 常数的首字符必须是数字 常数的首字符必须是数字 3 3 识别算法 识别算法 P39 P39 标识符的识别 常数的识别 算符的识别 界符的识别 标识符的识别 常数的识别 算符的识别 界符的识别 四 状态转换图四 状态转换图 1 1 状态转换图的表示形式 状态转换图的表示形式 是一张有向图是一张有向图 结点代表状态 用结点代表状态 用 表示 表示 结点间用箭弧线 结点间用箭弧线 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 5 页 20 3 27 连接 连接 箭弧线上的符号 表示射出结点到达射入结点可能 箭弧线上的符号 表示射出结点到达射入结点可能 识别的输入符号 终态结点代表分析结束 识别的输入符号 终态结点代表分析结束 初态初态 a a b b c c d d 初始状态初始状态 表示识别符号串的开始 表示识别符号串的开始 双圈双圈 终态 表示识别符号串的结束 终态 表示识别符号串的结束 表示多读入一个字符 表示多读入一个字符 例例 1 1 标识符的状态转换图 标识符的状态转换图 状态转换矩阵状态转换矩阵 字母字母 其它其它 字母 数字字母 数字 例例 2 2 标识符 标识符 AB1 AB1 的识别的识别 A A B B 1 1 其它其它 例例 4 4 无符号数状态转换图 无符号数状态转换图 数字数字 其它其它 状态转换矩阵状态转换矩阵 状状 态态 字字 母母 数数 字字 其其 它它 0 0 1 1 1 1 1 1 1 1 2 2 2 2 状态状态数字数字其它其它 0 01 1 1 11 12 2 31 1 2 3 2 1 01 2 0111 2 1 01 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 6 页 20 3 27 数字数字 2 2 识别过程 识别过程 从初态开始 逐步读入字符 转到下一个状态 或出错 从初态开始 逐步读入字符 转到下一个状态 或出错 直至终态 或不能到达终态出错 直至终态 或不能到达终态出错 例例 3 3 字符串 字符串 AB 12 AB 12 的识别的识别 A A B B 识别出单词识别出单词 AB AB 多读入一个字符多读入一个字符 由另一张状态转换图 由另一张状态转换图 识别单词符号识别单词符号 继续识别剩余字符继续识别剩余字符 12 12 数字数字 1 1 2 2 其它其它 上述识别过程把上述识别过程把 ABAB 1212 字符串分解为三个单词符号字符串分解为三个单词符号 AB AB 12 12 3 3 状态转换图的实现 状态转换图的实现 状态转换图非常容易用程序实现 每一个状态对应一段程序 状态转换图非常容易用程序实现 每一个状态对应一段程序 不含回路的分叉状态结点的程序设计不含回路的分叉状态结点的程序设计 字母字母 数字数字 其它符号其它符号 2 2 011 0 2 3 1 0112 L I J K 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 7 页 20 3 27 利用多分支语句利用多分支语句 CASECASE 或选择语句或选择语句 IF THEN ELSE IF THEN ELSE 含回路状态结点的程序设计含回路状态结点的程序设计 其它其它 数字 字母数字 字母 利用循环语句利用循环语句 WHILE DOWHILE DO 词法分析程序的组成词法分析程序的组成 状态转换图是一种特殊的流程 它可直观清晰地描述单词符状态转换图是一种特殊的流程 它可直观清晰地描述单词符 号的识别过程 只要把每一个结点加入语义动作 就构成了词法号的识别过程 只要把每一个结点加入语义动作 就构成了词法 分析程序 分析程序 4 4 词法分析程序的组成 八个模块 词法分析程序的组成 八个模块 主控模块 初始化模块 判定源程序文件是否存在模块 从主控模块 初始化模块 判定源程序文件是否存在模块 从 源程序文件中读一个字模快 拼读一个单词模块 查关键字模块 源程序文件中读一个字模快 拼读一个单词模块 查关键字模块 输出单词模块 错误处理模块 输出单词模块 错误处理模块 第三节第三节 正规式 正规集 正规文法正规式 正规集 正规文法 一 正规式的定义一 正规式的定义 中的符号为正规式的基本符号 单个符号或由符号与运算中的符号为正规式的基本符号 单个符号或由符号与运算 符组成的表达式称正规式 符组成的表达式称正规式 运算符优先级 运算符优先级 重复重复 用用 表示 表示 连接连接 用用 表示或省略 表示或省略 选择选择 用用 表示 表示 IJ 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 8 页 20 3 27 例 例 a a abab a a b b a a b b c c 都是正规式 都是正规式 二 正规集二 正规集 由正规表达式所表示的字符串的集合称为正规集 如正规式由正规表达式所表示的字符串的集合称为正规集 如正规式 用用 V V 表示 正规集表示 正规集 L L V V 表示 表示 三 正规文法三 正规文法 正规文法是上下文无关文法的一种特殊情况 所有产生式的正规文法是上下文无关文法的一种特殊情况 所有产生式的 右部至多含有一个非终结符号 左线性文法 右线性文法都属于右部至多含有一个非终结符号 左线性文法 右线性文法都属于 正规文法 正规文法 左线性文法 左线性文法 A A B B A A 右线性文法 右线性文法 A A B B A A 其中 其中 A A B B V VN N V V T T T 四 正规式与正规集的递归定义四 正规式与正规集的递归定义 1 1 正规式与正规集的递归定义 正规式与正规集的递归定义 P46P46 和和 都是都是 上的正规式 正规集为上的正规式 正规集为 和和 任何任何 a a a a 是是 上的正规式 正规集为上的正规式 正规集为 a a 假定假定 U U 和和 V V 是是 上的正规式 正规集为上的正规式 正规集为 L U L U L V L V U VU V 是正规式 正规集为是正规式 正规集为 L U L V L U L V UVUV 是正规式 正规集为是正规式 正规集为 L U L V L U L V 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 9 页 20 3 27 U U 是正规式 正规集为是正规式 正规集为 L U L U 例例 1 1 令 令 a a b b 则 则 正规式正规式 a a b b 的正规集是的正规集是 a a b b 正规式 正规式 a a b b a a b b 的正规集是 的正规集是 aa aa ab ab ba ba bb bb 正规式正规式 a a 的正规集是的正规集是 a a aa aa aaa aaa 正规式 正规式 a a b b 的正规集是的正规集是 a a b b aa aa ab ab ba ba bb bb aaa aaa a a b b a a b b 即所有 即所有 a a 和和 b b 的符号串的符号串 集合 集合 a a b b aa aa bb bb a a b b 的正规集是所有含有两的正规集是所有含有两 个相继个相继 a a 或两个相继或两个相继 b b 的字符串集合 的字符串集合 例例 2 2 a a b b c zc z 0 0 1 9 1 9 正规式 正规式 a a b zb z a a b z 0 1 9b z 0 1 9 代表标识符 代表标识符 2 2 正规式与正规集的等价性 正规式与正规集的等价性 若两个正规式代表的正规集相同 则认为正规式等价 若两个正规式代表的正规集相同 则认为正规式等价 U VU V 表示 表示 L L U U L L V V 例例 3 3 U 10U 10 0 0 L U 1 0 L U 1 0 V 10V 10 L V 1 0 L V 1 0 则则 1010 0 0 10 10 例例 4 4 b ab b ab ba ba b b abab a a b b a b a b a a b b a b a b a a b b 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 10 页 20 3 27 3 3 正规式的代数定律 正规式的代数定律 1 1 U U V VV V U U 交换律交换律 2 2 U U V V W W U U V V W W 结合律结合律 3 3 U U VWVW UVUV W W 结合律结合律 4 4 U U V V W W UV UV UWUW 分配律分配律 5 5 U U U U U U 6 6 U U U U 7 7 U U U U 8 8 U U U U U UUU UU 例例 1 1 选择规则 选择规则 U U V V 则描述的正规集 则描述的正规集 L UL U V L U L V V L U L V 令令 U a V bU a V b 则则 L UL U V V L U L V L a L b L U L V L a L b a b a a b a b b 例例 2 2 连接规则 连接规则 UVUV 则描述的正规集 则描述的正规集 L UV L U L V L UV L U L V 令令 U aU a b b V cV c 则则 L UV L UV L U L V L aL U L V L a b b L c L c a a b c ac bc b c ac bc 例例 3 3 重复规则 重复规则 U U 则描述的正规集 则描述的正规集 L UL U L U L U U U U U1 1 U U2 2 U Un n U U a a abab L UL U L U L U L a L a ab ab L a L ab L a L ab 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 11 页 20 3 27 a ab a ab a ab a ab 0 0 a ab a ab 1 1 a ab a ab 2 2 a ab a ab a a ab a ab a ab ab a a abab aaaa aabaab abaaba abababab 五 正规式与正规文法的转换五 正规式与正规文法的转换 正规式与正规文法都有相同的表达能力 用以描述语言 单正规式与正规文法都有相同的表达能力 用以描述语言 单 词符号 的结构 使得所描述的语言是等价的 即词符号 的结构 使得所描述的语言是等价的 即 L L V V L L G G 1 1 正规式与正规文法的特点 正规式与正规文法的特点 正规式描述的语言结构清晰 简洁 而正规文法描述的语言正规式描述的语言结构清晰 简洁 而正规文法描述的语言 于识别 于识别 2 2 正规定义式 正规定义式 d d1 1 r r1 1 d d2 2 r r2 2 其中其中 d di i 为定义式的名字 为定义式的名字 r ri i 是是 d d1 1 d d2 2 d di 1 i 1 构成 构成 的正规式 的正规式 r ri i 中不含有中不含有 d di i d di 1 i 1 3 3 正规式与正规文法的转换算法 正规式与正规文法的转换算法 例 高级语言标识符的正规式例 高级语言标识符的正规式 字母 字母字母 字母 数字 数字 根据正规定义式规则 给正规式分量 正规式定义名称根据正规定义式规则 给正规式分量 正规式定义名称 字母字母 A A B B C C 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 12 页 20 3 27 数字数字 0 0 1 1 2 2 idid 字母 字母字母 字母 数字 数字 对定义式的子表达式定义名称对定义式的子表达式定义名称 ridrid 字母 字母 数字 数字 对定义式的子表达式展开对定义式的子表达式展开 字母 字母 数字 数字 字母 字母 数字 数字 字母 字母 数字 数字 字母 字母 数字 数字 字母 字母字母 字母 数字 数字 数字 字母数字 字母 数字 数字 把展开式代入定义式把展开式代入定义式 ridrid 字母 字母字母 字母 数字 数字 数字 字母数字 字母 数字 数字 把把 rdirdi 字母 字母 数字 数字 代入定义式代入定义式 idid ridrid 将得到正 将得到正 规文法 规文法 idid 字母字母 ridrid ridrid 字母字母 ridrid 数字数字 ridrid 其中其中 id id ridrid V VN N 字母 数字字母 数字 V VT T 六 正规文法与正规式的转换六 正规文法与正规式的转换 建立正规文法的联立方程组 求描述同一语言的正规式 建立正规文法的联立方程组 求描述同一语言的正规式 1 1 右线性文法到正规式 使得 右线性文法到正规式 使得 L L G G L L V V 产生式产生式 X X rXrX t t 其中其中 r r t t V VT T X X V VN N 论断论断 1 1 方程方程 X rXX rX t t 有形如 有形如 X rX r t t 的解 的解 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 13 页 20 3 27 例 文法例 文法 G G S S aSaS bAbA b b A A aSaS 立联立方程组立联立方程组 S S aSaS bAbA b b A A aSaS 式 代入式 代入 式式 S S aSaS baSbaS b b S S a a abab S S b b 由论断得方程解由论断得方程解 S S a a abab b b a a abab b b 对于同一方程式采用不同的结合方式 可以得到不同形式的对于同一方程式采用不同的结合方式 可以得到不同形式的 正规式 但是所描述的语言 正规集 是等价的 正规式 但是所描述的语言 正规集 是等价的 S S aSaS baSbaS b b aSaS baSbaS b b a a baSbaS b b a a baSbaS a a b b a a baba a a b b 所以所以 a a baba a a b b a a abab b b 2 2 左线性文法与正规式的转换算法 左线性文法与正规式的转换算法 产生式产生式 X X XrXr t t 其中其中 r r t t V VT T X X V VN N 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 14 页 20 3 27 论断论断 2 2 方程方程 X XrX Xr t t 有形如 有形如 X trX tr 的解 的解 例 文法例 文法 G G idid idid 字母字母 idid 数字数字 字母字母 其中其中 id id V VN N 字母 数字 字母 数字 V VT T 建立方程建立方程 idid idid 字母字母 idid 数字数字 字母字母 idid 字母 字母 数字 数字 字母字母 字母 字母字母 字母 数字 数字 3 3 正规文法与正规式的转换规则 正规文法与正规式的转换规则 产生式产生式 A A xBxB B B y y 对应的正规式对应的正规式 A xyA xy 产生式产生式 A A xAxA y y 对应的正规式对应的正规式 A xA x y y 产生式产生式 A A x x A A y y 对应的正规式对应的正规式 A xA x y y 例 文法例 文法 G G S S aAaA S S a a A A aAaA A A dAdA A A a a A A d d 根据规则根据规则 先有正规式先有正规式 S S aAaA a a A A aAaA dAdA a a d d 再将再将 A A 的正规式变换为的正规式变换为 A A a a d d A A a a d d 根据规则根据规则 将将 A A 的正规式变换为的正规式变换为 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 15 页 20 3 27 A A a a d d a a d d 再将再将 A A 式的结果代入式的结果代入 S S 的正规式的正规式 S S a a a a d d a a d d a a 再利用正规式的代数性质得到的正规表达式为再利用正规式的代数性质得到的正规表达式为 S S a a a a d d a a d d 因为 因为 a a d d a a d d a a d d 所以所以 S S a a a a d d a a a a a a d d 又因为 又因为 a a d d a a d d 所以所以 S S a a a a d d 第四节第四节 有限自动机 有限自动机 FAFA 有限自动机是具有离散输入和输出系统的一种数学模型 它有限自动机是具有离散输入和输出系统的一种数学模型 它 能准确地识别正规文法所定义的语言和正规式表示的正规集 引能准确地识别正规文法所定义的语言和正规式表示的正规集 引 入有限自动机这个理论 正是为词法分析程序的自动构造寻找特入有限自动机这个理论 正是为词法分析程序的自动构造寻找特 殊的方法 殊的方法 有限自动机的分类 有限自动机的分类 确定有限自动机 确定有限自动机 DFADFA 非确定有限自动机 非确定有限自动机 NFANFA 一 有限自动机的表示形式一 有限自动机的表示形式 状态图状态图 一个有限自动机可以用一个状态图 状态转换图 表示 即一个有限自动机可以用一个状态图 状态转换图 表示 即 含有含有 m m 个状态 个状态 n n 个输入符号 若个输入符号 若 f f k ki i a a k kj j 则从状态结 则从状态结 点点 k ki i到状态结点到状态结点 k kj j画标记为画标记为 a a 的弧 弧上标记的符号表示当前的弧 弧上标记的符号表示当前 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 16 页 20 3 27 识别的符号 识别的符号 状态表状态表 一个有限自动机可以用一个矩阵表示 该矩阵的第一列表示一个有限自动机可以用一个矩阵表示 该矩阵的第一列表示 状态 第一行表示输入字符 矩阵元素表示相应状态和输入字符状态 第一行表示输入字符 矩阵元素表示相应状态和输入字符 到达的下一状态 即到达的下一状态 即 k k 行行 a a 列为列为 f f k k a a 的值 的值 二 有限自动机的应用二 有限自动机的应用 翻译器翻译器 有限自动机 有限自动机 FAFA M M 作为转换器将输入串变换为输出串 作为转换器将输入串变换为输出串 M M S S R R S S0 0 F F 串产生器串产生器 有限自动机 有限自动机 FAFA M M 如果只有输出没有输入 如果只有输出没有输入 M M S S R R S S0 0 F F 串识别器串识别器 有限自动机 有限自动机 FAFA M M 如果只有输入没有输出 如果只有输入没有输出 M M S S S S0 0 F F 其中 其中 S S 状态集 状态集 输入字母表 输入字母表 R R 输出字母表 输出字母表 状态转状态转 换函数 换函数 S S0 0 初态 初态 F F 终态终态 三 有限自动机的工作原理三 有限自动机的工作原理 例 有限自动机识别无符号实常数的过程例 有限自动机识别无符号实常数的过程 d d d d d d d d 接受接受 0231 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 17 页 20 3 27 从初始状态出发所识别的字符串结束时能够到达终态结点 从初始状态出发所识别的字符串结束时能够到达终态结点 例 例 35 6735 67 为有效字符串 为有效字符串 阻塞 出错 阻塞 出错 从初始状态出发所识别的字符串结束时没能到达终态结点 从初始状态出发所识别的字符串结束时没能到达终态结点 例 例 356 356 为无效字符串 为无效字符串 四 确定有限自动机四 确定有限自动机 DFADFA 确定有限自动机 确定有限自动机 DFADFA M M 是一个五元组 是一个五元组 DFADFA M M S S s s0 0 F F 其中 其中 S S 是一个状态的有穷集是一个状态的有穷集 自动机所有状态的集合 自动机所有状态的集合 是有穷字符集合 它的每一个元素为一个输入字符 是有穷字符集合 它的每一个元素为一个输入字符 状态转换函数状态转换函数 S S a a S S 当现行状态为 当现行状态为 S S 输入 输入 字符为字符为 a a 时 将转换到下一个状态时 将转换到下一个状态 S S S S S S 单值映照函数 单值映照函数 S S0 0 S S 唯一的初始状态 唯一的初始状态 F F S S 终态集 终态集 若若 DFADFA M M 上有上有 m m 个状态 个状态 n n 个输入符号 个输入符号 中的元素有中的元素有 n n 个 个 则状态转换图上有则状态转换图上有 m m 个状态结 每个状态结最多有个状态结 每个状态结最多有 n n 个射出弧线个射出弧线 与后续的状态连接 与后续的状态连接 例例 DFADFA M M 状态矩阵表状态矩阵表 状态状态 a ab b 1 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 18 页 20 3 27 a a a a b b a a a a b b b b b b 该该 DFADFA M M 有有 4 4 个状态个状态 0 0 1 1 2 2 3 3 a a b b S S0 0 0 0 为初始状态 为初始状态 F F 3 3 为终态 为终态 为状态转换函数 为状态转换函数 0 0 a 1 a 1 0 0 b 2b 2 1 1 a 3 a 3 1 1 b 2b 2 2 2 a 1 a 1 2 2 b 3b 3 3 3 a 3 a 3 3 3 b 3b 3 1 1 DFADFA M M 所识别的符号串所识别的符号串 DFADFA M M 所识别的符号串所识别的符号串 对对 若存在一条从初始状态结点到终态结点的道路 若存在一条从初始状态结点到终态结点的道路 在这条路上所有弧线标记符号连接成的符号串恰好是在这条路上所有弧线标记符号连接成的符号串恰好是 则称 则称 为为 DFADFA M M 所识别 所识别 上例上例 DFADFA M M 所识别的符号串为所识别的符号串为 a a b b 上的含有二个相上的含有二个相 0 01 12 2 1 13 32 2 2 21 13 3 3 33 33 3 2 30 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 19 页 20 3 27 继继 a a 或二个相继或二个相继 b b 的符号串的集合 的符号串的集合 例例 1 1 aab aab 是是 DFADFA M M 所能识别的符号串 所能识别的符号串 a a a a b b 不能被不能被 DFADFA M M 识别的符号串识别的符号串 被识别的符号串不能从初始状态结点到终态结点 有下列两被识别的符号串不能从初始状态结点到终态结点 有下列两 种情况 种情况 不能到达终态 不能到达终态 已识别完 已识别完 例例 2 2 abab abab 不是该不是该 DFADFA M M 所能识别的符号串 上例 所能识别的符号串 上例 a a b b a a b b 其中 其中 2 2 状态不是终态结点 状态不是终态结点 某一状态射出弧线上标记与所识别的符号不同 多态性 某一状态射出弧线上标记与所识别的符号不同 多态性 例例 3 3 给定 给定 DFADFA M M a a b b a a b b abb abb 不能被不能被 DFADFA M M 识别 识别 2 2 DFADFA M M 所识别的语言所识别的语言 L L M M DFADFA M M 所能识别的符号串的集合 称所能识别的符号串的集合 称 DFADFA M M 所识别的语言 所识别的语言 L L M M S0S0 F F 例例 4 4 L L M M a a 开头的 开头的 a a b b 符号串符号串 DFADFA M M 1 1 2 2 a b a b 1 1 2 2 a a a a b b 013 01212 0123 12 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 20 页 20 3 27 3 3 空字符串 空字符串 的识别的识别 如果如果 DFADFA M M 的初始状态又是终态 则空串的初始状态又是终态 则空串 可被可被 DFADFA M M 识别 识别 例例 5 5 a a a a L L M M a a aa aa aaa aaa 例例 6 6 a a b b L L M M 任意的 任意的 a ba b 符号串符号串 五 非确定有限自动机五 非确定有限自动机 NFANFA M M 1 1 非确定有限自动机的特性 非确定有限自动机的特性 某一结点射出多条标记相同字符的弧线到达不同的结点 某一结点射出多条标记相同字符的弧线到达不同的结点 a a a a b b b b b b 0 a 0 0 a 0 0 a 1 0 a 1 两个状态两个状态 0 a 0 a 0 1 0 1 0 b 0 b 1 1 1 b 1 b 0 0 1 b 1 1 b 1 两个状态两个状态 1 b 1 b 0 1 0 1 某一结点射出标记有某一结点射出标记有 字符的弧线 字符的弧线 a a 2 2 非确定有限自动机 非确定有限自动机 NFANFA M M 定义定义 NFANFA M M S S S S0 0 F F S S 同上 同上 12 1 1 0 10 1 2 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 21 页 20 3 27 SiSj 同上 同上 是一个从是一个从 S S 到到 S S 的子集的映照 即的子集的映照 即 S S 2 2s s S S0 0 S S 为一个非空初态集 为一个非空初态集 F F S S 为一个终态集 可空 为一个终态集 可空 3 3 NFANFA M M 与与 DFADFA M M 的区别的区别 NFANFA M M 状态转换函数具有多值性 状态转换函数具有多值性 即即 S S a a S S1 1 S S2 2 S Sn NFANFA M M 可以存在有可以存在有 弧 弧 NFANFA M M 可以有多个初态 初态集 可以有多个初态 初态集 六 非确定有限自动机 六 非确定有限自动机 NFANFA M M 的识别 的识别 例例 M 1M 1 2 2 3 3 4 4 a a b b c c 1 1 4 4 1 1 映射函数值 映射函数值 1 1 4 4 2 2 3 3 4 4 1 1 a a 2 2 3 3 2 2 a a 2 2 3 3 a a 4 4 a a 1 1 b b 2 2 b b 4 4 3 3 b b 4 4 b b 1 1 c c 2 2 c c 3 3 c c 3 3 4 4 4 4 c c 2 2 构造对应的状态转换矩阵 构造对应的状态转换矩阵 字符 状态 a b c 1 4 2 3 2 2 4 3 3 4 4 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 22 页 20 3 27 3 3 构造非确定有限自动机 构造非确定有限自动机 NFANFA M M a a a a b b a a c c c c 4 4 非确定有限自动机 非确定有限自动机 NFANFA M M 识别的有效字符串识别的有效字符串 例例 1 1 字符串 字符串 aaab aaab a a a a b b 被识别的语言被识别的语言 L L M M a an nb b 例 字符串例 字符串 accc accc a a c c c c 被识别的语言被识别的语言 L L M M acacn n 1 2 3 4 1 2 4 1 3 4 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 23 页 20 3 27 所以所以 L M L M a an nb b acacn n 第五节第五节 非确定有限自动机 非确定有限自动机 NFANFA M M 的确定化 的确定化 一 非确定有限自动机 一 非确定有限自动机 NFANFA M M 确定化的目的 确定化的目的 1 1 取消识别 取消识别 到达的状态结点 到达的状态结点 2 2 合并识别相同字符到达的状态结点 合并识别相同字符到达的状态结点 二 二 CLOSURE I CLOSURE I 闭包的定义闭包的定义 假设假设 I I 是是 NFANFA M M 的状态集的一个子集 的状态集的一个子集 1 1 I I 的的 CLOSURE CLOSURE I I 定义 定义 若若 S S I I 则 则 S S CLOSURE CLOSURE I I 若若 S S I I 那么从 那么从 S S 出发经过任意条出发经过任意条 弧而能到达的任何状弧而能到达的任何状 态态 S S 都属于都属于 CLOSURE CLOSURE I I 2 2 I Ia a定义定义 假定假定 I I 是是 NFANFA M M 的状态集的一个子集 的状态集的一个子集 a a 是是 中的一个字符 中的一个字符 I Ia a的定义的定义 I Ia a CLOSURE CLOSURE J J 其中 其中 J J 是所有那些可从是所有那些可从 CLOSURE CLOSURE I I 中的某一状态出 中的某一状态出 发 经过一条发 经过一条 a a 弧线而到达的状态及由当前状态出发经空弧线连弧线而到达的状态及由当前状态出发经空弧线连 接到达状态的全体 接到达状态的全体 例例 a a a a a a 1 6 23 4 5 8 7 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 24 页 20 3 27 若若 I 1 I 1 CLOSURE CLOSURE I I 1 1 2 2 I Ia 5 3 4 6 2 8 7 5 3 4 6 2 8 7 若若 I 5 I 5 CLOSURE CLOSURE I I 5 5 6 6 2 2 I Ia 3 3 8 8 三 三 NFANFA M M 的确定化的确定化 构造一个与构造一个与 NFANFA M M 等价的 等价的 DFADFA M M 使得 使得 L L M M L L M M 1 1 状态转换矩阵表的形式 状态转换矩阵表的形式 若若 中有中有 k k 个元素个元素 a a 状态转换矩阵形式为 状态转换矩阵形式为 I Ia1 Ia2 Iak CLOSURE s0 第一列是第一列是 DFADFA M M 中的初始状态 为中的初始状态 为 NFANFA M M 中的初始状态集中的初始状态集 闭包 闭包 CLOSURE CLOSURE S S0 0 用用 NFANFA M M 的初始状态集 空闭包 中的每一个状态 分别的初始状态集 空闭包 中的每一个状态 分别 构造构造 IaIa1 1 Ia Ia2 2 Ia Iak k的后继状态子集 每一个状态子集均为的后继状态子集 每一个状态子集均为 DFADFA M M 的一个状态 的一个状态 对新出现的状态子集置于第一列 作为对新出现的状态子集置于第一列 作为 DFADFA M M 的新状态 的新状态 如同步骤如同步骤 直至没有出现新的状态子集为止 直至没有出现新的状态子集为止 2 2 由由 NFANFA M M 构造构造 DFADFA M M 的具体步骤 的具体步骤 求求 NFANFA M M 的的 CLOSURE CLOSURE I I 求求 I Ix x的的 CLOSURE CLOSURE J J X X 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 25 页 20 3 27 构造构造 DFADFA M M 的转换矩阵 的转换矩阵 确定确定 DFADFA M M 的初始状态和终态 的初始状态和终态 含有含有 NFANFA M M 初始状态的子集为初始状态的子集为 DFADFA M M 的初始状态结点 的初始状态结点 含有含有 NFANFA M M 终态的子集为终态的子集为 DFADFA M M 的终态结点 的终态结点 不包含不包含 NFANFA M M 初始状态 终态的子集为初始状态 终态的子集为 DFADFA M M 的内部状态的内部状态 结点 结点 构造确定化有限自动机构造确定化有限自动机 DFADFA M M 使得 使得 L L M M L L M M 四 带四 带 弧弧 NFANFA 的确定化的确定化 例例 1 1 a a a a b b a a c c c c 其中其中 a a b b c c S 1S 1 2 2 3 3 4 4 S S0 0 1 1 F 4 F 4 求求 NFANFA M M 的的 CLOSURE CLOSURE I I I I CLOSURE CLOSURE 1 1 1 1 4 4 令令 S S0 0 1 1 4 4 求求 I Ix x的的 CLOSURE CLOSURE J J X X X X a a b b c c I Ia a CLOSURE CLOSURE J J 1 2 3 4 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 26 页 20 3 27 CLOSURE CLOSURE 1 1 a a U 4 4 a a CLOSURE CLOSURE 2 2 3 3 U 2 2 3 3 令令 S S1 1 2 2 3 3 I Ib b CLOSURE CLOSURE J J CLOSURE CLOSURE 1 1 b b U 4 4 b b CLOSURE CLOSURE U I Ic c CLOSURE CLOSURE J J CLOSURE CLOSURE 1 1 c c U 4 4 c c CLOSURE CLOSURE U 同理可求出从同理可求出从 S S1 1出发识别某一字符能到达的后继结点 出发识别某一字符能到达的后继结点 S S1 1 2 2 3 3 CLOSURE CLOSURE S S1 1 a a 2 2 a a U 3 3 a a 2 2 令令 S S2 2 2 2 CLOSURE CLOSURE S S1 1 b b 2 2 b b U 3 3 b b 4 4 令令 S S3 3 4 4 CLOSURE CLOSURE S S1 1 c c 2 2 c c U 3 3 c c 3 3 4 4 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 27 页 20 3 27 令令 S S4 4 3 3 4 4 再分别求出再分别求出 S S2 2 x x S S3 3 x x S S4 4 x x 直到不出 直到不出 现新的子集为止 现新的子集为止 构造构造 DFADFA M M 的子集转换矩阵表的子集转换矩阵表 确定确定 DFADFA M M 的初始状态和终态的初始状态和终态 含有含有 NFANFA M M 初始状态的子集为初始状态的子集为 DFADFA M M 的初始状态结点 的初始状态结点 含有含有 NFANFA M M 终态的子集为终态的子集为 DFADFA M M 的终态结点 的终态结点 不包含不包含 NFANFA M M 初始状态 终态的子集为初始状态 终态的子集为 DFADFA M M 的内部点 的内部点 其中 其中 S S0 0 1 1 4 4 为为 DFADFA M M 的初始状态和终态结点 的初始状态和终态结点 S S1 1 2 2 3 3 S S2 2 2 2 为为 DFADFA M M 的内部结点 的内部结点 S S3 3 4 4 S S4 4 3 3 4 4 为为 DFADFA M M 的终态结点 的终态结点 将子集矩阵表变换成状态矩阵表 将子集矩阵表变换成状态矩阵表 字符 状态 a b c S0 S1 S1 S2 S3 S4 S2 S2 S3 S3 S4 S4 I Ia Ib Ic 1 4 2 3 2 3 2 4 3 4 2 2 4 4 3 4 3 4 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 28 页 20 3 27 构造确定化有限自动机构造确定化有限自动机 DFADFA M M a a a a a a b b b b c c c c 该该 DFADFA M M 识别的语言是识别的语言是 L M L M a am mb b m m 1 1 ac acn n n n 1 1 例例 2 2 a a a a a a a a b b b b b b b b 改错改错 p p 4949 图图 3 63 6 状态状态 1 1 到状态到状态 4 4 的弧线方向有误的弧线方向有误 用子集法构造转换矩阵见下表用子集法构造转换矩阵见下表 I II Ia aI Ib b x x 5 5 1 1 5 5 3 3 1 1 5 5 4 4 1 1 5 5 3 3 1 1 2 2 6 6 y y 5 5 4 4 1 1 6 6 y y 5 5 4 4 1 1 2 2 6 6 y y 5 5 3 3 1 1 6 6 y y 5 5 3 3 1 1 5 5 3 3 1 1 2 2 6 6 y y 5 5 3 3 1 1 5 5 3 3 1 1 2 2 6 6 y y 5 5 3 3 1 1 6 6 y y 5 5 3 3 1 1 6 6 y y 5 5 3 3 1 1 2 2 6 6 y y 5 5 4 4 1 1 5 5 4 4 1 1 5 5 4 4 1 1 2 2 6 6 y y 5 5 4 4 1 1 6 6 Y Y 5 5 4 4 1 1 2 2 6 6 y y 5 5 4 4 1 1 2 2 6 6 y y 5 5 4 4 1 1 6 6 y y 对上表中的所有子集重新命名 形式成下表的转换矩阵对上表中的所有子集重新命名 形式成下表的转换矩阵 S0 S4 S3S1 S2 x56 4 21 3 Y 编译原理 第三章 词法分析 制作人 李明新 共 41 页第 29 页 20 3 27 S S a ab b 0 0 1