《《编译原理课程教案》第3章：词法分析》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第3章：词法分析（106页珍藏版）》请在金锄头文库上搜索。
1、词法分析第三章 主要内容 ： 词法分析的任务，手工实现词法分析程序， 正规式与 有穷自动机，词法分析程序的自动生成 重点掌握： 词法分析器的功能和接口，用状态转换图设计和实现词法分析程序，正规文法、正规式和有穷状态自动机的概念及相互转换本章要求词法分析程序所处的位置：语法分析器词法分析器 符号表编译程序的后续部分token取下一个单词语法树3.1 词法分析器的功能 功能： 逐个读入源程序字符并按照构词规则切分成一系列单词 主要任务： 读入源程序，输出单词符号 其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，指出源程序出错的行列位置 宏展开， 关键： 找出单词的分隔符源程序 词法分析程序
2、Token串 语法分析程序 单词 ： 是语言中具有独立意义的最小单位， 常用单词分类 ： 保留字： 具有固定意义的标识符 运算符 界符 标识符： 表示各种名字 常数 对于一个程序设计语言，保留字、运算符和界符都是确定的，可以给以固定的编号 (种别码 )。 标识符是根据构词规则定义的，常数是符合定义的各种类型的常数 种别码：是对能识别的单词的分类编码有多种编码方式： 标识符一般统一为一种：一个编号 常数按类型分别编码：整数、实数、布尔、字符 关键字一般一字一种 运算符一般一符一种 界符一般一符一种某语言单词的种别码定义举例单词 种别码 单词 种别码 单词 种别码and 1 procedure 2
3、1 * 41array 2 program 22 */ 42begin 3 read 23 + 43bool 4 real 24 ， 44call 5 repeat 25 45case 6 set 26 、 46char 7 then 27 47constant 8 to 28 / 48do 9 true 29 /* 49else 10 until 30 ： 50end 11 var 31 := 51false 12 while 32 ； 52for 13 write 33 55integer 16 实常数 36 = 56not 17 字符常数 37 57of 18 38 = 58or 19
4、( 39 59output 20 ) 40 60词法分析器的输出 1.Token串 :输出源文件中各个 有用 的单词格式： (单词的种别码，单词符号的属性值 )单词种别 ： 是对能识别的单词的分类编码 (P42)单词符号的属性值 ： 单词的某种特性或特征常数的值，标识符的名字等保留字、运算符、分界符的属性值可以省略 文件存放最好有格式，如每个单词占一行方便 “语法分析 ”程序调用P38例thisisasampleprogramwritinginsimplelanguageprogramexample1;usedforillustratingcompilingprocessvara,b,c:in
5、teger;x:char;beginif(a+c*3b)and(b3)thenc:=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： (数组 )入口 单词 名及 长 度 类 型 种属 值 内存地址
6、1 a 1 整 简单变 量 未知 未知2 b2 2 整 简单变 量 未知 未知3 test 4 实 简单变 量 未知 未知 格式 2： (用指针 )thisisasampleprogramwritinginsimplelanguageprogramexample1;usedforillustratingcompilingprocessvara,b,c:integer;x:char;beginif(a+c*3b)and(b3)thenc:=3;End.源程序 符号表举例 3.其它输出： 错误信息和源程序清单错误信息应该详细，准确，指出出错的具体行、列位置，发生了哪类错误等，方便用户修改错误处理
7、应尽可能发现更多的错误 处理方式每个程序段单独处理错误统一处理错误（商用软件系统） 记录式的文件 数据库 统计表明，现代软件系统中， 75%的程序代码都是用于处理错误与错误信息 商业系统中错误处理的特点是：统一错误编号，编制文档指出错误信息的含义、应对措施、解决方案词法错误类型 非法字符 单词拼写错误 难以发现下面的错误fi (a = x ) 在实数是 a.b格式下，可以发现下面的错误123. 词法分析是编译过程中的一个阶段，在语法分析前进行。可以作为一个独立的子程序，独立出来的原因：简化设计改进编译效率增加编译系统的可移植性 可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来
8、获得当前单词供语法分析使用。3.2 词法分析程序的设计扫描器的任务4 组织源程序的输入；4 按规则拼单词，并转换成二元式形式；4 删除注解行、空格及无用符号；4 行计数、列计数；4 列表打印源程序；4 发现并定位 词法错误 ；4 如需要，还要建立关键字表、符号表、常数表等表格。词法分析程序的接口 识别单词前作如下假定：关键字就是保留字单词中间不能有分界符 (如空格、空白、界符和算符等 )单词中间不能有注释单词必须在一行内写完，换行后认为是另一个单词一个单词不能超过规定长度识别单词 主要包括如下几种单词的识别：标识符的识别： 字母 +(字母 /数字 )关键字的识别：与标识符相同，最后查表常数的识
9、别界符和算符的识别超前搜索技术：如在读取 /*/时，当读到 /时，如何判别是注释还是除法运算？识别单词：掌握 单词的构成规则 很重要单词的构成规则用状态转换图表示状态转换图 是一张有限方向图。有限个状态，用结点表示状态，其中 有一个初态 (初态用箭头指出 )， 至少有一个终态 (终态用双圈表示 )。状态之间用带箭头的弧线连结，弧线上标记的字符表示在射出状态下可能出现的输入字符或字符类。识别标识符的转换图0 1 2字母字母或数字其它*一个状态图可用于识别一定的字符串，大多数程序设计语言的单词符号都可以用转换图来识别。识别过程是 ：从初始状态 0开始，若读入一个字母，转入 1状态，若再读入字母或数
10、字，仍处于 1状态，否则转向 2状态，结束一个标识符的识别过程。状态上的 *表示多读入一个符号。0 1 2字母字母或数字其它*写成 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); 回退一个符号。0 1 2字母字母或数字其它*0 1 2数字数字其它
11、识别整数的转换图*练 习 1 画出 Pascal中无符号实数的状态转换图 (不带正负号，可表示整数、可表示小数，可带指数部分 ) 如：下面几个数应该是符合规则的数：3， 3.51， 34E3,34.5E2,34.5E+2,34.5E-2练 习 2 画出识别标识符和整常数 (可带正负号 )的状态转换图 练 习 3 以下状态转换图接受的字符集合是什么？X Y001状态转换图的实现：使用一个switch case 语句：每条分支对应一个 case语句段见书 P45 例某简单语言的词法分析程序的实现词法分析器的自动生成 正规式 正规文法 有穷自动机3.3 正规文法、正规式与有限自动机 本节要求1 能根
12、据自然语言描述构造 NFA2 掌握 NFA转换为 DFA， DFA的化简3 掌握正规文法、正规式和有穷自动机间的转换 为了讨论词法分析程序的自动生成问题，将状态转换图加以形式化。一、正规文法 正规文法 ： 文法 G=(VN， VT， P， S)中的每个产生式的形式都是 A aB或 A a，其中 A和 B都是非终结符， a是终结符串。下面定义的标识符和无符号整数都是正规文法：letter|letter 字母数字 letter|digit|letter 字母数字 |digit 字母数字 digit|digit 无符号整数 结论： 每一种程序设计语言，都有它自己的字符集，语言中的每一个单词或者是上的
13、单个字符，或者是上的字符按一定方式组成的字符串。组成方式就是对字符或字符串进行 (连接 )“ ”、或 “ ”(并 )、或 “ ”闭包运算。二、正规式 正规式也称为正则表达式，是表示正规集的工具。 正规式（ regularexpression）是说明单词的 pattern的一种重要的表示法，是单词的描述工具。 下面是正规式和它所表示的正规集的递归定义n正规式和正规集的递归定义：（设字母 表 为 ）1、 和 都是 上的正规式，表示 和 ；2 、 任何 a ，则 a是正规式，表示 a；3 、假定 r和 s都是 上的正规式，分别表示语言 L(r)和 L(s)：a） (r) | (s)是正规式，表示 L
14、 (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， 上的正规式和相应的正规集有：正规式 正规集a aba* 所有以 b开头后跟任意多个 a的串ab a,bab ab(ab)(ab) aa,ab,ba,bba ,a,aa, 任意个 a的串(ab) ,a,b,aa,ab 所有由 a或 b组成的串(a|b)*(aa|bb)(a|b)* 所有含有两个相继的 a或两个相继的 b的串程序设计语言的单词都能用正规式来定义 .例 2：令 =l， d， l代表字母 ,d
