词法分析器的设计与实现.doc

词法分析器的设计与实现摘要：词法分析是源程序翻译的第一个阶段，它从词的级别上验证程序的合法性，为后继的语法分析、语义分析服务，为他们提供必要的与词相关内容。词法分析的思想在实际中也有很广泛的应用。关键字：词法分析器 正规式 自动机The Design and Implementation of lexical analyzerZHANG LanFinance and Economy college of Computer and Information Management Department , Inner Mongolia, Hohhot, 010051,ChinaAbstract： Lexical Analysis Program is the first stage of the translation from the level of words on the legality of the verification process. To follow the syntax analysis, semantic analysis, as they provide the necessary words associated with the content. Lexical analysis of the ideological and practical application in a wide range of applications.Key words : lexical analyzer regular automatic machine 词法分析器是编译程序进行翻译的第一个阶段，他对程序进行线性分析，从字符串中分出单词，并检查所分出的单词是否为合法的词类。编译中的分词思想在“文本格式化”及“公式排版”中应用的比较广泛，是一种实用性很强的分析方法。词法分析在教学上的主要应用是对源程序进行分词同时验证词的合法性，词法分析的输入是给定的模型语言，输出为单词序列。我给定的模型语言如图1。从词的角度来看，它涉及的内容较为简单，只包括几个较为常用的词类，词类的构成上也适当的作了一些简化。对词进行分析时，我们是按类型进行分析的。上面的单词可以分为“标识符”、“无符号整数”、“分隔符”、“运算符”几类。每个类型中的单词都有它的构成规则。符合构成规则的即为合法的类型，否则，为不合法。下面给出部分词类的正规式描述。<标识符><字母> (<字母><数字>)*<无符号整数>=<数字>（数字）*<分隔符>=;|n|<运算符>=+|-|*|/<赋值运算符>=:=正规式是一种常用的描述单词的手段。它简单、清晰。能清楚地描述出单词的构成。并且可以方便的转化为单词的识别装置自动机。根据给定的正规式得到的自动机如下图。 1 2字母字母数字 图1 标识符的自动机 1 2数字数字图2 无符号整数的自动机 2:= 图3 赋值运算符的自动机 1 2数字自动机是从识别的角度来看待单词。通过人为的在自动机（本质上是一个有向图）上找一条从起点到终点的路径就可以确定某个单词是否为合法的单词。自动机的另一个特点是可以非常方便的转化为程序。我们可以将每类单词连接成为只有一个入口一个出口的自动机。连接后的自动机如下图4。图4 模型语言单词的自动机该图已经确定化。为了提高效率，还可以将图最小化，即合并等价状态，减少状态总数。最小化后的状态图可以很方便的翻译为程序代码，而且效率较高。最后用直接转向法实现有限自动机，生成词法分析程序。部分代码如下。while(x!='')ai=x;i+;scanf("%c",&x);ai='0'printf("%sn",a);for(j=0;j<i;j+)if(aj=' ') strcpy(bj4,bj1);continue;if(aj<='z'&&aj>='a'|aj>='A'&&aj<='Z')bj1aa+=aj;while(aj+1>='0'&&aj+1<='9')j+;bj1aa+=aj;bj1aa='0'elseif(aj>='0'&&aj<='9')bj2b+=aj;bj2b='0'elseif(aj='+'|aj='-'|aj='*'|aj='/'|aj='=')bj3c+=aj;bj3c='0'elseprintf("输入错误！n ");printf("%sn%sn%sn",bj1,bj3,bj2);x=3;while(x>0)待添加的隐藏文字内容2x-;if(strcmp(bj4,lxx)=0) printf("%s是标识符n",bj4);bj=1;if(bj=0) printf("%s标识符定义错误n",bj1);bj=0;m=0;while(bj1m=bj4m)m+;for(x=0;x+m<100;x+)bj1x=bj1x+m;x=3;while(x>0)x-;if(strcmp(bj1,lxx)=0) printf("%s是标识符,不能定义为变量n",bj1);bj=1;if(bj=0) printf("%s不是标识符,是用户定义的变量n",bj1);printf("附值符号是：%sn",bj3);printf("您给定的值是：%sn",bj2);词法分析器设计器还需要注意以下问题。在设计程序时，需要为源程序设计一个符号表，符号表用来保存标识符信息，为单词语法分析和语义分析服务。验证了单词的合法性后，可以将单词放入符号表中，符号表中的表项除了类型名和数值以外还需要添加一些其他项目。语法分析、语义分析时，从符号表中读取单词信息，将其它后继处理的信息放入空白表项中保存。另外在处理过程中可能遇到“超前搜索”问题。当读入一个字符时，循环结束，不进行相关操作。下一次对字符操作前是要将多读入的字符回退。词法分析在整个编译器设计中处于初级阶段，词法分析器的设计与实现相对较简单。本文中所提到的词法分析器的设计还有待于进一步改进。如为了实现快速的表搜索，可以引入散列来设计各类需要存储的表等。参考文献1 陈火旺，刘春林.程序设计语言编译原理（第3版）M.北京：国防工业出版社，20002 Alfred V.Ano,Ravi Sethi,Jeffrey D.Ullman，编译原理，机械工业出版社，2003.83 张素琴，吕映芝，蒋维杜，戴桂兰，编译原理，清华大学出版社，2005.10