第3章 词法分析.ppt

1、第3章字句分析、内容摘要扫描处理单词的记述正则表达式单词的识别贫穷的机器人利用Lex自动生成扫描程序，在任务扫描和字句分析阶段将源程序作为文字文件读取，分为多个单词。 字句分析的处理结构(1)把字句分析程序作为主程序。 (2)把字句分析程序作为语法分析程序调用的子程序。 词法分析程序通常采用第二处理结构，因为词法分析器作为子例程安排是自然的。词素分析的2个处理结构(a )把词素分析程序作为主程序(b )把词素分析程序作为子程序，3.1扫描处理，单词的分类关键词(keyword)/保留词(reserved word ) :例如c语言中的if，else 标识符(identifier ) :用于标记

2、常量、数组、类型、变量、过程或函数名称等，通常由用户自己定义。 常数：整数常数386、实常数0.618、布尔常数TRUE、字符串常数“Hello world！ 等等。 运算符：、-、*、/、等。 边界符号：在语言中用作语法上的边界符号，“，”；” 如：“(”、“)”等。 单个程序语言的保留字、运算符和分隔符的数量是确定的，而标识符或常量的使用不限于数量。 字句解析器输出的单词的形式(单词的种类、单词的值)单词的种类表示单词的种类，是语法解析所需的信息。 对于保留字，可以将其整体看作一类，也可以看作一字一类，用一字一类的分类方法处理更方便的识别符一般分类。常数可以归纳为一个，也可以按整数型、实型

3、、布尔型等分类。运算符和分隔符采用一种分类法单词值是编译中其他阶段所需的信息。 对于单词，如果一个类别只包含一个单词，则该单词的类别代码完全表示该值。 如果一个类别包含多个单词，则必须为每个单词提供类别代码和单词值，以区分同一类别的不同单词。 应当注意，识别符的值是构成识别符的字符串，并且常数本身的值是常数本身的二进制值。 也可以使用指向符号表中相应项的指针来表示单词的值。 例3-1句if (计数0 ) INR=INR 368； else inr=inr * inr； 要通过词法分析器输出： (if、_ ) (、_)(id、“计数”) (、_)(num、0 ) ()、_)(id、_) (els

4、e、_)(id、“inr”) (=_)(id、“inr”)(*、_ ) (id、“INR”、_ )、空格和注释要删除空格，请单击常数将数字与常数组合起来，用一个单词类(例如num )来表示所有常数，将常数的值作为单词(此处为num )的值。 单词与单词值一起传递给解析器。 例如，输入31到28到59通过词法分析输出(num，31 ) (，_)(num，28 ) (，_)(num，59 )。 标识符和关键字用一个单词类别(例如id )表示所有标识符。 如果在输入流中出现形成标识符的字符串，则该字符串存储在符号表的表条目中，指向该表条目的指针为单词(在此为id )的值。 因为关键字通常满足标识符的

5、形成规则，所以区分关键字和标识符的简单方法是将所有关键字存储在一个表中并检查该表，以便不是关键字而是标识符。 词法分析器的接口词法分析器位于解析器和源程序字符输入流之间，与两者交互。 词法分析阶段从输入字符流读取字符以形成单词，并将生成的单词的最高值传递到编译器的下一阶段。中的组合图层性质变更选项。 在某些情况下，词法分析器在将单词传递给解析器之前，必须从输入列读取几个字符，以确定必须传递给解析器的正确单词。 例如，词法分析器在读取字符时必须读取以下字符： 如果下一个字符是=，则词法分析器将=组合作为形成“以上”操作符的单词的字符串，否则词法分析器已经多读了1个字符作为形成“更大”操作符的单词

6、的字符串。 多重汇入的字元可能是下一个字的开始符号，因此必须转换为输入流。 3.2单词的描述正则表达式、正则表达式用于表示字符串的结构。 正则表达式r完全由匹配的字符串集定义。 相反，将该集合称为用该正则表达式表示的正则集合或生成的语言，记作L(r )。 正则表达式简称为正则表达式。 编程语言单词是具有特定格式的字符串，因此可以用正则表达式定义单词。 例如，如果字符由letter表示，数字由digit表示，则可以在正则表达式中将标识符集定义为letter(letter|digit)*。 其中，letter和(letter|digit)*表示两者，“|”表示选择两个表达式之一，“letter|d

7、igit”表示选择letter或digit，“*”表示引用“*”标记0次以上的表达式letter(letter|digit)*表示以字母开头的字母数字字符串或标识符集。 letter(letter|digit)*是表示标识符的正则表达式，标识符集是该正则表达式表示的正则集。 对于给出的字母，正规式和正规集的递归定义： (1)都是以上的正规式，表示的正规集分别是和。 (2)对于任意的a、a为以上的规则式，表示的规则集为a。 (3)如果r和s是以上的规则式，它们表示的规则集分别是L(R )和L(S )，则R|S是以上的规则式，表示的规则集是L(R)L(S )； RS是以上的规则式，表示的规则集是L

