编译原理王晓斌编译第八章

1、第八章 词法分析第一节 词法分析概述一. 词法分析的功能1. 功能 扫描源程序的字符串,按照词法规则,识别出单词符号作为输出;对识别过程中发现的词法错误,则输出有关的错误信息。2. 词法分析器和语法分析器的关系（1）词法分析作为单独的一遍输入串词法分析器语法分析器单词流第八章 词法分析（2）词法分析作为子程序输入串词法分析器语法分析器符号表取下一单词返回下一单词第八章 词法分析二. 词法分析器的输出形式1. 单词的种类 (1)标识符:用来命名程序中出现的变量、数组、函数、过程、标号等 (2)基本字:也可称关键字或保留字, 如if、while、for、do、goto等 (3)常数:各种类型的常数

2、, 如216、3.14159、true等 (4)运算符:如+、-、*、/等 (5)界符:如;、:、/*、*/等第八章 词法分析2.单词的输出形式（1） 二元式 (单词类别,单词的属性)区分单词所属的类(整数编码) 单词的值（2） 单词类别的划分u基本字、运算符、界符:一字一码u标识符:单列一种u常数:按类型分类一个例子：a:=b50+10； 的输出为：（标识符的编码，a）（:=的编码，）（标识符的编码，b50）（的编码，）（整数的编码，10）（；的编码，）第二节 词法分析器的结构一. 扫描缓冲区1. 输入缓冲区：源程序输入缓冲区2. 预处理程序：取消注解，剔除无用的空白、跳格、回车、换行等3.

3、 扫描缓冲区：从输入缓冲区输入固定长度的字符串到另一个缓冲区（扫描缓冲区），词法分析可以直接在此缓冲区中进行符号识别。其结构为：左缓冲区右缓冲区起点指示器搜索指示器二. 符号的识别1. 词法分析技术超前搜索 为了判定一个单词符号的类别,必须扫描到某一地方,而该单词符号并没有这么长,这种扫描方式叫做“超前搜索”。（1）基本字的识别 do100i=1,10 do100i=1.10 if(5.eq.m)goto 100 if(5)=100（2）标识符的识别：读到非字母数字（3）常数的识别：根据常数的格式；大多数常数后都有运算符或界符（4）运算符的识别：需要超前搜索，如*（5）界符的识别：需要超前搜索

4、，如/*三. 词法分析器的结构预处理子程序词法分析器输入缓冲区扫描缓冲区单词符号输入第三节 状态转换图一. 状态转换图的定义u有限的有向图u有向边上标记字符u唯一初态u若干终态（至少一个）123xy二. 状态转换图识别的串 从初态出发到某一终态路径上字符的连接。下图是识别标识符的状态转换图：012字母其它字符字母或数字*第四节 词法分析器的设计一. 单词符号 第四章设计的语言允许下述单词： 标识符、数字串、begin、end、integer、if、 then、else、function、read、write、 、*、=、 =、=、:=、；、（、）单词符号单词符号类别编码类别编码助记符助记符标识

5、符数字串beginendintegerifthenelse12345678$id$int$begin$end$integer$if$then$else单词符号单词符号类别编码类别编码助记符助记符functionreadwrite*=910111213141516$function$read$write$sub$mul$lt$le$ne单词符号单词符号类别编码类别编码助记符助记符=:=；（）17181920212223$eq$gt$ge$assign$sem$lpar$rpar04123567开始空白字母/数字字母非字母数字数字非数字=-*数字二. 状态转换图89()101112=1314151

6、6其它=171819：其它=其它2021；其它* 三. 实现方法 每个状态结对应一小段程序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

7、;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;

8、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)bui

9、ldlist:将token中的标识符存入符号表，并将其在符号表中的位置填入val (10)dtb:将token中的数字串转换成二进制，并存入常数表，位置填入val (11)val:存放标识符在符号表中的位置，或常数在常数表中的位置 (12)return(c,val)：返回二元式 (13)error：出错处理第五节 符号表 在程序中,用户用标识符定义了不少名字来代表不同的数据对象,编译程序将这些名字保存在符号表中。符号表除了记录名字本身而外,还记录了与名字关联的各种属性信息。一. 符号表的一般形式 每个名字对应一个表项,一个表项包括名字域和信息域。名字信息其中,信息域通常设若干子域及标志位，其内容可以是和名字有关的任何信息： 类型,种属,长度,相对地址,数组的内情向量,记录