Click here to Skip to main content
15,867,835 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
See more:
hi, can anyone help me to give me an example of its output program ... its Cyk Algorithm Implementation ... i'll be thankful very much to help me to understand its code ...

many thanks

~lida


C++
#include "stdafx.h"
#include <Windows.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cassert>
#include<iomanip>
using namespace std;

#define MAX 100
#define for(i,a,b) for(i=a;i<b;i++)
#define ASSERTMSG(TST,MSG) ((TST) ? (void)0 : (cerr<<MSG<<endl,abort()))

string arr[MAX][MAX]; // to store entered grammar
string dpr[MAX];
int p,np; // np -> number of productions

inline string concat(string a, string b)//concatenates unique non-terminals
{
	int i;
	string r=a;
	for(i,0,b.length())
		if(r.find(b[i]) > r.length())
			r += b[i];
	return (r);

}

inline void deconc(string a)//seprates right hand side of entered grammar
{
	int i;
	p=0;

	while(a.length())
	{
		i = a.find("|");
		if ( i > a.length())
		{
			dpr[p++] = a;
			a=" ";
		
		}
		else
		{
			dpr[p++] = a.substr(0,i);
			a = a.substr(i+1,a.length());
		
		}
	
	}

}

inline int lchomsky (string a) //checks if LHS of entered grammar is in CNF
{
	if(a.length() == 1 && a[0] >= 'A' && a[0] <= 'Z')
		return 1;
	return 0;

}

inline int rchomsky (string a)//checks if RHS of grammar is in CNF
{
	if( a.length() == 1 && a[0] >= 'a' && a[0] <= 'z')
		return 1;
	if ( a.length() == 2 && a[0] >= 'A' && a[0] <= 'Z' && a[1] >= 'A' && a[1] <= 'Z')
       return 1;
	return 0;
}

inline string search_prod(string p)//returns a concatenated string of variables which can produce string p
{
	int j,k;
	string r= " ";
	for(j,0,np)
	{
		k=1;
		while(arr[j][k] != " ")
		{
			if (arr[j][k] == p)
			{
				r= concat(r,arr[j][0]);
			
			}
		k++;
		}
	
	}
return r;
}

inline string gen_comb(string a, string b)//creates every combination of variables from a and b . For eg: BA * AB = 
{
	int i,j;
	string pri=a,re=" ";
	for(i,0,a.length())
		for(j,0,b.length())
		{
			pri = " ";
			pri = pri + a[i] + b[j];

			re = re + search_prod(pri);//searches if the generated productions can be created or not
		
		}
		return re;

}

int main()
{
	int i,pt,j,l,k;
	string a,str,r,pr,start;

	cout<<"\n*************************CYK ALGORITHM Implementation**************************\n";
	cout<<"\nEnter the set of start variables ";
	cin>>start;
	cout<<"\nEnter number of productions ";
	cin>> np;

	for(i,0,np)
	{
		cin>>a;
		pt = a.find( " -> ");
		arr[i][0] = a.substr(0,pt);

		ASSERTMSG(lchomsky(dpr[j]),"\nGrammar not in Chomsky Form");
        
		a = a.substr(pt+2 , a.length());
		deconc(a);

		for(j,0,p)
		{
			arr[i][j+1]=dpr[j];
			ASSERTMSG(rchomsky(dpr[j]),"\nnGrammar not in Chomsky Form");

		
		}
	
	}
	string matrix[MAX][MAX],st;
	cout<<"\nEnter string to be checked : ";
cin>>str;

for(i,0,str.length())
{
	r = " ";
	st = " ";
	st += str[i];

	for(j,0,np)
	{
		k = 1;
		while(arr[j][k] != " ")
		{
			if(arr[j][k] == st)
			{
				r=concat(r,arr[j][0]);
		
			}
			k++;
		
		}
		
	
	}

matrix[i][i] = r;

}

int ii,kk;
for( k , 1 , str.length())
{
	for(j,k,str.length())
	{
		r = " ";
		for (l,j-k,j)
		{
			pr = gen_comb(matrix[j-k][l],matrix[l+1][j]);
			r = concat(r,pr);
		
		}
		matrix[j-k][j] = r;

	
	}

}

cout<< " \nMatrix Generated :- " << endl;

for(i,0,str.length())
{
	for(j,0,str.length())
		cout<< setw(5) << matrix[i][j] << " ";

	cout << endl;

}

int f=0;
for(i,0,start.length())
if( matrix[0][str.length()-1].find(start[i]) <= matrix[0][str.length()-1].length())
{
	cout << "String can be generated\n";
	return 0;

}

cout << "String cannot be generated\n";
return 0;
}
Posted
Comments
Sandeep Mewara 5-Jan-13 13:38pm    
Did you try by yourself? If yes, what was the result?
lida zar 5-Jan-13 14:10pm    
yes the result its that

Enter the set of start variables ab
Enter number of productions 3

and after it anything i type given error...
Sergey Alexandrovich Kryukov 5-Jan-13 22:45pm    
What exactly? Describe your problem in sufficient detail.
—SA

1 solution

Little hint did you have a subject called Theoretical Computer Science or(TCS),your code is checking whether ur entered string is in Chomsky Normal form (CNF) or not and does further processing on it depending on the outcome...
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900