川师编译原理课件.ppt

第四章词法分析 教学目的 让学生了解词法分析程序的概念的设计原则 单词的描述工具 掌握正规文法 正规式 有穷自动机的相关概念及相互转换 学会使用LEX语言构造简单词法分析器 教学重点 正规文法 正规式 有穷自动机课时分配 9学时 教学过程 4 1词法分析程序的设计 通常将词法分析程序 扫描器 设计为子程序形式 当语法分析程序需要单词时 则调用该子程序 扫描器的输出格式单词通常可分为5类 1 基本字 关键字 保留字 具有特殊含义的标识符 不作他用 有分隔语法的作用 2 标识符 表示各种名字 3 常量 整型 实型 布尔型 字符型 4 运算符 算术 逻辑 关系运算符 5 界符 包括 等 有时也把运算符称作界符 扫描器的设计把扫描器当作语法分析的一个过程 当语法分析需要一个单词时 便调用扫描器 扫描器从初态出发 当识别一个单词后便进入终态 同时送出二元组 扫描后输出二元组形式的单词序列二元组 单词种别 单词自身值或指针 例 若规定标识符 常数 基本字 运算符 界符的种别用整数编码分别为1 2 3 4 5 则对程序段 ifk 7thena b 则其经扫描器扫描后输出的单词符号及其二元组为 基本字if 3 if 标识符k 1 指向k的符号表入口的指针 等号 4 常数7 2 7 基本字then 3 then 标识符a 1 指向a的符号表入口的指针 赋值号 4 标识符b 1 指向b的符号表入口的指针 分号 5 4 2 单词的描述工具 3型文法 又称右线性文法或正规文法 RegularGrammars 其表达式形如 A aB或A a正规文法描述的语言是VT 上的正规集绝大部份程序设计语言的单词都能用正规文法来描述 4 2 1正规文法 4 2 2正规式和正规集 正规式也称正规表达式 是表示正规集的工具 递归定义如下 1 和 都是字母表 上的正规式 表示正规集为 和 2 a a是 上的正规式 表示正规集 a 3 假定e1 e2都是 上的正规式 对应正规集为L e1 L e2 则 e1 e1 e2 e1 e2 e1 也是正规式 分别表示的正规集为L e1 L e1 L e2 L e1 L e2 和L e1 4 仅有有限次运用上述步骤产生的表达式才是 上的正规式 仅由这些正规式产生的字集才是 上的正规集 例 设 0 1 则有 设r s t为正规式 则正规式服从如下的代数规则 r s s r 或 满足交换律 r s t r s t 或 满足结合律 r st rs t 连接 满足结合律 r s t rs rt 分配律 r r r 是连接的恒等元素 注意 rs srr st rs rt 正规式和正规文法之间的转换将 VT上的正规式r换成正规文法G VN VT P S 方法如下 1 令S r 2 对形如A xy的产生式 可分解成A xB B y 3 对形如A x y的产生式 可分解成为A xA A y 4 对形如A x y的产生式 可分解为A x A y反复利用上述规则 直至所有产生式中最多只含一个终结符 例 将R a a d 转换成相应的正规文法 解 步骤如下 1 S a a d 2 S aB B a d B B 3 S aB B aB B dB B 相应的正规文法如 3 式所示 即G S S aBB aB dB 将正规文法G VN VT P S 换成 VT上的正规式r的转换规则将产生式A xBB y合写为A xy 将产生式A xAA y合写为A x y 将产生式A xA y合写为A x y反复利用上述规则 直至只剩下一个由开始符定义的产生式 且该产生式右部不含一个非终结符 例 将正规文法G S S dAS eBA aAA bB bBB c换成正规式 解 步骤如下 1 由A aA A b 将A转换成a b 由B bB B c 将B转换成b c 2 由S dA S eB 将S可转换成 da b eb c 故所求正规式为R da b eb c 4 3有穷自动机 有穷自动机 FiniteAutomata 可准确的识别正规集 分类 1 确定的有穷自动机 DeterministicFiniteAutomata 简称DFA 2 不确定的有穷自动机 NondeterministicFiniteAutomata 简称NFA 4 3 1确定的有穷自动机 DFA DFAM K f S Z 其中 1 K是一有穷状态集 2 是一有穷字母表 称输入符号字母表 3 f是转换函数 是在K K上的映射 如f ki a kj 4 S是唯一的一个初态 5 Z K 是一终态集 终态也称结束态或可接受态 DFA的状态图表示假设DFAM有m个状态 n个输入字符 则 1 状态图有m个结点 每个结点最多有n条弧射出 2 有唯一的一个初态结点 前面冠以 或 标记 3 有若干终态结点 用双圆圈或 标记 DFA的矩阵表示1 行表示状态 2 列表示输入字符则 3 矩阵元素表示相应状态行和输入字符列下的新状态 即第k行a列为f k a 的值 4 用 标记行或第一行表示初态 5 终态行右端标以1 非终态行右端标以0 例 图示DFA可识别正则集L ab c 如串abbc可被认别 上图也可表示为矩阵形式 为方便讨论 对DFA中转换函数定义进行扩充 f是转换函数 是在K K上的映射 有 1 f k1 k1 2 f k1 a f f k1 a 其中 k1 K a 接受 识别 设DFA K f S Z 如果f S P Z 则称符号串 可被该DFA接受 识别 例 试证串abbc可被图示DFA识别证 f S abbc f f S a bbc f f A b bc f f A b c f A c BB为终态 得证 重要结论 上的一个字符串集V 是正规集 当且仅当存在着一个 上的确定有穷自动机M 使得V L M DFA的确定性表现在状态转换函数是一个单值函数 即f k a 唯一确定一个后继状态 4 3 2不确定的有穷自动机 NFA NFAM K f S Z 其中 1 K是一有穷状态集 2 是一有穷字母表 称输入符号字母表 3 f是转换函数 是在K K的子集上的映射 4 S是初态集 5 Z K 是一终态集 终态也称结束态或可接受态 NFA DFA NFA和DFA的比较 因为f是转换函数 是在K K的子集上的映射 有 1 f k a f k1 f k2 f kn 其中 ki K a 且f k a k1 k2 kn 设NFA K f S Z 如果z0 f S 且z0 Z 则称符号串 可被该NFA接受 识别 有穷自动机M所接受的所有符号串集称为此自动机可接受的语言L M 例 试证串abc可被图示NFA识别证 f S abc f A bc f A c f C c B又因为B 终态集 B 得证 重要结论 对于每个NFAM 必存在一个DFAM1 使得L M L M1 对于任何两个有穷自动机M1和M2 若L M1 L M2 则称有穷自动机M1和M2等价 4 3 3 FA到DFA的转换 闭包 closure I 表示状态集I中任何状态A经任意条 弧而能到达的状态集 状态集I的a弧转换 表示为 move I a J是所有那些从I中任何状态A经一条a弧而到达的状态全体令Ia closure J 例 取I S 1 则 closure I S 1 2 J move I 0 1 I0 closure J 1 2 用造表法将NFA确定化过程如下 0 表的第0行和第0列作标识行列 1 将 closure I 作为表中第1行第1列 2 假定 a1 a2 an 设第i行第一列已确定状态集为I 则置该行第i列为Iai 如Iai未曾在任何行第一列出现过 则将Iai加入后面空行第一列 3 反复重复第 2 步 直至无新状态出现为止 4 重新命名新状态 例 将图示NFA确定化 4 3 4DFA的化简 一个DFA是化简 最小化 了的 即是说 它没有多余状态且其状态中没有相互等价的 多余状态是指从自动机的开始状态出发 任何输入串也不可达的状态 在DFA中 两个状态s和t等价的条件是 1 一致性条件 状态s和t必须同时为可接受态和不可接受态 2 蔓延性条件 对于所有输入符号 状态s和t必须转换到等价的状态里 对DFA最小化的本质 消除多余状态 合并等价状态 DFA最小化过程 用分割法将不含多余状态的DFA分成一些不相交的子集 使得任何两个不同的子集中的状态都是可区别的 而相同子集中状态是等价的 分割时 首先将DFA状态分成终态子集和非终态子集 再根据输出弧所达到状态的性质逐步细分 例 对图示DFA最小化 解 P0 1 2 3 4 5 6 7 根据各子集输出弧0和1所达到状态是否为终态 划分为 P1 1 2 3 4 5 6 7 最小化后DFA为右下图 化简前的DFA 化简后的DFA 4 4正规式和NFA的等价性 对于 上的每个NFAM 可以构造一个相应的 上的正规式R 使得L R L M 对于 上的每个正规式R 可以构造一个相应的 上的NFAM 使得L R L M 一 为NFAM构造相应的正规式R首先引入两个新结点x y x经 弧到所有初态 所有终态经 弧到y 再用如下消解规则消去除x y外的所有结点 最后x y间弧上的标记串就是所求正规式 例 给出与图示NFAM等价的正规式R解 R 0 1 00 11 0 1 二 由正规式R构造相应的NFAN其过程与上述过程相反 用如下构造规则构造NFA 对R 构造 R a构造 aR st构造 N s N t 其中s t分别为正规式 X Y X Y X Y R s t构造 N s N t R s 构造 N s X Y X Y 例 为R a b abb构造NFAN 使L R L N 解 a b X Y 4 5NFA和正规文法的转换 对于 上的每个NFAM 可以构造一个相应的 上的正规文法G 使得L G L M 对于 上的每个正规文法G 可以构造一个相应的 上的NFAM 使得L M L G 一 构造正规文法G等价的NFAM过程如下 1 为G中每个非终结符生成M一个状态 开始符为初态 2 增加一新状态Z 做为NFAM的终态 3 对形如A aB或A B的产生式 构造M的转换函数f A a B或f A B 4 对形如A a的产生式 构造M的转换函数f A a Z 例 构造与下面文法G等价的NFAM G S S aS bS aBB bCC b解 用1 2 3对应S B C 加上终态4 按转换规则得NFAM如下 二 构造NFAM等价的正规文法G过程与上述过程相反 1 对转换函数f A a B或f A B 改成形如A aB或A B的产生式 2 对能识别终态Z 增加一个