PDA

View Full Version : الگوریتم CKY



loknatesabz
شنبه 10 مرداد 1394, 11:53 صبح
سلام دوستان
کسی میدونه چطوری میشه الگوریتم CKY یا همون الگوریتم Cocke-Kasami-Younger رو نوشت؟
ممنون میشم راهنمایی کنید...

loknatesabz
یک شنبه 11 مرداد 1394, 09:16 صبح
دوستان کسی نیست منو راهنمایی کنه... من رولهامو نوشتم و ذخیره کردم فقط مشکلم توی حلقه هاست که برنامه رو سنگین کرده.
کسی پیشنهادی داره لطفا راهنمایی کنید

for (int j = 1; j < temp; j++)
{
for (int u = 0; u < (temp - j) + 1; u++)
{
for (int k = 0; k < j - 1; k++)
{
foreach (string str in rule5) //A-->BC
{
chr3 = str[1];//B
chr4 = str[2];//C
str1 = table1[u, j];
str2 = table1[u + k, j - k];
str4=Comparison(str,str1,str2);
if (str4=="ok")
{
chr7 = str[0];
table1[j, u] += chr7;
}
//else
// Console.WriteLine(chr3);

}
}
}
}
این قسمتی از کد هست وقتی دستورات توی حلقه foreach رو اجرا میکنه خیلی طول میکشه و در نوبت بعد دیگه اجرا نمیشه بعبارت دیگه فقط یه بار این دستورات اجرا میشن

loknatesabz
یک شنبه 11 مرداد 1394, 10:26 صبح
دوستان من الگورینمو نوشتم فقط میخوام بدونم چطوری میتونم مشکل حلقه هامو برطرف کنم :گریه:

hamid_hr
یک شنبه 11 مرداد 1394, 11:27 صبح
ببخشید میشه بفرمایید این دستورات چکار میکنه

chr3 = str[1];//B chr4 = str[2];//C
str1 = table1[u, j];
str2 = table1[u + k, j - k];
str4=Comparison(str,str1,str2);
if (str4=="ok")
{
chr7 = str[0];
table1[j, u] += chr7;
}
//else
// Console.WriteLine(chr3);

میخواین چکار کنین؟

