《编译原理课程总复习----贾棋讲述》由会员分享，可在线阅读，更多相关《编译原理课程总复习----贾棋讲述（155页珍藏版）》请在金锄头文库上搜索。
1、编译原理课程总复习 贾棋 jiaqi7166 前端：依赖于源语前端：依赖于源语 言，独立于目标机言，独立于目标机 器。器。 词法分析器词法分析器 语法分析器语法分析器 语义分析器语义分析器 源程序源程序 中间代码生成器中间代码生成器 代码优化器代码优化器 代码生成器代码生成器 目标程序目标程序 出错管理器出错管理器符号表管理器符号表管理器 前端前端 后端后端 后端：依赖于后端：依赖于 目标机器，独目标机器，独 立于源语言。立于源语言。 第二章第二章 词法分析器词法分析器 词法分析器 记号（token）流 源代码 词法分析器工作原理词法分析器工作原理： 源程序 字符流 顺序顺序 组合组合 词法
2、单元 词法 记号 模式模式 非形式 化描述 形式化 描述 正规式 字母 组合组合 串语言 集合集合 集合集合 字母表 名 字 词法记号的描述与识别词法记号的描述与识别 n n 正规式的例子正规式的例子 = = a a, , b b qqa a | | b b a a, , b b qq( (a a | | b b) () (a a | | b b ) ) aaaa, , abab, , baba, , bbbb qqaa aa | | ab ab | | ba ba | | bbbb aaaa, , abab, , baba, , bbbb qq a a * * 由字母由字母a a构成的所有串
3、集构成的所有串集 qq( (a a | | b b) ) * * 由由a a和和b b构成的所有串集构成的所有串集 n复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：01001101000010000010111001 n n 正规定义的例子正规定义的例子 Pascal语言的标识符集合 letter A | B | | Z | a | b | | z digit 0 | 1 | | 9 id letter(letter|digit)* n n 正规定义的例子正规定义的例子 PascalPascal无符号数集合，例无符号数集合，例
4、19461946, ,11.2811.28, ,63.6E863.6E8, ,1.99E1.99E 6 6 digitdigit 0 0 | 1 | | 9| 1 | | 9 digitsdigits digitdigit digitdigit * * optional_fractionoptional_fraction . .digitsdigits| | optional_exponentoptional_exponent (E ( + | (E ( + | | | ) digits ) | ) digits ) | numnumdigits optional_fraction optio
5、nal_exponentdigits optional_fraction optional_exponent 简化表示简化表示 numnum digitdigit+ + ( (. .digit digit + + )? (E(+|)? (E(+| )? digit)? digit + + )?)? 简化规则：简化规则： (1) r+=rr* (2) r?=r| (3) a-z=a|b|c|z (4) abc=a|b|c 源程序 字符流 顺序顺序 组合组合词法 单元 词法 记号 模式模式 非形式 化描述 形式化 描述 正规式 字母 组合组合 串语言 集合集合 集合集合 字母表 名 字 连接连接
6、指数指数 和和 L LU UMM 连接连接 LMLM 闭包闭包 L L* * 正闭包正闭包 L L + + ? ? 计算机计算机 实现实现 状态状态 转换转换 图图 状态转换图状态转换图 转换图转换图 关系算符的转换图关系算符的转换图 0 5 1 6 2 4 8 3 7 return(relop, LE) return(relop, NE) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 开始 = = * * other other relop relop | | = = 有有 限限 自自 动动 机
7、机 正规式 计算机计算机 实现实现 状态转换图 ？ 有限自动机有限自动机 不确定有不确定有 限自动机限自动机 确定有限确定有限 自动机自动机 等价等价 有有 限限 自自 动动 机机 不确定的有限自动机（简称不确定的有限自动机（简称NFANFA） 一个数学模型，它包括一个数学模型，它包括: : n n 状态集合状态集合S S； n n 输入符号集合输入符号集合 ； n n 转换函数转换函数movemove : : S S ( ( ) ) P P( (S S) )； n n 状态状态s s 0 0 是开始状态；是开始状态； n n F F S S是接受状态集合是接受状态集合。 12 开始a 0 a
8、 b b 识别语言识别语言 ( (a a| |b b) ) * * abab 的的NFANFA 缺点：缺点：1 1、输入字、输入字 符包括符包括 2 2、一个状态对于、一个状态对于 某个字符，可能有某个字符，可能有 多条输出边多条输出边 有有 限限 自自 动动 机机 确定的有限自动机（简称确定的有限自动机（简称DFADFA) ) 一个数学模型，包括：一个数学模型，包括： 状态集合状态集合S S； 输入字母表输入字母表 ； 转换函数转换函数move move : : S S S S； 唯一的初态唯一的初态 s s S S； 终态集合终态集合F F S S； 12 开始 a 0 a b b a b
9、 识别语言识别语言 ( (a a| |b b) ) * * abab 的的DFADFA 优点：优点：1 1、输入字、输入字 符不包括符不包括 2 2、一个状态对于、一个状态对于 某个字符，只可能某个字符，只可能 存在唯一条输出边存在唯一条输出边 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b 状态状态 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b A A 状态状态 A A = 0, 1, 2, 4, 7 = 0,
10、1, 2, 4, 7 DFADFA中第一个状态由中第一个状态由NFANFA 中的开始状态求中的开始状态求 闭包得到闭包得到 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b A A B B 状态状态 A A = 0, 1, 2, 4, 7 = 0, 1, 2, 4, 7 B B = 1, 2, 3, 4, 6, 7, 8 = 1, 2, 3, 4, 6, 7, 8 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b A A
11、 B B B B 状态状态 A A = 0, 1, 2, 4, 7 = 0, 1, 2, 4, 7 B B = 1, 2, 3, 4, 6, 7, 8 = 1, 2, 3, 4, 6, 7, 8 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b A A B B C C B B 状态状态 A A = 0, 1, 2, 4, 7 = 0, 1, 2, 4, 7 B B = 1, 2, 3, 4, 6, 7, 8 = 1, 2, 3, 4, 6, 7, 8 C C = 1, 2, 4, 5, 6, 7 = 1,
12、2, 4, 5, 6, 7 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b A A B B C C B B C C 状态状态 A A = 0, 1, 2, 4, 7 = 0, 1, 2, 4, 7 B B = 1, 2, 3, 4, 6, 7, 8 = 1, 2, 3, 4, 6, 7, 8 C C = 1, 2, 4, 5, 6, 7 = 1, 2, 4, 5, 6, 7 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b
13、 b A A B B C C B B B B C C 状态状态 A A = 0, 1, 2, 4, 7 = 0, 1, 2, 4, 7 B B = 1, 2, 3, 4, 6, 7, 8 = 1, 2, 3, 4, 6, 7, 8 C C = 1, 2, 4, 5, 6, 7 = 1, 2, 4, 5, 6, 7 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b A A B B C C B B B B D D C C 状态状态 A A = 0, 1, 2, 4, 7 = 0, 1, 2, 4, 7 B B
14、= 1, 2, 3, 4, 6, 7, 8 = 1, 2, 3, 4, 6, 7, 8 C C = 1, 2, 4, 5, 6, 7 = 1, 2, 4, 5, 6, 7 D D = 1, 2, 4, 5, 6, 7, 9 = 1, 2, 4, 5, 6, 7, 9 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b A A B B C C B B B B D D C C D D 状态状态 A A = 0, 1, 2, 4, 7 = 0, 1, 2, 4, 7 B B = 1, 2, 3, 4, 6, 7, 8 = 1, 2, 3, 4, 6, 7, 8 C C = 1, 2, 4, 5, 6, 7 = 1, 2, 4, 5, 6, 7 D D = 1, 2, 4, 5, 6, 7, 9 = 1, 2, 4, 5, 6, 7, 9 NFANFA到到DFADFA的转换的转换子集构造法 1 9 开始 0 a b ab 678 23 45 输入符号输入符号 a a b b A A B B C C B B B B D D C C B B C C D D 状态状态 A A = 0, 1, 2, 4, 7 = 0, 1, 2, 4, 7 B B = 1, 2, 3, 4, 6, 7, 8
