状态转化图

开篇

编译，简单的说，就是把源程序转换为可执行程序。从hello world 说程序运行机制 里面简单的说明了程序运行的过程，以及一个程序是如何一步步变成可执行文件的。在这个过程中，编译器做了很多重要的工作。对底层该兴趣的我，自然的，也就迫切想搞清楚编译的内部实现，也就是编译的原理。

这篇文章主要说的是编译器前端，词法分析器的原理，最后会给出一个词法分析器的简单实现。 

介绍

 编译简单的说，就是把源程序转化为另一种形式的程序,而其中关键的部分就是理解源程序所要表达的意思，才能转化为另一种源程序。

可以用一个比喻来说明问题：人A和人B想要交谈，但是他们都不知道彼此的语言，这就需要一个翻译C，同时懂得A和B的语言。有了C做中间层，A和B才能正常交流。C的作用就有点像编译器，它必须能理解源程序所要表达的意思，才能把信息传递给另一个。

编译器也一样，它的输入是语言的源文件（一般可以是文本文件）对于输入的文件，首先要分离出这个输入文件的每个元素（关键字、变量、符号、、）

然后根据语言的文法，分析这些元素的组合是否合法，以及这些组合所表达的意思。

程序设计语言和自然语言不一样，都是用符号来描述，每个特定的符号表示特定的意思，而且程序设计语言是上下文无关的。上下文无关就是某一个特定语句所要表达的意思和它所处的上下文没有关系，只有它自身决定。

这篇博文主要说的就是词法分析，也就是把输入的符号串整理成特定的词素。

词法分析

定义：

词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等

(1) 关键字 是由程序语言定义的具有固定意义的标识符。例如，Pascal 中的begin，end，if，while都是保留字。这些字通常不用作一般标识符。

(2) 标识符 用来表示各种名字，如变量名，数组名，过程名等等。

(3) 常数  常数的类型一般有整型、实型、布尔型、文字型等。

(4) 运算符 如+、-、*、/等等。

(5) 界符  如逗号、分号、括号、等等。

输出：

词法分析器所输出单词符号常常表示成如下的二元式：

                 (单词种别，单词符号的属性值)

单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。界符一般用一符一种的方法。对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。

示例：

比如如下的代码段：

while(i>=j) i--

经词法分析器处理后，它将被转为如下的单词符号序列：

  

   <(, _>

  

   <>=, _>

  

   <), _>

  

   <--, _>

   <;, _>

 

词法分析分析器作为一个独立子程序

词法分析是编译过程中的一个阶段，在语法分析前进行。词法分析作为一遍，可以简化设计，改进编译效率，增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。

词法分析器设计

输入、预处理

词法分析器工作的第一步是输入源程序文本。在许多情况下，为了更好地对单词符号识别，把输入串预处理一下。预处理主要滤掉空格，跳过注释、换行符等。

超前搜索

词法分析过程中，有时为了确定词性，需超前扫描若干个字符。

对于FORTRAN 语言，关键字不作为保留字，可作为标识符使用， 空格符号没有任何意义。为了确定词性，需超前扫描若干个字符。

在FORTRAN中

         1   DO99K=1,10

         2   IF(5.EQ.M) I=10

         3   DO99K=1.10

         4   IF(5)=55

这四个语句都是正确的语句。语句1和2 分别是DO和IF语句，语句3和4是赋值语句。为了正确区别1和3，2和4语句，需超前扫描若干个字符。

           1   DO99K=1,10          2   IF(5.EQ.M) I=10

           3   DO99K=1.10          4   IF(5)=55

语句1和3的区别在于符号之后的第一个界符：一个为逗号，另一个为句末符。语句2和4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。为了识别1、2中的关键字，必须超前扫描多个字符。超前到能够肯定词性的地方为止。为了区别1和3，必须超前扫描到等号后的第一个界符处。对于语句2、4来说，必须超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。

状态转换图

词法分析器使用状态转换图来识别单词符号。状态转换图是一张有限方向图。在状态转换图中，有一个初态，至少一个终态。

其中0为初态，2为终态。这个转换图识别（接受）标识符的过程是：从初态0开始，若在状态0之下输入字符是一个字母，则读进它，并转入状态1。在状态1之下，若下一个输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到状态1发现输入字符不再是字母或数字时（这个字符也已被读进）就进入状态2。状态2是终态，它意味着到此已识别出一个标识符，识别过程宣告终止。终态结上打个星号意味着多读进了一个不属于标识符部分的字符，应把它退还给输入口中 。如果在状态0时输入字符不为“字母”，则意味着识别不出标识符，或者说，这个转换图工作不成功。

