算符优先.cpp

编译的词法分析

/* 实验题目： 对下列文法    */
/*    E->E+T|E-T|T   */
/*    T->T*F|T/F|F   */
/*    F->(E)|i    */

/****************************************/
/*     程序相关说明     */
/*  0=+ 1=- 2=* 3=/ 4=( 5=) 6=i 7=# */
/*          */
/*   算符优先关系表    */
/* -------------------------------- */
/*     +   -   *   /   (   )   i   #  */
/* +   >   >   <   <   <   >   <   >  */
/* -   >   >   <   <   <   >   <   >  */
/* *   >   >   >   >   <   >   <   >  */
/* /   >   >   >   >   <   >   <   >  */
/* (   <   <   <   <   <   =   <   ?  */
/* )   >   >   >   >   ?   >   ?   >  */
/* i   >   >   >   >   ?   >   ?   >   */
/* #   <   <   <   <   <   ?   <   =  */
/* -------------------------------- */
/****************************************/
#include "stdio.h"
#include "malloc.h"
struct Lchar{
 char char_ch;
 struct Lchar *next;
}LLchar,*p,*h,*temp,*top,*base;
int table[8][8]={{1,1,-1,-1,-1,1,-1,1},
    {1,1,-1,-1,-1,1,-1,1},
    {1,1,1,1,-1,1,-1,1},
    {1,1,1,1,-1,1,-1,1},
    {-1,-1,-1,-1,-1,-1,-1,0},
    {1,1,1,1,0,1,0,1},
    {1,1,1,1,0,1,0,1},
    {-1,-1,-1,-1,-1,0,-1,-1}};
/*存储算符优先关系表，大于为1，小于或等于为-1，其它为0表示出错*/
char curchar;
char curcmp;
int right;/*设置开关项，当出错时为0*/
int i,j;
int step=0;
int k;/*比较字符在栈的位置*/
void push(char pchar)/*入栈函数*/
{
 temp=(struct Lchar*)malloc(sizeof(LLchar));
 temp->char_ch=pchar;
 temp->next=top;
 top=temp;
}
void pop(void)/*出栈函数*/
{
 if(top->char_ch!='#')
  top=top->next;
}
int changchartoint(char ch)/*将字符转为数字，以得到算符优先值*/
{
 int t;
 switch(ch)
 {
  case '+':t=0;break;
  case '-':t=1;break;
  case '*':t=2;break;
  case '/':t=3;break;
  case '(':t=4;break;
  case ')':t=5;break;
  case 'i':t=6;break;
  case '#':t=7;
 }
 return t;
}
void dosome(void)
{
 k=1;
 
 for(;;)
 { printf("\n%d\t",step++);
  curchar=h->char_ch;
  temp=top;
  for(;;)
  {
   if(temp->char_ch=='N')
   {
    temp=temp->next;
    k++;
   }
   else
   {
    curcmp=temp->char_ch;
    break;
   }
  }
  //printf("\n%d\t",j);
  temp=top;
 
  for(;;)/*打印栈*/
  { 
   printf("%c",temp->char_ch);
   if(temp->char_ch=='#')
    break;
   else
    temp=temp->next;
  }
  printf("\t");
  temp=h;
  for(;;)/*打印待比较的字符*/
  {
   printf("%c",temp->char_ch);
   
   if(temp->char_ch=='#')
    break;
   else
    temp=temp->next;
  }
  i=changchartoint(curcmp);
  j=changchartoint(curchar);
  if(table[i][j]==0)/*算符优先值为空*/
  {
   printf("\t%d\t%c\t%c\terror1",k,curcmp,curchar);
   right=0;
   
   break;
  }
  else/*算符优先值不为空*/
  {
   if(table[i][j]<0)/*算符优先值为-1，移进*/
   {
    if(curchar=='#')/*待比较字符为空*/
    {
     if(k==2)/*当前比较字符在栈的位置为两个元素*/
      break;
     else
     {
      printf("\t%d\t%c\t%c\terror2",k,curcmp,curchar);
	  
      right=0;
	  step++;
      break;
     }
    }
    push(curchar);
    k=1;
    curcmp=curchar;
    h=h->next;
	printf("\t\t移进");
   }
   else/*算符优先值为1，归约*/
   {
    if(curcmp=='i')/*当前比较为i,出栈一次*/
     pop();
    else/*当前比较不为i,出栈三次*/
    {
     pop();
     pop();
     pop();
    }
	printf("\t\t归约");
    push('N');/*归约到N*/
    k=1;
   }
  }
 }
}
void main(void)
{
 printf("所用文法为:\n");
 printf(" E->E+T|E-T|T\n");
 printf("T->T*F|T/F|F\n");  
 printf("F->(E)|i");
 char ch;
 right=1;
 base=(struct Lchar*)malloc(sizeof(LLchar));
 base->next=NULL;
 base->char_ch='#';
 top=base;
 h=(struct Lchar*)malloc(sizeof(LLchar));
 h->next=NULL;
 p=h;
 printf("\n请输入待比较的字符串:");
 do{    /*输入待比较字符串，以'#'结束*/
  ch=getchar();
  putchar(ch);
  if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
  {
   temp=(struct Lchar*)malloc(sizeof(LLchar));
   temp->next=NULL;
   temp->char_ch=ch;
   h->next=temp;
   h=h->next;
  }
  else
  {
   temp=p->next;
   printf("\nInput a wrong char!Input again:\n");
   for(;;)
   {    
    if (temp!=NULL)
     printf("%c",temp->char_ch);      
    else
     break;
    temp=temp->next;
   }
  }
 }while(ch!='#');/*输入待比较字符串，以'#'结束*/
 printf("\n步骤\t分析栈\t剩余输入串\t动作\n");
 p=p->next;
 h=p;

 dosome();/*开始识别*/
 if(right)
  printf("\t\t接受\n");
 else
  printf("\t\t出错\n");
 getchar();
}