文档介绍：题目全称:常用边缘算法的实现
学生学号: 姓名
指导老师: 职称:
指导老师评语:

词法分析器构造

摘要:词法分析器构造技术起源于编译器前端的词法分析需求,是编译的第一阶段。其主要任务是读入输入字符,产生记号序列,并提交给语法分析使用。词法分析器技术也经常应用于其他领域,如查询语言与信息检索系统。在每个应用中,最基本的问题是如何设计与说明一种特殊的程序,它能够完成由字符串的模式触发的动作。本文通过实际构造FineC语言(作者设计的一个C语言的轻量子集)的词法分析器对词法分析器的构造原理做了基于实践的探讨。
关键字:词法分析器,双缓冲区,符号表,正则表达式,状态转换图

一、目的及意义
词法分析代表了一类问题的集合,即如何对输入字符串中的特定模式进行具备特定动作的匹配。解决此类问题,不仅对于编译器开发中的阶段抽象具有重要意义,更对应用领域中有关字符处理的需求具有深刻价值。
设计和实现词法分析器,要用到词素、记号、正则表达式、输入字符双缓冲区、符号表、状态转换图设计等概念。抽象地阐述这些概念往往晦涩难懂,而结合某一具体编译器的前端实现来分析探讨,则容易使概念条理清晰,目的明确。因此,从设计一个轻量级语言开始,根据语言编译的要求设计和实现词法分析器,将原理与实践结合,将是研究此类问题的最佳途径。
二、FineC语言词法设计:
这里定义一个编程语言称作FineC(“fine”指代轻量、精妙)。它是一种适合编译器设计方案的语言。本质上是C语言的一个限制了数据类型、算术操作、控制结构和处理效率的轻量子集。
这里仅给出与其词法分析器相关的词法标准描述:
[1]下面是语言的关键字:
else if return while int void
所有的关键字都是保留字,并且必须是小写
[2]下面是专用符号:
+ - * / < <= > >= == != = ; , { } [ ] ( ) /* */
[3]其他标记是NUM和ID,由正则表达式定义:
ID = letter (letter|digit)*
NUM = digit digit*
letter = a|…|z|A|…|Z
digit = 0|…|9
小写和大写字母是有区别的
[4]空格由空白、换行符和制表符组成。空格通常被忽略,除了它必须分开NUM、ID关
键字
[5]注释用通常的C语言符号/*…*/围起来。注释可以放在任何空白出现的位置(即注释
不能放在标记内)上,且可以超过一行。注释不能嵌套。不支持单行//注释。
三、词法分析器原理
词法分析器的作用:
词法分析器的主要任务是读入输入字符,产生记号序列,提交给语法分析使用。这种交互通常可以通过使词法分析器作为语法分析器的子程序或协作程序来实现。如下图所示:
词法分析器
语法分析器
记号
取下一个记号
符号表
源程序
图1 词法分析器与语法分析器的交互
在FineC的实践中,将词法分析器的主体定义为一个函数,函数声明为token nexttoken()。函数可以又语法分析器调用,返回给语法分析器一个记号。记号类由两个整型值组成,int tokentype表示记号的类型(如ID、NUM、分号、左括号等等),int lexeme表示记号的属性(用来区分一类记号不同的个体差异。如ID表示标识符,但某一具体标识符的名字,即词素信息,则包含在lexeme中)。
语法分析器可以根据返回的记号类型及记号属性,根据语法定义选择合适的产生式进行语法分析。另外,词法分析器还可以发现词法分析阶段源程序词法级错误,并做出相应的错误处理和提示。
记号、模式和词素
在词法分析的讨论中,我们使用术语“记号”、“模式”、“词素”表示特定的含义。
通常,在输入中有一组字符串会产生相同的记号,这个字符串构成的集合又一个与该记号相关联的称为“模式”的规则来描述。这个“模式”被说成匹配该集合中的每个字符串。最常用的描述模式的工具是正则表达式(正则表达式的概念稍后介绍)。词素是源程序的字符序列,由一个记号的模式来匹配。
例如,Pascal语句:
const pi = ;
中,pi是一个记号,其记号类型为“ID”(标识符),其词素是“pi”,其模式是由一个字母开头的字母或数字串。词法分析器分析pi时,成功匹配了标识符的模式,保存其词素到符号表中(符号表的概念稍后介绍),并将记号类型ID和指向符号表中保存词素“pi”的表项的指针这两者作为一个记号整体,返回给语法分析器。
在多数程序设计语言中,下列结构被处理为记号:关键字、标识符、常量、操作符、问字串和标点符号(如括号、逗号和分号)。
记号的属性
如果一个记号