《《编译原理实践与应用》第3章词法分析》由会员分享，可在线阅读，更多相关《《编译原理实践与应用》第3章词法分析（100页珍藏版）》请在金锄头文库上搜索。
1、词法分析,第三章,主要内容：词法分析的任务，手工实现词法分析程序，正规式与有穷自动机，词法分析程序的自动生成 重点掌握：词法分析器的功能和接口，用状态转换图设计和实现词法分析程序，正规文法、正规式和有穷状态自动机的概念及相互转换,本章要求,词法分析程序所处的位置：,3.1 词法分析器的功能,功能：逐个读入源程序字符并按照构词规则切分成一系列单词 主要任务： 读入源程序，输出单词符号 其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，指出源程序出错的行列位置 宏展开， 关键：找出单词的分隔符,单词：是语言中具有独立意义的最小单位，常用单词分类： 保留字：具有固定意义的标识符 运算符 界符 标
2、识符：表示各种名字 常数 对于一个程序设计语言，保留字、运算符和界符都是确定的，可以给以固定的编号(种别码)。 标识符是根据构词规则定义的，常数是符合定义的各种类型的常数,种别码：是对能识别的单词的分类编码 有多种编码方式： 标识符一般统一为一种：一个编号 常数按类型分别编码：整数、实数、布尔、字符 关键字一般一字一种 运算符一般一符一种 界符一般一符一种,某语言单词的种别码定义举例,词法分析器的输出,1. Token串: 输出源文件中各个有用的单词 格式： (单词的种别码，单词符号的属性值) 单词种别：是对能识别的单词的分类编码(P42) 单词符号的属性值：单词的某种特性或特征 常数的值，标
3、识符的名字等 保留字、运算符、分界符的属性值可以省略 文件存放最好有格式，如每个单词占一行方便“语法分析”程序调用 P38 例,this is a sample program writing in simple language program example1; used for illustrating compiling process vara,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 ; b
4、egin if ( a +,c * 3 b ) and ( b 3 ) then c := 3 ; end .,源程序 token文件,注意token文件的格式,举例,2. 符号表 各种常数和标识符一般放在符号表中，在输出的token文件中的单词属性值则存放单词在符号表中的指针 符号表的格式：字符串 if (ab2) test:=3;,格式1：(数组),格式2：(用指针),this is a sample program writing in simple language program example1; used for illustrating compiling process va
5、ra,b,c:integer;x:char; begin if (a+c*3 b) and (b3) then c:=3; End.,源程序 符号表,举例,3. 其它输出：错误信息和源程序清单 错误信息应该详细，准确，指出出错的具体行、列位置，发生了哪类错误等，方便用户修改,错误处理,应尽可能发现更多的错误 处理方式 每个程序段单独处理错误 统一处理错误（商用软件系统） 记录式的文件 数据库 统计表明，现代软件系统中， 75%的程序代码都是用于处理错误与错误信息 商业系统中错误处理的特点是：统一错误编号，编制文档指出错误信息的含义、应对措施、解决方案,词法错误类型,非法字符 单词拼写错误 难以
6、发现下面的错误fi (a = x ) 在实数是a.b格式下，可以发现下面的错误123.,词法分析是编译过程中的一个阶段，在语法分析前进行。可以作为一个独立的子程序，独立出来的原因： 简化设计 改进编译效率 增加编译系统的可移植性 可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,3.2 词法分析程序的设计,扫描器的任务 组织源程序的输入； 按规则拼单词，并转换成二元式形式； 删除注解行、空格及无用符号； 行计数、列计数； 列表打印源程序； 发现并定位词法错误； 如需要，还要建立关键字表、符号表、常数表等表格。,词法分析程序的接口,识别单词前作如下假
7、定： 关键字就是保留字 单词中间不能有分界符(如空格、空白、界符和算符等) 单词中间不能有注释 单词必须在一行内写完，换行后认为是另一个单词 一个单词不能超过规定长度,识别单词,主要包括如下几种单词的识别： 标识符的识别：字母+(字母/数字) 关键字的识别：与标识符相同，最后查表 常数的识别 界符和算符的识别,超前搜索技术：如在读取/* */时，当读到/时，如何判别是注释还是除法运算？ 识别单词：掌握单词的构成规则很重要,单词的构成规则用状态转换图表示,状态转换图是一张有限方向图。有限个状态，用结点表示状态，其中有一个初态(初态用箭头指出)，至少有一个终态(终态用双圈表示)。状态之间用带箭头的
8、弧线连结，弧线上标记的字符表示在射出状态下可能出现的输入字符或字符类。,识别标识符的转换图,一个状态图可用于识别一定的字符串，大多数程序设计语言的单词符号都可以用转换图来识别。,识别过程是：从初始状态0开始，若读入一个字母，转入1状态，若再读入字母或数字，仍处于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
9、 是字母或数字 state = 1; ch = getch(); else state = 2; break; while (state != 2); 回退一个符号。 ,练 习 1,画出Pascal中无符号实数的状态转换图 (不带正负号，可表示整数、可表示小数，可带指数部分) 如：下面几个数应该是符合规则的数：3，3.51，34E3,34.5E2,34.5E+2,34.5E-2,练 习 2,画出识别标识符和整常数(可带正负号)的状态转换图,练 习 3,以下状态转换图接受的字符集合是什么？,状态转换图的实现：使用一个switch case 语句：每条分支对应一个case语句段 见书P45 例,某
10、简单语言的词法分析程序的实现,词法分析器的自动生成,正规式 正规文法 有穷自动机,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字母
11、数字digit | digit无符号整数,结论：每一种程序设计语言，都有它自己的字符集，语言中的每一个单词或者是上的单个字符，或者是上的字符按一定方式组成的字符串。组成方式就是对字符或字符串进行(连接)“”、或“”(并)、或“”闭包运算。,二、正规式,正规式也称为正则表达式，是表示正规集的工具。 正规式（regular expression）是说明单词的pattern的一种重要的表示法，是单词的描述工具。 下面是正规式和它所表示的正规集的递归定义,正规式和正规集的递归定义：（设字母表为） 1、 和都是上的正规式，表示和 ； 2 、任何a ，则a是正规式，表示a； 3 、假定r和s都是上的正规式
12、，分别表示语言 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， 上的正规式和相应的正规集有：,程序设计语言的单词都能用正规式来定义.例2：令=l，d，l 代表字母,d 代表数字,则上的正规式: r = l(
13、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，写出不以a开头，但以aa结尾的字符串集合的正规式。,b(a|b)*aa,b(ab)*,思考题：=d，. ，则上表示无符号数的正规式是什么？（不考虑含
14、e的科学计数法，其中d为09的数字）如：2 ，12.59 ，471.88等都是该集合中的元素。,dd*(.dd*| ),正规式的等价,若两个正规式e1和e2所表示的正规集相同,则e1和e2等价,写作e1=e2。 设r,s,t为正规式，正规式服从的代数规律有： 1. rs=sr “或”服从交换律 2. r(st)=(rs)t “或”的可结合律 3. (rs)t=r(st) “连接”的可结合律 4. r(st)=rsrt(st)r=srtr 分配律 5. r=r=r 是“连接”的恒等元素 零一律 6. e*e+ 7. e+=e*e=ee* 8. (e*)*=e*,三、有穷自动机,有穷自动机(也称有
15、限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，是为词法分析程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类： 确定的有穷自动机(Deterministic Finite Automata) 不确定的有穷自动机(Nondeterministic Finite Automata),确定的有穷自动机DFA,一个确定的有穷自动机(DFA) M是一个五元组：M=(S，s0，F)，其中: 1.S是一个有穷集，它的每个元素称为一个状态； 2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表； 3.是转换函数，是在SS上的单值映射， (s，a)=s (sS，sS) ，就意味着，当前状态为s，输入符为a时，将转换为下一个状态s，我们把s称作s的一个后继状态； 4. s0 S是唯一的一个初态； 5.FS是一个终态集(可空)，也称可接受状态或结束状态。,
