利用状态图实现词法分析

实验一：词法分析程序

                                                                                              03070020 曹宁

一.  实验目的

基本掌握计算机语言的词法分析程序的开发方法。

二.  实验内容

编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。

三.  实验环境

PC微机

DOS操作系统或 Windows操作系统

Turbo C 程序集成环境或 Visual C++程序集成环境

四.  实验内容

1.    根据以下的正规式，编制正规文法，画出状态图；

2.    int nextToken()，完成以下功能：

1）             从文件读入数据，分析出一个单词。

2）             返回单词种别（用整数表示），

3）             返回单词属性（不同的属性可以放在不同的全局变量中）。

3.    int nextToken()，输出单词种别和属性。

五.  实验步骤

1.      根据状态图，设计词法分析算法

2.      C语言，设计函数scan( )，实现该算法

程序中的变量和函数声明

//对外函数
extern void initLexer();//打开文件，初始化词法分析器
extern int nextToken();//获得一个token
//对外变量
extern int attr=-1;//是数值的时候存储数值，是标识符时存储在名字表中的位置
extern int lineNo=1;//显示行数
extern char *keyWord[]={
        "if",
        "else",
        "then",
        "while",
        "do"
};
//内部函数
static int fail();//换状态图
static char getAnChar();//在文件中读取一个字符，指针下移一位
static void ungetAnChar();//在文件中指针回退一位
static void getNum(int type);//根据type，获得十进制数值，存储在attr
static int lookup(const char *s);//在符号表中查找ID
static int insert(const char *s);//返回再符号表中的下标位置
static int isKeyWord(char word[]);//判断是否为关键字
//内部变量
static char lexBuf[100];//字符缓存，用来存储当前分析的字
static int state=1, start=1;//当前状态和状态表的开始状态
static int currentPos=0;//文件中当前指针的位置
static int tokenBeginning=0;//进入一个状态表时指针位置，即换状态表时的回退位置。
static FILE *fp;//被编译的文件指针
static int smptableLength=0;//当前符号表的长度

int nextToken(){
 
    int length=0;
    char c;
    int keyWordPos=0;//在关键字数组中的下标
 
    state=1;start=1;
    //存储开始位置
    tokenBeginning=currentPos;
    //状态图的实现
    while(1){
 
        switch(state){
        case 1:
            c=getAnChar();
            if(c==' '||c=='/t'||c=='/r'){
                tokenBeginning++;
            }
            else if(c=='/n'){
                lineNo++;
                tokenBeginning++;
            }
            else if(isalpha(c)){
                state=2;
                lexBuf[length++]=c;
            }
            else if(c==EOF) return FILEEND;
            else state=fail();
            break;
        case 2:
            c=getAnChar();
            if(isdigit(c)||isalpha(c)){
                state=2;
                lexBuf[length++]=c;
            }
            else state=3;
            break;
        case 3:
            ungetAnChar();
            lexBuf[length]='/0';
            keyWordPos=isKeyWord(lexBuf);
            if(keyWordPos!=-1){
                //是关键字
                return IF+keyWordPos;
            }
            //不是关键字
            attr=insert(lexBuf);//把ID在名字表中的数组下标存储在attr中
            return ID;
        case 4:
            c=getAnChar();
            if(c=='0') state=5;
            else if(c>='1' && c<='9'){
                state=12;
                lexBuf[length++]=c;
            }
            else state=fail();
            break;
        case 5:
            c=getAnChar();
            if(c=='x') state=6;
            else if(c>='1'&& c<='8'){
                state=10;
                lexBuf[length++]=c;
            }
 
            else state=13;
            break;
        case 6:
            c=getAnChar();
            if(c>='1' && c<='9' || c>='a'&& c<='f' || c>='A' && c<='B'){
                state=7;
                lexBuf[length++]=c;
            }
            else state=fail();
            break;
        case 7:
            c=getAnChar();
            if(c>='1' && c<='9' || c>='a'&& c<='f' || c>='A' && c<='B'||c=='0'){
                state=7;
                lexBuf[length++]=c;
            }
            else state=8;
            break;
        case 8:
            ungetAnChar();
            lexBuf[length]='/0';
            getNum(INT16);//把数值存在attr中
            return INT16;
        case 10:
            c=getAnChar();
            if(c>='0'&& c<='8'){
                state=10;
                lexBuf[length++]=c;
            }
            else state=11;
            break;
        case 11:
            ungetAnChar();
            lexBuf[length]='/0';
            getNum(INT8);//把数值存在attr中
            return INT8;
        case 12:
            c=getAnChar();
            if(c>='0' && c<='9'){
                state=12;
                lexBuf[length++]=c;
            }
            else state=13;
            break;
        case 13:
            ungetAnChar();
            lexBuf[length]='/0';
            getNum(INT10);//把数值存在attr中
            return INT10;
        case 14:
            c=getAnChar();
            if(c=='+') state=15;
            else if(c=='-') state=16;
            else if(c=='*') state=17;
            else if(c=='/') state=18;
            else if(c=='>') state=19;
            else if(c=='<') state=20;
            else if(c=='=') state=21;
            else if(c=='(') state=22;
            else if(c==')') state=23;
            else if(c==';') state=24;
            else state=fail();
            break;
        case 15:
            return ADD;
        case 16:
            return SUB;
        case 17:
            return MUL;
        case 18:
            return DIV;
        case 19:
            return GT;
        case 20:
            return LT;
        case 21:
            return EQ;
        case 22:
            return LBR;
        case 23:
            return RBR;
        case 24:
            return SEM;
        }
    }     
}

