1.txt

自上而下的语法分析器

#include"stdio.h"  
#include"string.h"   
#define   R     30  
#define   C     20  

typedef   struct   elem  
{  
 char   e[4];  
}Elem;       //ACTION表与GoTo表中的元素类型  

Elem   LR[R][C];                             //存放ACTION表与GoTo表中的内容  

typedef   struct   out  
{  
 int     order;                   //序号  
 int     state[10];           //状态栈  
 char   sign[30];             //符号栈  
 char   grasen[20];         //产生式  
 char   input[30];           //输入串  
 char   explen[50];         //解释说明  
}OutNode;       //输出结果中每一行的类型  

OutNode   out[20];                         //存放输出结果  

char   Sentence[20];                     //存放文法的一个句子  
char   GramSent[10][20];             //存放文法的一组产生式  
int   row,colno;                             //row为状态个数数，colno为ACTION表与GoTo表列总数  
int   stateTop=0,signTop=0;               //状态栈与符号栈的栈顶位置(值与栈中元素的个数相等)  

void   input_GramSent()  
{  
 int   i,num;  
 printf("请输入文法中产生式的个数\n");  
 scanf("%d",&num);  
 for(i=1;i<=num;i++)  
 {  
  printf("请输入文法的第%d个产生式\n",i);  
  scanf("%s",GramSent+i-1);  
 }  
 printf("请输入文法的一个句子\n");  
 scanf("%s",Sentence);  
 
 printf("**********************************************************\n");  
 printf("*     文法的产生式如下：                                                                         *\n");  
 printf("**********************************************************\n");  
 for(i=0;i<num;i++)  
  printf("%s\n",GramSent+i);  
 printf("**********************************************************\n");  
 printf("*     文法的句子如下：                                                                             *\n");  
 printf("**********************************************************\n");  
 printf("%s\n",Sentence);  
}  
void   input_LR(int   row,int   colno)                                 //row为行总数，colno为列总数  
{  
 int   i,j;  
 char   mid[4];  
 printf("**********************************************************\n");  
 printf("*     提示：每输入一个元素后就回车                                                     *\n");  
 printf("**********************************************************\n");  
   
 printf("请输入LR分析表的终结符(包括#)与非终结符\n");  
 for(j=0;j<colno;j++)  
  scanf("%s",LR[0][j].e);  
   
 for(i=0;i<row;i++)  
 {  
  printf("请输入%d号状态所对应的各列的元素,空白的地方用s代替\n",i);  
  for(j=0;j<colno;j++)  
  {  
   scanf("%s",mid);  
   if(strcmp(mid,"s")==0||strcmp(mid,"S")==0)  
    strcpy(LR[i+1][j].e,"   ");  
   else  
    strcpy(LR[i+1][j].e,mid);  
  }  
 }      
}  
void   output_LR(int   row,int   colno)  
{  
 int   i,j;  
 printf("**********************************************************\n");  
 printf("*     LR分析表如下：                                                                                 *\n");  
 printf("**********************************************************\n");  
 printf("\n");  
   
 printf("         ");  
 for(j=0;j<colno;j++)  
  printf("%s       ",LR[0][j].e);  
 printf("\n");  
   
 for(i=1;i<=row;i++)  
 {        
  printf("%d       ",i-1);  
  for(j=0;j<colno;j++)  
   printf("%s       ",LR[i][j].e);  
  printf("\n");  
 }  
 printf("\n");  
}  

int   SignNum(char   ch)//给定一个终结符或非终结符,返回其在ACTION表与GoTo表中的列位置  
{  
 int   i;  
 char   c[2]="0";  
 c[0]=ch;  
 for(i=0;i<colno;i++)  
  if(strcmp(c,LR[0][i].e)==0)  
   return   i;  
  return   -1;  
}  

