工学第四章词法分析1课件

1、第四章 词法分析词法分析是编译过程的第一步，其主要任务是对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析是编译的基础。词法分析：根据词法规则识别及组合单词，进行词法检查。对数字常数完成数字字符串到（二进制）数值的转换。删去空格字符和注解。7/27/20221第四章：词法分析4.1 词法分析程序的设计任务执行词法分析的程序称为词法分析器.词法分析器的功能是输入源程序,输出单词符号.单词符号是一个程序语言的基本符号。7/27/20222第四章：词法分析4.1.2词法分析程序的输出程序语言的单词符号一般分为五种:关键字

2、: 由程序语言定义的具有固定意义的标识符。有时称这些标识符为保留字或基本字。例如，Pascal中的begin，end，if,while等。标识符:用来表示各种名字,如:变量名,数组名等. 常数: 整型,实型,布尔型等.运算符: + - * / 等.界符:逗号,分号,括号,/*, */等.一个程序语言的关键字,运算符,界符都是确定的,一般只有几十或上百个,而对标识符和常数的使用都不加什么限制.7/27/20223第四章：词法分析单词符号的表示单词符号常常表示成如下二元式: (单词种别, 单词符号的属性值)单词种别可用以下形式表示:单词种别通常用整数编码.一个语言的单词符号如何分种，分成几种，怎样

3、编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归一种。常数则宜按类型分种。关键字可将其全体视为一种，也可以一字一种。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。一类单词统一用一个整数值代表其属性如 1 代表保留字,2 代表标识符等.每一个单词一个类别.如 1 代表BEGIN,2 代表END等.7/27/20224第四章：词法分析如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。属性值

4、:单词符号的属性是指单词符号的特性或特征.属性值则是反应特性或特征的值.例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。在本书中，假定关键字、运算符和界符都是一符一种。对于它们词法分析器只给出某种别编码，不给出它自身的值。标识符单列一种。常数按类型分种类。7/27/20225第四章：词法分析1）按单词种类分类单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符类别编码1234567单词值内部字符串整数值数值0 或 1内部字符串保留字或内部编码分界符或内部编码7/27/20226第四章：词法分析2）