3.      main）。

void main(){
     int token;
     int oldLine=-1;
     initLexer();   
      
     while(1){
         token=nextToken();
         if(token==FILEEND) break;
         if(oldLine!=lineNo) {
             printf("___________Line %d____________/n",lineNo);
             oldLine=lineNo;
         }
         
        if(token==ID){//标识符
            printf("ID:%d,Pos:%d/n",token,attr);
        }
        else {
            switch(token){
                case INT16:case INT8:case INT10://数字
                    printf("%d/t/t%d/n",token,attr);
                    break;
                default: printf("%d/n",token);//关键字
                }
        }
        token=nextToken();
     }
}//*/

4.      调试程序：输入一组单词，检查输出结果

以上都是一行的没有出现什么问题，但是当对多行进行词法分析时，总是出错，通过打印读到的字符发现有字符13（ASCII），查资料才知是’/t’，把光标移到当前行的起始位置，我不知道为什么会有这个字符，添加滤掉这个字符的逻辑，才使词法分析成功。

while (1) do num=10;
num=11;
if (1) then caoning=0x11;
if (1) than caoning=878;

5.      词法分析程序的数据结构与算法

符号表的数据结构：采用的是结构数组

struct ENTYE{
   char word[100];
   float value;
};
int smptableLength=0;
struct ENTYE smptable[200];

在配以int lookup(const char *s)和int insert(const char *s)对这个符号表操作。

/*查找s在符号表的位置，没有返回-1*/
int lookup(const char *s){
    int i;
    for (i=0;i<smptableLength;i++){
        if (strcmp(smptable[i].word,s)==0) return i;
    }
    return -1;
}
/*返回s在符号表中的位置*/
int insert(const char *s){
   int i=lookup(s);
   if(i==-1){
        strcpy(smptable[smptableLength].word,s)；
       //smptableLength++;
       return smptableLength++;
   }
   return i;
}

六.  心得体会

这次词法分析的实验本身没有什么难度，但是在做这实验之前感觉没谱，所以踏下心仔细的阅读Aho的《编译原理》中前三章，受到很大启发，尤其是利用switch语句把状态图实现的技术，可谓一绝，这也是我学习词法分析的最大的收获。

在做语法分析的时候，对词法分析进行了一些修改，学习了一下不同文件内的函数和变量的使用，在做词法分析的时候架构没有做好，比如哪些函数和变量作为内部的，哪些是提供外部使用的接口，比较混乱，也没有进行大量测试，导致语法分析时受阻重重，最后停下语法分析的编程，对此词法分析修改，使程序清晰易读，并进行了大量的测试，再作语法分析时就容易多了。这也是个教训，以后编程首先得考虑好，再一步一步来。就会省很多麻烦。

