词法分析器的设计与实现

《词法分析器的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、词法分析器的设计与实现　　(内蒙古财经学院计算机信息管理学院，内蒙古呼和浩特010051) 　　摘要：介绍了词法分析器的概念，并指出词法分析器设计时，输入的源程序以文件的形式存储在外部。主控程序通过打开文件调用待分析的源程度。 关键词：词法分析器;正规式;自动机 　　中图分类号：TP391文献标识码：A文章编号：1007—6921(XX)14—0223—02 　　词法分析是编译程序进行翻译的第一个阶段，他对程序进行线性分析，从字符串中分出单词，并检查所分出的单词是否为合法的词类。编译中的分词思想在“文本格式化”及“公式排

2、版”中应用的比较广泛，是一种实用性很强的分析方法。 　　词法分析顾名思义就是分词。它以程序设计语言编制的源程序作为输入，以单词序列作为输出。分词过程可以通过编制程序自动完成，我们通常称这个分词程序为词法分析器。词法分析器分析的源程序可以是现有的各类程序设计语言源程序也可以是人为给定的模型语言的源程序。本文中的源程序为后者。 1词法分析器的设计 　　词法分析在教学上的主要应用是对源程序进行分词同时验证词的合法性，词法分析的输入是给定的模型语言，输出为单词序列。输入的源程序可以看成是一个字符串序列，通过把源程序看作字符串序列就

3、可以采用形式语言的一些现有理论处理相关的编译问题。分词的输出为单词序列，单词是一个有共同含义的字符集。由于程序设计语言中通常使用空格来分割不同的词，因此初学者在理解这一概念时可以简单的把空格分隔开的字符串认为是一个单词。 　　词法分析器设计时，输入的源程序以文件的形式存储在外部。主控程序通过打开文件调用待分析的源程序。 　　我给定的模型语言如图4。从词的角度来看，它涉及的内容较为简单，只包括几个较为常用的词类，词类的构成上也适当的作了一些简化。对词进行分析时，我们是按类型进行分析的。不同类型的词在后续的分析中所起的作用不同，相

4、应的操作也各有不同，但同种类型中的词虽然单词的构成不同但从宏观上看它们的操作大体一致。模型语言中的单词可以分为“关键字”、“标识符”、“常数”、“分隔符”、“运算符”几类。一般，关键字在程序设计语言中人为给定。程序设计时采用一字一码的形式处理。标志符为一类，不同的标志符通过值区别。常数只给出具体的值即可。根据以上的分析可以相应的设计如下的存储结构。 关键字可以设计为一个预先存储好的表格。 标志符和常数的逻辑结构设计如下： structToken { 　　Token[JX*2]-[JX-*2]Typet char*ch

5、}; 和 structToken { 　　Token[JX*2]-[JX-*2]Typet doublevalue; }; 　　每个类型中的单词都有它的构成规则。符合构成规则的即为合法的类型，否则，为不合法。下面给出部分词类的正规式描述。 ＝()* =(数字)* =;

6、''

7、'' =+

8、-

9、*

10、/ =:= 　　正规式是一种常用的描述单词的手段。它简单、清晰。能清楚地描述出单词的构成。并且可以方便的转化为单词的识别装置——自动机。根据给定的正规式得到的自动机如图。 　　740)this.width=

11、740"border=undefined#111nmousewheel="returnzoom_img(event,this)"> 　　740)this.width=740"border=undefined#111nmousewheel="returnzoom_img(event,this)"> 　　自动机是从识别的角度来看待单词。通过人为的在自动机(本质上是一个有向图)上找一条从起点到终点的路径就可以确定某个单词是否为合法的单词。自动机的另一个特点是可以非常方便的转化为程序。我们可以将每类单词连接成为只有一个入口一

12、个出口的自动机。连接后的自动机如下图4。 　　740)this.width=740"border=undefined#111nmousewheel="returnzoom_img(event,this)"> 　　该图已经确定化。为了提高效率，还可以将图最小化，即合并等价状态，减少状态总数。最小化后的状态图可以很方便的翻译为程序代码，而且效率较高。最后用直接转向法实现有限自动机，生成词法分析程序。 　　词法分析程序识别某类单词的部分代码如下。 token.ch=Buffer; for(;;) { Ch

13、ar=GetChar(); 　　if(Char=='')LineNo++; 　　if(!isspace(Char))break;//如果字符不为空结束取一个字符 } 　　AddCharTokenString(Char);