正规表达式与正规集

正规表达式是说明单词的一种重要的表示法(记号)，是定义正规集的工具。在词法分析中，正规表达式用来描述标示符可能具有的形式。

定义(正规式和它所表示的正规集)：

设字母表为S，

1. e和?都是S上的正规式，它们所表示的正规集分别为{e}和{ }；

2. 任何a? S，a是S上的一个正规式，它所表示的正规集为{a}；

3. 假定U和V都是S上的正规式，它们所表示的正规集分别为L(U)和L(V)，那么，(U), U|V, U·V, U*也都是正规式,它们所表示的正规集分别为L(U), L(U)?L(V), L(U)L(V)和(L(U))*；

4. 仅由有限次使用上述三步骤而定义的表达式才是S上的正规式，仅由这些正规式所表示的字集才是S上的正规集。

正规式的运算符的“?”读为“或” ,“· ”读为“连接”；“*”读为“闭包”(即，任意有限次的自重复连接)。

在不致混淆时，括号可省去，但规定算符的优先顺序为“(”、“)”、“*”、“· ”、“?” 。连接符“· ”一般可省略不写。

“*”、“· ”和“?” 都是左结合的。

例 令S={a,b}， S上的正规式和相应的正规集的例子有：

正规式                 正规集

a          　　　　　{a}

a?b                    {a,b}

ab                       {ab}

