词法分析第三章 主要内容：词法分析的任务，手工实现 词法分析程序，正规式与有穷自动机， 词法分析程序的自动生成 重点掌握：词法分析器的功能和接口， 用状态转换图设计和实现词法分析程序 ，正规文法、正规式和有穷状态自动机 的概念及相互转换本章要求词法分析 程序所处 的位置：语法 分析 器词法 分析 器符号 表编译 程序 的后 续部 分to ke n取下一个 单词语法 树3.1 词法分析器的功能 功能： 逐个读入源程序字符并按照构词规则切分成一系列单词 主要任务： 读入源程序，输出单词符号 其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，指出源程序出错的行列位置 宏展开， 关键：找出单词的分隔符源程序词法分析程序Token串 语法分析程序 单词：是语言中具有独立意义的最小单位，常用单 词分类： 保留字：具有固定意义的标识符 运算符 界符 标识符：表示各种名字 常数 对于一个程序设计语言，保留字、运算符和界符都 是确定的，可以给以固定的编号(种别码)。 标识符是根据构词规则定义的，常数是符合定义的 各种类型的常数 种别码：是对能识别的单词的分类编码 有多种编码方式： 标识符一般统一为一种：一个编号 常数按类型分别编码：整数、实数、布尔、字符 关键字一般一字一种 运算符一般一符一种 界符一般一符一种某语言 单词的 种别码 定义举 例单词种别码单词种别码单词种别码 and1procedure21*41 array2program22*/42 begin3read23+43 bool4real24，44 call5repeat2545 case6set26、46 char7then27 47 constant8to28/48 do9true29/*49 else10until30：50 end11var31:=51 false12while32；52 for13write3355 integer16实常数36=56 not17字符常数3757 of1838=58 or19(3959 output20)4060词法分析器的输出 1. Token串: 输出源文件中各个有用的单词 格式： (单词的种别码，单词符号的属性值) 单词种别：是对能识别的单词的分类编码(P42) 单词符号的属性值：单词的某种特性或特征 常数的值，标识符的名字等 保留字、运算符、分界符的属性值可以省略 文件存放最好有格式，如每个单词占一行方便“ 语法分析”程序调用 P38 例this is a sample program writing in simple language program example1; used for illustrating compiling process var a,b,c:integer; x:char; begin if (a+c*3 b) and (b3) then c:=3; end.program example1 ; var a , b , c : integer ; x : char ; begin if ( a +c * 3 b ) and ( b 3 ) then c := 3 ; end .源程序 token文件注意token文 件的格式举例 2. 符号表 各种常数和标识符一般放在符号表中，在输出的 token文件中的单词属性值则存放单词在符号表中 的指针 符号表的格式：字符串 if (ab2) test:=3;格式1：(数组)入口单词名及长度类型种属值内存地址1a1整简单变 量未知未知2b22整简单变 量未知未知3test4实简单变 量未知未知 格式2：(用指针)this is a sample program writing in simple language program example1; used for illustrating compiling process var a,b,c:integer; x:char; begin if (a+c*3 b) and (b3) then c:=3; End.源程序 符号表举例 3. 其它输出：错误信息和源程序清单 错误信息应该详细，准确，指出出错的具体行 、列位置，发生了哪类错误等，方便用户修改错误处理 应尽可能发现更多的错误 处理方式 每个程序段单独处理错误 统一处理错误（商用软件系统） 记录式的文件 数据库 统计表明，现代软件系统中， 75%的程序代码都 是用于处理错误与错误信息 商业系统中错误处理的特点是：统一错误编号，编 制文档指出错误信息的含义、应对措施、解决方案词法错误类型非法字符 单词拼写错误 难以发现下面的错误 fi (a = x ) 在实数是a.b格式下，可以发现下面的错误 123. 词法分析是编译过程中的一个阶段，在语法分析 前进行。可以作为一个独立的子程序，独立出来 的原因： 简化设计 改进编译效率 增加编译系统的可移植性 可以和语法分析结合在一起作为一遍，由语法分 析程序调用词法分析程序来获得当前单词供语法 分析使用。3.2 词法分析程序的设计扫描器的任务4组织源程序的输入； 4按规则拼单词，并转换成二元式形式； 4删除注解行、空格及无用符号； 4行计数、列计数； 4列表打印源程序； 4发现并定位词法错误； 4如需要，还要建立关键字表、符号表、常数表 等表格。词法分析程序的接口 识别单词前作如下假定： 关键字就是保留字 单词中间不能有分界符(如空格、空白、界符和 算符等) 单词中间不能有注释 单词必须在一行内写完，换行后认为是另一个 单词 一个单词不能超过规定长度识别单词 主要包括如下几种单词的识别： 标识符的识别：字母+(字母/数字) 关键字的识别：与标识符相同，最后查表 常数的识别 界符和算符的识别超前搜索技术：如在读取/* */时，当读到/时， 如何判别是注释还是除法运算？识别单词：掌握单词的构成规则很重要单词的构成规则用状态转换图表示状态转换图是一张有限方向图。有限个状态，用结点表示状 态，其中有一个初态(初态用箭头指出)，至少有一个终态(终 态用双圈表示)。状态之间用带箭头的弧线连结，弧线上标记 的字符表示在射出状态下可能出现的输入字符或字符类。识别标识符的转换图012字母字母或数字其它*一个状态图可用于识别一定的字符串，大多数程序 设计语言的单词符号都可以用转换图来识别。识别过程是：从初始状态0开始，若读入一个字母， 转入1状态，若再读入字母或数字，仍处于1状态 ，否则转向2状态，结束一个标识符的识别过程。 状态上的*表示多读入一个符号。012字母字母或数字其它*写成C语言的函数形式： recog_id() char state = 0;ch = getch();do switch(state)Case 0: if ch 是字母 state = 1; ch = getch();break;Case 1: if ch 是字母或数字 state = 1; ch = getch(); else state = 2; break; while (state != 2); 回退一个符号。 012字母字母或数字其它*012 数字数字其它识别整数的转换图*练 习 1 画出Pascal中无符号实数的状态转换图 (不带正负号 ，可表示整数、可表示小数，可带指数部分) 如：下面几个数应该是符合规则的数：3，3.51，34E3,34.5E2,34.5E+2,34.5E-2练 习 2 画出识别标识符和整常数(可带正负号)的状 态转换图 练 习 3 以下状态转换图接受的字符集合是什么？XY001状态转换图的实 现：使用一个 switch case 语 句：每条分支对 应一个case语句 段 见书P45 例某简单语言的词法 分析程序的实现词法分析器的自动生成 正规式 正规文法 有穷自动机3.3 正规文法、正规式与有 限自动机 本节要求 1 能根据自然语言描述构造NFA 2 掌握NFA转换为DFA，DFA的化简 3 掌握正规文法、正规式和有穷自动机间 的转换 为了讨论词法分析程序的自动生成问题， 将状态转换图加以形式化。一、正规文法 正规文法：文法G=(VN，VT，P，S)中的每个产生 式的形式都是AaB或Aa，其中A和B都是非终结 符，a是终结符串。下面定义的标识符和无符号整数都是正规文法： letter | letter字母数字 letter | digit | letter字母数字| digit字母数字digit | digit无符号整数 结论：每一种程序设计语言，都有它自己 的字符集，语言中的每一个单词或者是 上的单个字符，或者是上的字符按一 定方式组成的字符串。组成方式就是对字 符或字符串进行(连接)“”、或“”(并)、 或“”闭包运算。二、正规式 正规式也称为正则表达式，是表示正规集 的工具。 正规式（regular expression）是说明单词 的pattern的一种重要的表示法，是单词的 描述工具。 下面是正规式和它所表示的正规集的递归 定义n正规式和正规集的递归定义：（设字母表为）1、 和都是上的正规式，表示和 ；2 、任何a ，则a是正规式，表示a；3 、假定r和s都是上的正规式，分别表示语言 L(r)和L(s)：a） (r) | (s)是正规式，表示L (r) U L (s) ； b） (r)(s)是正规式，表示L (r)L (s)； c） (r)*是正规式，表示(L (r) )*； d） (r)是正规式，表示L (r)；4、有限次使用上述三步骤而定义的表达式才是上 的正规式，仅由这些正规式所表示的集合才是上的 正规集。或； 连接； 闭包规定优先顺序为“”、“ ”、“” (a)|(b)*(c)a|b*c例1：令=a，b， 上的正规式和相应的 正规集有：正规式正规集 aa ba*所有以b开头后跟任意多个a的串 aba,b abab (ab)(ab)aa,ab,ba,bb a ,a,aa, 任意个a的串 (ab) ,a,b,aa,ab 所有由a 或b组成的串(a|b)*(aa|bb)(a|b)* 所有含有两个相继的a或两个相继的b的串程序设计语言的单词都能用正规式来定义.例2：令=l，d，l 代表字母,d 代表数字,则上的 正规式: r = l(ld) 定义的正规集为: l,ll,ld,lll,ldd,就是Pascal和 多数程序设计语 言允许的的标识符的词法规则。例3：令d， ，e，其中d为09中的数字。则上的正规式: d*(.dd*| )(e(+|-|)dd*|)表示PASCAL语言中的无符号实数。 比如：2, 12.59, 3.6e2, 471.88e-1等都是正规式表示 集合中的元素。练 习1、=a,b，则上所有以b开头，后跟若 干个ab的字的全体所对应的正规式。2、 =a,b，写出不