int   CharChangeNum(char*   ch)//给定一数字字符串,返回其所对应的数字  
{  
 int   result=0;  
 while(*ch!='\0')  
 {  
  result=result*10+(*ch-'0');  
  ch++;  
 }  
 return   result;  
}  
int   OutResult(int   s,int   c,int   i)//输出结果的第i+1行处理函数,(s为状态，c为列)  
{  
 char   mid[4],gra[20];  
 int   s_num,r_num;  
 int   n,len,j;  
   
 strcpy(mid,LR[s+1][c].e);  
 if(strcmp(mid,"   ")==0)  
 {     printf("不能规约\n");       return   -2;     }  
   
 if(strcmp(mid,"acc")==0||strcmp(mid,"ACC")==0)  
 {     printf("规约成功\n");       return   -1;     }  
   
 out[i+1].order=i+2;  
   
 if(mid[0]=='s'||mid[0]=='S')  
 {  
  s_num=CharChangeNum(mid+1);//s_num为S后的数字  
  for(j=0;j<stateTop;j++)  
   out[i+1].state[j]=out[i].state[j];  
  out[i+1].state[stateTop]=s_num;    
  out[i+1].state[++stateTop]=-1;       //完成第i+1行的状态栈赋值  
  
  strcpy(out[i+1].sign,out[i].sign);  
  out[i+1].sign[signTop]=out[i].input[0];  
  out[i+1].sign[++signTop]='\0';     //完成第i+1行的符号栈的赋值  
  
  strcpy(out[i+1].grasen,"   ");                                 //完成第i+1行的产生式的赋值  
  
  strcpy(out[i+1].input,out[i].input+1);         //完成第i+1行的输入符号串的赋值  
  
  //说明暂时不写  
 }  
 else   if(mid[0]=='r'||mid[0]=='R')  
 {  
  r_num=CharChangeNum(mid+1);//r_num为r后的数字  
  strcpy(gra,*(GramSent+r_num-1));  
  len=strlen(gra);  
  for(j=0;j<len;j++)  
   if(gra[j]=='-'   &&   gra[j+1]=='>')  
    break;  
   n=strlen(gra+j+2);  
           
   stateTop-=n;     signTop-=n;  
   
   for(j=0;j<stateTop;j++)  
    out[i+1].state[j]=out[i].state[j];  
   j=SignNum(gra[0]);  
   out[i+1].state[stateTop]=CharChangeNum(LR[out[i+1].state[stateTop-1]+1][j].e);    
   out[i+1].state[++stateTop]=-1;       //完成第i+1行的状态栈赋值  
   
   strcpy(out[i+1].sign,out[i].sign);  
   out[i+1].sign[signTop]=gra[0];  
   out[i+1].sign[++signTop]='\0';     //完成第i+1行的符号栈的赋值  
   
   strcpy(out[i+1].grasen,gra);                                 //完成第i+1行的产生式的赋值  
   
   strcpy(out[i+1].input,out[i].input);         //完成第i+1行的输入符号串的赋值  
   
   //说明暂时不写  
 }  
 return   1;  
}  

void   OutputResult(int   r)  
{    
 int   i,j;  
 printf("**********************************************************\n");  
 printf("*     句子：%s   用LR分析表   规约过程如下：                                     *\n",Sentence);  
 printf("**********************************************************\n");  
 for(i=0;i<=r;i++)  
 {  
  j=0;  
  printf("%2d     ",out[i].order);  
  while(out[i].state[j]!=-1)  
   printf("%d",out[i].state[j++]);  
  printf("     %s     %s     %s\n",out[i].sign,out[i].grasen,out[i].input);  
 }  
}  

int   OutControl()//输出结果的总控函数  
{  
 int   s_num,i=0;  
 out[0].order=1;                                   //序号赋值  
 out[0].state[0]=0;     stateTop=1;     out[0].state[stateTop]=-1;           //状态栈赋值，置栈顶位  
 strcpy(out[0].sign,"#");       signTop=1;       //符号栈赋值，置栈顶位  
 strcpy(out[0].grasen,"   ");                             //产生式为空  
 strcpy(out[0].input,Sentence);                     //以下两行为输入串赋值  
 strcat(out[0].input,"#");  
 strcpy(out[0].explen,"0和#进栈");               //解释说明  
 //初使化输出结果的第一行  
 
 while(1)  
 {  
  s_num=SignNum(out[i].input[0]);  
  //if(s_num!=-1)  
  if(OutResult(out[i].state[stateTop-1],s_num,i)!=1)  
   break;  
  i++;  
 }  
 return   i;  
}  

main()  
{  
 int   r;  
 printf("**********************************************************\n");  
 printf("*     函数的输入:   文法的产生式,文法句型的一个句子,LR分析表     *\n");  
 printf("*     函数的输出:   LR分析器的工作过程与说明                                     *\n");  
 printf("**********************************************************\n");  
 printf("请输入LR分析表中终结符与非终结符的总个数\n");  
 scanf("%d",&colno);  
 printf("请输入LR分析表中状态的总个数\n");  
 scanf("%d",&row);  
 input_LR(row,colno);  
 output_LR(row,colno);  
 input_GramSent();  
 r=OutControl();     //r为输出结果的行数  
 OutputResult(r);  
}