编译原理2词法剖析.ppt

I a b {x,5,1} {5,1,3} {5,1,4} {5,1,3} {5,1,3,2,6,y} {5,1,4} {5,1,4 } {5,1,3} {5,1,4,2,6,y} {5,1,3,2,6,y} {5,1,3,2,6,y} {5,1,4,6,y} {5,1,4,2,6,y} {5,1,3,6,y} {5,1,4,2,6,y} {5,1,4,6,y} {5,1,3,6,y} {5,1,4,2,6,y} {5,1,3,6,y} {5,1,3,2,6,y} {5,1,4,6,y} M (3) 将M 中的状态集换名, si = Ii 得到一新的状态转换矩阵 M’ 注意: M 与 M’等价. S a b s0 s1 s2 s1 s3 s2 s2 s1 s4 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5 M’ M’满足确定有限自动机的定义,状态图 表示如下: s0 s1 s3 s5 s6 s4 a b b s2 a a a a a a b b b b b 第三节 词法分析器的 自动生成原理及LEX语言 正规式 确定自动机 状态转换矩阵 词法分析器 控制程序 自动生成器 转化 合成 一 自动生成原理 * * * 内容提要: 状态转换图 正规式与有限制动机 词法分析器的自动生成 词法分析器 源程序 单词序列 第一节 状态转换图 一 单词分类及表示 编译中,把高级语言的单词分为五类: 标识符,基本字,常数,运算符,界符 基本字,运算符,界符都是有限可枚举的;而标识符,常数可认为是无限的. 简单起见,单词可表示为如下二元组: (单词分类号,单词自身值); 或者为: (单词种别码,单词自身值); 标识符,常数 各为一个种别码,而由于基本字,运算符,界符的有限性,可以设计为一字一个种别码. 例如: 单词 单词种别码 分类号 标识符 1 1 常数 2 2 if 3 3 then 4 3 end 90 3 , 91 4 ; 92 4 = 151 5 + 152 5 保留字 界符 运算符 二 词法分析器的设计 1 源程序的预处理子程序 源程序中,存在许多编辑用的符号,它们对程序逻辑功能无任何影响. 例如:回车,换行,多余空白符,注释行等.在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单. 源程序 输入缓冲区 预处理子程序 扫描缓冲区2 扫描缓冲区1 缓冲区分为两部分,每个长度为256字节,这样单词的总长度可达到256字节.预处理子程序把处理好的字符串轮流放入两个缓冲区中,供词法分析程序使用. 2 词法分析程序 词法分析程序又称为词法分析器或扫描器.可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用词法分析子程序返回一个单词.这里,作为子程序介绍. 词法分析器的结构: 源程序 输入缓冲区 预处理子程序 扫描缓冲区2 扫描缓冲区1 词法分析子程序 调用 返回一单词 数据 3 词法规则的表示--------状态转换图 定义:状态转换图是一有向图,由有限个结点及有向边连接而成; 每个结点称为状态;状态图有一个初态,多个终态;每条边上 有相应的字符. 状态转换图用于表示单词结构,从状态转换图的初态到终态 间,每条路径上字符的连接,就构成了该状态图的合法单词. 例如: 0 1 2 初态 终态 字母 字母 数字 其它 * 1标识符的状态图表示: 星号表示单词尾部多跟一个