第三章 词法分析 编译程序首先是在单词级别上来分析和翻译源程序的。词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器。 3。1 对词法分析器的要求 3.1.1 词法分析器功能和输出形式 输入源程序，输出单词符号。 程序语言的单词符号一般分为五种：关键字，标识符，常数，运算符，界符 第三章 词法分析

词法分析器输出的单词符号常常表示为二元式： （单词种别，单词符号的属性值） 单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码是一个技术问题。它取决于处理上的方便。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般一符一种的分法。 第三章 词法分析

如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那麽，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。 单词符号的属性是指单词符号的特征或特性。属性值则是反映特性或特征的值。例如，对于某个标识符，常将存放它有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。 第三章 词法分析

经词法分析器处理后，它将转换为如下的单词符号序列： < while, - > < ( , - > 作为例子考虑下述C++代码段： while (i>=j) i- -; 经词法分析器处理后，它将转换为如下的单词符号序列： < while, - > < ( , - > < id ,指向i的符号表项的指针 〉 < >= , - > < id ,指向j的符号表项的指针> < ) , - > < id ,指向i的符号表项的指针 > < - - , - > < ; , - > 第三章 词法分析

3.1.2 词法分析器作为独立子程序 我们把词法分析器安排成一个独立子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从符号串中识别出一个单词符号，把它交给语法分析器。这样，把词法分析器安排成一个子程序似乎比较自然。在后面的讨论中，我们假定词法分析器是按这种方式进行工作的。 第三章 词法分析

3。2 词法分析器的设计 3。2。1 输入、预处理 词法分析器工作的第一步是输入源程序文本。输入串一般放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析器的工作可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。 预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。我们可以设想构造一个预处理子程序，他完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样分析器就可以在此缓冲区中直接进行单词符号的识别工作。 第三章 词法分析

不论扫描缓冲区设得多大都不能保证单词符号不会被缓冲区的边界所打断。因此，扫描缓冲区最好使用如下一分为二的区域： 分析器对扫描缓冲区进行扫描时一般使用两个指示器，一个指向当前正在识别单词的开始位置。（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。 不论扫描缓冲区设得多大都不能保证单词符号不会被缓冲区的边界所打断。因此，扫描缓冲区最好使用如下一分为二的区域： 第三章 词法分析

假定每半个区可容120个字符，而这两个半区又是互补的。如果搜索指示器从单词起点出发搜索到半区的边缘但尚未达到单词的终点，那么就调用预处理子程序，令其把后续的120个字符装入另半区。我们认定在另半区一定可以达到单词的终点。这意味着得标示符和常数的长度实际上必须加以限制，否则即使缓冲区再大也无济于事。 第三章 词法分析

3。2。2 单词符号的识别：超前搜索 词法分析器的结构图如图3。1所示。 图3。1词法分析器 第三章 词法分析

下面我们来介绍单词符号识别的一个简单方法-----超前搜索 当词法分析器调用预处理子程序处理出一串输入字符串放进扫描缓冲区之后，分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。 下面我们来介绍单词符号识别的一个简单方法-----超前搜索 第三章 词法分析

关键字的识别 像FORTRAN这样的语言，关键字不加保护（只要不引起矛盾，用户可以用它们作为普通标识符），关键字和用户自定义的标识符或标号之间没有特殊的界符作间隔。这使得关键字的识别甚为麻烦。请看下面例子： 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.10 4 IF(5)=55 这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以某基本字开头的。语句3和4是赋值语句，它们都是以用户自定义的标识符开头的。 第三章 词法分析

为了从1、2中识别出关键字DO和IF，我们必须要能够区别1、3和区别2、4。语句1、3的区别在于等号之后的第一个界符：一个为逗号，另个为句末符。语句2、4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。这就是说，为了识别 1、2句中的关键字，我们必须超前扫描许多个字符，超前到能够肯定词性的地方为止。对于1、3来说，尽管都以‘D’和‘O’两个字母开头，但不能一见‘DO’就认定是DO语句。我们们必须超前搜索，跳过所有的字母和数字，看看是否有等号。如果有，再向前搜索。若下一个界符是逗号，则可以肯定DO应为关键字。否则，DO不构成关键字，它只是用户标识符的头两个字母。所以为了区别1和3，我们必须超前扫描到等号后的第一个界符处。 第三章 词法分析

标识符的识别、常数的识别及算符和界符的识别相类似可以参考课本P40,P41这里就不再多述。 对于2和4来说，必须超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。若此字符是字母，则得逻辑IF。若此字符为数字，则得算术IF。否则，应认为是用户自定义标识符IF. 标识符的识别、常数的识别及算符和界符的识别相类似可以参考课本P40,P41这里就不再多述。 3。2。3 状态转换图 使用状态转换图是设计词法分析器的一种好途径。转换图是一张有限方向图。在转换图中，结点代表状态，用园圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。 第三章 词法分析

例如图3。2（a)表示：在状态1下，若输入字符为X，则读进X，并转换到状态2。若输入字符为y，则读进Y，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。 图3。2状态转换图 第三章 词法分析

