第2章--编译原理词法分析.ppt

2.1词法分析器设计方法。词汇分析是编译的第一阶段。它的任务是从左到右逐个字符地扫描源程序，生成单词符号，并将字符串形式的源程序转换成单词符号字符串形式的中间程序。执行词法分析的程序称为词法分析程序，也称为词法分析器或扫描器。词法分析器的功能是输入源程序和输出单词符号。词汇分析可以采用以下两种处理结构：(1)以词汇分析程序为主程序。词法分析作为一个独立的过程完成，即词法分析和语法分析明显分离，词法分析程序将字符串形式的源程序转换成单词符号串形式的中间程序，该中间程序作为语法分析程序的输入。在这种处理结构中，词法分析和语法分析是分开实现的，如图2-1(a)所示。(2)词法分析程序作为语法分析程序调用的子程序。在语法分析期间，每当语法分析程序需要一个单词时，就调用词法分析程序，并且词法分析程序在每次调用语法分析程序时从字符串源程序中识别出一个单词。在这种处理结构中，词汇分析和语法分析实际上是交替进行的，如图2-1(b)所示。由于将词法分析器安排为子例程是很自然的，因此词法分析器通常采用第二种处理结构。图2-1词法分析的两种处理结构(一)词法分析程序为主程序；(b)词法分析程序是一个子程序，2.1.1单词符号分类和输出形式1。单词符号分类词汇分析程序只是一个单词阅读程序，它扫描用高级语言编写的源程序，并将源程序中由单词符号组成的字符串一个接一个地分解成单词。因此，单词符号是程序语言的基本语法单位，具有明确的语法意义。程序语言中的单词符号一般可分为以下五种类型：(1)保留单词(也称为基本单词):如c语言中的if、else、while和do，它们保留了语言中指定的含义，是编译器识别各种语法成分的基础。几乎所有的编程语言都限制用户使用保留字作为标识符。(2)标识符：用于标记常数、数组、类型、变量、过程或函数名等。通常由用户自己定义。(3)常数：包括各种类型的常数，如整数常数386、实数常数0.618、布尔常数真等。(4)操作者：如、“*”、“/”、“等等。(5)定界符：在语言中用作语法定界符，如、；“(”、“”)等。程序语言中保留字、运算符和分隔符的数量是确定的，而标识符或常数的使用不受限制。我们知道词法分析程序的输入是源程序字符串，输出是相当于源程序的单词符号序列，输出单词符号通常表示为以下二进制形式：(单词类型，单词本身的值)(1)单词类型。单词类型表示单词的类型，这是语法分析所需的信息。如何将一种语言的文字符号分成几类，如何将它们分成几类，以及如何对它们进行编码都是技术问题，主要取决于处理的方便性。通常让每个单词对应一个整数，这样可以最大程度地区分每个单词。对于保留词来说，它们可以被看作一种类型或一种类型。使用逐词分类方法更方便。标识符通常被归入一个类别。常量可以根据整型、实型、布尔型等分为一种类型或几种类型。运算符和分隔符可以分为一个运算符和一个运算符，也可以分为一个运算符。(2)词本身的价值。这个词本身的价值是其他编译阶段所需的信息。对于一个单词符号，如果一个类别只包含一个单词符号，那么对于这个单词符号，它的类别代码完全代表它自己的值。如果一个物种包含不止一个单词符号，那么对于每个单词符号，除了物种代码之外，还应该给出单词符号本身的值，以便区分同一物种的单词。请注意，标识符本身的值是标识符本身的字符串，而常量本身的值是常量本身的二进制值。此外，我们还可以使用指向特定类型表中特定项目的指针来区分同一类型的不同单词。例如，对于标识符，它在符号表中的入口指针可以用作它自己的值；常量也可以使用常量表中的条目指针作为自己的值。状态转换图在词法分析中，可以用状态转换图来识别单词。状态转移图是有限有向图。节点代表状态，用圆圈表示。节点可以通过有向边连接，字符可以标记在有向边上。例如，图2-2示出了在状态I中，如果输入字符是x，则x被读入并且状态j被切换。如果输入字符是y，则y被读入，状态k被切换。状态(即节点)的数量是有限的，并且必须有一个初始状态和几个终止状态。处于终止状态(最终状态)的节点用双圆圈表示，以区别于其他状态。图2-3示出了用于识别标识符、无符号整数和无符号数的状态转换图，并且它们的初始状态都由0状态表示。图2-2不同输入字符的状态转换，图2-3标识符和无符号数的状态转换图(a)标识符；(b)无符号整数；(c)无符号数，当达到一类单词符号的结束状态时，可以给出相应的单词代码。一些终止状态在读入另一个不属于该单词的符号后得到相应的单词代码，这表明在识别单词的过程中又读入了一个附加符号，所以最后读入的符号应该在识别单词后返回；我们对这类病例的治疗在最后状态标有“*”。对于没有循环的分支状态，可以使它对应于switch()语句或一组if-else语句。例如，对应于图2-4(a)中状态I的开关语句如下：开关 casea : caseb :casez :；/*实现状态J功能的语句*/CASE 0: CASE 1:CASE 9:；/*语句*/，实现状态K函数，可以使其对应于带有循环的状态的while语句。例如，对应于图2-4(b)中状态I的while语句如下：while(letter()| | chgit()getchar()；/*实现状态J *功能的语句/最终状态一般对应一个return()语句；返回意味着从词法分析器返回到调用段，这通常指返回到解析器。图2-4示出了具有分支或循环的状态(a)具有分支I的状态；2.2作为一个简单的词法分析器示例，2.2.1C语言子集的单词符号代表了一个非常重要的事实：大多数程序语言单词符号可以通过状态转换图来识别。作为一个综合的例子，让我们构造一个简单的C语言子集的词法分析器。表2.1列出了C语言子集的所有单词符号及其类型代码和内部代码值。因为直接使用整数编码不利于记忆，所以在本例中使用了一些特殊符号来表示类型编码。表2.1C语言子集的单词符号和内部代码值，2.2.2C语言子集对应于状态转换图中的状态转换图的设计，首先对输入字符串进行预处理，即消除多余的空白字符(在实际的词法分析中，预处理还包括消除注释和制表换行符等编辑字符)，使词法分析简单明了。其次，保留字被视为特殊标识符，即保留字没有特殊的对应状态转换图。当转换图识别一个标识符时，检查表2.1中的前五项以确定它是否是一个保留字。当然，也可以建立一个保留字表进行处理。图2-5是对应于表2.1的简单词汇分析的状态转换图。图2-5简单词法分析的状态转换图。在状态2中，识别的标识符应与表2.1中的前五项逐一比较。如果匹配，则标识符是保留字，否则是标识符。如果是标识符，首先查找符号表，看看表中是否有这样的标识符。如果表中没有这样的标识符，将其记录到符号表中，然后将其在符号表中的入口指针(地址)作为标识符的内部代码值返回；如果表中有这个标识符，将给出一个重复名称错误消息。在状态4中，被识别的常数将被转换成二进制常数并记录在常数表中，然后它在常数表中的入口指针将作为常数的内部代码值返回。2.2.3状态转换图的实现状态转换图很容易用程序实现，最简单的方法是使每个状态对应于一小部分程序。对于图2-5的图形，我们首先引入一组变量和过程如下：(1)字符：字符变量，它存储新读取的源程序字符。(2)标记：字符数组，它存储构成单词符号的字符串。(3)getbe():如果字符中的字符为空，则调用getchar()直到字符非空。(4) concatenate():将标记中的字符串与字符中的字符连接起来，并将其用作标记中的新字符串。(5)字母()和数字():判断字符中的字符是否为字母和数字的布尔函数，如果是，返回真，否则返回假。(6)reserve():根据令牌数组中的字符串，查找表2.1中的前五项(即判断是否为保留字)；如果是保留字，返回它的代码；否则，返回值0。(7)retract():扫描指针回滚一个字符，同时将该字符留空。(8)buildlist():在符号表中注册标识符，或者在常量表中注册常量。(9)错误():出现非法字符，显示错误消息。相对于图2-5的词法分析器的结构如下：/*初始化令牌数组*/s=getchar()；getbe()；/*过滤出空间*/开关casea: caseb:casez: while(字母()u digit()， cooperative()；/*将当前读取的字符发送到令牌数组*/getchar()；收回()；/*扫描指针返回一个字符*/c=保留()；if(c=0) build list()；/*将标识符登录到符号表*/return(id，指向id的符号表条目指针)；，elsereturn(保留代码，空)；休息；case 0: case 1:case 9: while(数字()串联()；getchar()；收回()；build list()；/*将常量记录到常量表中*/return(常量表条目指针为num，num)；休息；case :return(，null)；休息；凯斯。返回(？null)；休息；case*:return(*，null)；休息；case : getchar()；如果(字符=)返回(relop，LE)；否则 retract()；返回(重新运行，LT)；休息；case=: getchar()；如果(字符=)，返回(relop，EQ)；否则 retract()；返回(=，_)；休息；案例； return(；_)；休息；default : error()；、2.3规范表达式和有限自动机简介、2.3.1规范表达式和规范集状态转移图对于构造词法分析程序是有效的。为了便于自动生成词法分析器，状态转换图的概念必须形式化。正则表达式是一种形式表示，它可以表示单词符号的结构，从而精确地定义单词符号集。正常表达式简称为正常表达式，它所代表的集合是正常集合。为了理解范式和范式集的含义，我们以程序语言中的标识符为例进行说明。程序语言中使用的标识符是以字母开头的字母数字字符串。如果字母用字母表示，数字用数字表示，标识符可以用letter(letterdigit)*表示，其中字母和(字母数字)*的并置表示两者之间的联系；括号内的“”表示字母或数字；“*”表示零个或多个对由“*”标记的表达式的引用；(字母数字)*是字母数字的零个或多个并置，表示长度为0、1、2，字母(字母数字)*表示以字母开头的字母数字字符串，即一组标识符。字母(字母数字)*是表示标识符的正常表达式，标识符集是由该正常表达式表示的正常集。对于给定的字母，正规形和正规集的递归定义如下：(1)和是上的正规形，它们所代表的正规集分别是和。(2)对于任何a ，a是上的正规形，它所代表的正规集是a。(3)如果r和s是上的正规表达式，它们所代表的正规集是L(R)和L(S)，那么：(1) R S是上的正规表达式，它所代表的正规集是l(r)l(s)；(2) R.S是上的正规形，它所代表的正规集是l(R)l(S)；(3) (r) *是上的正规表达式，它表示的正规集是(l(r)*；R也是上的正规形，它所代表的正规集是L(R)。(4)通过仅使用规则(1)至(3)有限次而获得的表达式是上的正规表达式，并且它所代表的集合是上的正规集合。在上述定义中，规则(1)和(2)是基本规则，规则(3)是归纳规则，规则(4)是边界规则或终止规则。此外，上的一个单词指的是由中的字符组成的有限序列；不包含任何字符的序列称为空词，用表示。我们用 *来表示上的所有单词，并且还包括空单词。例如，如果=a，b， *=，a，b，aa，ab，ba，bb，aaa，。我们还使用来表示不带任何元素的空集。请注意、和之间的区别：是一组空单词，而是一组没有任何单词的单词。1.正常表达式之间的运算符“”表示或，“”表示连接(通常省略)，“*”表示结束。使用括号更改操作顺序。如果 * 优先于 并且 优先于，圆括号也可以省略而不会混淆。请注意， *的范式r和s之间的联系可以正式定义为RS=RelSetReturn(关键字(标识) 17位(数字)*