宿迁学院三系 编译原理第三章 词法分析编译原理第2页宿迁学院三系词法分析l这一章将讨论词法分析程序的构造。l词法分析的任务：从左至右逐个字符地对源程序 进行扫描，产生一个个的单词符号，把作为字符 串的源程序改造成为单词符号串的中间程序。l前一部分讨论手工构造方法，后一部分讨论自动 构造方法。 编译原理第3页宿迁学院三系词法分析3.1对于词法分析器的要求 l词法分析器的功能和输出形式l词法分析器的功能是输入源程序，输出单词符号 。单词符号是一个程序语言的基本语法符号。程 序语言的单词符号一般可分为下列五种。 (1)关键字（保留字或基本字） (2)标识符 (3)常数（整型、实型、布尔型、文字型等） (4)运算符。 (5)界符(逗号、分号、括号、*，*等)。编译原理第4页宿迁学院三系词法分析l词法分析器所输出的单词符号常常表示成如下的 二元式：（单词种别，单词符号的属性值）编译原理第5页宿迁学院三系词法分析考虑下述c代码段： while（i=j）i-; 经词法分析器处理后，它将被转换为如下的单词符号序列： while，- （，- id，指向i的符号表项的指针 ，- id,指向i的符号表项的指针 ），- id，指向i的符号表项的指针 -，- ；，-编译原理第6页宿迁学院三系词法分析词法分析器作为一个独立子程序 l可使整个编译程序的结构更简沽、清晰和条理化 。 l也可以把词法分析器安排成一个子程序，每当语 法分析器需要一个单词符号时就调用这个子程序 。每一次调用，词法分析器就从输人串中识别出 一个单词符号，把它交给语法分析器。编译原理第7页宿迁学院三系词法分析3.2词法分析器的设计 l输入、预处理 词法分析器工作的第一步是输入源程序文本。输入 串一般是放在一个缓冲区中，这个缓冲区称输入 缓冲区。编译原理第8页宿迁学院三系词法分析编译原理第9页宿迁学院三系词法分析l扫描缓冲区进行扫描时一般用两个指示器，一个 指向当前正在识别的单词的开始位置（指向新单 词的首字符），另一个用于向前搜索以寻找单词 的终点。起点指示器搜索指示器编译原理第10页宿迁学院三系词法分析超前扫描关健字的识别 ：（如FORTRAN语言 ) 1 D099K1，10 2 IF（5 EQM）I=10 3 D099K1 10 4 IF(5)55编译原理第11页宿迁学院三系词法分析l标识符的识别 l常数的识别l算符和界符的识别编译原理第12页宿迁学院三系词法分析状态转换图 l转换图是一张有限方向图。在状态转换图中，结 点代表状态，用圆圈表示。状态之间用箭弧连结 。箭弧上的标记（字符）代表在射出结点（即箭 弧始结点）状态下可能出现的输入字符或字符类 。l一张转换图只包含有限个状态（即有限个结点） ，其中有一个被认为是初态，而且实际上至少要 有一个终态（用双圈表示）。一个状态转换图可 用于识别（或接受）一定的字符串。编译原理第13页宿迁学院三系词法分析123XY012字母字母或 数字 其它012数字数字其它编译原理第14页宿迁学院三系词法分析06123457.数字数字数字数字数字数字数字E或DE或D+或-其它*其它.编译原理第15页宿迁学院三系词法分析状态转换图的实现(1) ch 字符变量，存放最新读进的源程序字符。 (2) strToken 字符数组，存放构成单词符号的字符串。 (3) GetChar 子程序过程，将下一输入字符读到ch中，搜 索指示器前移一字符位置。 (4) GetBC 子程序讨程检杳ch中的字符是否为空白。 若是，则调用GetChar直至ch中进入一个非空白字符 (5) Concat 子程序过程，将ch中的字符连接到 strToken之后。编译原理第16页宿迁学院三系词法分析(6) IsLetter和IsDigit 布尔函数过程，它们分别判断ch中的 字符是否为字母和数字。 (7) Reserve 整型函数过程，对strToken中的字符串查找 保留字表，若它是一个保留字则返回它的编码，否则返回0 值（假定0不是保留字的编码）。 (8) Retract 子程序过程，将搜索指示器回调一个字符位置 ，将ch置为空白字符。 (9) InsertId 整型函数过程，将strToken中的标识符插入符 号表，返回符号表指针。 (10）InsertConst 整型函数过程，将strToken中的常数插 入常数表，返回常数表指针。编译原理第17页宿迁学院三系词法分析编译原理第18页宿迁学院三系词法分析对于不含回路的分叉结点来说，可让它对应一个switch语句或一组if . then . else语句。 例如，下图状态结点i所对应的程序段可表示为：GetChar(）；if（IsLetter（）状态J的对应程序段；else if（IsDigit（）状态k的对应程序段；else if（ch）状态I的对应程序段；else 错误处理；ijkl字母数字/编译原理第19页宿迁学院三系词法分析对于含回路的状态结点来说，可让它对应一个由while语句和if语句 构成的程序段。 例如，下图的状态结点i所对应的程序段可为：CetChar(）；while（IsLetter(）or IsDigit(）CetChar（）；状态j的对应程序段ij字母或数字其它编译原理第20页宿迁学院三系词法分析终态结点一般对应一个形如return（code，value） 的语句。 其中，code为单词种别编码；value或是单词符号的 属性值，或无定义。编译原理第21页宿迁学院三系词法分析3.3正规表达式与有限自动机 l正规式与正规集 正规式和正规集的递归定义： （1）和都是上的正规式，它们所表示的正规集分别为 和 (2)任何a，a是上的一个正规式，它所表示的正规集为 a； (3)假定U和V都是上的正规式，它们所表示的正规集分别记 为L(U)和L(V)，那么，(U|V)、(UV)和(U)*也都是正规式， 它们所表示的正规集分别为L(U) UL(V),L(U)L（V）（连接 积）和（L（U）*（闭包）。 仅由有限次使用上述三步骤而得到的表达式才是上的正规 式。仅由这些正规式所表示的字集才是上的正规集。 编译原理第22页宿迁学院三系词法分析l正规式的运算符，|”读为“或”，“”读为“连接”， “*”读为“闭包”（即，任意有限次的自重复连接） 。l规定算符的优先顺序为：先“*”，次“”最后 ”|”。连接符” ”一般可省略不写。编译原理第23页宿迁学院三系词法分析l例: 令=a,b，下面是上的正规式和相应的正规集：正规式 正规集ba* 上所有以b为首后跟任意多个a的字 。a(a|b) * 上所有以a为首的字。(a|b)*（aa|bb)（a|b)* 上所有含有两个相继的a或两个相 继的b的字。 l例3.2令=A，B，0，1，则正规式 正规集(A|B）（A|B|0|1)* 上的“标识符”的全体 (0|1)(0|1)* 上的“数”的全体。编译原理第24页宿迁学院三系词法分析l若两个正规式所表示的正规集相同，则认为二者等价。两 个等价的正规式U和V记为U =V。l例如，b（ab）*=（ba）*b，（a|b）*=（a*b*）*。l令U、V和W均为正规式，显而易见，下列关系普遍成立： （1）U|V=V|U（交换律）；(2） U|（V | W）=（U | V） | W（结合律）(3) U（VW）=（UV）W（结合律）；(4） U（V | W）UV | UW（分配律）(V | W)UVU | WU；(5）U=UU编译原理第25页宿迁学院三系词法分析确定有限自动机（DFA ) l一个确定有限自动机（DFA）M是一个五元式M（S，,s0，F) 其中 （1) S是一个有限集，它的每个元素称为一个状态。(2) 是一个有穷字母表，它的每个元素称为一个 输入字符。(3) 是一个从Sx至S的单值部分映射。(s，a) s 意味着：当现行状态为s、输入字符为a时， 将转换到下一状态s。我们称s为s的一个后继状 态。(4) s0S,是唯一的初态。(5) FS,是一个终态集（可空）.编译原理第26页宿迁学院三系词法分析l状态转换矩阵l例如，有DFA M=(0,1,2,3，a,b，0， 3) 其中为 (0,a)1 (0,b)2 (1,a)3 (1,b)=2 (2,a)l (2,b）=3 (3,a)3 (3,b）=3 它所对应的状态转换矩阵如表所列 状态ab 012132213333编译原理第27页宿迁学院三系词法分析l一个DFA也可表示成一张（确定的）状态转换图 。1203aaabbba/b编译原理第28页宿迁学院三系词法分析l对于*中的任何字，若存在一条从初态结点到 某一终态结点的通路，且这条通路上所有弧的标 记符连接成的字等于，则称可为DFA M所识 别（读出或接受）。l若M的初态结点同时又是终态结点，则空字可为 M所识别（或接受）。lDFA M 所能识别的字的全体记为L(M）。 编译原理第29页宿迁学院三系词法分析l如果一个DFA M的输入字母表为，则我们也称M 是上的一个DFA。l可以证明：上的一个字集V*是正规的，当且 仅当存在上的DFA M,使得VL(M) 。编译原理第30页宿迁学院三系词法分析非确定有限自动机（NFA) l一个非确定有限自动机（NFA) M是一个五元式M（S，S0,F)其中 （1）S同3.3.2的1；(2）同332的2；(3) 是一个从S*到S的子集的映照，即: S *2的s次方(4) S0S，是一个非空初态集；(5) FS，是一个终态集（可空）。编译原理第31页宿迁学院三系词法分析NFA和DFA的主要区别：(1)NFA可有若干初态, DFA仅有一个初态； (2)NFA的状态转换函数f是一多值函数，即f(si, a)= 某些状态的集合，它表示由当前状态和当前输入 字符不能唯一确定下一状态，即允许同一状态对 同一输入字符可有不同输出边；而DFA的状态转 换函数f是一个单值函数。编译原理第32页宿迁学院三系词法分析l一个含有m个状态和n个输入字符的NFA可表示成 如下的状态转换图：l该图含有m个状态结点，每个结点可射出若干条箭 弧与别的结点相连接，每条弧用*中的一个字（ 不一定要不同的字而且可以是空字）作标记（ 称为输入字），整张图至少含有一个初态结点以 及若干个（可以是0个）终态结点。某些结点既可 以是初态结点也可以是终态结点。编译原理第33页宿迁学院三系词法分析l对于*中的任何一个字，若存在一条从某一初 态结点到某一终态结点的通路，且这条通路上所 有弧的标记字依序连接成的字（忽略那些标记为 的弧）等于,则称可为NFA M所识别（读出 或接受）。l若M的某些结点既是初态结点又是终态结点，或者 存在一条从某个初态结点到某个终态结点的通 路，那么，空字可为M所接受。编译原理第34页宿迁学院三系词法分析l例如，下图就是一个NFA,这个NFA所能识别的也是所有含有相