编译原理实用教程 杨德芳 第3章 词法分析

《编译原理实用教程 杨德芳 第3章 词法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章词法分析本章学习目标词法分析程序的主要任务是对源程序进行扫描，从中识别出单词。它是编译程序的第一步，也是编译过程中不可缺少的部分。本章的主要内容是：正则表达式和有限自动机文法、正规表达式、正规集及自动机的相互转换词法分析器的C语言实现词法分析器的自动生成3.1词法分析器与单词符号3.1.1词法分析词法分析是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个一个的单词。编译程序中完成词法分析任务的程序段，称为词法分析程序。词法

2、分析程序对源程序进行扫描，从中识别出一个个的单词符号，因此，词法分析程序又称为词法分析器，又称扫描器。词法分析器作为编译程序的一部分，它与语法分析程序之间接口方式有两种。一种方式是词法分析程序独立工作，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件称为语法分析程序的输入而继续编译，如图3-1所示就是将词法分析单独作为一遍的接口方式。源程序词法分析程序单词序列图3-1词法分析单独作为一遍取符号源程序词法分析程序语法分析程序图3-2词法分析作为语法分析子程序送符号另一种方法，也是常用的一种方法就

3、是把词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，就调用该程序。词法分析程序每得到一次调用，就从源程序文件中读入一个字符，直到识别出一个单词为止。这种方法省去了中间文件。源程序词法分析程序单词序列图3-1词法分析单独作为一遍取符号源程序词法分析程序语法分析程序图3-2词法分析作为语法分析子程序送符号3.1.2单词符号单词符号是程序设计语言的基本语法单位和最小语义单位。单词符号一般分为五类。（1）关键字（又称保留字或基本字）如if，then，else，while，do，begin和end。（

4、2）标识符，用于表示变量名、过程名等。（3）常数，如123，实数型45.67等。（4）运算符，如+，-，*，/，<，=等。（5）界限符，如逗号、分号和括号等。程序设计语言中的关键字、运算符和界限符的数量都是确定的。而常数和标识符的数量是不确定的。1．单词类别的表示单词类别表示单词的种类，它是语法分析所需要的信息。一个语言的单词符号如何划分种类、分为几种，如何编码都属于技术性的问题，主要取决于处理上的方便。单词符号有5个类别：关键字、标识符、常数、运算符和界限符，可以用1、2、3、4、5来表示。也可以用一字

5、符一类别码的编码形式，如保留字可以采用一字一类别。分界符也可以采用一字一类别。对于一字一类别的单词，单词的类型就是单词的自身值，词法分析程序就不必输出其值了。常数的自身值是其自身的二进制。2．单词的自身值单词自身的值是编译程序中其他阶段所需要的信息。对于单词符号来说，如果一个种别只含有一个单词符号，那么这个单词符号，其种别就安全地代表了它的自身值。如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外，还应该给出单词符号自身的值，以便把同一种单词区别开来。注意，标识符自身的值就是标识

6、符自身的字符串。而常数自身的值是常数本身的二进制数值。3.1.3一个简单的词法分析程序的设计1．预处理词法分析器在识别单词符号之前，需要对输入区的源程序进行预处理。预处理包括删除无用的空格、跳格、回车和换行等编辑性字符以及注释部分。每一次对一串定长的输入字符进行预处理，并装进一个指定的缓冲区。2．状态转换图利用状态转换图可以设计词法分析器。状态转换图是一个有向图，仅包含有限个结点，每个结点表示一个状态，其中有一个初始结点，至少有一个终态结点，结点间弧的标记是输入字符或字符类。例3.2有状态转换图3-4所示

7、，其中，0结点用‘S’标记，表示初态结点；2结点用‘E’标记，表示终态结点。从初态结点出发到某一终态结点所经过的路径，称为能为该状态转换图所接受的符号串。012SE字母其它字符图3-4扫描缓冲区字母或数字012SE字母非字母、数字35678146174E数字数字+——*—=—（）；/其他EEEEEEE11109非数字126136166156EEEE非**=—非=图3-6识别各类单词符号的状态集合字母或数字—+++++++++++E+词法分析程序的构造如下：初始化：arr：=′′;getch;getnbc;

8、casechof′a′‥′z′:beginwhileletterordigitdobeginconcat;getchend;retract;c:=reserve;ifc=0thenreturn(1，arr);elsereturn(c,);end;′0′‥′9′:beginwhiledigitdobeginconcat;getch;end;retract;return(2,dtb);end;′+′:return(31,);′－′