一个状态转换图可用于识别一定的字符串。例如，识别标识符的转换图如图3。2（b)所示。其中0为初态，2为终态。这个转换图识别标识符的过程是：从初态0开始，若在状态0下输入字符是字母，则读进它，并转入状态1。在状态1之下，若输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到发现输入字符不再是字母或数字时（这个字符已经被读进）就近入状态2。状态2是终态，它意味着到此已经识别出一个标识符。终态上打个*号，表示多读进了一个不属于标识符部分的字符，应把它退还给输入串，如果在状态0时输入字符不为“字母”，则意味着这个转换图不工作。 图3。2状态 转换图 第三章 词法分析

又如书中图3。2（c)是识别整数的转换图。其中0为初态，2为终态。 书中图3。2（d)是一个识别FORTRAN实型常数的转换图。其中0态为初态，7态为终态。 一个非常重要的事实是，大多数程序语言的单词符号都可以用转换图予以识别。作为一个综合例子，课本P42构造了一个识别某个简单语言的所有单词符号的转换图。希望同学们好好读一下。 第三章 词法分析

转换图容易用程序实现。最简单的办法是让每个状态结点对应一小段程序。 3。2。4状态转换图的实现 转换图容易用程序实现。最简单的办法是让每个状态结点对应一小段程序。 在编制程序的过程中课本引进了一组全局变量和过程。将它们作为实现转换图的基本成分。希望同学能记住它们。 第三章 词法分析

对于字母表Σ，我们感兴趣的是它的一些特殊的字集，即所谓正规集。我们使用正规式这个概念来表示正规集。 3.3 正规表达式与有限自动机 为了更好地使用状态转换图构造词法分析器，为了讨论词法分析器的自动生成，还需要将转换图的概念形式化。为此我们引入：正规式，正规集，自动机等概念。 3.3.1 正规式与正规集 对于字母表Σ，我们感兴趣的是它的一些特殊的字集，即所谓正规集。我们使用正规式这个概念来表示正规集。 第三章 词法分析

下面是正规式和正规集的定义： （1）ε和都是 Σ上的正规式，他们所表示的正规集分别为{ε} 和； （2）任何a Σ, a是Σ上的一个正规式，它所表示的正规集为{a}； （3）假定U和V都是Σ上的正规式，他们所表示的正规集分别记为L(U)和L(V),并且，(U|V), (UV)*和（U)*也都是正规式，它们所表示的正规集分别为L(U)L(V), L(U)L(V)(连接积）和（L(U))*（闭包） 仅由有限次使用上述三步骤而得到的表达式才是Σ上的正规式。仅由这些正规式所表示的字集才是Σ上的正规集。 第三章 词法分析

[3。1] 令Σ={a, b}其正规式和正规集如下： 正规式 正规集 ba* Σ上所有以b为首后跟着任意多个a 的字 通过这一节的学习，根据给出的简单正规式，应会写出其正规集。 [3。1] 令Σ={a, b}其正规式和正规集如下： 正规式 正规集 ba* Σ上所有以b为首后跟着任意多个a 的字 a(a|b)* Σ上所有以a为首的字。 （a|b)*(aa|bb)(a|b)* 正规集是 所有两各相继的a或相继 的b 的字。 第三章 词法分析

(A|B)(A|B|0|1)* Σ上的“标识符”的全体 （0|1）（0|1）* Σ上“数”的全体 正规式 正规集 (A|B)(A|B|0|1)* Σ上的“标识符”的全体 （0|1）（0|1）* Σ上“数”的全体 若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。 例如：b(ab)*=(ba)*b等 第三章 词法分析

