Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.145.166.7] |
|
Сообщ.
#1
,
|
|
|
Добрый день, всем!
Помогите, пожалуйста, с заданием: Это программа для генерации регулярной грамматики. Вход программы: алфавит языка, обязательная конечная подцепочка, кратность длины всех цепочек языка, тип грамматики (ЛЛ либо ПЛ), 2 числа – диапазон длин для генерации цепочек. Выход: построенная грамматика (все 4 элемента), результат генерации цепочек. Задача: Добавить еще на вход ввод начальной подцепочки !!! StringStart Подскажите пож., как это сделать грамотно. Спасибо! #pragma hdrstop #include "Unit1.h" #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; const AnsiString Lambda="л"; AnsiString R[26][10]; int Lr[26]; AnsiString Vn, Vt, StringEnd, StringStart; int K, Min, Max; bool LL; //поиск свободной заглавной буквы латинского алфавита для нетерминального символа AnsiString __fastcall TForm1::GetVn() { for (int i=0;i<26;i++) { char v='A'+i; if (Vn.Pos(v)==0) return AnsiString(v); } ShowMessage("Не хватает заглавных символов латинского алфавита для нетерминальных символов"); return NULL; } //вычисление длин минимальных цепочек, выводимых из нетерминалов грамматики void __fastcall TForm1::GetLr() { int l=0; for (int i=0;i<26;i++) Vr[i]=-1; for (int i=0;i<26;i++) { if (Vr[i]!=-1) continue; l=0; for (int j=0;R[i][j]!="";j++) { if (R[i][j]==Lambda) { Vr[i]=0; break; } else for (int k=1;k<=R[i][j].Length();k++) { int n=Vn.Pos(R[i][j][k]); if (n==0) l++; else if (Vr[n]!=-1) l+=Vr[n]; } if ((l>=0)&&((Vr[i]<0)||(Vr[i]>l))) Vr[i]=l; } } for (int i=0;i<26;i++) if (Vr[i]==-1) Vr[i]=1; } //рекурсивная генерация цепочек языка по построенной грамматике void __fastcall TForm1::Generate(AnsiString s, AnsiString sgen, int dr) { AnsiString sl, sr; int i, k, l, n; if (dr>50) return; l=s.Length(); for (i=1;i!=l+1;i++) if ((n=Vn.Pos(s[i]))!=0) break; if (i==l+1) { if ((l>=Min)&&(l<=Max)) { if (s=="") sgen=sgen+Lambda; for (int j=0;j<ListBox3->Items->Count;j++) if (ListBox3->Items->Strings[j]==s) return; ListBox1->Items->Insert(ListBox3->Items->Add(s),sgen); } return; } k=i-1; for (int j=i;j<=l;j++) { int m=Vn.Pos(s[j]); if (m==0) k++; else k+=Vr[m]; } if (k>Max) return; sl=s.SubString(1,i-1); if (sl.Length()>Max) return; sr=s.SubString(i+1,l-i); if (sr.Length()>Max) return; for (i=0;R[n][i]!="";i++) if (R[n][i]==Lambda) Generate(sl+sr,sgen+"->"+sl+sr,dr+1); else Generate(sl+R[n][i]+sr,sgen+"->"+sl+R[n][i]+sr,dr+1); } //построение заданной грамматики bool __fastcall TForm1::Grammar() { AnsiString s, v, v0; int i, k, j, n; N8->Enabled=false; N10->Enabled=false; Vt=Edit1->Text; for (i=1;i<=Vt.Length();i++) { if (Vt[i]==Lambda[1]) { ShowMessage("В алфавите встречается символ, используемый как пустой 'л'"); return false; } for (j=i+1;j<=Vt.Length();j++) if (Vt[i]==Vt[j]) { ShowMessage("Символ алфавита встречается несколько раз"); return false; } } StringEnd=Edit2->Text; StringStart=Edit4->Text; v="S"; Vn=v; K=StrToIntDef(Edit3->Text,0); if (K<1) { ShowMessage("Ошибка в задании кратности длин цепочек"); return false; } for (i=0;i<26;i++) for (j=0;j<10;j++) R[i][j]=""; if (Vt=="") { ShowMessage("Не задан входной алфавит"); return false; } for (i=1;i<=StringEnd.Length();i++) if (Vt.Pos(StringEnd[i])==0) { ShowMessage("Посторонний символ в конечной цепочке"); return false; } ListBox2->Items->Clear(); k=StringEnd.Length()%K; if (k>0) k=K-k; n=1; if (LL) { if (StringEnd!="") { s=v+"->"; v=GetVn(); Vn=Vn+v; s=s+v+StringEnd; ListBox2->Items->Add(s); R[1][0]=v+StringEnd; n++; } v0=v; for (i=0;i<K-1;i++,n++) { s=v+"->"; v=GetVn(); Vn=Vn+v; for (j=1;j<=Vt.Length();j++) { s=s+v+Vt[j]; if (j<Vt.Length()) s=s+"|"; R[n][j-1]=v+Vt[j]; } if (k==i) { s=s+"|"+Lambda; R[n][j-1]=Lambda; } ListBox2->Items->Add(s); } s=v+"->"; for (j=1;j<=Vt.Length();j++) { R[n][j-1]=v0+Vt[j]; s=s+v0+Vt[j]; if (j<Vt.Length()) s=s+"|"; } if (k==i) { s=s+"|"+Lambda; R[n][j-1]=Lambda; } ListBox2->Items->Add(s); } else { //построение праволинейной грамматики for (i=0;i<K-1;i++,n++) { s=v+"->"; v=GetVn(); Vn=Vn+v; for (j=1;j<=Vt.Length();j++) { s=s+Vt[j]+v; R[n][j-1]=AnsiString(Vt[j])+v; if (j<Vt.Length()) s=s+"|"; } if (k==i) { s=s+"|"; if (StringEnd!="") { R[n][j-1]=StringEnd; s=s+StringEnd; } else { R[n][j-1]=Lambda; s=s+Lambda; } } ListBox2->Items->Add(s); } s=v+"->"; for (j=1;j<=Vt.Length();j++) { s=s+AnsiString(Vt[j])+"S"; if (j<Vt.Length()) s=s+"|"; R[n][j-1]=AnsiString(Vt[j])+"S"; } if (k==i) { s=s+"|"; if (StringEnd!="") { R[n][j-1]=StringEnd; s=s+StringEnd; } else { R[n][j-1]=Lambda; s=s+Lambda; } } ListBox2->Items->Add(s); } for (i=1;i<=Vt.Length();i++) if (Vn.Pos(Vt[i])>0) { ListBox2->Items->Clear(); ShowMessage("В алфавите языка встречается символ, используемый как нетерминальный символ: "+ AnsiString(Vt[i])); return false; } N8->Enabled=true; N10->Enabled=true; s="G({"; for (i=1;i<=Vn.Length();i++) { s=s+Vn[i]; if (i<Vn.Length()) s=s+","; } s=s+"},{"; for (i=1;i<=Vt.Length();i++) { s=s+Vt[i]; if (i<Vt.Length()) s=s+","; } s=s+"},P,S)"; Label1->Caption=s; return true; } __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //"Тема" void __fastcall TForm1::N3Click(TObject *Sender) { ShowMessage("Построение регулярной грамматики (леволинейной или праволинейной) по словесному описанию языка"); } //"Выход" void __fastcall TForm1::N5Click(TObject *Sender) { Application->Terminate(); } //"Автор" void __fastcall TForm1::N6Click(TObject *Sender) { ShowMessage("Автор: ."); } //"Сохранить в файл"->"Цепочки" void __fastcall TForm1::N11Click(TObject *Sender) { SaveDialog1->InitialDir=GetCurrentDir(); if (SaveDialog1->Execute()) ListBox1->Items->SaveToFile(SaveDialog1->FileName); } //"Ввести данные из файла" void __fastcall TForm1::N9Click(TObject *Sender) { OpenDialog1->InitialDir=GetCurrentDir(); if (OpenDialog1->Execute()) { ListBox1->Items->LoadFromFile(OpenDialog1->FileName); Edit1->Text=ListBox1->Items->Strings[0]; Edit2->Text=ListBox1->Items->Strings[1]; Edit3->Text=ListBox1->Items->Strings[2]; ListBox1->Items->Clear(); } } //"Расчеты"->"Построить ЛЛ-грамматику" void __fastcall TForm1::N4Click(TObject *Sender) { LL=true; Grammar(); } //"Расчеты"->"Построить ПЛ-грамматику" void __fastcall TForm1::N7Click(TObject *Sender) { LL=false; Grammar(); } //"Расчеты"->"Генерировать цепочки" void __fastcall TForm1::N8Click(TObject *Sender) { if (!Grammar()) return; Min=StrToIntDef(InputBox("Диапазон длин цепочек","Минимальная длина","1"),-1); Max=StrToIntDef(InputBox("Диапазон длин цепочек","Максимальная длина","5"),-1); if ((Min<0)||(Max<0)||(Max<Min)) { ShowMessage("Ошибка в задании диапазоны длин цепочек"); return; } ListBox1->Items->Clear(); ListBox1->Perform(LB_SETHORIZONTALEXTENT,700,0); ListBox3->Items->Clear(); ListBox3->Sorted=true; N8->Enabled=false; GetLr(); Generate("S","S",0); N8->Enabled=true; N11->Enabled=true; } |