5、保留字和分界符采用一符一类单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数IFTHENELSEFOR:+*,(类别编码123456789.20212223.单词值内部字符串整数值数值0 或 1内部字符串-.-7/27/20227第四章：词法分析考虑下述C+代码段：while (i=j) i-; 经词法分析器处理后，它将被转换为如下的单词符号序列： =,- 7/27/20228第四章：词法分析词法分析程序的实现方案1. 词法分析单独作为一遍S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串优点: 结构清晰、各遍功能单一缺点：效率低2. 词法分析程序作为单独的子程序

6、S.P.(字符串)词法分析程序语法分析程序取单词单词7/27/20229第四章：词法分析词法分析器的设计输入、预处理 1.输入缓冲区：词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称为输入缓冲区。 2.预处理：就是将程序语言中的空白符、跳格符、回车符、换行符和注解等编辑性字符剔掉。 3.预处理子程序：就是用来完成编译的预处理。 4.分析器：分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置，另一个用于向前搜索以寻找单词的终点。不论扫描缓冲区设得多大都不能保证单词符号不会被它的边界所打断。因此，扫描缓冲区最好使用一个如下所示的一分

7、为二的区域： 起点指示器 搜索指示器这意味着对标识符和常数的长度实际上必须加以限制，否则，即使缓冲区再大也无济于事。7/27/202210第四章：词法分析词法分析器的工作方式7/27/202211第四章：词法分析单词符号的识别：超前搜索在某些语言中，要识别一个单词符号必须超前看若干字符，直到能区别开这些单词为止，常应用在如下几个方面： 关键字的识别；标识符的识别；常数的识别；算符和界符的识别；7/27/202212第四章：词法分析例：关键字的识别在FORTRAN语言中，关键字和用户自定义的标示符或标号之间没有特殊的界符作间隔，所以识别比较麻烦，看如下例子：1 DO99K=1,102 IF(5.

8、EQ.M) I=103 DO99K=1.104 IF(5)=55语句1、3的区别在于等号之后的第一个界符：一个为逗点，另一个为句末符。所以一直搜索到这里 才能区分开1句是DO语句，3语句是赋值句。语句2、4主要区别在于右括号之后的第一个字符：一个为字母，另一个为等号。所以也只能搜索到该字符才能得到语句2是IF语句，语句4是赋值句。7/27/202213第四章：词法分析4.2单词的描述工具程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立词法分析技术，进而可以建立词法分析程序的自动构造方法。多数程序设计语言的单词的语法都能用正规文法来描述。

9、7/27/202214第四章：词法分析4.2.1正规文法文法G=(N，T，) G的任何产生式为AB或A，其中VT*，A，B VN。书上P52的例子都是用正规文法表示的。在这里注意可以为，所以右边的表达式可能是非终结符、终结符或终结符加上非终结符。可以看例子中那些规则分别属于那种类型。7/27/202215第四章：词法分析4.2.2正规式对于字母表而言,正规式和它所代表的正规集的递归定义为:和是正规式,它们所表示的正规集分别为 和;任何a, a是上的一个正规式,它所表示的正规集为a ;假定U和V都是上的正规式,它们所表示的正规集分别为L(U)和L(V),那么,(U|V),(U*V),(U)* 也

10、都是正规式,它们所表示的正规集分别为L(U)L(V),L(U)L(V)(连接积)和(L(U)* (闭包)。仅由有限次使用上述三步骤而得到的表达式才是上的正规式。由这些正规式所表示的字集才是上的正规集7/27/202216第四章：词法分析例4.2令=a,b,上所有正规式和相应正规集的例子有:正规式 正规集a aa|b a,bab ab ba* 上所有以b为首后跟任意多个a的字 a(a|b)* 上所有以a为首的字7/27/202217第四章：词法分析例令=A,B,0,1, 则:正规式 正规集(A|B)(A|B|0|1)* 上标识符的全体 (0|1)(0|1)* 上“数”的全体正归集是正规语言的另一

11、种表示方法。7/27/202218第四章：词法分析正规式的等价性若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U 和 V 记为U=V.例如： b(ab)*=(ba)*b (a|b)*=(a*b*)*7/27/202219第四章：词法分析注意(1)(a|b)* (2)a*b* (3)(ab)* (4)a*|b* 相互不等价12aba*b* a1b(a|b)*12ab(ab)*ax12yba*|b*7/27/202220第四章：词法分析另:U,V 和W均为正规式，下列关系普遍成立： (1) U|V=V|U (交换律） (2）U|（V|W）=（U|V）|W (结合律） (3）U（V

12、W）=（UV）W (结合律） (4) U（V|W）=UV|UW (分配律） （V|W）U =VU|WU (分配律） (5)U=U=U 是连接的恒等元素 (6) U|U=U “或”的抽取律正规式服从的代数规律7/27/202221第四章：词法分析4.2.3正规文法和正规式的等价性一个正规语言可以由正规文法定义，也可以由正规式定义。对任何正规文法，存在定义同一语言的正规式；对任何正规式，存在生成同一语言的正规文法。7/27/202222第四章：词法分析正规式转换成正规文法将上的一个正规式转换成文法=(T,N,).另其中的的T=，确定产生式和N的元素用如下办法：对任何正规式 r，选择一个非终结符号S

13、生成产生式 S r, 并将S定为G的识别符号。若x和y都是正规式，对形如Axy 的产生式，重写成AxB, By两个产生式, 其中B是新选择的非终结符号，即 BN7/27/202223第四章：词法分析正规式转换成正规文法对已转换的文法中的形如Ax*y的产生式,重写为： A xB A y B xB B y 其中B为一新非终结符.对形如A x|y 的产生式，重写为： A x , A y7/27/202224第四章：词法分析例：将R=a(a|d)*转化成相应的正规文法，令S是文法的开始符号，首先形成S a(a|d)*,然后形成SaA和A(a|d)*，再重写第二条产生式形成： SaA, A(a|d)B,

14、 A, B(a|d)B和 B 进而变换为：SaA, AaB, AdB, BaB, BdB, A和 B 7/27/202225第四章：词法分析正规文法转换成正规式即上述过程的逆过程, 转换规则为：文法产生式正规式规则1A-xB,B -yA=xy规则2A-xA|yA=x*y规则3A-x, A-yA=x|y7/27/202226第四章：词法分析例：文法GS S aA,S a,A aA,A dA,A a,A d先有 S= aA|a A=(aA|dA)|(a|d)再将A的正规式变换为A=(a|d)A|(a|d), 据表中规则2变换为A=(a|d)*|(a|d), 再将A右端代入S的正规式得： S=a(a

15、|d)*|(a(a|d)|a再利用正规式的代数变换可以此得到 S=a(a|d)* |(a|d)| S=a(a|d)* 即 a(a|d)* 为所求。7/27/202227第四章：词法分析补充：状态转换图（1）状态转换图状态转换图是一张有限方向图.它只包含有穷多个状态,即有穷多个结点，用表示；状态结点都代表文法的非终结符号,而且至少要包含一个终止状态，用表示. 状态之间用箭弧连接,箭弧上的标记指明在射出弧的结点状态下可能出现的输入字符或字符类.状态转换图实质上是语法图的一种变形。7/27/202228第四章：词法分析(2)利用状态图识别(或接受)字符串的过程从初始状态出发，按照与符号串余留部分中最

16、左字符相匹配的原则，游历状态图，直至符号串的末端为止。如果这时恰好到达终止状态，则符号串为该文法的句子；否则不是。大多数程序设计语言的单词符号都可以用状态转换图予以识别。可以用一张状态转换图或若干张状态转换图来描述一个语言的所有单词。7/27/202229第四章：词法分析(3)状态图的画法 由右线性正规文法（产生式形如 U-aW|a)构造状态转换图。除了原有代表非终结符号的状态，另增加一个终止状态Z, 对于每一条产生式U-a，从状态U向Z画一条弧，标记为a，即7/27/202230第四章：词法分析(3)状态转换图的画法对于每一条产生式U-aW，从状态U向状态W画一条弧，标记为a，即以识别符号为

17、开始状态。7/27/202231第四章：词法分析(3)状态图的画法 由左线性正规文法（产生式形如 U-Wa|a)构造状态转换图。除了原有代表非终结符号的状态，另增加一个开始状态S,对于每一条产生式U-a，从状态S向U画一条弧，标记为a，即7/27/202232第四章：词法分析(3)状态转换图的画法对于每一条产生式U-Wa，从状态W向状态U画一条弧，标记为a，即以识别符号为终止状态。7/27/202233第四章：词法分析例1:(a)表示在状态1下,若输入字符为X,则读进X,并转换到状态2.若输入字符为Y,则读进Y,并转换到状态3.(b)表示在状态0下,若输入字符是一个字母,则读进它,并转入状态1

18、.在状态1下,若下一个输入字符为字母或数字,则读进它,并重现进入状态1.一直重复这个过程,直到状态1发现输入不再是字母或数字就进入状态2.(c)为识别整数的转换图.终态结上打个星号*意味着多读进了一个不属于标识符部分的字符，应把它退还给输入串。7/27/202234第四章：词法分析例2:语言无符号整数的描述八进制数: ( OCT，值 )oct o ( 0|.|7 ) ( 0|.|7 )*十进制数: ( DEC，值 )dec 0 | ( 1|.|9 ) ( 0|.|9 )*7/27/202235第四章：词法分析整数的状态图（1/2）3421o0-70-756101-90-9十进制整数八进制整数7

19、/27/202236第四章：词法分析识别十六进制整数的状态图。将上述三个状态转换图合并为一个，得到语言无符号整数识别的状态图，方法步骤： （1）从开始状态出发；（2）选择输入符号，构成目标状态集；（3）从新状态集出发，重复（1）、（2） 7/27/202237第四章：词法分析例3:识别某个简单语言的所有单词用一些带$的特殊符号来表示种别编码和内部值7/27/202238第四章：词法分析为了对例3进行更好的说明，做了如下的限制： 1）所有关键字（如IF，WHILE等）都是“保留字”；2）对关键字不需专设对应的转换图，而只需要将他们预先安排在一张表格中；3）如果关键字、标识符和常数之间没有确定的运

20、算符或界符作间隔，则必须至少用一个空白符作间隔。 有了上述假定后，多数单词符号的识别就不必使用超前搜索技术。下图是一张识别表的单词符号的状态转换图。在图中，状态0为初态；凡带双圈者均为终态；状态13是识别不出单词符号的出错情形。7/27/202239第四章：词法分析例3的状态图：7/27/202240第四章：词法分析状态转换图的实现让每个状态结点对应一段小程序，即可用程序实现状态图。在此引进了一组全局变量和过程，将他们作为实现转换图的基本成分。它们是：1）ch 字符变量，存放最新读进的源程序字符。2）strToken 字符数组，存放构成单词符号的字符串。3）GetChar子程序过程，将下一输入

21、字符读到ch中，搜索指示器前移一字符位置。4）GetBC子程序过程，检查ch中的字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符。5）Concat子程序过程，将ch中的字符连接到strToken之后。例如，假定strToken原来的值为“AB”，而ch中存放C，经调用concat后，strToken的值就变为“ABC”。6）IsLetter和IsDigit布尔函数过程，分别判断ch中的字符是否是字母和数字7）Reserve整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值。8）Retract子程序过程，将搜索指示器回调一个

22、字符位置，将ch置为空白字符9）InsertId整型函数过程，将strToken中的标识符插入符号表，返回符号表指针10）InsertConst整型函数过程，将strToken中的常数插入常数表，返回常数表指针7/27/202241第四章：词法分析对于不含回路的分叉结点来说，可让它对应一个switch语句或一组ifthenelse语句。对应程序如下：Getchar();If (isLetter()状态j的对应程序段;Else if(isDigit()状态k的对应程序段；Else if (ch=/)状态l对应程序段；Else 错误处理；iljk字母数字/当程序执行到达“错误处理”时，意味着现行状

23、态I和当前所面临的输入串不匹配。如果后面还有状态图，出现在这个地方的代码应为：将搜索指示器回退一个位置，并令下一个状态图开始工作。如果后面没有其它状态图，则出现在上述位置的代码应进行真正的出错处理，报告源程序含有非法符号，并进行善后处理。7/27/202242第四章：词法分析对于含回路的状态结点来说，可让它对应一个由while语句和if语句构成的程序段，右图所对应的程序段可为：GetChar();While(isLetter() or isDigit()GetChar();状态j的对应程序段ij字母或数字其它终态结点一般对应一个形如return(code,value)的语句。其中，code为单词种别编码；value或是单词符号的属性值，或无定义。这个return意味着从分析器返回到调用者，一般指返回到语法分析器。凡带*的终态结点意味着多读了一个不属于现行单词符号的字符，这个字符应予退回，也就是说，必须把搜索指示器回调一字符位置。这项工作有Retract过程来完成。7/27/202243第四章：词法分析转换图3.3的词法分析器可构造如下：例3的词法分析器：int code,value;strToken :=“ ”; /*置strToken 为空串*/GetChar(); GetBC(); /*读入一字符*/if (IsLetter()begin w