8、(R)L(S )； (R)*是以上的正规式，其表示的正规集是(L(R)*； (r )也是以上的正规式，其表示的正规集合是L(R )。 (4)仅从有限次使用规则(1)(3)中得到的式子是以上的正规式，其表示的集合是以上的正规集合。正则式之间的运算符“|”或“”表示连接(通常可省略)，“*”表示闭包，可以使用括弧来改变运算的顺序。 如果规定“*”优先于“”，而“”优先于“|”，则可以省略括号而不混淆。 注意到正则表达式a、字符串a、符号a这三个含义不同，可以从上下文中明确区分所提及的a的具体含义。 对于以上的规则式r和s，如果是表示规则集L(R)=L(S )，则r和s被称为等价，记作R=S。 正则

9、表达式的性质(1)交换规则： R|S=S|R。 结合法则： R|(S|T)=(R|S)|T R(ST)=(RS)T。 (3)分配律： R(S|T)=RS|RT； 中国语： t=rt|ST。 (4)一律： R=R=R。 (5)幂等律： R*=R*，例3-2令=a、b L(a|b)=a、b。 对于L(a|b)(a|b)=aa、ab、ba、bb，表示相同集合的另一规则表达式可以是aa|ab|ba|bb。 L(a*)=、a、aa、aaa。 L(a|b)*)=、a、b、aa、ab、ba、bb、aaa、aab、aba、abb、baa、bab、aba。 也可以用正则表达式(a*b*)*表示。 L(a|a*b

10、)=a、b、ab、aab、aaab表示紧跟在串a之后的包括零个或多个a的字符串集合。 例3-3证明：假设L(a )=a*-的话，有a=aa*。 证明L(a )=a*-=、a、a2、a3、-=a、a2、a3、=a、a2、=aa*=l(a)l ()状态转换图是有向图，节点表示状态，用圆表示的节点之间可以用有向边连接，有向边可以标记字符。在状态I的下方显示从节点I前往节点j的符号字符x的有向边。如果输入字符为x，则读取x并转变为状态j。 也就是说，光节点的数量有限，在其中必定存在初始状态(简称为初始状态，通常以start表示)和一些结束状态(简称为结束状态)，结束状态的光节点用双圈表示，与其他状态相

11、区别。 从初始状态，状态转移图的有向边上的文字逐个匹配输入文字，到达最终状态时，输入文字构成该状态转移图中被识别的一个单词。标识符和无符号数量的状态转移图(a ) -标识符(b ) -无符号整数(c ) -用于标识无符号数量(例如，标识符、无符号整数、无符号数量)的状态转移图，其初始状态均用0来表示。 有些结束状态，读取不属于该单词的其他符号后，获取对应的单词代码。 这表示在识别单词的过程中读取了符号，所以在识别了单词之后，必须回滚最后读取的符号。对于这种情况，我们的处理是在终端状态下显示“*”。 以模式“=”和“”的状态转移图为例。 状态转移图的实现状态转移图容易通过程序实现，最简单的方法是

12、使短程序对应于各状态。 对于不包含循环的分支状态，可以与一组switch ()或if-else语句相对应。 在包含循环的状态下，可以与while语句相对应。 最终状态通常对应于return ()语句，return表示从词法分析器调用段，通常表示解析器。 程序的大小与图中的状态数和边数成正比。c语言子集的单词符号和内码值，综合示例： c语言子集的简单词法分析器、简单词法分析的状态迁移图、(1) character :字符变量、最新读取的源程序字符。 (2) token :收纳构成单词的字符串的字符数组。 (3) getbe () :过滤空白字符。 (4) concatenation () :将t

13、oken中的字符串与character中的字符连接，作为token中的新字符串。 (5) letter ()和digit () :确定character中的字符是否为字母和数字布尔函数，返回true，否则返回false。 (6) reserve () :在token数组的字符串查找表中判别是否为保留字，如果是保留字则返回该代码，否则返回0的值。 (7) retract () :将扫描指针空白1个字符，同时将character留空。 (8) buildlist () :将识别符登录在符号表中，或者在常数表中登录常数。 (9) error () :出现不正确的文字，显示错误信息。 token0=0

14、； token数组初始化*/s=getchar ()； getbe ()； /*空格*/switch (s ) casea : caseb 3360 casez :while (letter () digit () ) concatenation ()/*目前读取的字元为token阵列*/getchar ()； retract ()； 扫描指针移动一个字符*/c=reserve ()； if (c=0)构建列表()； /*在符号表中注册标识符*/return (指向id、id的符号表条目指针)、else return (保留字代码，空) case 0: case 13360 case 9336

15、0 while (digit () ) co getchar ()； retract ()； 生命列表()； /*在常数表中登录常数*/return (num，num的常数表入口指针) case : return (，null )； case-:返回(-，空值)； case * :返回(*，空值)；case : getchar ()； 回复(回复，回复) :回复()； 回复(回复，回复)； case=: getchar ()； 字符=返回(循环，EQ )； else retract ()； return (=)； case；返回(； _ )； default :错误()； 3.4有穷人机器人，

16、穷人机器人(FA，finite automata )是更一般化的状态迁移图，可分为有穷人机器人DFA和无穷人机器人NFA两种。 通过构建贫穷机器人，可以从正则表达式导出识别正则集合的识别器。 有确定和不确定的贫穷机器人，只能识别正规集合。 也就是说，可以识别正则表达式表示的语言。确定的穷人机器人导出的识别器可能比不确定的穷人机器人导出的识别器快得多，而确定的穷人机器人可能比等价的不确定的穷人机器人大得多。 3.4.1穷人机器人(DFA，deterministic finite automata )定义确定：穷人机器人MD (标记为df amd )为五组Md=(S，f )。 (2)是贫穷的输入字母(3) f是从s到s的单值映射，称为转换函数，f(si，a)=sj，有si、s