编译原理--递归下降语法分析源代码(C Language)

时间:2021-11-23 03:53:56

    花了一晚上写的编译原理作业,递归下降语法分析,实现'i'字符进行的+ - * / 操作,错误跳出(未完善错误提示),语法分析过程.  现把源程序贴出来,时间仓促,难免有错误请给与指正.

  运行,例如输入:i+i#                             ---------------------------'#'结束------------------------------------------------

/**
*@Create:       2006-11-08 WED
*@Author:       oDon
*@Describe:    A simple Descent LL(1) Syntax Analysiser
*@Copyright:   yuanonline@hotmail.com  --oDon--
*(1)E→TG
*(2)G→+TG|-TG
*(3)G→ε
*(4)T→FS
*(5)S→*FS|/FS
*(6)S→ε
*(7)F→(E)
*(8)F→i
*/
#include <stdio.h>
#include<dos.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
#define SIZE 50
#define EMPTY 14
char LAnalysisStr[MAXSIZE]; //Left Analysis String
char stack[SIZE];           //A Stack
char expression[SIZE];      //Expression that inputed by user
char G_Expression[SIZE];    //Generate Expression
char symbol;                //current char of expression
int  Index_exp;             //The index of Expression
int  current_Index;         //current index of expression
char state = 0;             //whether the Syntax is starting
int  LIndex;                //The Index of Left Analysis String
int  AnalyseTrace[SIZE];    //Record the trace of Syntax Analyse
int  Index_Trace;
//Syntax Analysiser Function Definate Below ...
int  E_Start();
int  G_Syntax();
int  T_Syntax();
int  S_Syntax();
int  F_Syntax();
//************************************************
/***************************************
 Describe:Append append[] to String test[]
          after Index
 @Param:  char test[], char append[]
 @Return: void
 @note:   Never using this fuction !
 *****************************************/
void append(char test[], char append[])
{
    int i = 0;
    int Index = 0;
    while(LAnalysisStr[Index]!= '/0')Index++;
    while(append[i]!= '/0')
    {
        test[Index] = append[i];
        Index++;
        i++;
    }
    // name of 'LIndex' can not modify
    LIndex = Index;
}
/***************************************
 Describe:Modify the Generate expression
         
 @Param:  char pre, char substance[]
 @Return: void
 *****************************************/
void modify(char pre, char substance[])
{
     int i = 0;
     int j = 0;
     int k = 0;
     char temp[SIZE];
     strcpy(temp, G_Expression);          //copy G_Expression to temp string
     puts(G_Expression);
     while((temp[i]!= pre) && (i < SIZE))
         i++;                             //i is now point to the index of [pre]
                                         
     for(j = i,k = 0; j < strlen(substance) + i; j++, k++)
           temp[j] = substance[k];        //pre is instead of substance
     for(k = i + 1; k < strlen(G_Expression); k++,j++)
           temp[j] = G_Expression[k];     //The rest of G_Expression is copy to temp
           temp[j] = '/0';                //temp is end of '/0'
     strcpy(G_Expression, temp);          // copy temp to G_Expression
}
/***************************************
 Describe:Printing the Trace of the
          Syntax Analyser
 @Param:  void
 @Return: void
 *****************************************/
 void PrintTrace()
 {
      int i = 0;
      while(AnalyseTrace[i] != 0)
     {
          switch(AnalyseTrace[i])
          {
              case 1:
                   modify('E',"TG");
                   break;
              case 2:
                   modify('T',"FS");
                   break;
              case 3:
                   modify('G',"+TG");
                   break;
              case 4:
                   modify('G',"-TG");
                   break;
              case 5:
                   modify('S',"*FS");
                   break;
              case 6:
                   modify('S',"/FS");
                   break;
              case 7:
                   modify('F',"(E)");
                   break;
              case 8:
                   modify('F',"i");
                   break;
              case 9:
                   modify('G',"@");
                   break;
              case 10:
                   modify('S',"@");
                   break;
          }
          i++;
          printf("%c/n",25);
     }
     puts(G_Expression);
 }
 
/***************************************
 Describe:Geting Expression that inputed
       by user;
 @Param:  void
 @Return: void
 *****************************************/
void GetExpression()
{
    char in;
 printf("Input Expression below <end of '#'>:/n");
 Index_exp = 0;
 in = getchar();
 while(in != '#')
 {
  expression[Index_exp++] = in;
  in = getchar();
 }
}
/***************************************
 Describe:Printing Expression that inputed
       by user;
 @Param:  void
 @Return: void
 *****************************************/
void PrintExpression()
{
     int i = 0;
     printf("You have inputed below:/n");
     for(i = 0; i < Index_exp; i++)
     printf("%c",expression[i]);
     printf("/n");
     printf("********************************************************/n");
     printf("|        /t%c Analysing... %c/t/t/t|/n",EMPTY,EMPTY);
     printf("********************************************************/n");
     printf("Syntax  |  Analysing String  | Analysing char  | Rest Expression String/n");
}
/***************************************
 Describe:Printing Expression that analysis
 @Param:  void
 @Return: void
 *****************************************/
void PrintAnalysisExpression()
{
     int i = 0;
     for(i = 0; i <= current_Index; i++)
     printf("%c",expression[i]);
     printf("/t");
}
/***************************************
 Describe:Printing Expression that wait
          to be analysed
 @Param:  void
 @Return: void
 *****************************************/
