编译原理（王晓斌）编译第八章.ppt

第八章 词法分析 第一节 词法分析概述 一. 词法分析的功能 1. 功能 扫描源程序的字符串,按照词法规则,识 别出单词符号作为输出;对识别过程中发 现的词法错误,则输出有关的错误信息。 2. 词法分析器和语法分析器的关系 （1）词法分析作为单独的一遍 输入串词法分析器语法分析器 单词流 第八章 词法分析 （2）词法分析作为子程序 输入串 词法分析器 语法分析器 符号表 取下一单词 返回下一单词 第八章 词法分析 二. 词法分析器的输出形式 1. 单词的种类 (1)标识符:用来命名程序中出现的变量、数组、 函数、过程、标号等 (2)基本字:也可称关键字或保留字, 如if、while、 for、do、goto等 (3)常数:各种类型的常数, 如216、3.14159、 TRUE等 (4)运算符:如+、-、*、/等 (5)界符:如;、:、/*、*/等 第八章 词法分析 2.单词的输出形式 （1） 二元式 (单词类别,单词的属性) 区分单词所属的类(整数编码) 单词的值 （2） 单词类别的划分 u基本字、运算符、界符:一字一码 u标识符:单列一种 u常数:按类型分类 一个例子： A:=B50+10； 的输出为： （标识符的编码，A） （:=的编码，） （标识符的编码，B50） （的编码，） （整数的编码，10） （；的编码，） 第二节 词法分析器的结构 一. 扫描缓冲区 1. 输入缓冲区：源程序输入缓冲区 2. 预处理程序：取消注解，剔除无用的空白、 跳格、回车、换行等 3. 扫描缓冲区：从输入缓冲区输入固定长 度的字符串到另一个缓冲区（扫描缓冲 区），词法分析可以直接在此缓冲区中 进行符号识别。其结构为： 左缓冲区右缓冲区 起点指示器搜索指示器 二. 符号的识别 1. 词法分析技术超前搜索 为了判定一个单词符号的类别,必须扫 描到某一地方,而该单词符号并没有这么 长,这种扫描方式叫做“超前搜索”。 （1）基本字的识别 DO100I=1,10 DO100I=1.10 IF(5.EQ.M)GOTO 100 IF(5)=100 （2）标识符的识别：读到非字母数字 （3）常数的识别：根据常数的格式；大多 数常数后都有运算符或界符 （4）运算符的识别：需要超前搜索，如* （5）界符的识别：需要超前搜索，如/* 三. 词法分析器的结构 预处理子程序 词法分析器 输入缓冲区 扫描缓冲区 单词符号 输入 第三节 状态转换图 一. 状态转换图的定义 u有限的有向图 u有向边上标记字符 u唯一初态 u若干终态（至少一个） 1 2 3 x y 二. 状态转换图识别的串 从初态出发到某一终态路径上字符的连 接。下图是识别标识符的状态转换图： 012 字母 其它字符 字母或数字 * 第四节 词法分析器的设计 一. 单词符号 第四章设计的语言允许下述单词： 标识符、数字串、begin、end、integer、if、 then、else、function、read、write、 、*、 =、=、:=、；、（、） 单词符号类别编码助记符 标识符 数字串 begin end integer if then else 1 2 3 4 5 6 7 8 $ID $INT $BEGIN $END $INTEGER $IF $THEN $ELSE 单词符号类别编码助记符 function read write * 9 10 11 12 13 14 15 16 $FUNCTION $READ $WRITE $SUB $MUL $LT $LE $NE 单词符号类别编码助记符 = = := ； （ ） 17 18 19 20 21 22 23 $EQ $GT $GE $ASSIGN $SEM $LPAR $RPAR 0 4 1 2 3 5 6 7 开始 空白 字母/数字 字母 非字母数字 数字 非数字 = - * * * 数字 二. 状态转换图 8 9 ( ) 10 11 12 = 13 1415 16 其它 = 1718 19 ： 其它 = 其它 20 21 ； 其它 * * * * 三. 实现方法 每个状态结对应一小段程序 u分支状态if或case语句 u循环状态while语句 u终态return语句 四. 一个示意算法 start: token:= ; getchar;getnb; case character of az: begin while letter or digit do begin concatenate;getchar end; retract; c:= reserve; if c = 0 then begin buildlist; return($ID,val) end else return(c,) end; 09: begin while digit do begin concatenate;getchar end; retract; dtb; return($INT,val) end; = : return($EQ,); - : return($SUB,); * : return($MUL,); ( : return($LPAR,); ) : return($RPAR,); then return($NE, ); retract; return($LT, ) end; : begin getchar; if character = = then return($GE, ); retract; return($GT, ) end; : : begin getchar; if character = = then return($ASSIGN,) else error end; ; : return($SEM,) other: error end of case; goto start; 全局量及过程: (1)token：字符数组 (2)character：字符变量 (3)getchar：取一字符 (4)getnb：读到非空白字符 (5)concatenate：连接 (6)letter和digit：布尔函数 (7)reserve：查保留字表 (8)retract:退一字符;character置空 (9)buildlist:将token中的标识符存入符号表，并 将其在符号表中的位置填入val (10)dtb:将token中的数字串转换成二进制，并 存入常数表，位置填入val (11)val:存放标识符在符号表中的位置，或常数 在常数表中的位置 (12)return(c,val)：返回二元式 (13)error：出错处理 第五节 符号表 在程序中,用户用标识符定义了不少 名字来代表不同的数据对象,编译程序将 这些名字保存在符号表中。符号表除了 记录名字本身而外,还记录了与名字关联 的各种属性信息。 一. 符号表的一般形式 每个名字对应一个表项,一个表项包括 名字域和信息域。 名字信息 其中,信息域通常设若干子域及标志位，其 内容可以是和名字有关的任何信息： 类型,种属,长度,相对地址,数组的内情向 量,