编译原理(王晓斌)编译第八章.ppt
第八章 词法分析,第一节 词法分析概述一.词法分析的功能1.功能 扫描源程序的字符串,按照词法规则,识别出单词符号作为输出;对识别过程中发现的词法错误,则输出有关的错误信息。,2.词法分析器和语法分析器的关系（1）词法分析作为单独的一遍,输入串,词法分析器,语法分析器,单词流,第八章 词法分析,（2）词法分析作为子程序,输入串,词法分析器,语法分析器,符号表,取下一单词,返回下一单词,第八章 词法分析,二.词法分析器的输出形式1.单词的种类(1)标识符:用来命名程序中出现的变量、数组、函数、过程、标号等(2)基本字:也可称关键字或保留字,如if、while、for、do、goto等(3)常数:各种类型的常数,如216、3.14159、TRUE等(4)运算符:如+、-、*、/等(5)界符:如;、:、/*、*/等,第八章 词法分析,2.单词的输出形式（1）二元式(单词类别,单词的属性),区分单词所属的类(整数编码)单词的值,（2）单词类别的划分基本字、运算符、界符:一字一码标识符:单列一种常数:按类型分类,一个例子：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）界符的识别：需要超前搜索，如/*,三.词法分析器的结构,预处理子程序,词法分析器,输入缓冲区,扫描缓冲区,单词符号,输入,第三节 状态转换图一.状态转换图的定义有限的有向图有向边上标记字符唯一初态若干终态（至少一个）,1,2,3,x,y,二.状态转换图识别的串 从初态出发到某一终态路径上字符的连接。下图是识别标识符的状态转换图：,0,1,2,字母,其它字符,字母或数字,*,第四节 词法分析器的设计一.单词符号 第四章设计的语言允许下述单词：标识符、数字串、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,14,15,16,其它,=,17,18,19,：,其它,=,其它,20,21,；,其它,*,*,*,*,三.实现方法 每个状态结对应一小段程序分支状态if或case语句循环状态while语句终态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:errorend 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：出错处理,第五节 符号表 在程序中,用户用标识符定义了不少名字来代表不同的数据对象,编译程序将这些名字保存在符号表中。符号表除了记录名字本身而外,还记录了与名字关联的各种属性信息。,一.符号表的一般形式 每个名字对应一个表项,一个表项包括名字域和信息域。,名字,信息,其中,信息域通常设若干子域及标志位，其内容可以是和名字有关的任何信息：类型,种属,长度,相对地址,数组的内情向量,记录与分量的联系,形参标志,说明标志,赋值标志等。因名字的长度、信息域的组成及长度可能是各不相同的,一般采用间接表技术。,二.常用的符号表结构1.线性表:用N个数组A1,A2,AN来存放符号表的N个子域 2.HASH表,第八章习题实验题：词法分析器的设计与实现思考题：8-3、8-4,
