/*
*词法分析程序
*Code by:Prudence
*QQ:95678648
*/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <malloc.h>

#define MAXLENGHT 80  //定义标志符的最大程度
#define SIZE 5   //关键字表大小
char word[SIZE][MAXLENGHT]={"begin","else","end","if","then"};

char cn[MAXLENGHT];//存放解析过程中的字符,做为临时变量使用

struct WordTable  //为链表结构,存放词法分析过程中单词
{
   int type;//1为关键字,2为标志符,3为数字,4为运算符
   union
   {
     long value;
     char name[MAXLENGHT];
   }k;
   WordTable *next;
}wt;

void InsertLastNode(char *name,int type,long value)
{
  WordTable *n=&wt;
  while(n->next!=NULL)
    n=n->next;
  WordTable *newp=(WordTable *)malloc(sizeof(WordTable));
  newp->type=type;
  newp->next=NULL;
  if(type!=3)
     strcpy(newp->k.name,cn);
  else
     newp->k.value=value;
  n->next=newp;
}

void getword()
{
  int k,len=0,mid;
  int low,high;//二分法查找关键字表
  char c;
    while((c=getchar())!='#')
  {
    if(isalpha(c)||c=='_')//关键字
    {
      k=0;
      memset(cn,0,MAXLENGHT);
      do
      {
         cn[k++]=c;
         len++;
         c=getchar();
      }while(isalpha(c) || isdigit(c) ||c=='_');

            ungetc(c,stdin);

      if(len>MAXLENGHT)
      {
        printf("变量定义太长\n");
        exit(1);
      }
            low=0;
      high=SIZE;
      while(low<=high)
      {
        mid=(low+high)/2;
        if(strcmp(cn,word[mid])<0)
          high=mid-1;
        else if(strcmp(cn,word[mid])>0)
          low=mid+1;
        else
          break;
      }
      if(low>high)
      {
        InsertLastNode(cn,2,0);
      }
      else
      {
        InsertLastNode(cn,1,0);

      }
    }
    else if(isdigit(c))//数字
    {
      long value=0;
      do
      {
                value=value*10+c-'0';
      }while(isdigit(c=getchar()));
      ungetc(c,stdin);
      InsertLastNode(NULL,3,value);

    }
    else//特殊字符
    {
      k=0;
      memset(cn,0,MAXLENGHT);
      if(c=='<')
      {
        cn[k++]=c;
        c=getchar();
        if(c=='='||c=='>')
        {
          cn[k++]=c;
          c=getchar();
        }
        ungetc(c,stdin);
        InsertLastNode(cn,4,0);
      }

      else if(c=='>')
      {
        cn[k++]=c;
        c=getchar();
        if(c=='=')
        {
          cn[k++]=c;
          c=getchar();
        }
        ungetc(c,stdin);
        InsertLastNode(cn,4,0);
      }
      else if(c=='=')
      {
        cn[k++]=c;
        InsertLastNode(cn,4,0);
      }
      else if(c=='+')
      {
        cn[k++]=c;
        InsertLastNode(cn,4,0);
      }
      else if(c=='-')
      {
        cn[k++]=c;
        InsertLastNode(cn,4,0);
      }
      else if(c=='*')
      {
        cn[k++]=c;
        InsertLastNode(cn,4,0);
      }
      else if(c=='/')
      {
        cn[k++]=c;
        InsertLastNode(cn,4,0);
      }
      else
      {
        if(c==' ' || c=='\t' ||c==10 || c==13)
          continue;
        printf("不能识别的符号\n");
        exit(1);
      }
    }
  }
}

void output()
{
  WordTable *p=wt.next;
  while(p!=NULL)
  {
    switch(p->type)
    {
    case 1:
      printf("(%s,关键字)\n",p->k.name);
      break;
    case 2:
      printf("(%s,标志符)\n",p->k.name);
      break;
    case 3:
      printf("(%d,数字)\n",p->k.value);
      break;
    case 4:
      printf("(%s,运算符)\n",p->k.name);
      break;
    }
    p=p->next;
  }
}

void main()
{
    printf("********************************词法分析程序***********************************\n");
  printf("                              Code by:Prudence                                 \n");
  printf("                                 QQ:95678648                                   \n");
  printf("*********************************以#号结束*************************************\n");
  getword();
  printf("*******************************************************************************\n");
  output();
}