http://blog.chinaunix.net/uid-26750235-id-3088397.html

代码下载: git clone git://git.code.sf.net/p/redy/code redy-code

这一章的内容有：

通过一个实例来说明状态机合并的方法

状态机合并算法

状态链在合并中的优点

（1）简介

在这一章里面，你会看到两个简单的状态机：

     一个为状态机用于识别正则式   [0-7]+abf 所表于的语言，[0-7]　表于数字0-7中的任意一个，'+'表示重复一次或多次。

    另一个状态机用于识别正则式　[4-9]+acd所表于的语言。同样[4-9]表示数字4-7中的任意一个。'+'表示重复一次或多次。

（2）状态机１

根据正则式[0-7]+abf，绘出的状态图如下：

我们使用状态链的算法来用程序来构造该状态机，从状态中可以看出，该状态机总共有５个状态，其中Abegin为开始状态，A4为终态，由于每个状态，都只在一个输入类型下发生状态转移，所以每一个状态，这里采用函数指钍的方法来判断输入类型。

在程序开头，我们对于每一个状态都进行申明，以使后面引用：

1. extern struct state Abegin;
2. extern struct state A1;
3. extern struct state A2;
4. extern struct state A3;
5. extern struct state A4;

状态Abegin在数据输入字符0-7的情况下转移到状态A1，在其它输入情况下让状态Abegin转移到错误状态lex_state_err。

1. int input_map_abegin(char c)
2. {
3. if(c>='0'&&c<='7')return 1;
4. else return 0;
5. }
6. struct state* Abegin_targets[]={&lex_state_err,&A1};
7. struct state Abegin={ "Abegin",2,1,0, input_map_abegin, Abegin_targets, 0,};

状态A1begin在输入入字符0-7的情况下转移到自身，当输入为字符‘a’时转移到A2，其它则转移到状态lex_state_err。

1. int input_map_a1(char c)
2. {
3. if(c=='a')return 1;
4. if(c>='0'&&c<='7')return 2;
5. else return 0;
6. }
7. struct state* A1_targets[]={&lex_state_err,&A2,&A1};
8. struct state A1={ "A1",2,1,0, input_map_a1, A1_targets, 0,};

状态A2,A3,A4构造方法和前面一样，所以我就全部贴出。

1. int input_map_a2(char c)
2. {
3. if(c=='b')return 1;
4. else return 0;
5. }
6. struct state* A2_targets[]={&lex_state_err,&A3};
7. struct state A2={ "A2",2,1,0, input_map_a2, A2_targets, 0,};
8. 
   
9. int input_map_a3(char c)
10. {
11. if(c=='f')return 1;
12. else return 0;
13. }
14. struct state* A3_targets[]={&lex_state_err,&A4};
15. struct state A3={ "A3",2,1,0, input_map_a3, A3_targets, 0,};
16. 
    
17. int input_map_a4(char c)
18. {
19. return 0;
20. }
21. struct state* A4_targets[]={&lex_state_err};
22. struct state A4={ "[0-7]+abf",2,1,0, input_map_a4, A4_targets, 1,};

这样我们已经用状态链的方法构造出了整个状态机１的模型。把该模型带入驱动程序，就可能对类似于011444abf ，2122abf，4abf，的字符串进行识别了。

状态机１的程序可以在下载的文件夹下面的tutorial/lexical/merge1中找到，对程序进行编译，运行可执行文件a1。｀

下面我们来构造状态机２

（3）状态机２

根据正则式[4-9]+acd，绘出状态图：

同样我们也使用状态链的方法来构造状态机２，状态机２总共有５个状态，开始状态为Bbegin，终态为B4，同构造状态机１的方法一样。我这里就直接贴出程序，不进行说明。

状态申明：

1. extern struct state Bbegin;
2. extern struct state B1;
3. extern struct state B2;
4. extern struct state B3;
5. extern struct state B4;

状态机２的５个状态：

1. int input_map_bbegin(char c)
2. {
3. if(c>='4'&&c<='9')return 1;
4. else return 0;
5. }
6. 
   
7. struct state* Bbegin_targets[]={&lex_state_err,&B1};
8. struct state Bbegin={ "Bbegin",2,1,0, input_map_bbegin, Bbegin_targets, 0,};
9. 
   
