消除文法左遞歸的算法

存儲文法的資料結構

1 typedef struct P{
 2     char key;           // 産生式左部
 3     char * value [16];  // 産生式右部
 4     int count;          // 幾組規則
 5 }P;
 6 typedef struct G{
 7     char * vn ;     // 非終結符集合
 8     char * vt ;     // 終結符集合
 9     P   p[16];      // 産生式
10     char start;     // 開始符号
11     int pcount ;
12 }G;      

文法G由多條産生式組成，出現在産生式左部的非終結符，會指向一個P文法數組，每一個數組元素對應一個程式的右部，這樣的結構顯然是對文法進行了壓縮的

算法過程

1、 掃描文法，先将間接做遞歸轉換成直接左遞歸

2、 借助如下公式，消除直接左遞歸

對形如這樣的程式

A->Aα1|Aα2|Aα3| Aαn|..|ρ1|ρ2|….| ρn

轉換成如下形式

A->ρ1A'|ρ2A'|ρ3A'

A'->α1A'|α2A'|....|ε

輸入

1 3
2 2 S Qc|c
3 2 Q Rb|b
4 2 R Sa|a      

完整算法

1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include <string.h>
  4 
  5 typedef struct P{
  6     char key;           // 産生式左部
  7     char * value [16];  // 産生式右部
  8     int count;          // 幾組規則
  9 }P;
 10 typedef struct G{
 11     char * vn ;     // 非終結符集合
 12     char * vt ;     // 終結符集合
 13     P   p[16];      // 産生式
 14     char start;     // 開始符号
 15     int pcount ;
 16 }G;
 17 
 18 int main(){
 19     int i,n;
 20     freopen("xczdg.in","r",stdin);
 21     printf("Plese input P count :");
 22     scanf("%d",&n);
 23     printf("\n");
 24     G g;
 25     g.pcount = n;
 26     //g.p = (P *)malloc(sizeof(P)*n);
 27     for(i=0;i<n;i++){
 28         scanf("%d%*c",&g.p[i].count);
 29         g.p[i].key = getchar();
 30         getchar();
 31         char ch,str[255];
 32         int sp = 0,c=0;
 33         while((ch = getchar()) != '\n'){
 34             if('|' == ch){
 35                 str[sp]='\0';
 36                 g.p[i].value[c] = (char *) malloc(sizeof(char)*255);
 37                 strcpy(g.p[i].value[c],str);
 38                 sp = 0;
 39                 c++;
 40             }
 41             else{
 42                     str[sp] = ch;
 43                     sp++;
 44             }
 45         }
 46         str[sp]='\0';
 47         g.p[i].value[c] = (char *) malloc(sizeof(char)*255);
 48         strcpy(g.p[i].value[c],str);
 49 
 50         printf("%c=>%s|%s\n",g.p[i].key,g.p[i].value[0],g.p[i].value[1]);
 51     }
 52 
 53     for(i=0;i<n;i++){
 54         int j = 0;
 55         for(;j<i;j++){
 56             // 将間接左遞歸轉換成直接左遞歸
 57             // 掃描Ai的開始符号，一定要是非終結符
 58             int k;
 59             for(k=0;k<g.p[i].count;k++){
 60                 char i_start = g.p[i].value[k][0];
 61                 //printf("%c\n",start);
 62                 if(i_start==g.p[j].key){
 63                     // 滿足 Ai->Ajr
 64                     char tmp[255];
 65                     char fiel[255];
 66                     strcpy(fiel,&g.p[i].value[k][1]);
 67 
 68                     strcpy(tmp,g.p[j].value[0]);
 69                     strcpy(g.p[i].value[k],strcat(tmp,fiel));
 70                     printf("%d %s\n",k,g.p[i].value[k]);
 71                     int m;
 72                     for(m=1;m<g.p[j].count;m++){
 73                         strcpy(tmp,g.p[j].value[m]);
 74                         g.p[i].value[g.p[i].count] = (char *) malloc(sizeof(char)*255);
 75                         strcpy(g.p[i].value[g.p[i].count],strcat(tmp,fiel));
 76                         printf("%d %s\n",g.p[i].count,g.p[i].value[g.p[i].count]);
 77                         g.p[i].count++;
 78 
 79                     }
 80                 }
 81 
 82             }
 83         }
 84         // 消除直接左遞歸
 85         // 掃描Pi.key 為産生式右部的所有産生式
 86         for(j=0;j<g.p[i].count;j++){
 87             char * pivj = g.p[i].value[j];
 88             if(g.p[i].key == pivj[0]){
 89                 // 存在直接左遞歸
 90                 int m;
 91                 for(m=0;m<g.p[i].count;m++){
 92                     if(m!=j){
 93                         // A->ρ1A'|ρ2A'|ρ3A'    ρρσσαα
 94                         char aci[2] = {g.p[i].key-32,'\0'};
 95                         strcat(g.p[i].value[m],aci);         // 這裡A'直接已A的ASCII碼值減32表示
 96                     }else{
 97                         // A'->α1A'|α2A'|....|ε
 98                         g.p[g.pcount].key = g.p[i].key-32;
 99                         g.p[g.pcount].value[0] = (char *) malloc(sizeof(char)*255);
100                         strcpy(g.p[g.pcount].value[0],&pivj[1]);
101                         char aci[2] = {g.p[g.pcount].key,'\0'};
102                         strcat(g.p[g.pcount].value[0],aci);
103                         g.p[g.pcount].value[1] = (char *) malloc(sizeof(char)*255);
104                         strcpy(g.p[g.pcount].value[1],"kong");
105                         g.p[g.pcount].count = 2;
106                         g.p[i].value[j] = NULL;
107                         g.pcount++;
108                     }
109                 }
110                 break;
111             }
112         }
113 
114     }
115 
116     printf("\n-----------------------\n");
117     // 列印文法
118     for(i=0;i<g.pcount;i++){
119         if(g.p[i].key){
120             if(g.p[i].key) printf("%c=>",g.p[i].key);
121             int j;
122             for(j=0;j<g.p[i].count;j++){
123                 if(g.p[i].value[j]) printf("%s ",g.p[i].value[j]);
124             }
125             printf("\n");
126         }
127     }
128     free(g.p);
129     return 0;
130 }      

運作結果

（這裡用2代替R'，用kong代表空字元）