编译原理 实验2 语法分析器的构造 LL(1)

时间:2021-06-11 03:57:18
【实验目的】
       练习构造语法分析程序的方法,熟悉上下文无关文法的使用,加深对课堂教学的理解;提高词法分析方法的实践能力
【实验要求】
    利用某一高级程序设计语言构造语法分析程序 
【具体要求】对于给定的文法G[E]
              E->TE’
             E’->+TE’ | ε
            T->FT’
            T’->*F T’| ε
            F->(E) | i
     采用递归下降分析法编写语法分析程序及LL(1)语法分析法编写语法分析程序,该语法分析程序判断输入的字符串是否符合上述文法,并能够输出相应的结果(是语法成分或不是语法成分)。
 
  1. /*  
  2.     实验名称:实验2 语法分析器实验  
  3.     学号:  
  4.     姓名:niu91(859222829)  
  5.     班级:  
  6. */   
  7. #include<stdio.h>  
  8. #include<string.h>  
  9. #include<malloc.h>  
  10. #define N 100  
  11.   
  12. int seekProd(int stackTop,int inputstrTop);  
  13. //char inputstr[10]="i*i+i#";  
  14. char inputstr[20];  
  15. char stack[10]="";  
  16.   
  17. typedef struct production{  
  18.     char leftChar;  
  19.     char rightChars[4];  
  20.     char allChars[8];  
  21. }Prod;  
  22.   
  23. Prod productions[8];  
  24. void init();  
  25. int stackPush(int *top, Prod prod);  
  26. int matching(int *top, char *inputstr);  
  27. int main()  
  28. {  
  29.     int len;//输入串的长度  
  30.     int stackTop=1;  
  31.     int inputstrTop=0;  
  32.     int i;  
  33.     char *z="#";  
  34.     int index=0;  
  35.   
  36.       
  37.     init();//产生式初始化  
  38.       
  39.     stack[0]='#';  
  40.     stack[stackTop]='E';  
  41.     printf("请输入字符串:");  
  42.     gets(inputstr);  
  43.       
  44.     len=strlen(inputstr);  
  45.     inputstr[len]='#';  
  46.     while( stackTop>=0 )  
  47.     {  
  48.     //  printf("%d,%d\n",stackTop,inputstrTop);  
  49.         printf("第%2d步:",++index);  
  50.         printf("当前栈:%-8s",stack);  
  51.         printf("输入字符串:%8s",inputstr);  
  52.         //根据栈定元素和字符串首字母  
  53.           
  54.         if(matching(&stackTop,inputstr)){  
  55.             printf("\n");  
  56.         }else{  
  57.             i=seekProd(stackTop,inputstrTop);  
  58.             stackPush(&stackTop,productions[i]);//压栈  
  59.             printf("进行下一步所用的产生式:%s\n",productions[i].allChars);  
  60.         }         
  61.     }  
  62.     if(stackTop+1==0)  
  63.     {  
  64.         printf("分析成功!\n");  
  65.     }  
  66.   
  67.     return 0;  
  68. }  
  69.   
  70. //搜索分析表  
  71. int seekProd(int stackTop,int inputstrTop)  
  72. {  
  73. //  printf("stack[stackTop]=%c\n",stack[stackTop]);  
  74.     if(stack[stackTop]=='E'){  
  75.         if(inputstr[inputstrTop]=='i')  
  76.         {  
  77.             return 0;  
  78.         }else if(inputstr[inputstrTop]=='('){  
  79.             return 0;  
  80.         }else{  
  81.             return -1;  
  82.         }  
  83.     }else if(stack[stackTop]=='X'){  
  84.         if(inputstr[inputstrTop]=='+')  
  85.         {  
  86.             return 1;  
  87.         }else if(inputstr[inputstrTop]==')'){  
  88.             return 2;  
  89.         }else if(inputstr[inputstrTop]=='#'){  
  90.             return 2;  
  91.         }else{  
  92.             return -1;  
  93.         }  
  94.     }else if(stack[stackTop]=='T'){  
  95.         if(inputstr[inputstrTop]=='i')  
  96.         {  
  97.             return 3;  
  98.         }else if(inputstr[inputstrTop]=='('){  
  99.             return 3;  
  100.         }else{  
  101.             return -1;  
  102.         }  
  103.     }else if(stack[stackTop]=='Y'){  
  104.         if(inputstr[inputstrTop]=='+')  
  105.         {  
  106.             return 5;  
  107.         }else if(inputstr[inputstrTop]=='*'){  
  108.             return 4;  
  109.         }else if(inputstr[inputstrTop]==')'){  
  110.             return 5;  
  111.         }else if(inputstr[inputstrTop]=='#'){  
  112.             return 5;  
  113.         }else{  
  114.             return -1;  
  115.         }  
  116.     }else if(stack[stackTop]=='F'){  
  117.         if(inputstr[inputstrTop]=='i'){  
  118.             return 7;  
  119.         }else if(inputstr[inputstrTop]=='('){  
  120.             return 6;  
  121.         }else{  
  122.             return -1;  
  123.         }  
  124.     }else{  
  125.         printf("错误!");  
  126.     }  
  127.     return -1;  
  128. }  
  129. void init()  
  130. {  
  131.     productions[0].leftChar='E';strcpy(productions[0].rightChars,"TX"); strcpy(productions[0].allChars,"E->TX");  
  132.     productions[1].leftChar='X';strcpy(productions[1].rightChars,"+TX");strcpy(productions[1].allChars,"E->+TX");  
  133.     productions[2].leftChar='X';strcpy(productions[2].rightChars,"ε");  strcpy(productions[2].allChars,"X->ε");  
  134.     productions[3].leftChar='T';strcpy(productions[3].rightChars,"FY"); strcpy(productions[3].allChars,"T->FY");  
  135.     productions[4].leftChar='Y';strcpy(productions[4].rightChars,"*FY");strcpy(productions[4].allChars,"Y->*FY");  
  136.     productions[5].leftChar='Y';strcpy(productions[5].rightChars,"ε");  strcpy(productions[5].allChars,"Y->ε");  
  137.     productions[6].leftChar='F';strcpy(productions[6].rightChars,"(E)");strcpy(productions[6].allChars,"F->(E)");  
  138.     productions[7].leftChar='F';strcpy(productions[7].rightChars,"i");  strcpy(productions[7].allChars,"F->i");  
  139. }  
  140. int stackPush(int *top, Prod prod)  
  141. {  
  142.     int len;  
  143.     int i;  
  144.     char *c="ε";  
  145.     len=strlen(prod.rightChars);  
  146.     if(!strcmp(prod.rightChars,c))  
  147.     {  
  148.         stack[(*top)]='\0';  
  149.     }else{  
  150.         for(i=len-1;i>=0;i--)  
  151.         {  
  152.             stack[(*top)++] = prod.rightChars[i];  
  153.         }  
  154.           
  155.     }  
  156.     --(*top);  
  157.     return 0;  
  158. }  
  159. int matching(int *top, char *inputstr)  
  160. {  
  161.     int len;  
  162.     int i;  
  163.     if(stack[(*top)]==inputstr[0])  
  164.     {     
  165.         stack[(*top)--]='\0';  
  166.         len=strlen(inputstr);  
  167.         for(i=0;i<len-1;i++)  
  168.         {  
  169.             inputstr[i]=inputstr[i+1];  
  170.         }  
  171.         inputstr[i]='\0';  
  172.         return 1;  
  173.     }else  
  174.     {  
  175.         return 0;  
  176.     }  
  177. }  

编译原理 实验2 语法分析器的构造 LL(1)