10. 
    
11. int input_map_b1(char c)
12. {
13. if(c=='a')return 1;
14. if(c>='4'&&c<='9')return 2;
15. else return 0;
16. }
17. struct state* B1_targets[]={&lex_state_err,&B2,&B1};
18. struct state B1={ "B1",2,1,0, input_map_b1, B1_targets, 0,};
19. 
    
20. int input_map_b2(char c)
21. {
22. if(c=='c')return 1;
23. else return 0;
24. }
25. struct state* B2_targets[]={&lex_state_err,&B3};
26. struct state B2={ "B2",2,1,0, input_map_b2, B2_targets, 0,};
27. 
    
28. int input_map_b3(char c)
29. {
30. if(c=='d')return 1;
31. else return 0;
32. }
33. struct state* B3_targets[]={&lex_state_err,&B4};
34. struct state B3={ "B3",2,1,0, input_map_b3, B3_targets, 0,};
35. 
    
36. int input_map_b4(char c)
37. {
38. return 0;
39. }
40. struct state* B4_targets[]={&lex_state_err};
41. struct state B4={ "[4-9]+acd",2,1,0, input_map_b4, B4_targets, 1,};

现在我们就用状态链的方法构造出状态机２模型，同样把该模型带入驱动程序，这样我们就可以识别例如：4578589acd , 87acd , 9978acd , 等类似的字符串。

状态机２的程序可以在下载的文件夹下面的tutorial/lexical/merge1中找到，对程序进行编译，运行可执行文件b1。

（4）状态机的合并

现在我们要把两个状态机合并在一起，以便我们的程序同时能够识别正则式[0-7]+abc所表示的语言和[4-9]+acd所表示的语言，合并状态机的方法与自动机ENFA转化为NFA的算法理论基本一样。总共分为下面几步：

a）输入类型分析

对于状态机1来说，输入类型有这么５种

1. 数字0到7　　（D0_7）
2. 字符'a'　　　（S_a）
3. 字符'b' 　　　（S_b）
4. 字符'f'　　　（S_f）
5. 除以上以外的所有字符　　（Other）

对于状态机２来说，输入类型有么５种

1. 数字4到9 　　（D4_9）
2. 字符'a'　　　（S_a)
3. 字符'c' 　　　（S_c）
4. 字符'd'　　　（S_d）

除以上以外的所有字符　　（Other）

把两个状态机的输入类型进行合并得到下面９种输入类型

1. 数字0到3　　（D0_3）
2. 数字4到7　　（D4_7）
3. 数字8到9　　（D8_9）
4. 字符'a'　　　（D_a）
5. 字符‘b‘　　　（D_b）
6. 字符‘f’　　　（D_f）
7. 字符‘c’　　　（D_c）
8. 字符‘d‘　　　（D_d)
9. 除以上以外的所有字符 　　（other）

其中类型D0_7包括：D0_3，D4_7；类型D4_9包括：D4_7，D8_9。

b）合并第一步

状态机１的开始状态为Abegin，状态机２的开始状态为Bbegin，把两个状态合成一个状态Cbegin，Abegin和Bbegin两个状态能发生的状态转移，Cbegin同样能发生。

这时状态图为：

其中黄色表示状态机１，绿色表示状态机２，黄色表示为新创建的状态。

因为Abegin，Bbegin能发生的状态转移，Cbegin都以发生，即

f(Abegin,D0_7)->A1

f(Begin,D4_9)->B1

所以推得出：

f(Cbegin,D0_3)->A1

f(Cbegin,D4_7)->(A1,B1)

f(Cbegin,D8_9)->B1

这里我们绘出一个状态转换表

输入\状态

D0_3

D4_7

D8_9

S_a

S_b

S_c

S_d

S_f

Other

Cbegin

(Abegin,Begin)

A1

A1,B1

B1

c）合并第二步

假设状态S在输入类型I下的后继状态组合为C：

