《编译原理课程设计之第二章词法分析》由会员分享，可在线阅读，更多相关《编译原理课程设计之第二章词法分析（152页珍藏版）》请在金锄头文库上搜索。
1、mcy,1,课程内容 第一章 概论 第二章 词法分析 第三章上下文无关文法及分析 第四章自上而下的语法分析 第五章自下而上的语法分析 第六章语义分析 第七章运行时环境 第八章代码生成,mcy,2,第2章 词法分析,2.1 词法分析器的作用 2.2 正规表达式 2.3 有穷自动机 2.4 从正规表达式到DFA 2.5 用代码实现有穷自动机 2.6 利用lex自动生成词法分析程序,单词的描述工具,单词的识别系统,设计和实现词法分析程序,作业,课程设计1,mcy,3,2.1 词法分析器的作用,词法分析器(词法分析程序)的任务：从源代码中读取输入字符，产生单词序列(生成独立的有意义的逻辑单元称作单词(
2、token)，提交给语法分析使用。,mcy,4,任务：逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 识别出源程序中的单词； 删除无用的空白字符及注释（空格、回车 等），这些信息仅增加了源程序的可读性，便于程序员阅读和维护程序，而对于语法分析是完全无用的。 进行词法检查，能够检测出输入中不能形成源语言任何单词的错误字符串。,mcy,5,The big elephant ate the peanut.,词法分析的结果：,mcy,6,token表示的字符串（串值或词义）： if , y, ,3,then,x,=,
3、0,token的类型（词法）： 关键字（if, else, for,int,return） 操作符（+ , -, ） 数字 （3, 45,） 标示符（x, y, ）,词法分析器的输出: token序列,mcy,7,if y3 then x=0,词法分析器,例如：C源代码:if y3 then x=0,词法分析器的输出是？,mcy,8,定义逻辑项token的数据类型： typedef struct,union char *stringval; int numval; attribute;,TokenRecord;, TokenType tokenval;,Token类型,Token词义,mcy,
4、9,词法分析程序的函数接口： TokenRecord getToken(void);,Token,getToken(),源程序,词法分析程序,语法分析程序,符号表,mcy,10,第2章 词法分析,2.1 词法分析器的作用 2.2 正规表达式 2.3 有穷自动机 2.4 从正规表达式到DFA 2.5 用代码实现有穷自动机 2.6 利用lex自动生成词法分析程序,记号的描述工具,记号的识别系统,设计和实现词法分析程序,作业,课程设计1,mcy,11,正规表达式的引入：,对自动生成词法分析程序而言，正规表达 式也是非常有用的工具。,所谓正规表达式就是用特定的运算符及运算对象按某种规则构造的表达式。例
5、如：c-语言的词法。,正规表达式用来描述单词结构(定义单词)。,mcy,12,2.2.1 基本概念和术语 2.2.2 正规表达式的定义 2.2.3 正规表达式基本等价关系 2.2.4 正规表达式的扩展 2.2.5 单词的正规表达式举例,2.2正规表达式 单词的描述工具,mcy,13,2.2.1 基本概念和术语,字母表（符号表、符号集） 由若干元素（符号、字母）组成的有限非空集合。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。,mcy,14,符号串 由字母表中的符号组成的任何有穷序列称为符号串: 例如00 11 10 是字母表 =0，1上的符号串。 字母表A=a，b
6、，c上的符号串有： a，b，c，ab，aaca。 在符号串中，符号的顺序是很重要的，符号串ab就不同于ba，abca和aabc也不同。,mcy,15,符号串的长度 如果某符号串x中有m个符号，则称其长度为m，表示为x=m，如001110的长度是6。 空符号串，即不包含任何符号的符号串，用表示，其长度为0，即=0。,mcy,16,符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。 例如 x=ST，y=abu，则它们的连接 xy=STabu，x=2，y=3，xy=5 由于的含义，显然有x=x=x。 符号串的方幂：符号串自身连接n次得到的符号串xn 定义为 xx
7、xx； n个x x1=x, x2=xx且x0=,mcy,17,例；若x=ab 则: x0 = x1 =ab x2 = abab x3 = ababab xn = xxn-1 = xn-1x (n0),mcy,18,符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 符号串集合的和与积 设A，B为两个符号串集合，定义 和 A+B(或AB) =w|wA，或wB 积 AB=xy|xA,yB,mcy,19,若用表示空集，则有： A+ = +A = A A = A = A = A = A 例：若集合A=ab,cde ，集合B = 0,1，则AB =ab1,ab0,cde
8、0,cde1；,mcy,20,的闭包：用*表示上的一切符号串（包括）组成的集合，*称为的闭包。 例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 的正闭包：上除外的所有符号串组成的集合记为+ ，+称为的正闭包。 例如：=a,b +=a,b,aa,ab,ba,bb,aaa,aab,mcy,21,2.2.1 基本概念和术语 2.2.2 正规表达式的定义 2.2.3 正规表达式基本等价关系 2.2.4 正规表达式的扩展 2.2.5 单词的正规表达式举例,2.2正规表达式,mcy,22,正规表达式(也称正则表达式)就是用特定的运算符及运算对象按某种规则构造的表达式。 每个正规表达
9、式代表一个字符串的集合，我们把其称为正规集。 语言(Language)是字符串组成的集合，我们也可以把正规表达式表示的正规集称为该正规表达式表示的语言。,2.2.2正规表达式的定义,mcy,23,正规表达式和它所表示的正规集(字符串的集合)的递归定义如下： 设有字母表为，辅助字母表=, | , . , * , ( , ) ,mcy,24,(1)和是上的正规式，它们所表示的正规集分别为和; (2) 若a，则a是上的正规式，它所表示的正规集为a;,若r和s都是上的正规式，且它们所表示的正规集分别为L(r)和L(s)，那么：,mcy,25,r|s 是正规式，表示的正规集为 L(r|s)=L(r)L(
10、s) ； rs 是正规式，表示的正规集为 L(rs)=L(r)L(s) ； r *是正规式，表示的正规集为(L(r)*。 (r) 是正规式，表示的正规集为L(r)；,“.”运算符常省略,mcy,26,(4)仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的符号串集合才是上的正规集。 注：算符的优先级为先“ * ”，再“ . ”最后“ | ” ,都是左结合的，它们满足结合律。,举例： C-语言的词法,mcy,27,例1，令=a，b，上的正规式和相应的正规集的例子：,正规式 正规集,a,a,ab,ab,(ab)(ab),a ,a,b,ab,aa,ab,ba,bb, ,a,
11、aa, 任意个a的串,(ab) ,a,b*,即,a,b,aa,ab,ba,bb,mcy,28,例2，正规式(a)| (b) * (c)它所表示的正规集为：,根据运算符的优先级，上述正规式可以表示成 a|b*c a|b*c所表示的正规集为：字符串a以及由零个或多个b后跟一个c 形成的字符串的集合 或写成L(a|b*c)=a bnc | 其中n是大于或等于0的整数,mcy,29,给定一个正规式,它唯一确定一个正规集；反之不成立。即一个正规集可由多个不同的正规式表示。,aa,a,aa, aaa,任意个a的串,a|aa,a,aa, aaa,任意个a的串,例如：,mcy,30,若二正规式描述同一正规集，
12、则称二式等价(相等)。 判断下列正规表达式e1和e2是否等价？ e1= (ab)， e2 = ba e1= b(ab) ,e2 =(ba)b e1= (ab), e2 =(ab),mcy,31,正规表达式是表示模式的一种重要方法，每个模式匹配一个字符串集合(即正规集)。 正规集是正规表达式所定义的语言。 正规表达式可以作为字符串集合(即正规集)的名字。,mcy,32,2.2.1 基本概念和术语 2.2.2 正规表达式的定义 2.2.3 正规表达式基本等价关系 2.2.4 正规表达式的扩展 2.2.5 单词的正规表达式举例,2.2正规表达式,mcy,33,A1. r|s=s|r A2. r|r=
13、r A3. r|=r A4. (r|s)|t=r|(s|t) A5. (rs)t=r(st) A6. r(s|t)=rs|rt A7. (s|t)r=sr|tr A8. r=r= A9. r=r=r A10. r*=(|r)*=|rr*,2.2.3 正规式基本等价关系,mcy,34,2.2.1 基本概念和术语 2.2.2 正规表达式的定义 2.2.3 正规表达式基本等价关系 2.2.4 正规表达式的扩展 2.2.5 单词的正规表达式举例,2.2正规表达式,mcy,35,2.2.4 正规表达式的扩展,1.一个或多个重复（+，*）： 假设r是正则表达式， r的重复是通过使用标准的闭包运算来描述，写
14、作r*。它允许r被重复0次或更多次。 用r +表示r 被重复1次或更多次。因此有： (0|1)+=(0|1)(0|1)*,mcy,36,2.任意字符（.）: 句点“ .”表示可以匹配除换行符之外的任意单个符。 利用这个字符就可为所有包含至少一个b 的串写出 一个正则表达式，如下所示： .*b .* 引号“ ”，引号中的字符串表示文本字符串本身。例如：“.”表示要匹配.字符本身。,mcy,37,字符范围： 表示法a|b|z 表示所有小写字母；0|1|9表示0到9间的所有数字； 常见的表示法是利用方括号和一个连字符，如a-z是指所有小写字母，0-9则指数字。 第二种表示法还可用作表示单个的解，a|
15、b|c可写成abc，它还可用于多个范围，如 a - z A - Z 代表所有的大小写字母。,mcy,38,正规表达式的名字,为较长的正则表达式提供一个简化的名字很有用处，这样就不用每次使用正则表达式书写较长的表达式本身了； 如要写一个正则表达式: a - z A - Z ( a - z A - Z 0-9 ) ,它定义的正规集为：以字母打头后跟若干字母或数字组成的符号串的集合。,mcy,39,上述正规式定义的是程序设计语言标识符的词法规则，通过为正规表达式提供一个简化的名字，上述正规表达式可写作： letter= a - z A - Z digit=0-9 r=letter(letterdigit),mcy,40,例：写出正则表达式signedNat nat=0-9+ signedNat=nat|+ nat|- nat 对应的正规集？,mcy,41,可选的子表达式（？）： 如果在特定的串中包括既可能出现又可能不出现的可选部分。例如， nat=0-9+ signedNat=nat|+nat|-nat 我们可以引入问号?来表示r 匹配的串是可选的；上面的例子可写成： nat=0-9 + signedNat=(+|-)？nat,mcy,42,2.2.1 基本概念和术语
