CYK

#include "pch.h"
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cassert>
#include<iomanip>
#include<fstream>
using namespace std;

#define MAX 100
#define for(i,a,b) for(i=a;i<b; i++)

string gram[MAX][MAX];  //to store entered grammar
string grambuf[MAX];
string matrix[MAX][MAX];
string dpr[MAX];
int key;
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 break_gram(string a)    //seperates 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 (gram[j][k] != "")
		{
			if (gram[j][k] == p)
			{
				r = concat(r, gram[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 = {BA, BB, AA, BB}
{
	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;
}
//	if (matrix[0][str.length() - 1].find(start[i]) <= matrix[0][str.length() - 1].length())
inline int gen(int i, int j, char B,int end, int ukaz)
{
	cout << endl << i << ' ' << j << ' ' << B << endl;
	if (i == end) return -2;
	if (j == 0) {
		for (p, 0, ukaz) {
			if ((grambuf[p][0] == B) && (grambuf[p].length() == 2)) cout<<p<<" is parser number";
		}
	}
	else {
		int check = 0;
		int z, x, c;
		int buf;
		for (p, 0, j - 1) {
			for (z, 0, ukaz) {
				if ((grambuf[z][0] == B) &&
					((matrix[i][p].find(grambuf[z][1]) <= matrix[i][p].length())) &&
					((matrix[i + p][j - p].find(grambuf[z][2])) <= matrix[i + p][j - p].length())) {
					cout << z << " is parser number";
					cout << endl;
					cout << grambuf[z][1] << grambuf[z][2] << endl;
					cout << endl << i << ' ' << j << ' ' << B << endl << "Next step" << endl;
					gen(i, 0, grambuf[z][1], end, ukaz);
					gen(i+1 , j-1 , grambuf[z][2], end, ukaz);
					check = 1;
					break;

				}
			}
			if (check == 1) break;
		}
		return -1;
	}
}

int main()
{
	int i, pt, j, l, k;
	string a, str, r, pr, start;
	cout << "\nEnter the start Variable ";
	start='S';
	cout << "\nNumber of productions ";
	np=2;
	ifstream in("start.txt");
	for (i, 0, np)
	{
		in >> a;
		pt = a.find("->");
		gram[i][0] = a.substr(0, pt);
		if (lchomsky(gram[i][0]) == 0)
		{
			cout << "\nGrammar not in Chomsky Form";
			abort();
		}
		a = a.substr(pt + 2, a.length());
		break_gram(a);
		for (j, 0, p)
		{
			gram[i][j + 1] = dpr[j];
			if (rchomsky(dpr[j]) == 0)
			{
				cout << "\nGrammar not in Chomsky Form";
				abort();
			}
		}
	}
	string st;
	cout << "\nEnter string to be checked : ";
	str="abaab";
	for (i, 0, str.length())       //Assigns values to principal diagonal of matrix
	{
		r = "";
		st = "";
		st += str[i];
		for (j, 0, np)
		{
			k = 1;
			while (gram[j][k] != "")
			{
				if (gram[j][k] == st)
				{
					r = concat(r, gram[j][0]);
				}
				k++;
			}
		}
		matrix[i][i] = r;
	}
	int ii, kk;
	for (k, 1, str.length())       //Assigns values to upper half of the matrix
	{
		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 << endl;
	for (i, 0, str.length())   //Prints the matrix
	{
		k = 0;
		l = str.length() - i - 1;
		for (j, l, str.length())
		{
			cout << setw(5) << matrix[k++][j] << " ";
		}
		cout << endl;
	}
	int ukaz = 0;
	for (i, 0, np) {
		for (j, 1, 10) {
			if (gram[i][j] != "") {
				string buf;
				buf += gram[i][0];
				buf += gram[i][j];
				grambuf[ukaz] += buf;
				ukaz += 1;
			}
		}
	}
	cout << endl;
	for (i, 0, ukaz) {
		cout << i<<' '<<grambuf[i] << endl;
	}
	// gen(int i, int j, char B, int end, int ukaz) end - последняя строка, ее номер, указатель - понятно
	cout << endl;
	for (i, 0, start.length())
		if (matrix[0][str.length() - 1].find(start[i]) <= matrix[0][str.length() - 1].length())   //Checks if last element of first row contains a Start variable
		{
			cout << "String can be generated\n";
			int check = 0;
			int i=0;
			int j= 4;
			int k = 1;
			char B = 'S';
			cout << gen(i, j, B, str.length()-1, ukaz) << ' ';

			system("pause");
			return 0;
		}
	system("pause");
	cout << "String cannot be generated\n";
	return 0;
}