(1)S是一个有限集，它的每个元素称为一个状态。 （2）是一个有穷字母集，它的每个元素称为一个输入字符。 3.3.2 确定有限自动机（DFA) 确定有限自动机(DFA)是一个五元式 M= (S, Σ,δ,s0, F) 其中: (1)S是一个有限集，它的每个元素称为一个状态。 （2）是一个有穷字母集，它的每个元素称为一个输入字符。 （3） δ是一个从S x 至S的单值部分映射。 δ(s,a）=S’。意味着：当现行状态为s、输入字符为a时，将转换到下一个状态S’。我们称S’为s的后继状态。 （4）S0S，是唯一的初态。 （5）FS，是一个终态机（可空） 第三章 词法分析

显然， DFA可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元表示δ(s,a）的值，该矩阵称为状态转换矩阵。 DFA也可以表示成一张（确定的）状态转换图。假定DFA M 含有m个状态n个输入字符，那末，这张图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用上的一个不同字符作标记，整张图含有唯一的初态和若干个（可以是0个）终态结点。 第三章 词法分析

若M的初态结点同时又是终态结点，则为空字可以为M所识别。DFA M所能识别的字的全体记为L(M). 第三章 词法分析

问：有几个状态？几个输入字符？并画出其转换图。L(M)=? 解：有0，1，2，3共四个状态。输入字符为a,b两个。其状态转换图如右 [例] 有DFA M=({0,1,2,3},{a,b},,0,{3}) 其中： （0,a)=1; （0,b)=2 （1,a)=3; （1,b)=2 （2,a)=1; （2,b)=3 （3,a)=3; （3,b)=3 问：有几个状态？几个输入字符？并画出其转换图。L(M)=? 解：有0，1，2，3共四个状态。输入字符为a,b两个。其状态转换图如右 L(M)为在上所有含相继两个a或相继两个b的字。 第三章 词法分析

一个非确定有限自动机（NFA)是一个五元式 M= (S, Σ,δ,S0, F) 其中: (1) S 同3。3。2的1 （2）同3。3。2的2 （3） δ是一个从S x Σ*到S的子集的映照，即 δ：S x Σ*→2s (4) S0S,是一个非空的初态集； （5）F S，是一个终态集（可空） 第三章 词法分析

显然，NFA也可以表示成一张状态转换图。假定NFA 含有m个状态n个输入字符，那末，这张图含有m个状态结点，每个结点可以射出若干条箭弧和别的结点相连接，每条箭弧用*上的一个字（不一定要不同的字而且可以是空字）作标记（称为输入字），整张图至少含有一个的初态和若干个（可以是0个）终态结点。某结点既可以是初态也可以是终态结点。 第三章 词法分析

若M的初态结点同时又是终态结点，或者存在一条某处态结点到某各终态结点的通路，则为空字可以为M所识别。 对于*中的任何一个字符，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字（忽略那些标记为的弧）等于，则称为NFA M所识别（读出或接受）。 若M的初态结点同时又是终态结点，或者存在一条某处态结点到某各终态结点的通路，则为空字可以为M所识别。 这里应注意DFA与NFA的异同点。 第三章 词法分析

显然DFA式NFA的特例。对于每个NFA M存在一个DFA M”，使L(M)=L(M”)。其证明如下（略）（这个证明需要掌握） 在这个证明中我想特别强调的是课本P49页下边提到的对M的状态转换图进一步施行图3。7所示的替换，其中k是新引入的状态。 第三章 词法分析

书中的这个图3。7同时也是从正规式画有限自动机状态转换图的重要方法。对于正规式中的连接可按1式画其转换图，对于或可用2式，对于闭包可用3式将正规式转换为状态转换图灵活使用这些规则非常重要的。 如：正规式：R=(a*b)*ba(a|b)* 可以画为： 第三章 词法分析

（a|b)*(aa|bb)(a|b)*对应的NFA 其中（a*b)* 和(a|b)*分别可以看成一个闭包。形成A和G结点。 [例]：画出正规式： （a|b)*(aa|bb)(a|b)*对应的NFA 第三章 词法分析

[例]：用状态子集法构造图3。6的状态转换矩阵： 表3。3 I Ia Ib {X,5,1} {5,3,1} {5,4,1} [例]：用状态子集法构造图3。6的状态转换矩阵： 表3。3 I Ia Ib {X,5,1} {5,3,1} {5,4,1} {5,3,1} {5,3,1,2,6,Y} {5,4,1} {5,4,1} {5,3,1} {5,4,1,2,6,Y} {5,3,1,2,6,Y} {5,3,1,2,6,Y} {5,4,1,6,Y} {5,4,1,6,Y} {5,3,1,6,Y} {5,4,1,2,6,Y} {5,4,1,2,6,Y} {5,3,1,6,Y} {5,4,1,2,6,Y} {5,3,1,6,Y} {5,3,1,2,6,Y} {5,4,1,6,Y} 第三章 词法分析

