词法分析器的设计与实现

(内蒙古财经学院 计算机信息管理学院，内蒙古 呼和浩特 010051)
摘 要：介绍了词法分析器的概念，并指出词法分 析器设计时，输入的源程序以文件的形式存储在外部。主控程序通过打开文件调用待分析的 源程度。
关键词：词法分析器;正规式;自动机
中图分类号：TP391  文献标识码：A  文章编号：1007—6921(2008)14—0223—02

词法分析是编译程 序进行翻译的第一个阶段，他对程序进行线性分析，从字符串中分出单词，并检查所分出的 单词是否为合法的词类。编译中的分词思想在“文本格式化”及“公式排版”中应用的比较 广泛，是一种实用性很强的分析方法。

词法分析顾名思义就是分词。它以程序设计语言编制的源程序作为输入，以单词序列作为输 出。分词过程可以通过编制程序自动完成，我们通常称这个分词程序为词法分析器。词法分 析器分析的源程序可以是现有的各类程序设计语言源程序也可以是人为给定的模型语言的源 程序。本文中的源程序为后者。
1 词法分析器的设计

词法分析在教学上的主要应用是对源程序进行分词同时验证词的合法性，词法分析的输入是 给定的模型语言，输出为单词序列。输入的源程序可以看成是一个字符串序列，通过把源程 序看作字符串序列就可以采用形式语言的一些现有理论处理相关的编译问题。分词的输出为 单词序列，单词是一个有共同含义的字符集。由于程序设计语言中通常使用空格来分割不同 的词，因此初学者在理解这一概念时可以简单的把空格分隔开的字符串认为是一个单词。

词法分析器设计时，输入的源程序以文件的形式存储在外部。主控程序通过打开文件调用待 分析的源程序。

我给定的模型语言如图4。从词的角度来看，它涉及的内容较为简单，只包括几个较为常用 的词类，词类的构成上也适当的作了一些简化。对词进行分析时，我们是按类型进行分析的 。不同类型的词在后续的分析中所起的作用不同，相应的操作也各有不同，但同种类型中的 词虽然单词的构成不同但从宏观上看它们的操作大体一致。模型语言中的单词可以分为“关 键字”、“标识符”、“常数”、“分隔符”、“运算符”几类。一般，关键字在程序设计 语言中人为给定。程序设计时采用一字一码的形式处理。标志符为一类，不同的标志符通过 值区别。常数只给出具体的值即可。根据以上的分析可以相应的设计如下的存储结构。
关键字可以设计为一个预先存储好的表格。
标志符和常数的逻辑结构设计如下：
struct Token
{
Token[JX*2]-[JX-*2]Type  t
char *ch   
};
和 
struct Token
{
Token[JX*2]-[JX-*2]Type  t
double value;   
};
每个类型中的单词都有它的构成规则。符合构成规则的即为合法的类型，否则，为不合法。 下面给出部分词类的正规式描述。
<标识符>＝<字母> (<字母><数字>)*
<无符号整数>=<数字>(数字)*
<分隔符>=;|" \  n"|""
<运算符>=+|-|*|/
<赋值运算符>=:=

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



自动机是从识别的角度来看待单词。通过人为的在自动机(本质上是一个有向图)上找一条从 起点到终点的路径就可以确定某个单词是否为合法的单词。自动机的另一个特点是可以非常 方便的转化为程序。我们可以将每类单词连接成为只有一个入口一个出口的自动机。连接后 的自动机如下图4。


该图已经确定化。为了提高效率，还可以将图最小化，即合并等价状态，减少状态总数。最 小化后的状态图可以很方便的翻译为程序代码，而且效率较高。最后用直接转向法实现有限 自动机，生成词法分析程序。
词法分析程序识别某类单词的部分代码如下。
      token.ch=Buffer;   
      for(;;)
      {
            Char=GetChar();
            if(Char=="\ n") LineNo++;
            if(!isspace(Char))break;   //如果字符不为空结束取一个字符
      }
      AddCharTokenString(Char);
      if(isalpha(Char))     
      {
            for(;;)
            {
                  Char=GetChar();
                  if(isalnum(Char))AddCharTokenString(Char); 
                  else break;
            }
            BackChar(Char);
            t=Judge (Buffer);
            token.ch=Buffer;
            return t;
      }
      else if(isdigit(Char))
      {
            for(;;)
            {
                  Char=GetChar();
                  if(isdigit(Char))
AddCharTokenString(Char);
                  else break;
            }
            BackChar(Char);
            token.type=CONST[JX*2]-[JX-*2]ID;
            token.value=atof(Buffer);
            return token;
      }
      else
      {
            switch(Char)
            {
            case";":token.type=SEMICO;break;
            case",":token.type=COMMA;break;
            case"+":token.type=PLUS;break;
            default:token.type=ERRTOKEN;break;
            }
            }
2 词法分析器设计注意的问题

词法分析器设计还需要注意以下问题。

在设计程序时，需要为源程序设计一个符号表，符号表用来保存标识符信息，为单词语法分 析和语义分析服务。验证了单词的合法性后，可以将单词放入符号表中，符号表中的表项除 了类型名和数值以外还需要添加一些其他项目。语法分析、语义分析时，从符号表中读取单 词信息，将其他后继处理的信息放入空白表项中保存。

另外在处理过程中可能遇到“超前搜索”问题。当读入一个字符时，循环结束，不进行相关 操作。下一次对字符操作前是要将多读入的字符回退。
3 结语

词法分析在整个编译器设计中处于初级阶段，词法分析器的设计与实 现相对其他几个阶段来说比较简单。本文中所提到的词法分析器的设计还有待于进一步改进 。如为了实现快速的表搜索，可以引入散列来设计各类需要存储的表等。
［参考文献］
［1］ 陈火旺，刘春林.程序设计语言编译原理 ［M］.北京：国防工业出版社，2000.
［2］ Alfred V·Ano,Ravi Sethi,Jeffrey D·Ullman，编译原理［M］.机械工业出 版社，2003.
［3］ 张素琴，吕映芝，蒋维杜，等.编译原理［M］.北京：清华大学出版社，2005.