void PrintRestExpression()
{
     int i;
     printf("/t/t");
     for(i = current_Index; i < Index_exp; i++)
     {
           printf("%c",expression[i]);
     }
     printf("/n");
}
 int G_Syntax()
 {
     if(expression[current_Index] == '+')
     {
          printf("[G -> +TG]/t/t");
          AnalyseTrace[Index_Trace++] = 3;
          PrintAnalysisExpression();
          printf("%c/t",expression[current_Index]);
          PrintRestExpression();
          current_Index++;
          // T_Syntax & G_Syntax
          if(!T_Syntax())           
          {return 0;}
          if(!G_Syntax())
          {return 0;}
          //return to E_Start
          return 1;
     }
     else if(expression[current_Index] == '-')
     {
          printf("[G -> -TG]/t/t");
          AnalyseTrace[Index_Trace++] = 4;
          PrintAnalysisExpression();
          printf("%c/t",expression[current_Index]);
          PrintRestExpression();
          current_Index++;
          // T_Syntax & G_Syntax
          if(!T_Syntax())           
          {return 0;}
          if(!G_Syntax())
          {return 0;}
          //return to E_Start
          return 1;
     }
     else
     {
         printf("G -> %c/t/t/t",EMPTY);
         AnalyseTrace[Index_Trace++] = 9;
         PrintAnalysisExpression();
          printf("%c/t",expression[current_Index]);
          PrintRestExpression();
     }
 }
 
/****************************************
 Describe: S gernerate syntax
 @Param:   void
 @Return:  int
 *****************************************/
 int S_Syntax()
 {
     if(expression[current_Index] == '*')
     {
          printf("[S -> *FS]/t/t");
          AnalyseTrace[Index_Trace++] = 5;
          PrintAnalysisExpression();
          printf("%c/t",expression[current_Index]);
          PrintRestExpression();
          current_Index++;
          if(!F_Syntax())            // F_Syntax fail then return
          {return 0;}
          if(!S_Syntax())
          {return 0;}
          return 1;
     }
     else if(expression[current_Index] == '/')
     {
          printf("[S -> /FS]/t/t");
          AnalyseTrace[Index_Trace++] = 6;
          PrintAnalysisExpression();
          printf("%c/t",expression[current_Index]);
          PrintRestExpression();
          current_Index++;
          if(!F_Syntax())            // F_Syntax fail then return
          {return 0;}
          if(!S_Syntax())
          {return 0;}
          return 1;
     }
     else
     {
         printf("S -> %c/t/t/t",EMPTY);
         AnalyseTrace[Index_Trace++] = 10;
         PrintAnalysisExpression();
          printf("%c/t",expression[current_Index]);
          PrintRestExpression();
         return 1;
     }
     return 1;
 }
/***************************************
 Describe: T gernerate syntax
 @Param:   void
 @Return:  int
 *****************************************/
 int F_Syntax()
 {
     if(expression[current_Index] == '(')
     {
          AnalyseTrace[Index_Trace++] = 7;
          printf("[F -> (E)]/t/t");
          PrintAnalysisExpression();
          printf("%c/t",expression[current_Index]);
          PrintRestExpression();
          current_Index++;     // Get next char in expression
          return 1;
     }
     else if(expression[current_Index] == 'i')
     {
         AnalyseTrace[Index_Trace++] = 8;
         printf("[F -> i]/t/t");
         PrintAnalysisExpression();
         printf("%c/t",expression[current_Index]);
         PrintRestExpression();
         current_Index++;     // Get next char in expression
         return 1;
     }
     else
     return 0;
 }
/***************************************
 Describe: T gernerate syntax
 @Param:   void
 @Return:  int
 *****************************************/
int T_Syntax()
{
    printf("[T -> FS]/t/t");
    AnalyseTrace[Index_Trace++] = 2;
    if(state)
    {
         PrintAnalysisExpression();
         printf("%c/t",expression[current_Index]);
    }
    else
    {printf("/t%c/t",expression[current_Index]);}
    PrintRestExpression();
    //LAnalysisStr[LIndex++] = '';
    state = 1;
    if(!F_Syntax())            // F_Syntax fail then return
    {return 0;}
    if(!S_Syntax())
    {return 0;}
    return 1;
   
}
/***************************************
 Describe: E gernerate syntax
 @Param:   void
 @Return:  int
 *****************************************/
int E_Start()
{
    current_Index = 0;                     // Current Index of Expression
    printf("[E -> TG]/t/t");
    printf("/t%c/t",expression[current_Index]);
    PrintRestExpression();
    AnalyseTrace[Index_Trace++] = 1;
    if(!T_Syntax())
    {return 0;}
    if(!G_Syntax())
    {return 0;}
    else
    {return 1;}
    return 0;
   
   
}
/***************************************
 Describe: Main
 @Param:   void
 @Return:  void
 *****************************************/
main()
{
    GetExpression(); 
 PrintExpression();
 if(E_Start() == 1)
 {
        printf("********************************************************/n");
        printf("|      /t%c Trace of Analysing %c/t/t/t/t|/n",EMPTY,EMPTY);
        printf("********************************************************/n");
        G_Expression[0] = 'E';
        PrintTrace();
        printf("********************************************************/n");
        printf("|      /t%c ACCEPT! %c/t/t/t/t/t|/n",EMPTY,EMPTY);
        printf("********************************************************/n");
        printf("/n/n/tPress any key to quit/n");
        getchar();
    }
    else
    {
        printf("********************************************************/n");
        printf("|      /t%c ERROR %c/t/t/t/t|/n",EMPTY,EMPTY);
        printf("********************************************************/n");
        printf("/n/t[Press any key to quit]/n");
        getchar();
    }/*end of if*/
    getchar();
 
}