Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // CYK.cpp: определяет точку входа для консольного приложения.
- //
- #include "stdafx.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];
- ofstream out("out.txt");
- 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())
- void gen(int i, int j, char B, int end, int ukaz) //left parser via table
- {
- cout << endl << i << ' ' << j << ' ' << B << endl;
- if (j == 0) {
- cout << "Okimhere" << endl;
- for (p, 0, ukaz) {
- if ((grambuf[p][0] == B) && (grambuf[p].length() == 2)) {
- cout << p << " is parser number"; out << p;
- }
- }
- }
- else {
- int check = 0;
- int z, x, c;
- int buf;
- for (p, 0, 10) {
- cout << endl << "P is " << p << endl;
- for (z, 0, ukaz) {
- int k;
- if (p == 0) k = 1;
- else k = p;
- if ((grambuf[z][p] == B) && ((matrix[i][p].find(grambuf[z][1]) <= matrix[i][p].length())) && ((matrix[i + k][j - k].find(grambuf[z][2])) <= matrix[i + k][j - k].length())) {
- cout << z << " is parser number";
- out << z;
- cout << endl;
- cout << endl << i << ' ' << j << ' ' << B << endl << "Next step" << endl;
- gen(i, p, grambuf[z][1], end, ukaz);
- gen(i + k, j - k, grambuf[z][2], end, ukaz);
- check = 1;
- break;
- }
- }
- if (check == 1) break;
- }
- }
- }
- int main()
- {
- int i, pt, j, l, k;
- ifstream in("start.txt");
- string a, str, r, pr, start;
- cout << "\nEnter the start Variable ";
- in>>start;
- cout << "\nNumber of productions ";
- in>>np;
- cout << endl << "Out must be = 053245152" << endl;
- 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 : ";
- in>>str;
- 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 f;
- for (i, 0, 10) { //исправляем пирамидчатое заполнение
- for (j, 0, 10) if ((matrix[i][j] == ""))
- {
- for (f, 1, 11) if (matrix[i][j + f] != "") {
- matrix[i][j] = matrix[i][j + f];
- matrix[i][j + f] = "";
- break;
- }
- }
- }
- /*for (i, 0, 10) { //вывод с кодами
- for (j, 0, 10) if(matrix[i][j]!="") cout << "i="<<i << setw(1)<<j << setw(1)<<matrix[i][j] << setw(5);
- 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';
- gen(i, j, B, str.length() - 1, ukaz);
- system("pause");
- return 0;
- }
- system("pause");
- cout << "String cannot be generated\n";
- return 0;
- }
Add Comment
Please, Sign In to add comment