编译原理与技术 词法分析 (2).ppt

2020 3 1 编译原理与技术 讲义 1 编译原理与技术 词法分析 2 2020 3 1 编译原理与技术 讲义 2 有限自动机 有限自动机 finiteautomata fa 是种更一般化的状态转换图 分为nfa和dfa 词法分析器自动生成 正规式nfadfa词法程序 非确定有限自动机 确定的有限自动机 2020 3 1 编译原理与技术 讲义 3 非确定有限自动机 nfa nfamn是一个五元组mn s s0 f 其中 有限字母表 输入符号集 s 有限状态集s0 非空初态集合 s0 sf 终态集合 f s 状态转换函数 sx 2s 2020 3 1 编译原理与技术 讲义 4 确定的有限自动机 dfa dfamd是一个五元组md s s0 f 其中 s s0 f同nfa中的定义 而 定义如下 sx s 为一单值映射函数 2020 3 1 编译原理与技术 讲义 5 有限自动机的表示 1 状态转换图 开始状态 一般状态 终态 s s a t t a s s t t 2020 3 1 编译原理与技术 讲义 6 有限自动机的表示 2 状态转换矩阵 表 si a sj 2020 3 1 编译原理与技术 讲义 7 有限自动机的表示 e g 7nfamn s s0 f 其中 0 1 s s0 s1 s2 s3 s4 f s2 s4 s0 0 s0 s3 s0 1 s0 s1 s1 0 s1 1 s2 s2 0 s2 s2 1 s2 s3 0 s4 s3 1 s4 0 s4 s4 1 s4 2020 3 1 编译原理与技术 讲义 8 有限自动机的表示 e g 7中nfa的状态转换图如下 s0 s3 s1 0 1 0 0 0 1 1 1 0 1 s2 s4 2020 3 1 编译原理与技术 讲义 9 有限自动机的表示 e g 7中nfa的状态转换矩阵 表 如下 2020 3 1 编译原理与技术 讲义 10 有限自动机识别的语言 e g 8下面fa识别 接受 的串是什么 s0 s1 s2 0 1 fa识别 接受 串 如果存在一个从fa的初态到某个终态的 状态 转换路径 该路径上所有标记的字符依次连接为 fam所识别的语言l m l m m识别 2020 3 1 编译原理与技术 讲义 11 有限自动机识别的语言 e g 9下面dfam识别的语言l m 是什么 2020 3 1 编译原理与技术 讲义 12 有限自动机识别的语言 e g 9l m 含偶数个0和偶数个1的0 1串 s2 s1 s0 s3 偶数个 0 与偶数个 1 的0 1串 偶数个 0 与奇数个 1 的0 1串 奇数个 0 与偶数个 1 的0 1串 奇数个 0 与奇数个 1 的0 1串 2020 3 1 编译原理与技术 讲义 13 有限自动机识别的语言 e g 10下面dfam识别的语言l m 是什么 s2 s1 s0 0 1 0 1 0 1 2020 3 1 编译原理与技术 讲义 14 有限自动机识别的语言 e g 10l m 能被 3 整除的二进制数 串 s2 s1 s0 能被3整除 被3整除 余1 被3整除 余2 2020 3 1 编译原理与技术 讲义 15 有限自动机识别的语言 e g 10l m 能被 3 整除的二进制数 串 二进制串10010 即十进制18的识别过程 s2 s1 s0 0 1 0 1 0 输入串1 0 0 1 0 2020 3 1 编译原理与技术 讲义 16 比较dfa和nfa 1 2020 3 1 编译原理与技术 讲义 17 比较dfa和nfa 2 2020 3 1 编译原理与技术 讲义 18 比较dfa和nfa 3 e g 11识别正规式 0 1 01的dfa和nfa 2020 3 1 编译原理与技术 讲义 19 对于 上正规式r 存在一个nfam 使得l m l r 反之亦然 thopmson方法 r r r a 正规式与有限自动机 s0 s1 s0 s1 s0 a 只引入初态s0和终态s1 他们之间无状态转换 2020 3 1 编译原理与技术 讲义 20 正规式与有限自动机 r r1 r2 1 si fi sj fj r1对应的nfa si为初态 fi为终态 r2对应的nfa sj为初态 fj为终态 2020 3 1 编译原理与技术 讲义 21 正规式与有限自动机 r r1 r2 2 s0 si fi sj fj 引入新的初态s0和 s0 si和 s0 sj 2020 3 1 编译原理与技术 讲义 22 正规式与有限自动机 r r1 r2 3 s0 f0 si fi sj fj 引入新的终态f0和 fi f0和 fj f0 2020 3 1 编译原理与技术 讲义 23 正规式与有限自动机 r r1 r2 1 r1对应的nfa si为初态 fi为终态 r2对应的nfa sj为初态 fj为终态 2020 3 1 编译原理与技术 讲义 24 正规式与有限自动机 r r1 r2 2 s0 引入新的初态s0和 s0 si 2020 3 1 编译原理与技术 讲义 25 正规式与有限自动机 r r1 r2 3 s0 引入新的状态转换 fi sj 2020 3 1 编译原理与技术 讲义 26 正规式与有限自动机 r r1 r2 4 sj fj s0 引入新的终态f0和状态转换 fj f0 f0 2020 3 1 编译原理与技术 讲义 27 正规式与有限自动机 r r1 1 r1对应的nfa si为初态 fi为终态 2020 3 1 编译原理与技术 讲义 28 正规式与有限自动机 r r1 2 s0 引入新的初态s0和 s0 si 2020 3 1 编译原理与技术 讲义 29 正规式与有限自动机 r r1 3 si fi s0 引入新的终态f0和状态转换 fi f0 f0 2020 3 1 编译原理与技术 讲义 30 正规式与有限自动机 r r1 4 si fi s0 引入新的状态转换 fi si f0 2020 3 1 编译原理与技术 讲义 31 正规式与有限自动机 r r1 5 si fi s0 引入新的状态转换 s0 f0 f0 2020 3 1 编译原理与技术 讲义 32 正规式与有限自动机 r r1 r1对应的nfa 它也是 r1 对应的nfa 2020 3 1 编译原理与技术 讲义 33 e g 12构造 0 1 01的对应的fa 1 0 0 1 1 0 1 0 1 2020 3 1 编译原理与技术 讲义 34 e g 12构造 0 1 01的对应的fa 2 0 1 同0 1 0 1 0 1 2020 3 1 编译原理与技术 讲义 35 e g 12构造 0 1 01的对应的fa 3 0 1 0 0 1 0 2020 3 1 编译原理与技术 讲义 36 e g 12构造 0 1 01的对应的fa 4 0 1 01 2020 3 1 编译原理与技术 讲义 37 e g 12构造 0 1 01的对应的fa 5 r1 r2 r3 0 1 r4 r5 r7 r9 r6 0 r8 1 2020 3 1 编译原理与技术 讲义 38 thompson方法所构造的nfa的状态数和 转换较多 可以采用下面方法减少之 r r1 r2 r1 r2 r r1r2 r1 r2 r r1 r1 r r r1 2020 3 1 编译原理与技术 讲义 39 e g 13构造 0 1 01的对应的fa 简化版 0 1 01 1 0 1 0 1 2 0 1 1 3 0 1 4 0 0 1 2020 3 1 编译原理与技术 讲义 40 e g 13构造 0 1 01的对应的fa 简化版 1 4 0 0 1 1 5 0 0 1 2020 3 1 编译原理与技术 讲义 41 nfa的确定化 转换到dfa 子集构造法对nfa进行模拟 nfa的转换表中每个条目是状态子集 而在dfa中则为单一的状态 nfa到dfa的转换的一般想法是 让dfa中的每个状态代表nfa中的状态子集 dfa用它的状态去记住nfa在读入每个输入符号后能到达的所有状态的集合 即在dfa在读了符号a1a2 an后到达代表nfa状态子集t的状态 而这个子集t是从nfa开始状态沿着标记有a1a2 an的路径所能到达的所有状态的集合 2020 3 1 编译原理与技术 讲义 42 nfa的确定化 转换到dfa 子集构造法dfa的 状态 sd是nfa的非空状态子集 sd 2sdfa的初态sd0 包括原nfa初态s0及其经 转换能到达的所有状态 即sd0 s0 u s0 u closure s0 closure t 从状态集合t的每一个状态t出发 经过若干空转换 转换 所能到达的所有状态 2020 3 1 编译原理与技术 讲义 43 nfa的确定化 转换到dfa 子集构造法dfa状态转换函数 d sd1 asd2 sd2 t u s at s sd1 t u closure t s at s sd1 dfa的终态f 含有原nfa终态的sd 2020 3 1 编译原理与技术 讲义 44 初始时 dfa的状态集合dstates中只有初态sd0且未标记 while dstates中有未标记的状态t do 标记t for每个输入符号ado u closure s nfa状态转换函数 t a s t t ifu不在dstates中则将其加入dstates且未加标记 记下dfa状态转换函数 d t a u 2020 3 1 编译原理与技术 讲义 45 nfa的确定化 e g 14确定化以下nfam 2020 3 1 编译原理与技术 讲义 46 e g 14确定化以下nfam 续1 2020 3 1 编译原理与技术 讲义 47 e g 14确定化以下nfam 续2 2020 3 1 编译原理与技术 讲义 48 e g 14确定化以下nfam 续3 2020 3 1 编译原理与技术 讲义 49 e g 14确定化以下nfam 续4 2020 3 1 编译原理与技术 讲义 50 dfa的简化 极小化 dfam 极小化dfam 其中l m l m 且dfam 是和dfam等价 识别语言相同 的dfa中状态数最少的 状态s1和s2是等价的 如果s1 f1且s2 f2 f1 f2 f 状态t1和t2是可区分的 如果t1和t2不等价 2020 3 1 编译原理与技术 讲义 51 dfa的简化 极小化 状态极小化 将dfa的状态集合s划分成若干不相交状态子集 不同子集的状态间是可区别的 相同子集内的状态间等价 取各个状态子集中的某一个状态为该子集代表 消除该子集中其他状态 初始划分 终态集合与非终态集合划分过程 如果s1 s2 划分子集i a 有 s1 a 划分j s2 a 划分k 则划分i应进一步再划分成i1 i2 s1 i1 s2 i2 2020 3 1 编译原理与技术 讲义 52 dfa的简化 极小化 e g 15将下面的dfam极小化 1 2020 3 1 编译原理与技术 讲义 53 e g 15将下面的dfam极小化 2 初始划分i0 终态集合 3 4 5 6 和i1 非终态集合 0 1 2 考查i1 0 1 2 0 a1 1 a3 2 a1 i1需再划分成i2 0 2 和i3 1 此时划分为 i0 i2和i3即 3 4 5 6 0 2 和 1 考查i2 0 b2 2 b4 i2需再划分成i4 0 和i5 2 此时划分为 i0 i4 i5和i3即 3 4 5 6 0 2 和 1 考查i0 3 4 5 6 3 a3 4 a6 5 a6 6 a33 b5 4 b4 5 b4 6 b5 不需要划分i0 此时划分过程结束 2020 3 1 编译原理与技术 讲义 54 e g 15将下面的dfam极小化 3 最终划分 0 1 2 和 3 4 5 6 取状态3为代表 极小化的dfa如下 2020 3 1 编译原理与技术 讲义 55 词法分析器自动生成 lex lex源程序 lex lex yy cyylex lex yy cyylex c编译器 可执行文件 a out 可执行文件 a out 输入串 单词记号 2020 3 1 编译原理与技术 讲义 56 词法分析器自动生成 lex lex源程序组成定义段 规则段 用户程序段 2020 3 1 编译原理与技术 讲义 57 词法分析器自动生成 lex lex源程序组成 定义段 include includeintcount 0 任何形式的c声明 上述c声明 语句被拷贝到lex yy c文件中 2020 3 1 编译原理与技术 讲义 58 词法分析器自动生成 lex lex源程序组成定义段 正规定义digit 0 9 number digit 2020 3 1 编译原理与技术 讲义 59 词法分析器自动生成 lex lex源程序组成 规则段正规式 语义动作 number intn atoi yytext printf x n 语义动作 合法的c语句 语义动作 c语句 被拷贝到yylex 中当正规式匹配时其相应的语义动作即被执行 2020 3 1 编译原理与技术 讲义 60 词法分析器自动生成 lex lex源程序组成用户程序段 包含用户自定义的c函数 此段可空 如 main intyywrap yylex return0 return1 2020 3 1 编译原理与技术 讲义 61 include includeintcount 0 任何形式的c声明 digit 0 9 number digit number intn atoi yytext printf x n