07-第三章有限自动机与词法分析器.ppt

第三章 有穷自动机与词法分析器 任课教师 王养廷 主要内容 词法分析 有穷自动机 3.1 词法分析 词法分析功能 源程序文件 ASCII编码 文本文件 例如：“A1”保存为4131 单词 源程序的语法成分 例如：if, (, … 3.1 词法分析 词法分析功能 Token 单词的内部表示，例如： 3.1 词法分析 词法分析功能 标识符 用户定义的符号 作为一类来处理 常量 可以作为一类或多类 保留字 用来分隔语法成分 一般每个一类 与保留字的区别（算法设计？） 3.1 词法分析 词法分析功能 词法分析输入：源程序 词法分析输出：Token序列 词法分析功能：把源程序转换成Token序列 词法分析器种类 作为语法分析的一个子程序，每次产生一个Token 作为编译器独立的一遍、生成Token序列 3.1 词法分析 词法分析功能 单词识别 从字符串中分离出单个单词 主要的单词 标识符 正整数 保留字 符号 …… 3.1 词法分析 词法分析功能 词法分析复杂性，例子： DO 10 I = 1 , 100 DO 10 I = 1. 100 3.1 词法分析(续) 单词内部表示 标识符的内部表示 指针方法 其它符号的内部表示 为什么单独处理标识符 3.1 词法分析(续) 保留字 什么识保留字 分析保留子的方法 保留字表，数据实现 非保留字表，程序实现 空格、制表符、换行符 它们可以作为分隔符 有的语言空格符无词法意义 例如：下面两行等价 beginx begin x 字符串中的空格需要单独处理 换行可以用于行计数 3.1 词法分析(续) 括号类配对 Pascal语言中的括号类 begin ......end record......end if......then [......] (......) {......} 检查配对 使用计数器 更准确地方法如何实现？ 3.1 词法分析(续) 向前看多个字符 词法分析有时需要向前看多个字符，例如： 10 10.12 10..12 有时需要看到第一个‘.’后的字符才能确定 处理技术 沿着收到的字符倒退到终态 把回退字符集如缓冲区，以便下一次扫描 引入Token标志 例如：12.3e+q的分析 3.1 词法分析(续) 字符串空间 字符串的存储问题 一般方法 使用缓冲区记录开始地址和长度 注意检查是否有重复存储的字符串 字符编码问题 3.1 词法分析(续) 词法错误校正 目的：发现更多的错误，分析继续下去 手段： 删去已读过的字符 删去已读过的第一个字符 特别注意越行字符串的处理 3.1 词法分析(续) 词法分析结束 使用程序结束标志 例如：Pascal中的end. 使用文件结束标志 可以有效处理错误程序 3.1 词法分析(续) 使用词法分析的好处 使语法分析与语义分析更简练 便于使用自动机理论描述 有利于提高编译器的效率 有利于编译器的移植 3.2 确定有穷自动机 说明 有穷自动机（FA） 确定有穷自动机（DFA） 非确定有穷自动机（NFA） 3.2 确定有穷自动机（续） 定义 确定有穷自动机（DFA）有以下几个部分组成： 符号集Σ（输入符号集）; 状态集合SS={S0, S1, S2, S3... Sn}; 开始状态： S0 ; 转换函数Φ：SS X Σ →SS; 终止状态集：{Si1, Si2... Sik}; 其中Φ表示给定一个状态和输入字符就可以唯一确定下一个状态 3.2 确定有穷自动机（续） 自动机定义方式 图形法 转换表法 函数法 3.2 确定有穷自动机（续） DFA例子（函数法） 符号集Σ={0, 1, 2, ...... ,9}; 状态集合SS={S0, S1}; 开始状态： S0 ; 转换函数Φ：SS X Σ →SS; Φ(S0, d)= S1 , Φ(S1, d)= S1 终止状态集：{S1}; 3.2 确定有穷自动机（续） DFA有向图表示 状态 开始状态 转换边 接受（或终止）状态 3.2 确定有穷自动机（续） 接受 自动机接受字符串 作用？？ 3.2 确定有穷自动机（续） 特殊例子 3.2 确定有穷自动机（续） DFA举例 3.2 确定有穷自动机（续） 练习 实数的DFA 第二个位置上为2的所有正整数 标识符，由字母字符引导的数字、字母字符串。 接受偶数个0的DFA 接受奇数个1的DFA 接受偶数个0和偶数个1的DFA 3.2 确定有穷自动机（续） 实数的DFA 3.2 确定有穷自动机（续） 第二个位置上为2的正整数（包括一位） 3.2 确定有穷自动机（续） 思考 将上题改成不包