1. 如果C为空，则认为S在输入类型I下不能发生状态转移
2. 如果C中只有一个后继状态，则在状态图引一条状态转移线从状态S到C，并标记输入类型为I
3. 如果C是由两个或多个状态组合在一起，而且这状态组合在以前没有出现过，则创建一个新的状态N，新状态N等价原状成组合，从状态图引一条状态转移线从状态S到N，并标记输入类型为I
4. 如果C是由两个或多个组合在一起，而该状态组合已经出现过，则在状态图引一条转移线从状态S到该状态组合的等价状态。

现在我们来看状态机1与状态机2的合并

因为

1. 状态Cbegin在D0_3转换为A1，A1为单一状态，所以在状态图上引一条转移线从Cbegin到A1，并标记输入类型为D0_3
2. 状态Cbeign在D8_9转换为B1，B1为单一状态，所以在状态图上引一条转移线从Cbegin到B1，并标记输入类型为D8_9
3. 状态Cbegin在D4_7转换为(A1,B1)，(A1,B1)为状态组合，并且前面没有出现该状态组合，所以创建一个新状态C1，在状态图上引一条转移线从Cbegin到C1，并标记输入类型为D4_7。同时对C1进行标记，表示C1还未进行状态转移处理。

此时状态图为：

d）合并第三步

在这一步中，找出标记一个标记过的状态，进行状态转移处理，在一步时，我们只有状态C１被标记过，状态C1等价于(A1,B1)的组合，这时我们对状态Ｃ１进行处理，并且取消对Ｃ１的标记。

因为

f(A1,D0_7)->A1

f(A1,S_a)->A2

f(B1,D4_9)->B1

f(B1,S_a)->B2

所以

f(C1,D0_3)->A1

f(C1,D4_7)-:>(A1,B1)

f(C1,D8_9)->B1

f(C1,S_a)->(A2,B2)

根据上面的转移公式，我们继续绘画状态转移表

输入\状态

D0_3

D4_7

D8_9

S_a

S_b

S_c

S_d

S_f

Other

Cbegin

(Abegin,Begin)

A1

A1,B1

B1

C1

(A1,B1)

A1

A1,B1

B1

A2,B2

根据上面的转换，我们继续绘制状态图

1. 由于C1在D0_3，D8_9分别转移到状态A1，B1。A1与B1分别都是单状态，所以从C1引一条转移线分别到A1与B1。
2. C1在D4_7转换为(A1,B1)，(A1,B1)为状态组合，但是(A1,B1)在前面已经出现过了，就是状态C1本身，所以引一条转移线，从Ｃ１自己到自己。
3. C1在S_a的转换到(A2,B2)，(A2,B2)为状态组合，以前也没有出现过，所以创建一个等价于(A2,B2)的状态C2，标记C2，并且从C1引一条到C2。

此时状态图为：

e）合并第四步

合并第四步，就是得重复第三步，直到没有标记状态为止，现在被标记的状态只有C2,所以我们需要对C2进行处理，并且取消标记C2。按照第三步的方法来处理。

因为

f(A2,S_b)=A3

f(B2,S_c)=B3

所以

f(C2,S_b)=A3

f(C2,S_c)=B3

根据上面公式，这时转移表为：

输入\状态

D0_3

D4_7

D8_9

S_a

S_b

S_c

S_d

S_f

Other

Cbegin

(Abegin,Begin)

A1

A1,B1

B1

C1

(A1,B1)

A1

A1,B1

B1

A2,B2

C2

(A2,B2)

A3

B3

继续绘制我们的状态转换图，因为状态C2在S_b，S_c分别转移到A3，B3。两个都是单状态，所以分别画一条转移线从C2到A3,B3。

此时状态图为：

到现在为些，已经没有标记过的状态了，所以状态机１与状态机２的合并也算完成了。

（5）合并后的状态机

通过合并后的状态图，我们可以看到合并后，我们并不用修改状态机１和状态机２，只是增加了３个新的状态，把两个状态机链接起来。这次合并总共增加了三个新的状态，我们把这三个状态加入我们的状态链中去。

为了后面引用，我们先申明这三个状态

1. extern struct state Cbegin;
2. extern struct state C1;
3. extern struct state C2;

状态Cbegin，在D0_3转移到状态A1,　在D4_7转移到C1，在状态D8_9转移到B1。

