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

2020 3 1 编译原理与技术 讲义 1 编译原理与技术 词法分析 1 2020 3 1 编译原理与技术 讲义 2 词法分析 词法分析器介绍正规式与正规集有限自动机词法分析器的自动生成 lex 2020 3 1 编译原理与技术 讲义 3 词法分析器介绍 词法分析器的功能 高级语言源程序 词法分析器 语法分析器 token get next token 编译器其它阶段 符号表 字符流 记号 流 2020 3 1 编译原理与技术 讲义 4 词法分析器介绍 词法分析器的功能读源程序 产生记号序列剥去源程序中的注释 块 行 和 空白 符预处理 宏处理与文件包含 2020 3 1 编译原理与技术 讲义 5 词法分析器介绍 词法分析器作为独立子程序简化设计提高编译效率增强可移植性 2020 3 1 编译原理与技术 讲义 6 词法分析器介绍 记号 模式与单词记号 同类单词的总称模式 描述构成记号的字符串的规则单词 源程序中能匹配任一记号的字符串 2020 3 1 编译原理与技术 讲义 7 程序语言的记号 1 2020 3 1 编译原理与技术 讲义 8 程序语言的记号 2 2020 3 1 编译原理与技术 讲义 9 词法分析器介绍 词法分析器的二元输出 单词 字符串 的类别 匹配记号的单词多于一个时 须提供额外的信息以区别之 2020 3 1 编译原理与技术 讲义 10 词法分析器介绍 词法分析器的二元输出 记号影响语法分析的决策 属性 如类型 偏移 则关系到记号的翻译 2020 3 1 编译原理与技术 讲义 11 词法分析器介绍 e g 1pascal源程序片段 beginlength length 1 iflength 20thenread nextch end 2020 3 1 编译原理与技术 讲义 12 2020 3 1 编译原理与技术 讲义 13 e g 1词法分析器的输出记号流 1 不是多余的 属性是常量 值 本身 2020 3 1 编译原理与技术 讲义 14 e g 1词法分析器的输出记号流 2 2020 3 1 编译原理与技术 讲义 15 词法分析器介绍 超前搜索fortran中的关键字 不保留 1 do100k 1 102 do100k 1 103 if 5 eq m i 104 if 5 55有关算符的识别c c java的 等 与之对应 2020 3 1 编译原理与技术 讲义 16 词法分析器介绍 词法错误可检测非法字符的出现ifvsfi词法分析器的设计手工编写 采用汇编语言或高级语言自动生成 lex 2020 3 1 编译原理与技术 讲义 17 词法分析器介绍 状态转换图用于记号的识别 状态之间用带有标记 字符 的有向边连接 每读入一个字符会引起状态变化 直至单词 记号 被识别出来 开始状态 状态转换图的初始状态 尚未读字符 接受状态 某个单词被识别时所处的状态 终态 单词 记号 的识别过程即是从开始状态出发到某接受状态的变化过程 2020 3 1 编译原理与技术 讲义 18 词法分析器介绍 状态转换图 2020 3 1 编译原理与技术 讲义 19 词法分析器介绍 状态转换图 0 5 数字 识别pascal无符号数的转换图 数字 6 7 8 9 10 11 数字 数字 e 数字 数字 其它 e 数字 其它 其它 2020 3 1 编译原理与技术 讲义 20 词法分析器介绍 状态转换图 0 5 数字 红线 识别pascal无符号整数的转换图 数字 6 7 8 9 10 11 数字 数字 e 数字 数字 其它 e 数字 其它 其它 2020 3 1 编译原理与技术 讲义 21 词法分析器介绍 状态转换图 0 5 数字 识别pascal无符号小数的转换图 数字 6 7 8 9 10 11 数字 数字 e 数字 数字 其它 e 数字 其它 其它 2020 3 1 编译原理与技术 讲义 22 状态转换图的实现e g 2简单词法分析的转换图 识别关键字 标识符 无符号整数 算符和界符 tobecontinued 2020 3 1 编译原理与技术 讲义 23 e g 2简单词法分析的转换图 tobecontinued 2020 3 1 编译原理与技术 讲义 24 e g 2简单词法分析的转换图 10 11 return le 12 return ne 13 return lt 其它字符 14 return eq 15 16 return ge 17 return gt 其它字符 tobecontinued 2020 3 1 编译原理与技术 讲义 25 e g 2简单词法分析的转换图 18 19 return assign 20 return 其它字符 21 return 其它 22 error 状态转换程序 2020 3 1 编译原理与技术 讲义 26 串与语言 语言语言l s s是 上任一字符串 s称为语言l的一个句子 字母表 符号 字符的非空有限集合e g 二进制数的 0 1 而十进制数的 0 1 9 表示 上所有字符串的集合 l 字符串 上若干字符组成的有穷序列 2020 3 1 编译原理与技术 讲义 27 串与语言 语言字符串e g 0 1 上的0 1串 二进制数 如0111 10101 a b 上的a b aa abab 空串 串长 s s中所含字符的个数 0串的连接运算 任意串x y 一般地 xy yx x x串的前缀 任意串x 从其第一个字符 最左字符 起的字符序列是其前缀 亦是 e g x abc 则 a ab abc均是x的前缀 2020 3 1 编译原理与技术 讲义 28 语言的运算 2020 3 1 编译原理与技术 讲义 29 语言e g l a b z d 0 1 9 b l d ld l l l d l b l d b d 2020 3 1 编译原理与技术 讲义 30 正规式与正规集 正规式 用于描述记号的构成规则正规集 正规式描述的语言 匹配正规式的串集 2020 3 1 编译原理与技术 讲义 31 正规式与正规集 如果r和s是 上的正规式 分别对应 上的正规集l r 和l s 则 2020 3 1 编译原理与技术 讲义 32 正规式与正规集 上的正规式 其运算有 和 2020 3 1 编译原理与技术 讲义 33 正规式与正规集 上的正规式 满足如下代数定律 2020 3 1 编译原理与技术 讲义 34 正规式与正规集 上的正规式 也具有如下代数定律 r r r r r rr 2020 3 1 编译原理与技术 讲义 35 正规式与正规集 e g 3设 a b 则 2020 3 1 编译原理与技术 讲义 36 正规式与正规集 e g 3设 a b r a a b 事实上有l r l a a b l a l a b l a l a b l a l a l b a a b a a b a a b aa ab ba bb abb a aa ab aaa aab aba abb aabb 即l r 是 上以a开头的串集 2020 3 1 编译原理与技术 讲义 37 正规式与正规集 正规定义d1 r1d2 r2 dn rn各个di的名字不同 每个ri是 d1 d2 di 1 上的正规式 2020 3 1 编译原理与技术 讲义 38 正规式与正规集 e g 4pascal标识符letter a b z a b zdigit 0 1 9id letter letter digit 英文字母集合 十进制数字集合 标识符的正规定义 2020 3 1 编译原理与技术 讲义 39 正规式与正规集 e g 5pascal无符号数digit 0 1 9digits digitdigit fraction digits