编译原理：第4章 词法分析

1、第4章 词法分析 词法分析器 完成词法分析任务的程序段；可作为独立的程序；可作为独立的子程序： 对源程序进行扫描，从中识别各个单词符号。输出数对（单词类别，单词号值）单词符号 程序设计语言的基本语法单位和最小语义单位单词符号的种类： 关键字 用户标识符 常量 运算符 分界符扫描程序的设计 状态转换图4.4 词法分析程序的直接分析方法由正规文法设计词法分析程序正规文法FADFA最小化 例：用户标识符文法( l字母，d数字) GI: IlA | l AlA | dA | l | d4.4 词法分析程序的直接分析方法由正规表达式设计词法分析程序正规表达式NDFADFA最小化 例：用户标识符正规表达式

2、( l字母，d数字) l(l |d)* 词法分析的主要任务是对源程序进行扫描，从中识别出单词，它是编译过程的第一步，也是编译过程中不可缺少的部分。本章介绍词法分析程序的手工构造和自动构造原理。 4.1 词法分析概述 词法分析的任务是：从左至右逐个字符地扫描源程序形式的字符流，将这些单个字符组合成一个个单词符号，把作为字符串的源程序转换成由单词符号串组成的中间语言程序供语法分析使用。因此，词法分析是编译程序的基础。把词法分析从语法分析中独立出来有下述优点： 部分编译时间花费在扫描字符上。 单词符号的语法可以用非常简单的文法加以描述。 对同一语言来说，常有不同的表示方法。 高级语言时，需要考虑词法

3、和语法两方面的特性，若把两者分开，有利于分别地研究它们。可以把词法分析程序作为独立的一遍去编写，它实现源程序的全部词法分析工作，并把转换后的内部形式的源程序传递给语法分析程序。也可以把它设计成一个子程序 (如有图所示)。4.2 单词符号单词符号是语言的基本符号，它具有独立的意义且是不可再分的。程序语言中的大部分单词符号都属于下述几类之一。 标识符。用以表示各种名字，如变量名，过程名等等； 保留字（或键字）。如if，goto，begin，end等等，它实质上是标识符的一个子集。 整数。125，38，0，1等等； 单分界符。如，*，/，（，），；，等等； 复合分界符。如+，/*，+等等。例4.1

4、识别标识符的状态转换图如下左图所示：其中0为初态，2为终态，它识别标识符的过程为：从初态0开始，若输入符号识一字母，则读进它，并转到状态1；在状态1下，若下一个输入符号是字母或数字则读进它，并重新进入状态1；重复这个过程，直至在状态1下发现读入的符号不再是字母或数字时(注意，此时该字符已被读出)，就进入状态2。状态2是终态，它意指至此已识别出一个标识符，识别过程终止。若在状态0下输入符号不是字母，则意味着识别不出所给的输入串是一个标识符。4.3 扫描程序的设计下面用一个比较简单的语言作为例子来讨论扫描程序的设计。假定该语言中有分界符或运算符（如，*，/，（，），键字（如begin，abs，en

5、d），标识符（非保留字）以及整数。至少要有一个空白符将相邻的标识符、整数和（或）键字隔开，但不能用空白符将符号中的相邻字符分开。此外，注解是以符号/*开始，并以符号*/的第一次出现作为结束的。 扫描程序构造每个单词符号的内部表示，这种表示通常是一个定长的整数。编译程序的其余部分将只加工这些定长的整数。下表给出了这些符号的内部表示。 例 4.3 对于程序段begin A+B*C/* Comment */ end扫描程序将产生下面的结果：状态转换图可用于识别符号串，而且使识别工作直观化。因此我们先画一个用于识别符号的转换图。 添加动作后的状态转换图: 根据转换图编写出扫描程序。该程序有两个参数：S

6、YN和SEM，其中，SYN表示所标识的那个单词符号的内部表示；SEM是组成该符号的字符串。SYN和SEM可以是两个全局量，它们的作用域即扫描程序本身以及所有调用它的地方。该过程使用了Case语句，它根据Char中字符的类型数进行判断处理。Procedure SCAN(SYN:integer;SEM:string); begin start:GETNB;Token:= ;Case Class of1:begin while Calss=1 do begin Token:=Token CAT Char; GETCHAR; end; SYN:=$INT; end;2:begin while clas

7、s=2 do begin Token:=Token CAT Char; GETCHAR; end;SYN:=$ID; LOOKUP(Token); if add0 then SYN:=add; end;3:begin Token:=Char;GETCHAR; if Char= * then begin h1:GETCHAR; h2:if Char*then go to h1; GETCHAR; if Char/ then goto h2; GETCHAR;goto start; end else SYN:=$SLASH end;4:begin LOOKUP(Token); SYN:=add;G