5 6 5 6 3 4 表3。4 对表3。3中状态子集从新命名后状态转 换矩阵 S a b 0 1 2 1 3 2 2 1 5 3 3 4 表3。4 对表3。3中状态子集从新命名后状态转 换矩阵 S a b 0 1 2 1 3 2 2 1 5 3 3 4 4 6 5 5 6 5 6 3 4 第三章 词法分析

图3。8 未化简DFA 第三章 词法分析

3.3.4, 3.3.5 正规文法，正规式与有限自动机的等价性 证明不作要求 3.3.6 确定有限自动机的化简 是本节应掌握的内容。(参看P56) 我们这里举个例子帮助理解这个过程： [3。6 例]：图3。8所示的化简过程是： 首先把M的状态分为两组：终态组{3，4，5，6}，和非终态组{0，1，2} 其次考察终态组，由于 {3，4，5，6}a{3,4,5,6}和 {3，4，5，6}b{3,4,5,6}所以不能再划分 第三章 词法分析

现在划分已经有3个组：{3，4，5，6}，{1}，{0，2}。 再考察{0，1，2} 由于 {0，1，2}a{1，3}，它既不属于{0，1，2}也不属于{3，4，5，6}，因此应将其一分为二，由于1态经a弧到达3态，而且状态0，2经a弧到达1态故应把1态分出形成{1}， {0，2}。 现在划分已经有3个组：{3，4，5，6}，{1}，{0，2}。 由于{0，2}b={2,5}未包括在上述分组中，故{0，2}应一分为二{0}，{2}。 到此四个分组{3，4，5，6}，{0}，{1}，{2}。每个组都不可再分。 最后，令状态3代表{3，4，5，6}。把原来到达4，5，6的弧都导入3，并删除4，5，6状态。得到化简的DFA. 第三章 词法分析

我们用正规式描述单词符号，并研究如何从正规式产生识别这些单词符号的词法分析程序。 3.4 词法分析器的自动产生 我们用正规式描述单词符号，并研究如何从正规式产生识别这些单词符号的词法分析程序。 首先介绍一个描述词法分析器的语言LEX，讨论LEX的实现，从而，用它来描述和自动产生所需的各种词法分析器。 3。4。1语言LEX的一般描述 一个LEX源程序主要包括两部分。一部分是正规定义式，另一部分是识别规则 第三章 词法分析

为超前搜索，我们引进一个正规式运算符‘/’，用它来指出一个单词符号的截取点。于是关于“DO”的识别规则可以写为： 3。4。2超前搜索 为超前搜索，我们引进一个正规式运算符‘/’，用它来指出一个单词符号的截取点。于是关于“DO”的识别规则可以写为： DO/(letter|digit)*=(letter|digit)*,{动作} 这意味着要求词法分析器L向前扫描到逗号处，识别除具有下列词形的输入子串： DO/(letter|digit)*=(letter|digit)* 在寻找到这种匹配后，就按识别规则中斜线所指处将输入串截断，取其前一部分字串作为词法分析器的输出，而将后一部分归还输入串。 3。4。3 LEX的实现 请读书P61. 第三章 词法分析

例题与习题解答 [例3。1]写能被5整除的十进制整数的文法及正则表达式。 解：能被5整除的文法： G[Z]: Z→(+|- )A(0|5) 　　　　A→0|1|2|3|4|5|6|7|8|9|AA 　　如果要求：除零以外不以0开头，责文法为： G[Z]: Z→(+|- ) A (0|5) A→AB|C B→0|C|BB C→ 0|1|2|3|4|5|6|7|8|9 正则表达式：G[Z]: Z= (+| - )A*(0|5) A∈(0,1,2,3,4,5,6,7,8,9) 第三章 词法分析

写一个文法，使其语言是奇数集，且每个奇数不以0开头。 [例3。2] 写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：文法G(N)： 　　　　　 　N→AB|B 　　　　　 　A→AC|D 　　　　　 　B→1|3|5|7|9 　　　　　 　D→B|2|4|6|8 　　　　　 　C→0|D　　　　　 第三章 词法分析

