编译原理课程之词法分析详解.ppt

词法分析;主要内容：词法分析的任务，手工实现词法分析程序，正规式与有穷自动机，词法分析程序的自动生成 重点掌握：词法分析器的功能和接口，用状态转换图设计和实现词法分析程序，正规文法、正规式和有穷状态自动机的概念及相互转换;词法分析程序所处的位置：;3.1 词法分析器的功能;单词：是语言中具有独立意义的最小单位，常用单词分类： 保留字：具有固定意义的标识符 运算符 界符 标识符：表示各种名字 常数 对于一个程序设计语言，保留字、运算符和界符都是确定的，可以给以固定的编号(种别码)。 标识符是根据构词规则定义的，常数是符合定义的各种类型的常数;;某语言单词的种别码定义举例;词法分析器的输出;{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. 其它输出：错误信息和源程序清单 错误信息应该详细，准确，指出出错的具体行、列位置，发生了哪类错误等，方便用户修改 ;错误处理;词法错误类型;词法分析是编译过程中的一个阶段，在语法分析前进行。可以作为一个独立的子程序，独立出来的原因： 简化设计 改进编译效率 增加编译系统的可移植性 可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。;3.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); 回退一个符号。 };;练 习 1;;练 习 2;练 习 3;状态转换图的实现：使用一个switch case 语句：每条分支对应一个case语句段 见书P45 例;词法分析器的自动生成;3.3 正规文法、正规式与有限自动机;为了讨论词法分析程序的自动生成问题，将状态转换图加以形式化。;一、正规文法;结论：每一种程序设计语言，都有它自己的字符集Ｖ，语言中的每一个单词或者是Ｖ上的单个字符，或者是Ｖ上的字符按一定方式组成的字符串。组成方式就是对字符或字符串进行(连接)“．”、或“｜”(并)、或“＊／＋”闭包运算。;二、正规式;正规式和正规集的递归定义：（设字母表为?） 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、有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集。; ?——或；? ——连接；? ——闭包 规定优先顺序为“?”、“? ”、“?” ;例1：令?={a，b}， ?上的正规式和相应的正规集有：;程序设计语言的单词都能用正规式来定义. 例2：令?={l，d}，l 代表字母,d 代表数字,则?上的正规式: r = l(l?d)? 定义的正规集为: {l,ll,ld,lll,ldd,……},就是Pascal和 多数程序设计语言允许的的标识符的词法规则。;练 习;思考题： ?={d，. }，则?上表示无符号数的正规式是什么？（不考虑含e的科学计数法，其中d为0~9的数