词法分析(6学时)调整版.ppt

第四章词法分析 有穷自动机FA 是一个识别装置 用于识别 所有句子 引入FA的目的 为词法分析程序的自动构造寻找特殊的方法和工具类型 确定的有穷自动机DFA不确定的有穷自动机NFA 返回 4 1有穷自动机 FA FiniteAutomata FA FiniteAutoMata 是一个识别装置 用于识别 所有句子 引入FA的目的 为词法分析程序的自动构造寻找特殊的方法和工具类型 确定的有穷自动机DFA不确定的有穷自动机NFANFA DFA 子集法 DFA的化简 最小化DFA 下一节 确定的有穷自动机 DFA 1 定义 一个DFA是一个五元组M K f S Z K 有穷的状态集 有穷的字母表 即输入字符的集合 f 转换函数K K上的映像S 初态 初态唯一 Z 终态集 终态不唯一 例 DFAM S U V Q a b f S Q f f S a Uf S b Vf U a Qf U b Vf V a Uf V b Qf Q a Qf Q b Q 确定的有穷自动机 DFA 2 DFA的 直观 表示 状态图 状态转换图 每个状态用结点表示若f Ki a Kj 则初态用 或 标出终态用双圈或 标出矩阵列标题 输出符号 VT 行标题 状态若f Ki a Kj 则Ki和a的交汇处是Kj初态用 标出或默认第一行 表格左端 终态用 1 标出 表格右端 非终态用 0 标出 表格右端 例 参见上例的DFA 分别用状态图和矩阵表示 确定的有穷自动机 DFA 3 DFA可以接受的句子 符号串 若t 且存在f S t P P 终态集 则t为该DFA可以接受的句子 即 从初态S到某终态结点P的道路上 所有弧上的标记符连接而成字符串t t为该DFA可以接受的句子 例 参见上例的DFA状态图 判断下列句子能否被接受 abbabaababbaaa DFAM能够接受的句子的全体记为L M 确定的有穷自动机 DFA 4 DFA的确定性 f K K是一个单值函数即对任何状态K 当输入字符a时 下一状态唯一 上例的有穷状态机就是DFA DFAM K f S Z 的行为模拟程序 K S c getchar while ceof K f K c c getchar if KinZ return yes else return no DFA的行为模拟程序 返回 示例 一个识别标识符的确定的有穷状态机 数字或其它 最小化DFA没有多余状态 死状态 没有两个状态是互相等价 DFA的化简 最小化DFA 1 多余状态 从开始状态出发 任何输入串也不能到达的状态处理 消除多余状态 2 两个状态s和t等价 满足一致性 同是终态或同是非终态蔓延性 从s出发读入某个a a 和从t出发读入某个a到达的状态等价 处理 合并等价状态 使用 分割法 DFA的化简 最小化DFA 举例 消除多余状态 解 步骤一 消除多余状态步骤二 使用分割法 合并等价状态 举例 求最小化DFA DFA的化简 最小化DFA 举例 求最小化DFA 返回 P70例2课后题 4 b 9 不确定的有穷自动机 NFA 1 定义 一个NFA是一个五元组M K f S Z K 有穷的状态集 有穷的字母表 即输入字符的集合 f 转换函数K K 上的映像 K 表示K的子集 S 初态集 初态不唯一 Z 终态集 例 NFAM 0 1 2 3 4 a b f 0 2 4 f f 0 a 0 3 f 0 b 0 1 f 1 b 2 f 2 a 2 f 2 b 2 f 3 a 4 f 4 a 4 f 4 b 4 2 NFA的 直观 表示 状态图 状态转换图 每个状态用结点表示若f Ki a Kj 则初态用 或 标出终态用双圈或 标出矩阵列标题 输出符号 VT 行标题 状态若f Ki a Kj 则Ki和a的交汇处是Kj初态用 标出或默认第一行 表格左端 终态用 1 标出 表格右端 非终态用 0 标出 表格右端 举例 参见上例的NFA 分别用状态图和矩阵表示 不确定的有穷自动机 NFA 3 NFA可以接受的句子 符号串 同DFA 若t 且存在f S t P P 终态集 则t为该NFA可以接受的句子 例 参见上例的NFA状态图 判断下列句子能否被接受 aaabaababbaababab NFAM 能够接受的句子的全体记为L M 对于每个NFAM 存在一个DFAM 使得L M L M 不确定的有穷自动机 NFA 可以被NFAM 能够接受的两种情况 M 的某结点既是初态 又是终态存在一条从初态到终态的 道路 4 NFA的不确定性 对于状态K 当输入字符a时 下一状态不一定唯一 5 NFA的确定化 对每个NFAM 一定存在一个DFAM 使得L M L M 即 对每个NFAM存在着与之等价的DFAM 注 与某一NFA等价的DFA不唯一 不确定的有穷自动机 NFA 返回 NFA DFA 子集法 一 基本运算 状态集合I的 闭包 表示为 closure I 状态集I中的任何状态S经任意条 弧而能到达的状态的集合 注 状态集I的任何状态S都属于 closure I 状态集合I的a弧转换 表示为move I a 定义为状态集合J 其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体 定义Ia closure J 举例 参见P58图4 4 求 closure 0 move 0 a move 0 b closure 1 move 2 a move 2 b move 0 1 2 4 7 a closure 1 3 move 0 1 2 4 7 b NFA DFA 子集法 二 转换的主要思想 DFA的一个状态可能对应NFA的一个或一组状态DFA同样记录在NFA上读入某个VT后可能到达的所有状态 三 子集法NFAN K f K0 Kt 构造DFAM S d S0 St 使得L M L N M的状态集S由K的一些子集组成M和N的输入字母表相同转换函数d是这样定义的 d S1 Sj a closure move S1 Sj a S0 closure K0 为M的开始状态St Si Sk Se 其中 Si Sk Se S且 Si Sk Se Kt NFA DFA 子集法 构造NFAN的状态K的子集的算法 假定所构造的子集族为C T1 T2 Ti 其中T1 T2 Ti为状态K的子集 1 开始 令 closure K0 为C中唯一成员 并且它是未被标记的 2 While C中存在尚未被标记的子集T do 标记T for 每个输入字母a do U closure move T a if U不在C中 then 将U作为未标记的子集加在C中 举例 参见P58图4 4构造NFA对应的子集 NFA DFA 子集法 初态 终态 DFAM 课后习题 2 3 4 a 返回 4 2词法分析程序的设计 词法分析 lexicalanalysis 功能 逐个读入源程序字符 输出 单词符号 供语法分析使用 主要任务 读源程序 产生单词符号其他任务 滤掉空格 跳过注释 换行符追踪换行标志 复制出错源程序宏展开 单词符号 一般可分为下列五种 基本字 关键字 begin end if while标识符 各种名称 如常量名 变量名 过程名常数 量 25 3 1415 TRUE ABC 等运算符 如 等界符 逗号 分号 括号等 词法分析程序与语法分析程序的接口方式 方式一 常用 二元式 单词种类 值 优点 1 整个编译结构简洁 清晰 条理化 2 可移植性好 词法分析程序与语法分析程序的接口方式 方式二 PL 0采用 4 3单词的描述工具 单词的描述工具和识别工具 正规文法 正则文法 3型文法 正规式 正则式 有穷自动机 NFA DFA 三者之间可以相互转换 下一节 正规文法 文法的每个产生式的形式都为 A aB或A a 右线性A Ba或A a 左线性其中A B VN a VT 例如 标识符的正规文法 若i表示任一字母 d表示任一数字 标识符 i i 字母数字 字母数字 i d i 字母数字 d 字母数字 无符号整数的正规文法 无符号整数 d d 无符号整数 运算符的正规文法 运算符 等号 等号 界符的正规文法 界符 返回 正规式 regularexpression 正规式 是描述单词符号串规则的工具设字母表 a z A Z 0 9 辅助字母表 表示 闭包 即任意有限次的自重复连接 表示 连接 有时可以省略 表示 或 优先顺序为 和 都是左结合的正规式为 e e1 e2 e1 e2 e 中的符号 其中e表示任一正规式 例1 令 0 1 上正规式和相应正规集的例子有 正规式正规集0 0 0 1 0 1 01 01 0 1 0 1 中间省略连接号 00 01 10 11 0 0 0 任意个0的串 0 1 0 1 00 01 所有由0和1组成的串 0 1 00 11 0 1 上所有含有两个相继的0或两个相继的1组成的串 正规式举例 两个正规式等价 若两个正规式e1和e2所表示的正规集相同 则说e1和e2等价 记作e1 e2例如 0 1 1 01 01 10 1 0 1 0 1 正规式的代数运算 设r s t为正规式 则有 r s s r 或 的交换律r s t r s t 或 的结合律 rs t r st 连接 的可结合律r s t rs rt s t r sr tr分配律 r rr r 是 连接 的恒等元素 程序中的单词符号都能用正规式表示 e 返回 转换 正规文法 正规式 等价转换的规则 不断用上述规则进行变换 直到最后只剩一个开始符号为止 正规文法 正规式举例 例 正规文法G S S aA 将正规式 正规文法 S aA aAA dAA aA d S aAS aA aAA dAA aA d S aA aA aA dAA a d S a A A a d AA a d S a A A a d a d S a a d a d S a a d 课后习题 8 正规式 正规文法 任何正规式r 定义S为开始符号S r 转换规则 不断用上述规则进行变换 直到每个产生式的右部只含一个VT为止 正规式 正规文法举例 例 正规式r 0 0 1 将正规式 正规文法 S 0 0 1 S 0AS 0 1 S 0AA 0 1 AA S 0AA 0A 1AA S 0AA 0AA 1AA 练习 R 01 10 0 1 将正规式 正规文法 返回 4 4正规式和有穷自动机的等价性 转换 对于 上的NFAM 可以构造一个 上的正规式R 使得L R L M 对于 上的正规式R 可以构造一个 上的NFAM 使得L M L R 在FAM的状态图上加两个状态结点x和y 从x结点出发 用 弧连接x结点到所有初态结点从M的所有终态结点用 弧连接到y结点此时 x为初态和y为终态 利用消结规则 逐步消去M 中的所有结点 直至只剩下x和y 最后x和y结点间的弧上的标记则为所求的正规式R FA 正规式 举例 求FA所对应的正规式R 解 FA 正规式 则 R a b aa bb a b 课后习题 9 将正规式分解成一系列子表达式 对于每个子表达式 用如下规则构造FA 正规式 FA 注意 由于分解的方法和顺序不同 构造的NFA可能不同 但最小化的DFA一定相同 举例 为R a b abb构造NFAN 使得L N L R P68例1课后习题 1 3 4 11 正规式 FA 4 5正规文法和有穷自动机的等价性 转换 输入字符集与正规文法的VT相同状态集与正规文法中的VN相同左线性正规文法的转换规则 增加一个初态结点 开始符号对应的结点作为终态 对形如A t的规则 引一条从初始状态到A的弧 标记为t 对形如A Bt的规则 引一条从B到A的弧 标记为t右线性正规文法的转换规则 增加一个终态结点 开始符号对应的结点作为初态 对形如A t的规则 引一条从A到终态结点的弧 标记为t 对形如A tB的规则 引一条从A到B的弧 标记为t注 t为VT或 正规文法 FA 举例 求与文法G S 等价的NFAMG S S aAS bBS A aBA bAB aSB bAB 正规文法 FA举例 课后习题 7 举例 求与文法G S 等价的DFA 并给出该文法的语言的正规式 G S S AaS A AaA SbA a 正规文法 FA举例 则 正规式为R aa ba a 课后习题 10 与f A a B对应的产生式为 A aB对终态结点Z 增加产生式 Z NFA的初态对应文法的开始符号NFA的输入字符集对应文法的VT FA 正规文法 G S