#pragma hdrstop
#include "Unit1.h"
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;

const AnsiString Lambda="л";

AnsiString R[26][10];
int Vr[26];
AnsiString Vn, Vt, StringEnd;
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;
 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;
}

//"Сохранить в файл"->"Грамматику"
void __fastcall TForm1::N10Click(TObject *Sender)
{
 SaveDialog1->InitialDir=GetCurrentDir();
 if (SaveDialog1->Execute()) {
  ListBox2->Items->Add(Label1->Caption);
  ListBox2->Items->SaveToFile(SaveDialog1->FileName);
  ListBox2->Items->Delete(0);
 }
}