(a?b)(a              {aa,ab,ba,bb}

a *                    {e ,a,a, ……任意个a的串}

ba*                                           {b, ba, baa, baaa, …}

(a?b)*                                      {e ,a,b,aa,ab ……所有由a和b

                                                  组成的串}

(a?b)*(aa?bb)(a?b)*               {S*上所有含有两个相继的a

                                                   或两个相继的b组成 的串}

 

定理：若两个正规式U和V所表示的正规集相同,则说U和V等价,写作U=V。

 证明b(ab)*=( ba)*b

证明：因为L(b(ab)*)={b}{e, ab, abab, ababab, …}

                                   ={b, bab, babab, bababab, …}

                   L((ba)*b) ={e, ba, baba, bababa, …}{b}

                                   ={b, bab, babab, bababab, …}

                                   = L(b(ab)*)

所以,  b(ab)*=( ba)*b

 

设U，V，W为正规式，正规式服从的代数规律有：

(1) U?V=V?U  (交换律)

(2) U?(V?W)=(U?V)?W   (结合律)

(3) U(VW)=(UV)W   (结合律)

(4) U(V?W)=UV?UW   (V?W)U=VU?WU   (分配律)

(5) eU=U e=U

分析器的简单实现

上文主要介绍了词法分析的一些相关的知识，而对词法分析器的具体实现还没有具体提到，为了能更好的理解词法分析，我写了一个简单的词法分析器。

虽然说是语法分析器，但实现的功能很简单，只是对输入的程序把注释去掉，其中用到了上面关于状态转换图部分的知识。

分析：

一般的程序设计语言， 注释部分的形式为；  

/* 注释部分、、、、*/

我们的程序总是顺序的一个一个字符读取输入文件的。我们的目的是把注释部分去掉，那么对于输入的字符流，我们只要识别出“/*”就知道后面的部分是注释部分，直到识别输入流中出现"*/"为止。

对字符流的处理是一个一个进行的，每读入一个字符，就判断，如果字符是“/”,就说明后面 的部分可能是注释，再看下一个输入字符，如果是“*”, 就是上面所说的情况：“ /*”那么后面的部分就是注释部分，然后再用相同的方法找出"*/"就可以了。

这个识别的过程就可以用状态转换图来清晰的表示:

对于读入的每个符号都要进行判断，如果是“/”说明后面的部分有可能是注释，进入状态1。如果后面的输入是“*”那么就可以确定以后的内容为注释内容，如果后面的输入不是"*"，说明后面的内容不是注释，前面出现的"/"可能是做除号使用，如“5/3”

其实上面的流程图也就对应了程序实现的逻辑，可以用switch-case 来实现，对于每个输入，判断后跳转到相应的状态，然后继续判断。

下面是程序伪代码：

while((ch=getchar())!=EOF)

　　switch(state)

　　　　case 1 :if ch=="/",state=2,break;

　　　　case 2: if ch=="*",state=3

　　　　　　　　else state=1;break;

　　　　case 3:..........

　　　　case 4:..........

 

词法分析器

这个程序比较简单，就不给出源代码了。接下来是一个简单的词法分析器的代码，可以实现对关键字（如 while end if 等），对数字的识别，去掉空格符等。

下面是这个分析器的功能：

1、    待分析的简单语言的词法

（1）    关键字：

begin  if   then   while   do   end

所有关键字都是小写。

（2）    运算符和界符：

:=   +   –   *   /   <   <=   <>   >   >=   =   ;   (   )   #

（3）    其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义：

ID=letter（letter| digit）*

NUM=digit digit *

（4）    空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM,运算符、界符和关键字，词法分析阶段通常被忽略。

2、  各种单词符号对应的种别码

词法分析程序的功能

输入：所给文法的源程序字符串。

输出：二元组（syn，token或sum）构成的序列。

其中：syn为单词种别码；

token为存放的单词自身字符串；

sum为整型常数。

#include<stdio.h>
#include<string.h>
#include<iostream.h>
char prog[80],token[8];
char ch;
int syn,p,m=0,n,row,sum=0;
char *rwtab[6]={"begin","if","then","while","do","end"};

void scaner()
{
    /*
        共分为三大块，分别是标示符、数字、符号，对应下面的 if else if 和 else


    */
    for(n=0;n<8;n++) token[n]=NULL;
    ch=prog[p++];
    while(ch==' ')
    {
        ch=prog[p];
        p++;
    }
    if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) //可能是标示符或者变量名
    {
        m=0;
        while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
        {
            token[m++]=ch;
            ch=prog[p++];
        }
        token[m++]='\0';
        p--;
        syn=10;
        for(n=0;n<6;n++) //将识别出来的字符和已定义的标示符作比较，
            if(strcmp(token,rwtab[n])==0)
            {
                syn=n+1;
                break;
            }
    }
    else if((ch>='0'&&ch<='9')) //数字
    {
        {
            sum=0;
            while((ch>='0'&&ch<='9'))
            {
                sum=sum*10+ch-'0';
                ch=prog[p++];
            }
        }
        p--;
        syn=11;
        if(sum>32767)
            syn=-1;
    }
    else switch(ch) //其他字符
    {
        case'<':m=0;token[m++]=ch;
            ch=prog[p++];
            if(ch=='>')
            {
                syn=21;
                token[m++]=ch;
            }
            else if(ch=='=')
            {
                syn=22;
                token[m++]=ch;
            }
            else
            {
                syn=23;
                p--;
            }
            break;
        case'>':m=0;token[m++]=ch;
            ch=prog[p++];
            if(ch=='=')
            {
                syn=24;
                token[m++]=ch;
            }
            else
            {
                syn=20;
                p--;
            }
            break;
        case':':m=0;token[m++]=ch;
            ch=prog[p++];
            if(ch=='=')
            {
                syn=18;
                token[m++]=ch;
            }
            else
            {
                syn=17;
                p--;
            }
            break;
        case'*':syn=13;token[0]=ch;break;
        case'/':syn=14;token[0]=ch;break;
        case'+':syn=15;token[0]=ch;break;
        case'-':syn=16;token[0]=ch;break;
        case'=':syn=25;token[0]=ch;break;
        case';':syn=26;token[0]=ch;break;
        case'(':syn=27;token[0]=ch;break;
        case')':syn=28;token[0]=ch;break;
        case'#':syn=0;token[0]=ch;break;
        case'\n':syn=-2;break;
        default: syn=-1;break;
    }
}

int main()
{
    p=0;
    row=1;
    cout<<"Please input string:"<<endl;
    do
    {
        cin.get(ch);
        prog[p++]=ch;
    }
    while(
    p=0;
    do
    {
        scaner();
        switch(syn)
        {
        case 11: cout<<"("<<syn<<","<<sum<<")"<<endl; break;
        case -1: cout<<"Error in row "<<row<<"!"<<endl; break;
        case -2: row=row++;break;
        default: cout<<"("<<syn<<","<<token<<")"<<endl;break;
        }
    }
    while (syn!=0);
}

原文连接：http://www.cnblogs.com/yanlingyin/archive/2012/04/17/2451717.html

参考连接：http://www.cnblogs.com/longhuihu/p/4128203.html