cyk.rar_CYK算法实现_WFX_cyk算法_pcfg_乔姆斯基范式

/*算法的描述： 依我个人的理解cyk只这样工作的： 先将要测试的字符串分解成长度为1的子串，并找出它们都由 那些变元可以得到。这个工作是很容易的。 下来要计算所有的长度为2的字串可以由那些单个变元得到， 这一步就要使用第一步的结果了，比如说"ab"，我们只需要把他看 作是a后面加b，和b前面加a。这两种情况的区别在长度为n的子串 中显的尤为重要。接下来只需要将能够生成a和b的变元交叉组合， 然后到文法中查找可以生成这些组合的变元，这些变元就是能够生 成"ab"的变元了。 再下来就是要计算所有长度为m的子串了，这步需要第一步和 第m-1步的结果了，比如说"abcd"，把它看做是a后边加"bcd"，和 "abc"后边加d，因为有前 */ /*输入示例 S->AB|BC//输入的乔姆斯基范式，其中第一个字母必须是初始变元 A->BA|a B->CC|b C->AB|a S->AB A->AC|a B->BC|b C->CC|c # bbabaa//要测试的字符串 */ #include <stdio.h> #include <stdlib.h> #define cfg_variable 10//单个表达式的长度，包括"->"(它是两个字符) #define test_length 10//测试表格的宽度 void get_cfg( char cfg[][cfg_variable]);//得到乔姆斯基范式 int test( char cfg[][cfg_variable],char a[test_length]);//测试函数 void new_table( int line,char cfg[cfg_variable][cfg_variable],char table[][cfg_variable],char create[][cfg_variable*cfg_variable*2],int b_length); //更新表格 int main() { char cfg[cfg_variable][cfg_variable]; char a[test_length]; printf("输入你的乔姆斯基范式，最后一行输入回车表示输入结束：\n"); get_cfg(cfg); printf("输入你要测试的字符串：\n"); gets(a); printf("\n算法演示：\n\n"); test(cfg,a); return 0; } void get_cfg( char cfg[][cfg_variable]) { int i; for (i = 0;i<cfg_variable;i++)//初始化cfg cfg[i][0] = '\0'; i = 0; do//得到cfg { gets(cfg[i]); i++; } while ( cfg[i-1][0] != '\0'); } int test( char cfg[][cfg_variable],char a[test_length]) { char table[test_length*test_length/2 + test_length/2][cfg_variable]; int i,j,k,m,n; int a_length; int b_length; int c_length; int line = 0; int flag = 0; char create[test_length][cfg_variable*cfg_variable*2]; for (i=0;i<test_length;i++)//算数测试字符串的长度 { if (a[i] == '\0') { a_length = i; break; } } m = 0; //得到表格的第一行 for (i=0;i<a_length;i++) { for (j=0;j<cfg_variable;j++) { for (k=0;k<cfg_variable;k++) { if ( cfg[j][k] == a[i] ) { table[i][m] = cfg[j][0]; m++; break; } } } table[i][m] = '\0'; printf("%s\t",table[i]); m = 0; } printf("\n"); //以下是算出表格的其余部分 m = 0; n = 0; b_length = a_length; c_length = 0; for (i=1;i<a_length;i++)//从第二行开始 { for (j=0;j<b_length-1;j++)//从第一列开始，其中b_length是递减的 { /*第n行是由第1行和第-1行组合得到的，每一项都有两种情况 比如长度为4的子串，可以理解为1+3和3+1两种情况*/ while (table[j][n] != '\0') { for (k=0;table[j+1+c_length][k] != '\0';k++) { create[j][m] = table[j][n]; m++; create[j][m] = table[j+1+c_length][k]; m++; } n++; } n = 0; while (table[j+c_length][n] != '\0') { for (k=0;table[j+i][k] != '\0';k++) { create[j][m] = table[j+c_length][n]; m++; create[j][m] = table[j+i][k]; m++; } n++; } n = 0; create[j][m] = '\0'; m = 0; } line += (b_length-1); line++; //这个函数显然是用来更新子表格的 new_table(line,cfg,table,create,b_length-1); c_length += b_length; b_length--; } for (i=0;i<cfg_variable;i++) { if (table[a_length*a_length/2+a_length/2-1][i] == cfg[0][0]) flag++; } if(flag == 0) printf("\n不可以接受\n"); else printf("\n可以接受\n"); return 0; } void new_table( int line,char cfg[cfg_variable][cfg_variable],char table[][cfg_variable],char create[][cfg_variable*cfg_variable*2],int b_length) { int i,j,k,m,x; int n = 0; char mid[2]; int flag = 0; for (i=0;i<b_length;i++) { for (j=0;create[i][j] != '\0';j++) { mid[0] = create[i][j]; j++; mid[1] = create[i][j]; for (k=0;k<cfg_variable;k++) { for (m=1;(cfg[k][m] != '\0') && (cfg[k][m-1] != '\0');m++) { if (cfg[k][m] == '>' || cfg[k][m] == '|') { m++; if (cfg[k][m] == mid[0] && cfg[k][m+1] == mid[1]) { /*其中如果有相同的项，那么只保留一项，如果要研究歧义性就可以从这里下手了*/ for (x=0;x<n;x++) { if (table[line+i][x] == cfg[k][0]) flag = 1; } if (flag == 0) { table[line+i][n] = cfg[k][0]; n++; } flag = 0; } m++; } } } } table[line+i][n] = '\0'; n = 0; printf("%s\t",table[line+i]); } printf("\n"); }