/*算法的描述：
依我个人的理解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");
}
评论0