ll(1)文法分析程序.txt

LL(1)文法源代码

#define MAX 100 
#include <iostream> 
using namespace std; 
#include <string.h> 
#include <stdlib.h> 

//函数声明 
void input(); 
void init_stack(); 
void ll1_analyzing(); 
void ll1array_push(char); 
int is_Vt(); 
int is_ll1array(char); 
int Vn_index(); 
int Vt_index(char); 
void pop(); 
void push(char); 
void reverse(); 
int printerror(); 

//全局变量定义 


//LL(1)表一 
//定义LL(1)分析表 
char Vn_array[] = "ABCDE"; 
char Vt_array[] = "i+*()#"; 
char  *LL1_array[][6] = { 
   {"CB", " ", " ", "CB", " ", " "}, 
   {" ", "+CB", " ", " ", "u", "u"}, 
   {"ED", " ", " ", "ED", " ", " "}, 
   {" ", "u", "*ED", " ", "u", "u"}, 
   {"i", " ", " ", "(A)", " ", " "} 
}; 
//end 


/* 
//LL(1)表二 
//定义LL(1)分析表 
char Vn_array[] = "PDEFS"; 
char Vt_array[] = "bdes;#"; 
char  *LL1_array[][6] = { 
   {"bDSe", " ", " ", " ", " ", "bDSe "}, 
   {" ", "d;E", " ", " ", " ", " "}, 
   {" ", "D", " ", "u", " ", " "}, 
   {" ", " ", "u", " ", ";sF", "u"}, 
   {" ", " ", " ", "sF", " ", " "} 
}; 
//end 
*/ 

char analyzed_sentence[MAX]; 

char stack[MAX]; 
char top; 
char *temp; 
char identified[MAX]; 
int n=0; 

void main() 
{ 
   input(); 
   init_stack(); //初始化栈，将'#'和开始符进栈 
   ll1_analyzing(); 
} 


void input() 
{ 
   int ch=0; 
   int   i=0; 
   while((ch=cin.get()) != '#') { 
      analyzed_sentence[i] = ch; 
      i++; 
   } 
   analyzed_sentence[i] = '#'; 
} 

void init_stack() 
{ 
   stack[0] = '#'; 
   stack[1] = Vn_array[0]; //开始符进栈 
   cout << stack[1] << "->"; 
} 

void ll1_analyzing() 
{ 
   top = stack[1]; 
   int error; 
   for (int i=0;i<=strlen(analyzed_sentence);i++) { 
      int test; 
      test = is_Vt(); 
      if (1 == test) { 
         if (top == analyzed_sentence[i]) { 
            identified[n++] = top; 
            pop(); 
            continue; 
         } 
         else { 
            printerror(); 
            break; 
         } 
      } 
      else if ('#' == top) {   //结束，将最终的表达式打印出来，除了'#' 
         for (int p=0;p<strlen(analyzed_sentence)-1;p++) { 
               printf("%c", analyzed_sentence[p]); 
            } 
               break; 
         } 
      else { 
         do  { 
               int judge=0; 
               judge = is_ll1array(analyzed_sentence[i]); 
               if (judge == 1) { 
                  if (1 == is_Vt()) {     //假设有符号不匹配，出错 
                     error=printerror(); 
                     break; 
                  } 
                  ll1array_push(analyzed_sentence[i]); 
               } 
               else { 
                  error = printerror(); 
                  break; 
               } 
                               
            } 
            while (top != analyzed_sentence[i]); 
            if (error == 1) 
               break; 
            identified[n++] = top; 
            if (top != '#') 
               pop(); 
      } 
    
   } 
} 

void ll1array_push(char currentchar) 
{ 
   int i,j; 
   i=Vn_index();  //求栈顶元素在Vn数组里面的下标 
   j=Vt_index(currentchar);  //求当前处理的符号在Vt数组里面的下标 
   temp=LL1_array[i][j]; 
   reverse(); 
   pop(); 
   int k; 
   for(k=0;k<strlen(temp);k++) 
   { 
      push(temp[k]); 
   } 
   printf("%s", identified); 
   for (int m=strlen(stack)-1;m>0;m--) 
      cout << stack[m] ; 
   cout << "->"; 
   if (top == 'u') 
      pop(); 
} 

void pop() 
{ 
   int topnum; 
   topnum = strlen(stack)-1; 
   stack[topnum] = '\0'; 
   top = stack[topnum-1]; 
} 

void push(char element) 
{ 
   int topnum; 
   topnum = strlen(stack); 
   stack[topnum] = element; 
   top = element; 
} 

int is_Vt() 
{ 
   int i; 
   int hit=0; 
   for (i=0;i<strlen(Vt_array);i++) { 
      if(top == Vt_array[i]) 
         hit = 1; 
   } 
   if (top == '#') 
      hit = 0; 
   if (hit == 1) 
      return 1; 
   else 
      return -1; 
} 
    
int is_ll1array(char currentchar) 
{ 
   int i,j; 
   i=Vn_index();  //求栈顶元素在Vn数组里面的下标 
   j=Vt_index(currentchar);      //求当前处理的符号在Vt数组里面的下标 
   if (LL1_array[i][j] == " ") { 
      return -1; 
   } 
   else 
      return 1; 

} 


int Vn_index() 
{ 
   for(int i=0;i<strlen(Vn_array);i++) { 
      if (top == Vn_array[i]) 
         return i;       
   } 
   return -1; 
} 

int Vt_index(char index_array) 
{ 
   for(int i=0;i<strlen(Vt_array);i++) { 
      if (index_array == Vt_array[i]) 
         return i; 
   } 
   return -1; 
} 

void reverse() //逆序处理 
{ 
   char s[MAX]; 
   strcpy(s, temp); 
   int i,j; 
   char tem; 
   i=0; 
   while (s[i] != '\0') 
      ++i; 
   --i; 
   if (s[i] == '\n') 
      --i; 
   j=0; 
   while (j<i) 
   { 
      tem = s[j]; 
      s[j] = s[i]; 
      s[i] = tem; 
      --i; 
      ++j; 
   } 
   temp=s; 
} 

int printerror() 
{ 
   cout << "这不是一句合法的句子，无法推导！" <<endl; 
   return 1; 
}