8、ETCHAR; end;other:begin ERROR;GETCHAR;goto start; end;end of case;SEM:=Token;end.4.4 标识符的处理在词法分析中，标识符的处理比其它单词的处理复杂得多，且涉及得面也很广，因此，在编译程序中，标识符得处理占有极为重要得位置。标识符得处理主要包括其语义表示、作用域处理、符号表构造以及内存单元分配等工作。标识符处理得难易程度依赖于语言的数据结构的复杂程度。一般，数据结构越复杂，标识符的处理也就越复杂。 4.4.1 类型的机内表示所讨论的PASCAL子集只有如下类型：整型 integer实型 real布尔型 boolea

9、n数组 arrayn1n2 of T;记录 record id1:T1;idn:Tn end(j=1,2,n)其中n1,n2为整型数；T，T1为上述五种类型之一；idj(j=1,2,n)为标识符。我们用一种称之为类型信息表的表格TypeTab来登陆类型信息，它的每一项的结构为： 其中Tclass用以指明类型的五种种类，即：这里，我们采用一种简化的数组信息表AinfTab，它的每一项的结构为：简化的记录信息表RinfTab中的每一项的结构为：综合上述内容，类型的内部表示可概括为： 设某记录类型的RinfTab表如下：RinfTabrp: 用length(ftp)表示类型ftp的长度，则有此外，我

10、们假定，integer,real,boolean作为标准类型，其内部表示已预先存放在类型表TypeTab中，且其地址分别为itp,rtp和btp,并假定length(itp)=length(rtp)= length(btp)=1为直观起见，总是用常数本身和标识符本身代替它们在相应表中的地址。4.4.2 标识符的语义表示程序中标识符的出现分为定义性出现和使用性出现两大类，前者系指在说明部分出现的标识符，后者是指在语句部分出现的标识符。 标识符定义性部分确定定义性标识符的语义，主要包括标识符的种类，类型及地址等信息。在我们假定的语言中，标识符的种类有：常量；类型；变量；过程或函数。标识符语义字的一

11、种参考结构为：其中class的具体结构可考虑为：综上所述，我们可得到如下形式的标识符的语义字：4.4.3 符号表（标识符表）符号表在编译程序中具有十分重要的意义，它是编译程序中不可缺少的部分。在编译程序中，符号表用来存放在程序中出现的各种标识符及其语义属性。 标识符表SymbTab的一般结构如下所示：如前所述，在程序中，标识符分为定义性出现和实用性出现两大类。在我们假定的语言中，定义性标识符的出现情况如下： CONST id=，id=; TYPE id=，id=; VAR id,id,，id,:T; id,id,，id,:T; PROCEDURE id(VAR id,，id:T;id,id:T

12、;PROCEDURE id();FUNCTION id():T):T; FUNCTION id(VAR id,，id:T;id,id:T;PROCEDURE id();FUNCTION id():T): T; RECORD id1:T1,idn:Tn END;标识符的作用域由以下四种语法单位划定： PROGRAMEND,程序段在其首部定义性出现的标识符为全局量。 PROCEDUREEND；过程段 FUNCTIONEND；函数段在过程段和函数段中可包含形参、局部量和全局量。 RECORDEND；记录类型域名的作用域是包含它的最小记录类型。 4.4.4 标识符处理的基本思想标识符处理的基本思想是：

13、 每当进入新的一层时，记住本层标识符表SympTab的初始地址； 当遇到定义性标识符时，构造其语义字并去查本层的标识符表。 当编译程序遇到使用性标识符时，也要去查标识符表，在标识符表中必须已登记过此标识符，否则会出现“此标识符未定义”的错误。 每当结束（退出）一层的时，“删除”本层的SymbTab表。4.5 设计词法分析程序的直接方法在具体实现过程中，可把词法分析设计成一个子程序，即在扫描源程序时，一旦识别出标识符、保留字、常数和分界符之一，就可形成相应的单词并传递给所需部分。 在具体实现时，可将各类单词设计成结构和长度均相同的形式，例如，每一单词可设计成如下形式：(type,pointer)其中type指明单词的种类，例如： k 关键字（可事先构造好） i标识符 c常数s分界符（可事先构造好）point指向本单词存放处的开始位置。 将词法分析程序设计成子程序的框图 :4.6 与设计扫描程序相关的几个问题设计扫描程序时，会遇到下面一些问题。首先，应注意的是一般应构造尽