一、实验设计

基本实验题目：若某一程序设计语言中的单词包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序（各类单词的分类码参见表I）。

输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。

输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。

表I  语言中的各类单词符号及其分类码表

在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后添加当进行状态转移时所需执行的语义动作，就可以据此构造词法分析程序了。

为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、无符号常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。

采用上述策略后，针对表I中的部分单词可以参考教材P80的图3-22（见图1）和P81的程序3-4，用C语言编写出符合以上几项要求的一个扫描器程序。按照实验题目的具体要求将其中的整常数改为无符号常数。关于无符号数的文法可参见教材P49，其识别方法参考P51的图3-3（见图2）、P55的表3-1（见表II）和P57的程序3-3。

图1  识别表I所列语言中的部分单词的DFA及相关的语义过程

图1中所出现的语义变量及语义函数的含义和功能说明如下：

函数GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。

字符数组TOKEN：用来依次存放一个单词词文中的各个字符。

函数CAT：每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。

函数LOOKUP：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。

函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。

函数OUT：一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码助记符；实参VAL为TOKEN（即词文）或为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。

图2所示为上述文法的状态转换图，其中编号0、1、2、…、6分别代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>。

图2  文法G1[<无符号数>]的状态转换图

无符号数识别中的语义处理方法详见教材P56。表II即为嵌入了语义动作的状态矩阵，其功能是在扫描源程序字符串的过程中，把识别出的字符串形式的无符号数的值，逐步转换为相应的二进制整数（ICON）或二进制浮点数（FCON）的内部形式。（注：考虑能否采用C语言的库函数实现此语义处理工作；是否可将无符号常数这一类单词进一步细分成整型常数和浮点型常数两类单词。）

根据表II所示的加入了语义过程说明的识别无符号数的状态矩阵，编写词法分析程序，部分实现代码如程序二所示。

表II  包含语义处理过程的识别无符号数的状态矩阵

二、程序代码

在VC++6.0中运行

# include

# include

# include

# include

# include

# define BEGIN 1  

# define END 2

# define IF 3

# define THEN 4

# define ELSE 5

# define ID 6   //标识符

# define UCON 7  //整数

# define LT 8 //<

# define LE 9 //<=

# define EQ 10  //=

# define NE 11 //<>

# define GT 12 //>

# define GE 13 //>=

# define IS 14  //:=

# define PL 15  //+

# define MI 16  //-

# define MU 17  //*

# define DI 18  // /

# define Mao 19 // :

#define LETTER 0 //

#define DIGIT 21

#define POINT 22

#define OTHER 23

#define POWER 24

#define ClassNo 100

#define ClassOther 200

#define EndState -1

char TOKEN[20];

extern int lookup (char*);

extern void out (int, char*);

extern void report_error (void);

double pow(double,double);

int GetChar(void);

int EXCUTE(int,int);

int LEX(void);

int w,n,p,e,d;

int Class;

int ICON;

double FCON;

static int CurrentState;

char ch;

/********************关键词部分*************************/

typedef struct

{

    int ad;

    char id[6];

}info_ele;

info_ele Tab[5]={{1,"begin"},{2,"end"},{3,"if"},{4,"then"},{5,"else"}};

/*********************************************/

void scanner_example (FILE *fp)   //读字符

{

  int i,c;

  ch=fgetc (fp);

 if (isalpha (ch))  /*it must be a identifer!*/

 {

   TOKEN[0]=ch; 

   ch=fgetc(fp); 

   i=1;

   while (isalnum (ch))

   {

    TOKEN[i]=ch; 

    i++;

    ch=fgetc (fp);

   }

   fseek(fp,-1,1);  /* retract*/

   TOKEN[i]='\\0';

   c=lookup (TOKEN);

   if (c==0) 

   out(ID,TOKEN); 

   else 

  out (c,TOKEN);

 }

   else if(isdigit(ch))

{

TOKEN[0]=ch; 

ch=fgetc(fp); 

i=1;

while(isdigit(ch)||ch=='.'||ch=='E'||ch=='e'||ch=='-')

{

TOKEN[i]=ch; 

i++;

ch=fgetc(fp);

}

fseek(fp,-1,1);

TOKEN[i]='\\0';

out(UCON,TOKEN);

LEX();

}

else if(ch==' '||ch=='\\n');

else

switch(ch)

{

case'<': ch=fgetc(fp);

  if(ch=='=')

out(LE,"<=");

else if(ch=='>')

out (NE,"<>");

 else

{

fseek (fp,-1,1);

out (LT,"<");

}

break;

case '=': out(EQ, "="); break;

case '+': out(PL,"+");  break;

case ':': ch=fgetc(fp);

if(ch=='=') out(IS,":=");

else

{

fseek(fp,-1,1);

out(Mao,":");

}

case '>': ch=fgetc(fp);

if(ch=='=')out(GE,">=");

else

{

fseek(fp,-1,1);

out(GT,">");

}

break;

default:break;

}

}