ژیار رحیمی
یک شنبه 11 مرداد 1394, 11:34 صبح
الگوریتم مربوط به دست آوردن تجزیه گرامری جملات با استفاده از گرامر مستقل از متن (https://fa.wikipedia.org/wiki/%DA%AF%D8%B1%D8%A7%D9%85%D8%B1_%D9%85%D8%B3%D8%AA% D9%82%D9%84_%D8%A7%D8%B2_%D9%85%D8%AA%D9%86) است.
این کد استادارد هست

static void Main(string[] args)
{
bool Output = false; //Variable de salida del programa//
List<Production> Grammar = new List<Production>(); //Lista de producciones de la gramatica//
//Adicion de producciones a la gramatica//
Grammar.Add(new Production("S","AA"));
Grammar.Add(new Production("S","0"));
Grammar.Add(new Production("A","SS"));
Grammar.Add(new Production("A","1"));
//Fin de adicion de producciones a la gramatica//


string Word = "00001";//Palabra que se debe comprobar//
List<Production>[,] CKYMat = new List<Production>[Word.Length,Word.Length];//Matriz de resultados//

//Inicializacion de la matriz de resultados//
for (int a = 0; a < Word.Length; a++)
{
for (int b = 0; b < Word.Length; b++)
{
CKYMat[a, b] = new List<Production>();
}
}
//Fin de inicializacion de la matriz//


//Llenado de la primera fila de la matriz//
for (int h = 0; h < Word.Length; h++)
{
foreach (Production prod in Grammar)
{
if (Word[h].ToString() == prod.Produccion)
{
CKYMat[h, h].Add(prod);
}
}
}
//Fin del llenado//


int i1 = 0;//Variable estatica representando a la primera columna//
int i = 0;//Variable que recorre la matriz//
int j = 1;//Variable que recorre la matriz//
int k = 0;//Variable que toma el valor de k//
int k1 = 0;//Variable que toma el valor de k+1//
List<string> Productos = new List<string>();//Lista de producciones a ser buscadas dentro de la gramatica//
List<Production> Swaplist1 = new List<Production>();//Lista en la que se almacenan las producciones de una posicion de la matriz//
List<Production> Swaplist2 = new List<Production>();//Lista en la que se almacenan las producciones de una posicion de la matriz//
int column = Word.Length - 1;//Variable que indica la cantidad de veces que se debe trabajar en una columna//
for(int je=1;je<Word.Length;je++)//Loop sobre el numero de fila en el que se deben encontrar productos//
{
j = je;
i = i1;
for (int v=0; v<column; v++)//Loop sobre el numero de columnas que se deben recorrer en la fila actual//
{
for (int k2 = i; k2 < j; k2++)//Loop para encontrar k y tomar los generadores en las posiciones [i,k] y [k,j]
{
k = k2;
k1 = k2 + 1;
Swaplist1 = CKYMat[i, k];
Swaplist2 = CKYMat[k1, j];
if (Swaplist1.Count == 0 || Swaplist2.Count == 0)
break;
else
{
foreach (Production p1 in Swaplist1)
{
foreach (Production p2 in Swaplist2)
Productos.Add(p1.Generador + p2.Generador);
}
}
}
foreach (string str in Productos)//Loop para comprobar si las alguna Produccion en la gramatica genera los resultados encontrados por la union de los puntos encontrados por k//
{
foreach (Production prod in Grammar)
{
if (str == prod.Produccion)
{
CKYMat[i, j].Add(prod);//Si la produccion existe en la gramatica se agrega la regla que la produce a la matriz en esa posicion//
}
}
}
i++;
j++;
}
Productos.Clear();//Vaciado de la lista de producciones encontradas//
column--;//Reduccion del numero de columnas a analizar (esto genera la escalera en la matriz)//
}


foreach (Production prod in Grammar)
{
if (prod.Generador == "S"&&CKYMat[0, Word.Length - 1].Contains(prod))//Se comprueba si existe un generador S en la punta de la escalera para ver si hay que devolver true//
{
Output = true;
}
}
Console.WriteLine(Output);//Escribe true si la palabra es generada por la gramatica//
Console.Read();//Mantiene la consola abierta//
}



این الگوریتم زیاد کار نشده تو اینترنت نمونه کد زیاد در دسترس نیست .تا درک قابل مشهودی از زبان های مستقل از متن نداشته باشی درک کردن امکان پیاده سازی الگوریتم آن مشکل خواهد بود.عذر میخواهم من خودم رو پیاده سازی الگوریتم های درس زبان ماشین کار نکردم تجربه ای ندارم.الگوریتم رو اینترنت گیر آوردم ولی روند کد نویسی آن گویا ست

loknatesabz
دوشنبه 12 مرداد 1394, 07:02 صبح
بسیار ممنونم که جواب دادید...
ببخشید دیر جواب دادم... در واقع قسمت کوچکی از پایان نامه م، الگوریتم CKY هست. برای نوشتنش به مشکل برخوردم. این کد بسیار شبیه الگوریتم CKY هست . من برای پایان نامه م رفرنس های زبان اصلی زیادی رو مطالعه کردم؛ کتابهایی در مورد نظریه های زبان ماشین، پردازش زبان طبیعی، شناسایی ساختاری الگو و ... .
باز هم بی نهایت سپاسگزارم

loknatesabz
دوشنبه 12 مرداد 1394, 07:14 صبح
عذر میخوام میشه آدرس سایتی که این کد رو ازش گرفتید اینجا بذارید؟
ممنون میشم

loknatesabz
دوشنبه 12 مرداد 1394, 07:22 صبح
ببخشید میشه بفرمایید این دستورات چکار میکنه

chr3 = str[1];//B chr4 = str[2];//C
str1 = table1[u, j];
str2 = table1[u + k, j - k];
str4=Comparison(str,str1,str2);
if (str4=="ok")
{
chr7 = str[0];
table1[j, u] += chr7;
}
//else
// Console.WriteLine(chr3);

میخواین چکار کنین؟

این یه تیکه از کد منه و فقط این رو برای امتحان سه تا حلقه for نوشتم... ولی خب تا حدودی درست هست این کد داره با استفاده از مقادیر دو خانه از جدول (table1) در آرایه ای از رول ها جستجو میکنه و در صورت تشابه این دو سمت چپ ترین غیر پایانه ی مربوط به این دوخانه رو در خانه (j,u) جدول بریزه.

loknatesabz
دوشنبه 12 مرداد 1394, 08:32 صبح
عذر میخوام میشه آدرس سایتی که این کد رو ازش گرفتید اینجا بذارید؟
ممنون میشم

مرسی خودم پیداش کردم...