1. int input_map_cbegin(char c)
2. {
3. if(c>='0'&&c<='3')return 1;
4. else if(c>='4'&&c<='7')return 2;
5. else if(c>='8'&&c<'9')return 3;
6. else return 0;
7. }
8. 
   
9. struct state* cbegin_targets[]={ &lex_state_err,&A1,&C1,&B1};
10. struct state Cbegin={"Cbegin",4,3,0,input_map_cbegin,cbegin_targets,0};

状态Ｃ１在D0_3转移到状态Ａ１，在D4_7转移到本身，在D8_9转移到Ｂ１，在S_a转移到C2

1. int input_map_c1(char c)
2. {
3. if(c>='0'&&c<='3')return 1;
4. else if(c>='4'&&c<='7')return 2;
5. else if(c>='8'&&c<'9')return 3;
6. else if(c=='a')return 4;
7. else return 0;
8. }
9. struct state* C1_targets[]={&lex_state_err,&A1,&C1,&B1,&C2};
10. struct state C1={"C1",5,4,0,input_map_c1,C1_targets,0};

状态C2在S_a转移到状态A3，在S_c转移到状态状态B3

1. int input_map_c2(char c)
2. {
3. if(c=='b')return 1;
4. else if(c=='c')return 2;
5. else return 0;
6. }
7. 
   
8. struct state* C2_targets[]={&lex_state_err,&A3,&B3};
9. struct state C2={"C2",3,2,0,input_map_c2,C2_targets,0};

这样我们就以经完成合并后状态机模型的状态链，这时把开始状态改为Cbegin，代入驱动程序，可以对正则式[0-7]+abf和正则式[4-9]+acd表示的语言进行综合识别了

合并后的状态机可以在下载的文件夹下面的tutorial/lexical/merge1中找到，对程序编译，运行可执行文件merge

顺便在这里也贴出一个运行后的图给大家看看运行结果。

（6）总结

a）合并算法总结

通过上面的实例大家应该对状态机合并了解了。状态机合并总共分为这么几步：

１）分析两个状态机的输入类型。

２）找到两个状态机的开始状态，并且建立一个与组合状态等价的新状态Begin，标记新的状态，这里等价意义为，组合状态中任意一个状态，在某种输入类型下发生状态转移，与之等价的新状态同样也会在该输入类型下发生状态转移

３）找出一个被标记过的状态（命名为Ｓ）执行下面的步骤：

a）找出状态Ｓ在每一种输入类型下的后继状态，等价于找出与之等价的组合状态中的每一个在该输入类型下发生的后继状态的组合。

b）对于后继状态来说，有下面３种情况：

如果状态Ｓ在输入类型Ａ下的后继状态Ｂ只有一个，则画一条从状态Ｓ出发到后继状态Ｂ的转移线，并在转移线上标出输入类型Ａ。

如果状态Ｓ在输入类型Ａ下的后继状态有两个或多个，并且该状态组合在以前没有出现过，则创建一个与之等价的状态Ｃ，并且标记Ｃ。随后画一条从状态Ｓ出发到新状态Ｃ的转移线，并在转移线上标出输入类型Ａ

如果状态Ｓ在输入类型Ａ下的后继状态有两个或多个，并且与状态组合状态Ｂ在以前已经出现过，则画一条从从状态Ｓ出发到状态Ｂ的转移线，并在转移线上标出输入类型Ａ。

c）取消对状态Ｓ的标记

４）重复第三步，直到没有标记过的状态。

５）把状态Begin设置为该状态机的开始状态。

６）自动机合并完成。

b）采用状态链状态机的优点

从上面自动机合并的实例相信大家已经看到，当我们在合并两个状态机的时候，并没有更改状态１和状态机２的任何结构，我们只是简单的增加几个状态，把两个状态机连接在一起，来实现的状态机的合并。这样的好处在于当我们要开发的识别系统中存在不同的单词类型时，我们可以分开来制作每一类单词的状态机，在合并的时候，我们不用去改变那些现有的自动机，只是简单增加新的状态，把它们连接到一起。这样就可以把一个大的事情，分多个小的步骤来完成。

在状态中每一个状态，不用去关心状态机的整体结构。这是我们实现状态机合并的关键。