[例3。3]写出能被3整除十进制整数的文法和正则表达式： 解： 能被3整除的文法： G=( {0,1,2,3,4,5,6,7,8,9},{S, A, B}, S, P,) 其中P为： S -> (0|3|6|9)S|ε S -> (1|4|7)A|(2|5|8)B A -> (0|3|6|9)A|(1|4|7)B|(2|5|8)S B -> (0|3|6|9)B|(2|5|8)A|(1|4|7)S 整则表达式： Z= a*| (bc)*|(cb)*|(a|cibi)*|(ciabi)*(i>= 1) a∈(0,3,6,9) b∈(1,4,7) c∈(2,5,8)　 第三章 词法分析

(1)以上状态转换图表示的语言有什么特征？ (2)写出其正规式与正规文法. (3)构造识别该语言的有限自动机DFA. [例3。4]：已知有限自动机如图 (1)以上状态转换图表示的语言有什么特征？ (2)写出其正规式与正规文法. (3)构造识别该语言的有限自动机DFA. 第三章 词法分析

（1） L={W |W {0,1},并且W至少有两个连续的1} （2） 正则式为（0|1)*11(0|1)* 正则文法G(Z)为： 解： （1） L={W |W {0,1},并且W至少有两个连续的1} （2） 正则式为（0|1)*11(0|1)* 正则文法G(Z)为： Z0Z|1Z|1A A 1B|1 B 0B|1B|0|1 （3）将图中有限自动机确定化： 首先从处态A出发： 第三章 词法分析

I I0 I1 (1){A} (1){A} (2) {A,B} (2){A,B} (1){A} (3){A,B,C} (3){A,B,C} (4){A,C} (3){A,B,C} (4){A,C} (4){A,C} (3){A,B,C} 其相应的DFA如下图： 第三章 词法分析

由于状态1输入1到达状态K1集，而状态2输入1到达K2集故将k1分为 K11={1}, K12={2} 将这个DFA最小化： 首先分终态和非终态两个集 K1={1,2} 和 K2={3,4} 由于状态1输入1到达状态K1集，而状态2输入1到达K2集故将k1分为 K11={1}, K12={2} 由于状态3，和 4 输入1，或0 都到达k2集所以状态3，4等价。 则可以分割成三个子集： {1}，{2}，{3，4} 第三章 词法分析

所以将DFA最小化的状态图如下： 第三章 词法分析

[例3.5]请构造与正则式R=(a*b)*ba(a|b)* 等价的状态最少的DFA（确定有限自动机） 解： （1）首先构造转换系统图： （2）由系统转换图构造DFA（NFA确定化） 设初态为[S, A, B, G,F] 第三章 词法分析

NFA确定化为DFA的过程： I Ia Ib (1)[S,A,B,G,F] (2)[G,F] (3)[A,B,C,G,F] (2)[G,F] (2)[G,F] (4)[A,B,G,F] (3) [A,B,C,G,F] (5)[D,F,G,E,Z] (3)[A,B,C,G,F] (4)[A,B,G,F] (2)[G,F] (3)[A,B,C,G,F] (5)[D,F,G,E,Z] (6)[G,F,E,Z] (7)[A,B,E,Z,G,F] (6)[G,F,E,Z] (6)[G,F,E,Z] (7)[A,B,E,Z,G,F] (7)[A,B,E,Z,G,F] (6)[G,F,E,Z] (8)[A,B,C,E,Z,G,F] (8)[A,B,C,E,Z,G,F] (5)[D,F,G,E,Z] (8)[A,B,C,E,Z,G,F] DFA 这状态图如下： 第三章 词法分析

确定有限自动机图如下： 第三章 词法分析

（3）将DFA最小化：先将终态和非终态分成两个集: K1={1,2,3,4} , K2={5,6,7,8} 对于K1中的3态输入a则进入K2集，而1，2，4态输入a仍然在K1中，故K1可一分为二K11={1,2,4}和K12={3}; 考察K11对于1，4态输入b到达3态而2态输入b到达4态。故K11可一分为二K111={1,4}; K112={2}最后考察K2输入a或b都到达K2集。则DFA化简为{1，4}，{2}，{3}，{5，6，7，8}四个子集。其状态图如下： 第三章 词法分析

第四章 语法分析——自上而下分析（1） 4.1 语法分析器功能 下图表明了语法分析器在编译程序中的地位。 单词符号 语法分析树 词法分析器 编译后续 取下一个单词符号 符号表 第三章 词法分析