/********************查保留字表*************************/

int lookup(char p[])

{

    int i=0;

for(i=0;i<5;i++)

    {

        if(!strcmp(Tab[i].id,p))

            return(Tab[i].ad);

    }

    return 0;

}

/*****************输出函数****************************/

void out(int a,char *p)   //输出字符

{

    switch(a)

    {

    case BEGIN: printf("(BEGIN,%s)\\n",p); break;    

    case END:   printf("(END,%s)\\n",p);  break;

    case IF:    printf("(IF,%s)\\n",p);  break;

    case THEN:  printf("(THEN,%s)\\n",p);break;

    case ELSE:  printf("(ELSE,%s)\\n",p);break;

    case ID:    printf("(ID,%s)\\n",p);break;

    case UCON:   printf("(UCON,%s)\\n",p);break;

    case LT:    printf("(LT,%s)\\n",p);break;

    case LE:    printf("(LE,%s)\\n",p);break;

    case EQ:    printf("(EQ,%s)\\n",p);break;

    case NE:    printf("(NE,%s)\\n",p); break;

    case GT:    printf("(GT,%s)\\n",p); break;

    case GE:    printf("(GE,%s)\\n",p); break;

    case PL:    printf("(PL,%s)\\n",p); break;

    case IS:    printf("(IS,%s)\\n",p); break;

    case Mao:   printf("(Mao,%s)\\n",p); break;

    default:break;

    }

}

/*********************************************/

void report_error()

{

    printf("\\n错误！\\n");

    exit(0);

}

/*********************************************/

int HandleOtherWord(void)

{

    return ClassOther;

}

/*********************************************/

int HandleError(void)

{

    printf("Error!\\n");

    return 0;

}

/*********************************************/

int GetChar(int i)

{

    int c;

    c = (int)TOKEN[i];

    if(isdigit(c)){d=c-'0';return DIGIT;}

    if(c=='.') return POINT;

    if(c=='e'||c=='E') return POWER;

    if(c=='+')return PL;

    if(c=='-') return MI;

    return OTHER;

}

/*********************************************/

int EXCUTE(int state,int symbol)

{

    double pow(double,double);

    switch(state)

    {

    case 0:switch(symbol)

           {

    case DIGIT:n=0;p=0;e=1;w=d;CurrentState=1;Class=ClassNo;break;

    case POINT:w=0;n=0;p=0;e=1;CurrentState=3;Class=ClassNo;break;

    default: HandleOtherWord();ClassOther;

       CurrentState=EndState;

           }

        break;

    case 1:switch(symbol)

           {

    case DIGIT:w=w*10+d;break;

    case POINT:CurrentState=2;break;

    case POWER:CurrentState=4;break;

    default:ICON=w;CurrentState=EndState;

     //    printf("%d\\n",ICON);

           }

        break;

    case 2:switch(symbol)

           {

    case DIGIT:n++;w=w*10+d;break;

    case POWER:CurrentState=4;break;

    default:FCON=w*pow(10,e*p-n);CurrentState=EndState;

        //printf("%f\\n",FCON);

           }

        break;

    case 3:switch(symbol)

           {

    case DIGIT:n++;w=w*10+d;CurrentState=2;break;

    default:HandleError();CurrentState=EndState;

           }

        break;

    case 4:switch(symbol)

           {

    case DIGIT:p=p*10+d;CurrentState=6;break;

    case MI:e=1;CurrentState=5;break;

    case PL:CurrentState=5;break;

    default:HandleError();CurrentState=EndState;

           }

        break;

    case 5:switch(symbol)

           {

    case DIGIT:p=p*10+d;

        CurrentState=6;

        break;

    default:HandleError();

        CurrentState=EndState;

           }

        break;

    case 6:switch(symbol)

       {

    case DIGIT:p=p*10+d;break;

     default:FCON=w*pow(10,e*p-n);CurrentState=EndState;

     //printf("%f\\n",FCON);

       }

break;

}

return CurrentState;

}    

/*********************************************/

int LEX(void)

{

    int ch,a=0;

    CurrentState=0;

    while(CurrentState!=EndState)

    {

        ch=GetChar(a);

        EXCUTE(CurrentState,ch);

        a++;

    }

    return Class;

}

/*********************************************/

void main()

{

    extern char ch;

    FILE *fp;

    if((fp=fopen("file.txt

    {

        printf("\\nfile open error!\\n");

        exit(0);

    }

    do

    {

        scanner_example(fp);

    }while(ch!=EOF);

}

三、实验结果分析

下载本文