《5.第三章词法分析(1)》由会员分享，可在线阅读，更多相关《5.第三章词法分析(1)（47页珍藏版）》请在金锄头文库上搜索。
1、第3章 词法分析,词法分析(Lexical Analysis)词法的表示词法分析器的设计与实现,2,本章在编译程序中的地位,表格管理,词法分析器,语法分析器,语义分析与中间代码产生,优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,出错处理,3,回顾: 词法分析,任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词符号。,单词：标识符，保留字，常数，算符，界符词法分析阶段的工作所依循的是语言的词法规则。描述词法规则的有效工具是正规式和有限自动机。,主要教学内容,3.1 词法分析器的功能、输出形式和结构3.2 词法分
2、析程序的设计方法 - 重点 3.3 正规表达式与有穷状态自动机 - 重点难点3.4 词法分析器的自动产生,2017/8/22,Ch3.词法分析,4,5,教学要求,掌握：正规式、状态转换图、有限自动机的概念,将NFA转换为DFA、DFA的化简、正规式与有限自动机间的转换、正规文法与有穷自动机间的转换，词法分析程序的功能和设计方法。了解理解：词法分析器的自动产生工具LEX。,词法分析涉及的概念及关系,7,3.1 对词法分析器的要求,3.1.1 词法分析器的功能和输出形式输入源程序，扫描识别, 输出单词符号程序语言的单词符号一般分为五种：关键字(保留字或基本字)：如 begin,end,if,the
3、n,else,while,do等 标识符：用来表示各种名字，如 X1字面常数：如 256，3.14，true,abc运算符：如 、*、/ 等等分界符：如 逗号，分号，冒号等,8,while ij do if ij then i:ij else j:=ji ;,例,while i j do if i j then i := i jelse j := j i ;,3.1 .1 词法分析（扫描）器的功能,功能：读源程序，产生记号序列剥去源程序中的注释（块、行）和“空白”符预处理宏处理与文件包含单词符号的形式按照最小的语义单位设计通常表示为二元组：（单词符号种别，属性值 ）关键找出符号的分割符,1)
4、单词符号的表示,常用单词符号种别分类（P42）各关键字（保留字、基本字），各种运算符，各种分界符各用一个种别码标识其它标识符用一个种别码标识常数用一个种别码标识属性（值）单词符号的值常数的值，标识符的名字等保留字、运算符、分界符的属性值可以省略,单词的机内表示,编译器使用二元式标识特定的标识符： ,又称种别码,单词值,单词值,关键字和分界符若采用一字和一符一种编码时，单词值无意义；倘若一类一种编码，单词值可取整数的内部编码或自身的符号串表示。标识符的单词值可取单词符号本身；常数的单词值通常取二进制表示。,2017/8/22,Ch3.词法分析,12,单词符号的内部表示是二元式： (词类种别编码,
5、 单词符号自身的属性值)1. 词类种别编码提供给语法分析程序使用；2.单词自身的属性值提供给语义分析程序使用。3. 具体的分类设计方法以方便语法分析程序使用为原则。,单词符号的内部表示,13,例子,考虑下述C语言代码段： while (i=j) i- -; 经词法分析器处理后，它将转换为如下的单词符号序列： id ,指向i的符号表项的指针 = , - ,14,3.1.2 词法分析器作为独立子程序,把词法分析设计成一个独立程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法分析器处理。如图所示：,15,3
6、.2 词法分析器的设计,3.2.1 输入、预处理 处理源程序输入的技术3.2.2 单词符号的识别：超前搜索 识别单词符号的技术3.2.3 状态转换图 单词符号结构的一种图形表示方法 识别单词符号的一种方法3.2.4 状态转换图的实现 词法分析程序的一种手工构造方法 状态转换图 词法分析程序,16,3.2.1 输入、预处理,词法分析器工作的第一步是输入源程序文本。输入串一般放在一个输入缓冲区中。但在许多情况下，可以先预处理输入串，识别工作将更方便。预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。可以构造一个预处理子程序完成上面的工作。每当词法分析器调用它时就处理出
7、一串确定长度的输入字符，并将其装入指定的缓冲区 - 扫描缓冲区中。这样分析器就可以在扫描缓冲区中直接进行单词符号的识别工作。 P40.图3.1词法分析器的结构,17,输入、预处理：词法分析第一步,词法分析程序,2）相关问题,词法分析器可以作为一个独立的子程序，也可以作为一遍独立的扫描来安排。输入缓冲区,工作区(token),双缓冲区并行、捻接,每次移动向前指针都需要做两次测试,2）相关问题,？如何设计和实现扫描器,大小问题128Byte*2|1024Byte*2|4096Byte*2,forward := forward +1;if forward在缓冲区第一部分末尾 then 重装缓冲区第二
8、部分else if forward在缓冲区第二部分末尾 then begin 重装缓冲区第一部分; 将forward移到缓冲区第一部分开始 end,forward := forward + 1;if forward！= eof then if forward在第一部分末尾 then 重装第二部分 else if forward在第二部分末尾 then begin 重装第一部分; 将forward 移到第一部分开始 end else终止词法分析 /* eof 在表示输入结束 */,2017/8/22,Ch3.词法分析,20,下面通过单词符号：关键字的识别标识符的识别常数的识别算符的识别界符的识别
9、介绍单词符号识别的一个简单方法 - 超前搜索,3.2.2 单词符号的识别：超前搜索,2017/8/22,Ch3.词法分析,21,关键字的识别(1),像FORTRAN这样的语言，关键字的识别甚为麻烦。因为1. 关键字不加保护（只要不引起矛盾，用户可以用它们作为普通标识符）。2. 关键字和用户自定义的标识符或标号之间没有特殊的界符作间隔。,22,关键字的识别(2),下面是几个FORTRAN的正确语句，空白可有可无，不作分隔符： 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.1 4 IF(5)=55语句1和2分别是DO和IF语句，它们都是以某关键字开头的。语句3和4
10、是赋值语句，它们都是以用户自定义的标识符开头的。,23,标识符、常数的识别,标识符的识别 (参考P40,P41)是字母开头的字母数字串，后跟算符或界符，识别不困难，例如 DO99K=1.10常数的识别算术常数的识别: 多数语言很直接，有的须采用超前搜索，如FORTRAN语言中： IF(5.EQ.M)GOTO55 - 5.E08逻辑(布尔)常数的识别: 比较容易FORTRAN文字常数的识别: 麻烦, 须作特殊处理,2017/8/22,Ch3.词法分析,24,算符、界符的识别,(参考P40,P41) 算符的识别单个字符构成的算符的识别较容易 如 i+j多个字符构成的算符的识别须使用超前搜索 如 i
11、+界符的识别 界符的识别比较简单,25,3.2.3 状态转换图,状态转换图用来：描述单词符号的结构识别单词符号串是设计词法分析器的工具手工生成词法分析器的方法:,构造识别单词符号的状态转换图,2017/8/22,Ch3.词法分析,26,状态转换图,状态转换图是一张有限方向图，只包含有限个状态，即有限个结点。1. 结点代表状态，用圆圈表示2. 终止状态用双圈表示3. 初始状态前标记符号“ ”来表示4. 状态之间用箭弧连结5. 箭弧上的标记代表在射出结点即箭弧始结点状态下可能出现的输入字符或字符类，箭弧标记表示状态转换的条件。,27,状态转换图：例,例 P41.图3.2(a)表示：在状态1下，若输
12、入字符为X，则读进X，并转换到状态2。若输入字符为y，则读进y，并转换到状态3。若输入字符非x和非y，则此转换图不工作。,一个状态转换图可用于识别一定的字符串,28,状态转换图识别字符串：例1,例1 P41.图3.2(b)，识别标识符的状态转换图。其中0为初态，2为终态。这个转换图识别标识符的过程是: 从初态0开始，若在状态0下输入字符是字母，则读进它，并转入状态1。在状态1之下，若输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到发现输入字符不再是字母或数字时(这个字符已经被读进)就进入状态2。,29,状态转换图识别字符串: 例,例1 P41.图3.2(b)，识别标识符的
13、状态转换图。其中0为初态，2为终态。状态2是终态，它意味着到此已经识别出一个标识符。终态上打个*号，表示多读进了一个不属于标识符部分的字符，应把它退还给输入串。如果在状态0时输入字符不为“字母”，则意味着这个转换图不工作。,2017/8/22,Ch3.词法分析,30,状态转换图识别字符串: 例2,例2 P41.图3.2(c)是识别整数的转换图。其中0为初态，2为终态, 打了*号。识别的过程类似前例。,31,例3 P41.图3.2(d)是一个识别FORTRAN实型常数的转换图。其中0为初态，7为终态。,状态转换图识别字符串: 例3,该转换图可以识别下面形式的一些实数:123. , .123, 1
14、23E3 ,123.456 .123E+10, 123.456E-3 等,单词符号编码举例,状态图,letter,digit,letter,（IDN，入口）,digit,digit,(其它), (其它),（NUM，值）,（ASG，_）,=,*,（STAR，_）,s,*,（POWER，_）,其它,IDNletter(letter|digit)*,NUMdigit(digit)*,ASG=,POWER*,STAR*,空白,2017/8/22,Ch3.词法分析,34,3.3 正规表达式与有限自动机,为了更好地使用状态转换图构造词法分析器，为了讨论词法分析器的自动生成，还需要将转换图的概念形式化。本节主要讨论词法分析器自动产生所需要的工具, 引入：正规式，正规集，有限自动机等概念。本节是本章的重点和难点。,本节内容及关系,三者相同,36,3.3.1 正规式与正规集,对于字母表，有符号串集合*和+, 我们感兴趣的是它的一些特殊的子集，即所谓正规集。使用正规式这个概念来描述正规集。例如, =a,b,c,z,0,1,2,9 * =所有字母数字串 我们对如下子集感兴趣 : 字母开头的字母数字串 = 标识符集合,
