正规文法-正规式.doc

正规文法-正规式
{
string left; //规则左部,因为输入的为2型文法,
string right; //规则右部
};
struct RuleData
{
string= 0; j < int (grammardata[i].()); j++)
{
= grammardata[i].(j);
(rule);
}
}
}
}
void Grammar::Show()
{
cout<<"输入的文法的正规式为:"<<endl;
for (int i=0; i< int (()); i++)
cout<<grammar[i].left<<"="<<grammar[i].right<<endl;
}
class GenerateGtoE: public Grammar //正规文法转正规式
{
private:
public:
GenerateGtoE(){}
~GenerateGtoE(){}
void Generating ();
};
void GenerateGtoE::Generating ()
{
DataChange (0);
//STEP 1
//将文法G的所有非终结符形如a1A|a2A|...的候选式
//归并为(a1|a2|...)A的侯选式， 其中a∈Vt,A∈Vn
string Z1 = "|";
string Z2 = "(";
string Z3 = ")";
string Z4 = "*";
string help1, help2;
for (int i = 0; i < int (()); i++)
for (int j = 0; j <int ( grammardata[i].()); j++)
for(int k = j + 1; k < int (grammardata[i].()); k++)
{
();
();
int cj = grammardata[i].(j).length() - 1;
int ck = grammardata[i].(k).length() - 1;
string Aj = grammardata[i].(j).substr(cj);
string Ak = grammardata[i].(k).substr(ck);
if (Aj == Ak && Aj >= "A" && Aj <= "Z")
{
if (grammardata[i].(j).find (Z2) != 0)
{
help1 = Z1 + grammardata[i].(k).substr(0, ck);
help2 = Z2 + grammardata[i].(j).substr(0, cj);
grammardata[i].(j) = help2 + help1 + Z3 + Aj;
}
else
{
help1 = Z1 + grammardata[i].(k).substr(0, ck);
help2 = grammardata[i].(j).substr(0, cj-1);
grammardata[i].(j) = help2 + help1 + Z3 + Aj;
}

for(int t=k;t < int (grammardata[i].()-1);t++)
{
grammardata[i].(t)=grammardata[i].(t+1);
}
grammardata[i].();