编译原理第2讲.ppt

编译原理概论第2讲词法分析 贾西平Email jiaxp 2 提纲 词法分析器状态转换图词法分析器示例正规表达式与正规集 3 提纲 词法分析器状态转换图词法分析器示例正规表达式与正规集 4 词法分析程序所处的位置 5 词法分析器的功能 功能 逐个读入源程序字符并按照构词规则切分成一系列单词符号 主要任务 读入源程序 输出单词符号其他任务 滤掉空格 跳过注释 换行符追踪换行标志 指出源程序出错的行列位置关键 找出单词的分隔符 6 词法分析的两种处理结构 词法分析程序作为主程序把词法分析与语法分析分开 由词法分析程序将字符串形式的源程序改造成单词符号串形式的中间程序词法分析程序作为子程序把词法分析程序作为语法分析程序调用的子程序 7 词法分析器的输出 词法分析器的输出 单词符号序列单词符号 语言中具有确定意义的最小语法单位 常用单词符号的种类 保留字 基本字 具有固定意义的标识符 如begin repeat 标识符 表示各种名字 如变量名 数组名和过程名常数 各种类型的常数运算符 界符 逗号 分号 括号和空白 8 输出单词的表示 词法分析器输出单词符号的表示形式 单词种别 单词自身的值 单词种别 表示单词的种类每种单词对应一个整数编码若一个种别只有一个单词符号 则种别编码表示该单词符号 一般保留字 运算符和界符都是一符一种 单词自身的值 区分同一种别中的不同单词符号若一个种别有多个单词符号 则对于每个单词符号 给出种别编码和自身的值 标识符自身的值 标识符自身的字符串常数按类型分种 常数的自身的值是常数本身的二进制数值 9 例C程序 while i j i 输出单词符号 10 例FORTRAN程序 IF 5 EQ M GOTO100输出单词符号 逻辑IF 34 左括号 2 整常数 20 5 的二进制 等号 6 标识符 26 M 右括号 16 GOTO 30 标号 19 100 的二进制 11 提纲 词法分析器状态转换图词法分析器示例正规表达式与正规集有限自动机 12 状态转换图 状态转换图是一个有限的有向图意义结点代表状态 用圆圈表示 状态之间用有向边连结 边上的标记代表输入字符或字符类 状态 结点 数是有限的 其中必有一个初态 若干终态 初始状态用0状态表示 终止状态用双圈表示 13 状态转换图可用于识别一定的字符串 当到达一类单词符号的终止状态时即可给出相应的单词编码某些终止状态是在读入了一个其它不属于该单词的符号后才得到相应的单词编码 终态上加 表示识别出单词后应将多读入的这个符号予以回退 状态转换图 14 状态转换图示例 15 图2 4含有分支或回路的状态示意 a 含分支的状态i b 含回路的状态i 状态转换图示例 16 思想 每个状态结点对应一小段程序 做法 1 对不含回路的分支 可用一个switch语句或一组IF ELSE语句实现 GetChar if IsLetter 状态j的对应程序段 elseif IsDigit 状态k的对应程序段 elseif ch 状态l的对应程序段 else 错误处理 状态转换图实现 17 2 含回路的状态 可对应一段由WHILE语句构成的程序 GetChar while IsLetter orIsDigit GetChar 状态j的对应程序段 状态转换图实现 18 3 终态结点表示识别出某种单词符号 对应语句为RETURN C VAL 其中 C为单词种别 VAL为单词自身值 状态转换图实现 19 提纲 词法分析器状态转换图词法分析器示例正规表达式与正规集 20 词法分析器 词法分析器主要识别如下几种单词 标识符的识别 字母 字母 数字 关键字的识别 与标识符相同 最后查表常数的识别界符和算符的识别 21 词法分析基本过程 22 23 C语言词法分析器示例 设计过程 设计C语言子集对应的状态转换图状态转换图的编程实现每个状态对应一段程序 24 C语言子集的单词符号及内码值 25 简单词法分析的状态转换图 26 状态转换图的实现 变量和过程定义 character 字符变量 存放最新读入的源程序字符 token 字符数组 存放构成单词符号的字符串 getbe 若character中的字符为空白 则调用getchar 直至character为非空白符为止 concatenation 将token中的字符串与character中的字符连接并作为token中新的字符串 27 状态转换图的实现 letter 和digit 判断character中的字符是否为字母和数字的布尔函数 是则返回true 否则返回false reserve 判断token数组中的字符串是否为保留字 查表 若是则返回其编码 否则返回0值 retract 扫描指针回退一个字符 同时将character置为空白 buildlist 将标识符登录到符号表或将常数登录到常数表 error 出现非法字符 显示出错信息 28 词法分析器 标识符识别 token 对token数组初始化 s getchar getbe 滤除空格 switch s case a case b case z while letter digit concatenation 将当前读入的字符送入token数组 getchar retract 扫描指针回退一个字符 29 词法分析器 标识符 保留字识别 c reserve if c 0 标识符 非保留字 buildlist 将标识符登录到符号表中 return id 指向id的符号表入口指针 elsereturn 保留字码 null break 判断是否为保留字 30 词法分析器 识别数字 case 0 case 1 case 9 while digit concatenation getchar retract buildlist 将常数登录到常数表中 return num num的常数表入口指针 break 31 词法分析器 识别算符 case return null break case return null break case return null break 32 词法分析器 识别算符 case getchar if character return relop LE else retract return relop LT break 33 词法分析器 识别算符 case getchar if character return relop EQ else retract return null break 34 词法分析器 识别算符 case return null break default error 35 提纲 词法分析器状态转换图词法分析器示例正规表达式与正规集 36 正规表达式与有限自动机 为了讨论词法分析程序的自动生成问题 需将状态转换图加以形式化正规表达式就是一种形式化方法 37 正规表达式与有限自动机 几个概念 考虑一个有穷字母表 字符集其中每一个元素称为一个字符 上的字 也叫字符串 指由 中的字符所构成的一个有穷序列不包含任何字符的序列称为空字 记为 用 表示 上的所有字的全体 包含空字 例如 设 a b 则 a b aa ab ba bb aaa 38 空字和空集 表示不含任何元素的空集 和 的区别 空字 表示不含任何字符的序列 表示不含任何字的集合 由空字组成的集合 39 连接与闭包 的正规式R和S的连接定义为RS R记R RR 称R 是R的正则闭包 40 正规式和正规集的递归定义 1 对给定的字母表 1 和 都是 上的正规式 它们所表示的正规集为 和 2 任何a a是 上的正规式 它所表示的正规集为 a 41 正规式和正规集的递归定义 2 3 假定R和S都是 上的正规式 它们所表示的正规集为L R 和L S 则i R S为 上的正规式 它所表示的正规集为L R L S ii R S为 上的正规式 它所表示的正规集为L R L S iii R 为 上的正规式 它所表示的正规集为 L R 仅由有限次使用1 3 步骤而定义的表达式才是 上的正规式仅由这些正规式表示的字集才是 上的正规集 42 正规式间运算符 表示或 表示连接 通常可省略 表示闭包使用括号可以改变运算的次序 规定 优先于 优先于 在不出现混淆的情况下括号可省去 43 正规式等价 若两个正规式R和S所表示的正规集相同 即L R L S 则称正规式R和S等价 记为R S 如b ab ba b L b ab L ba b b ab ba b 44 正规式的性质 正规式具有下列性质 交换律 R S S R 结合律 R S T R S T R ST RS T 分配律 R S T RS RT R S T RT ST 同一律 R R R 45 正规式运算 例2 1令 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 aaa a aa ab aaa aab aba abb aaaa 46 正规式运算 例2 2判断下述正规式之间是否等价 1 a b 与a b 2 a b 与 a b 解 47 1 a b 与a b L a b L a b L a L b a b a b a b aa ab ba bb aaa L a b L a L b L a L b a b a aa aaa b bb bbb a b aa bb aaa bbb L a b L a b 正规式 a b 与a b 不等价 48 2 a b 与 a b L a b L a b L a L b a b a b a b aa ab ba bb aaa L a b L a L b a b a aa aaa b bb bbb a b aa bb aaa bbb a b aa ab ba bb aaa L a b L a b 正