论文一：词法分析器

计算机科学与工程学院课程设计报告题目全称：常用边缘算法的实现学生学号：2506203010姓名：王嘉指导老师：职称：指导老师评语：签字：课程设计成绩：设计过程表现设计报告质量总分词法分析器构造作者：王嘉学号：2506203010指导老师：吴洪摘要：词法分析器构造技术起源于编译器前端的词法分析需求，是编译的第一阶段。其主要任务是读入输入字符，产生记号序列，并提交给语法分析使用。词法分析器技术也经常应用于其他领域，如查询语言与信息检索系统。在每个应用中，最基本的问题是如何设计与说明一种特殊的程序，它能够完成由字符串的模式触发的动作。本文通过实际构造FineC语言（作者设计的一个C语言的轻量子集）的词法分析器对词法分析器的构造原理做了基于实践的探讨。关键字：词法分析器，双缓冲区，符号表，正则表达式，状态转换图正文：一、目的及意义词法分析代表了一类问题的集合，即如何对输入字符串中的特定模式进行具备特定动作的匹配。解决此类问题，不仅对于编译器开发中的阶段抽象具有重要意义，更对应用领域中有关字符处理的需求具有深刻价值。设计和实现词法分析器，要用到词素、记号、正则表达式、输入字符双缓冲区、符号表、状态转换图设计等概念。抽象地阐述这些概念往往晦涩难懂，而结合某一具体编译器的前端实现来分析探讨，则容易使概念条理清晰，目的明确。因此，从设计一个轻量级语言开始，根据语言编译的要求设计和实现词法分析器，将原理与实践结合，将是研究此类问题的最佳途径。二、FineC语言词法设计：这里定义一个编程语言称作FineC（“fine”指代轻量、精妙）。它是一种适合编译器设计方案的语言。本质上是C语言的一个限制了数据类型、算术操作、控制结构和处理效率的轻量子集。这里仅给出与其词法分析器相关的词法标准描述：[1]下面是语言的关键字：elseifreturnwhileintvoid所有的关键字都是保留字，并且必须是小写[2]下面是专用符号：+-*/====!==;,{}[]()/**/[3]其他标记是NUM和ID，由正则表达式定义：ID=letter(letter|digit)*NUM=digitdigit*letter=a|…|z|A|…|Zdigit=0|…|9小写和大写字母是有区别的[4]空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开NUM、ID关键字[5]注释用通常的C语言符号/*…*/围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。不支持单行//注释。三、词法分析器原理1.词法分析器的作用：词法分析器的主要任务是读入输入字符，产生记号序列，提交给语法分析使用。这种交互通常可以通过使词法分析器作为语法分析器的子程序或协作程序来实现。如下图所示：图1词法分析器与语法分析器的交互在FineC的实践中，将词法分析器的主体定义为一个函数，函数声明为tokennexttoken()。函数可以又语法分析器调用，返回给语法分析器一个记号。记号类由两个整型值组成，inttokentype表示记号的类型(如ID、NUM、分号、左括号等等)，intlexeme表示记号的属性（用来区分一类记号不同的个体差异。如ID表示标识符，但某一具体标识符的名字，即词素信息，则包含在lexeme中）。语法分析器可以根据返回的记号类型及记号属性，根据语法定义选择合适的产生式进行语法分析。另外，词法分析器还可以发现词法分析阶段源程序词法级错误，并做出相应的错误处理和提示。词法分析器语法分析器记号取下一个记号符号表源程序2.记号、模式和词素在词法分析的讨论中，我们使用术语“记号”、“模式”、“词素”表示特定的含义。通常，在输入中有一组字符串会产生相同的记号，这个字符串构成的集合又一个与该记号相关联的称为“模式”的规则来描述。这个“模式”被说成匹配该集合中的每个字符串。最常用的描述模式的工具是正则表达式（正则表达式的概念稍后介绍）。词素是源程序的字符序列，由一个记号的模式来匹配。例如，Pascal语句：constpi=3.1416;中，pi是一个记号，其记号类型为“ID”（标识符），其词素是“pi”，其模式是由一个字母开头的字母或数字串。词法分析器分析pi时，成功匹配了标识符的模式，保存其词素到符号表中（符号表的概念稍后介绍），并将记号类型ID和指向符号表中保存词素“pi”的表项的指针这两者作为一个记号整体，返回给语法分析器。在多数程序设计语言中，下列结构被处理为记号：关键字、标识符、常量、操作符、问字串和标点符号（如括号、逗号和分号）。3.记号的属性如果一个记号的模式不止能匹配一个词素，词法分析器必须为这个记号提供附加的关于匹配的特殊词素的信息。例如，模式NUM既能匹配字符串0，也能匹配字符串1，此时代码生成器需要知道NUM到底匹配了他们之中的哪一个。词法分析器吧与记号有关的信息收集到记号的属性中。记号影响语法分析，而属性影响记号的翻译。在实际实现时，记号的属性可能是指向符号表中一个表项的指针（ID记号的属性），也可能是数字字符串转化成的整形值（NUM记号的属性）。例如Fortran语句E=M*C**2中的记号和它们的属性值可用二元组序列表示如下：id，指向符号表中与E相关的表项的指针assign_op,id,指向符号表中与M相关的表项的指针mult_op,id,指向符号表中与C相关的表项的指针exp_op,num，整数值2而这种二元组序列正是我们的词法分析器要输出给语法分析器的结果。4.正则表达式描述记号的模式，通常使用正则表达式例如，标识符ID的模式可以用正则表达式“letter(letter|digit)*”表示。其中竖线表示“或”，括号用于子表达式组在一起，星号的含义是“零个或多个”括号中的表达式，letter和(letter|digit)*的并列表示两者的连接。下面我们形式化的定义正则表达式这一概念：I.ɛ是正则表达式，它表示{ɛ},即包含空串的集合II．如果a是字母表∑上的符号，那么a是正则表达式，表示{a}，也就是包含符号串a的集合。III．假定r和s都是正则表达式，分别表示语言L(r)和L(s)，则a)(r)|(s)是正则表达式，表示L(r)∪L(s)。b)(r)(s)是正则表达式，表示L(r)L(s)。c)(r)*是正则表达式，表示(L(r))*。d)(r)是正则表达式,表示L(r)。正则表达式表示的语言叫做正则集。建立正则表达式时，可以先建立简单的正则表达式，然后根据规则III构造出更复杂的正则表达式。例如，表示NUM的正则表达式digit(digit)*是这样构成的：digit表示单个的数字0—9，(digit)*表示零或者多个数字构成的数字串。将digit和(digit)*连接起来就能保证至少包含一位数字的数字串，也就是任意十进制（通过限定digit的集合可以更换进制）整数的正则表达式表示。正则表达式是计算机科学的一个重要概念，广泛应用于各个分支和领域，故这里不做详细的讨论。对于词法分析器的设计者，只需要掌握标识符ID和数字NUM的正则表达式就可以了。在进行了关于记号，词素，模式等基本概念的阐述后，又结合了正则表达式这一强有力的工具，现在我们可以规范化得描述FineC语言的词法翻译标准如下表：表1FineC语言翻译表模式记号属性elseelseelseifififintintintreturnreturnreturnwhilewhilewhilevoidvoidvoidGTLT=GE=LE==EQ!=NE++--**//[0-9]+num整数值[A-Za-z][A-Za-z0-9]*id指向符号表表项的指针==,,;;(())[[]]{{}}/**/接下来需要研究的，是如何设计一个词法分析器，来实现以上模式的匹配。在介绍词法分析器之前，先要介绍一下符号表和双缓冲区的概念。双缓冲区和符号表可以被比喻为词法分析器的两翼，在词法分析阶段与词法分析器合作密切。其中符号表的功能还将于编译器设计的语法分析，中间代码生成以致代码生成阶段所用，意义更为重要。5.符号表[1]符号表概述符号表是一种数据结构，通常用于保存源语言结构的各种信息。编译器在分析阶段收集信息放入符号表，在综合阶段使用符号表中的信息生成目标代码。在此法分析阶段，形成标识符的词素被存储在符号表的一个表项中。编译器的以后各个阶段会在这个表项上逐步添加其他信息，如标识符的类型、用处（用作过程名、变量名或标号）以及存储位置。在代码生成阶段，编译器使用这些信息生成存取这些变量的正确代码。[2]符号表的结构符号表的表项包括两个域，一个保存了记号的类型，另一个保存了指向词素表的指针。词素表可以看作是符号表的内表。我们用语句“intgcd(intu,intv);”词法分析后形成的符号表格局来阐述符号表和词素表之间的关系：图2符号表格局下面分析一下上图中符号表格局形成的步骤：intgcd(intu,intv);int是关键字，关键字（if、else、int、return、while、void）在符号表被词法分析器使用前先被加入到符号表中，这样当词法分析器识别出一个字母开头的字母数字串时，就无需再判断它究竟是标识符还是关键字，而只需做如下的操作：用当前字母数字串的内容搜索符号表，若已经存在（或者它是标识符且已经出现过，或者它是关键字），则返回指向符号表项的指针；若不存在，则将其插入符号表并返回指向新加入表项的指针。如此一来，关键字就被“保留”了起来而不会被错误地视作标识符。在上面的程序中，六个关键字先被加入到符号表中。当词法分析器得到输入时，匹配到“int”，通过符号表访问词素表，找到“int”，返回2（INT符号表项距离符号表首项的距离）。接下来匹配到“gcd”，通过符号表访问词素表，找不到“gcd”，则把“gcd”插入到词素表中并将其指针和ID（ID是一个宏定义）形成的符号表项插入符号表，并将指向此新表项的指针6返回给词法分析器。以此类推，等到词法分析器完成“v”的匹配时，就形成了上图中的格局。[3]符号表支持的操作由上面对符号表结构的解释，可以归纳出符号表与调用它的词法分析器有以下两个接口：查询操作——查询符号表，看某一字符串是否在符号表中（实际上查询的是词素表）。插入操作——若查询失败，则插入字符串到词素表中，并形成相应的符号表项然后插入符号表中。[4]符号表的初始化即将关键字“提前保留”在符号表中的过程，可以参照上面对符号表结构的解释理解其含义。IFELSEINTRETURN“if”“else”“int”“return”“while”“void”“gcd”“u”“v”WHILEVOIDIDIDID符号表词素表6.双缓冲区[1]输入缓冲对很多源语言来说，在一个词素被一个模式匹配上之前，词法分析器往往需要超前扫描该词素后面的若干字符。直接操纵源程序文件灵活性、速度和安全性不佳，因此人们开发出一些特殊的缓冲技术来弥补这些不足。在此简单地介绍一下最常用的双缓冲区的原理。词法分析器匹配符号时需要移动指向当前输入字符的指针，例如匹配完单个字符后的后移操作，匹配错误后的回归操作（具体解释将在后面的状态转换图部分阐述），匹配多余字符后的回滚操作等。这一系列的操作都需要在输入缓冲区上进行。[2]双缓冲区的结构双缓冲区的结构如下所示图3双缓冲区的结构顾名思义，双缓冲区就是由两个相同的大小为N的缓冲区域构成的整体。这两个存储区域协调工作如下：一次读取N个字符给其中一个缓冲区，当forward指针到达此缓冲区尾部时，将输入文件中的下面N个字符读入另一个缓冲区。之所以使用双缓冲区，是为了避免单缓冲区末尾某个词素匹配了一半，而读入下一批字符开头有这个词素的下一半，却因为新的读入而丢失了前面一半的情况。[3]双缓冲区支持的操作双缓冲区在工作时，需要两个指针，一个lexeme_beginning指向当前正在识别的词素的开头，一个forward指向当前指向的字符。当词法分析器成功匹配完一个符号后，位于lexeme_beginning和forwa