编译原理2词法分析课件.ppt

第二章 词法分析;第一节 状态转换图;例如:;二 词法分析器的设计 1 源程序的预处理子程序 源程序中,存在许多编辑用的符号,它们对程序逻辑功能无任何影响. 例如:回车,换行,多余空白符,注释行等.在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单.;2 词法分析程序 词法分析程序又称为词法分析器或扫描器.可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用词法分析子程序返回一个单词.这里,作为子程序介绍. 词法分析器的结构:;3 词法规则的表示--------状态转换图 定义:状态转换图是一有向图,由有限个结点及有向边连接而成; 每个结点称为状态;状态图有一个初态,多个终态;每条边上 有相应的字符. 状态转换图用于表示单词结构,从状态转换图的初态到终态 间,每条路径上字符的连接,就构成了该状态图的合法单词. 例如: ;0;4 单词的识别 状态图即可以表示单词规则,同时也可以用于识别单词. 设有一字符串S = s1s2......sn, 若状态图中存在一初态到终态的 路径,且路径上字符的连接为: s1s2......sn, 称 S 可被状态图识别. 例如: S=‘var1’;5 一个简单示例 构造一个简单语言所有单词的状态转换图.该语言的单词种类如下表所示:;0 ;6 状态转换图的程序实现 为便于程序实现,假设每个单词间都有界符或运算符或空格隔 开,并引入下面的全局变量及子程序: 1) CHAR 字符变量 2) TOKEN 单词字符串 3) GETCHAR 读一个字符到 CHAR 中 4) GETBC 读一个非空白字符到CHAR 中 5) CONCAT 把CHAR 中字符连接到TOKEN 之后 6) LETTER 判断CHAR 中字符是否为字母 7) DIGIT 判断CHAR 中字符是否为数字 8) RESERVE 用TOKEN中的字符串查找保留字表,并返回保留 字种别码,若返回零,则非保留字 9) RETRACT 把CHAR 中字符回送到缓冲区 ; 下面分析状态图的结构特点.每个状态图都由三种结构构成: 分支结构 循环结构 终结点 1分支结构程序设计;2循环结构程序设计;TYPE WORDTYPE=RECORD C：INTEGER； VAL：CHAR； END； FUNCTION RETURN_WORD( ):WORDTYPE; { STATE0: TOKEN:=‘’;GETCHAR;GETBC; CASE CHAR OF ‘A’..’Z’: { CONCAT; STATE1:GETCHAR; WHILE (LETTER OR DIGIT) DO { CONCAT;GETCHAR}; RETRACT； STATE2: C:=RESERVE; IF C=0 THEN RETURN($ID,TOKEN) ELSE RETURN(C,__ ) } ; ‘ 0’..’ 9’: { CONCAT; STATE3:GETCHAR; WHILE ( DIGIT) DO { CONCAT;GETCHAR};