Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++
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
 

#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 5-Jan-13 7:03am
Comments
Sandeep Mewara at 5-Jan-13 13:38pm
   
Did you try by yourself? If yes, what was the result?
lida zar at 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 at 5-Jan-13 22:45pm
   
What exactly? Describe your problem in sufficient detail.
—SA

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

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...
  Permalink  

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



Advertise | Privacy | Mobile
Web03 | 2.8.140709.1 | Last Updated 10 Jan 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid