消除文法左递归的算法

简介: 存储文法的数据结构 1 typedef struct P{ 2 char key; // 产生式左部 3 char * value [16]; // 产生式右部 4 int count; // 几组规则 5 }P...

存储文法的数据结构

 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代表空字符)

 

 

 

目录
相关文章
|
12天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
30 2
|
5月前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
|
1月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
23 1
|
5月前
|
存储 算法 程序员
数据结构与算法===递归
数据结构与算法===递归
|
1月前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
40 0
|
3月前
|
算法
【算法】递归、搜索与回溯——汉诺塔
【算法】递归、搜索与回溯——汉诺塔
|
4月前
|
算法 Python
python中算法递归错误(Recursion Errors)
【7月更文挑战第18天】
69 1
|
3月前
|
算法
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
|
3月前
|
算法
【算法】递归、搜索与回溯——简介
【算法】递归、搜索与回溯——简介
|
5月前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用,包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现,通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数,分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例,展示了递归的优雅与效率。然而,递归可能导致栈溢出,需注意优化。学习递归深化了对“分而治之”策略的理解。**
111 7
下一篇
无影云桌面