#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;

}