正规文法-正规式.doc
由正规文法构造正规式年级专业学号 一、实验目的要求输入：任意的正规文法。输出：相应的正规式。二、实验原理一个正那么表达式的值是正那么集，它是正那么语言的另一种表示法。不难看出，除了符号外，一个正那么表达式的含义类似于正那么文法的一个非终结符号规那么右部的含义。例如，对于<数字> := 0/1/2/9，由非终结符数字所产生的字符串集合与正那么表达式0/1/2/9所定义的字符串集合是一样的。正那么集，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。三、实验代码：#include <stdio.h>#include <string> #include <vector> #include<iostream>using namespace std;struct Rulestring left; /规那么左部,因为输入的为2型文法,string right; /规那么右部;struct RuleDatastring left;vector <string> right;class Grammarprivate:vector<Rule> grammar; /文法Rule rule; /规那么vector<string> Dleft; RuleData ruledata;public:Grammar()Grammar()void ChangeInput (string input); /输入分析void Show(); /void DataChange (int C); /存储结构转换vector<RuleData> grammardata;void Grammar:ChangeInput (string input) /扫描字符串,遇到'-'停止, /并跳两格int help1 = 0;rule.left.erase();rule.right.erase();for (int i = 0; i < int (input.size(); i+) if (inputi = '-') help1 = i; break; rule.left += inputi;if (help1 != 1) cout<<"不符合要求!" exit(0);help1 = help1 + 2;for (int j = help1; j <int ( input.size(); j+) rule.right += inputj;grammar.push_back(rule); void Grammar:DataChange (int C) int i,j;if (C = 0) /简单->复杂 int l = 0; grammardata.clear(); ruledata.left.erase(); ruledata.right.clear(); ruledata.left = grammar0.left; ruledata.right.push_back (grammar0.right); grammardata.push_back (ruledata); for (i = 1; i < int (grammar.size(); i+) /存储转换 for (j = 0; j < int (grammardata.size(); j+) if (grammari.left = grammardataj.left) grammardataj.right.push_back (grammari.right); l = 1; break; if (l = 0) ruledata.left.erase(); ruledata.right.clear(); ruledata.left = grammari.left; ruledata.right.push_back (grammari.right); grammardata.push_back (ruledata); l = 0; if (C = 1) /复杂->简单 grammar.clear(); for (i = 0; i < int (grammardata.size(); i+) rule.left.erase(); rule.right.erase(); rule.left = grammardatai.left; for (j = 0; j < int (grammardatai.right.size(); j+) rule.right = grammardatai.right.at(j); grammar.push_back (rule); void Grammar:Show()cout<<"输入的文法的正规式为:"<<endl;for (int i=0; i< int (grammar.size(); i+) cout<<grammari.left<<"="<<grammari.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的侯选式， 其中aVt,AVnstring Z1 = "|"string Z2 = "("string Z3 = ")"string Z4 = "*"string help1, help2;for (int i = 0; i < int (grammardata.size(); i+) for (int j = 0; j <int ( grammardatai.right.size(); j+) for(int k = j + 1; k < int (grammardatai.right.size(); k+) help1.erase(); help2.erase(); int cj = grammardatai.right.at(j).length() - 1; int ck = grammardatai.right.at(k).length() - 1; string Aj = grammardatai.right.at(j).substr(cj); string Ak = grammardatai.right.at(k).substr(ck); if (Aj = Ak && Aj >= "A" && Aj <= "Z") if (grammardatai.right.at(j).find (Z2) != 0) help1 = Z1 + grammardatai.right.at(k).substr(0, ck); help2 = Z2 + grammardatai.right.at(j).substr(0, cj); grammardatai.right.at(j) = help2 + help1 + Z3 + Aj; else help1 = Z1 + grammardatai.right.at(k).substr(0, ck); help2 = grammardatai.right.at(j).substr(0, cj-1); grammardatai.right.at(j) = help2 + help1 + Z3 + Aj; for(int t=k;t < int (grammardatai.right.size()-1);t+) grammardatai.right.at(t)=grammardatai.right.at(t+1); grammardatai.right.pop_back(); k-; /DataChange (1);/STEP 2/先将规那么变A->(b1|b2.)*(a1|a2|.),再用其替换掉其他规那么中的A/由下而上,逐步替换for ( i = grammardata.size() - 1; i >= 0; i-) string help; help.erase(); help1.erase(); help2.erase(); /A的右部的最后的符号为A for (int j = 0; j < int (grammardatai.right.size(); j+) int cj = grammardatai.right.at(j).length() - 1; /在A的右部集中含有最后符号为A的右部 if (grammardatai.right.at(j).find (grammardatai.left) = cj) /将A->yA 变为 A->y*,help1 = "y" + "*", if (help1.length() = 0) help1 = grammardatai.right.at(j).substr (0, cj); else help1 += Z1 + grammardatai.right.at(j).substr (0, cj); else if (help2.empty() help2 = grammardatai.right.at(j); else help2 += Z1 + grammardatai.right.at(j); if (help2.find (Z2) = string:npos && help2.find(Z3) = string:npos && help2.find (Z1) != string:npos) help2 = Z2 + help2 + Z3; grammardatai.right.clear(); if (help1.empty() = false) help = help1 + Z4; help += help2; grammardatai.right.push_back (help); help.erase(); for ( j = i - 1; j >= 0; j-) for (int k = 0; k < int (grammardataj.right.size(); k+) int ck = grammardataj.right.at(k).length() - 1; if (grammardataj.right.at(k).find (grammardatai.left) = ck) help = grammardataj.right.at(k).substr (0, ck) + grammardatai.right.at(0); grammardataj.right.at(k) = help; for ( i = 0; i < int (grammardata.size() - 1); i+) grammardata.pop_back();DataChange (1);void main()string input;GenerateGtoE gg_e;int N;cout<<"个数:"cin>>N;cout<<"请输入规那么:"<<endl; for (int i=0; i<N; i+) input.erase(); cin>>input; gg_e.ChangeInput(input);gg_e.Generating();gg_e.Show();四、实验结果对于正规文法SaA|a；A(aA|dA)|(a|d)；其正规式应为S=a(a|d)*.实验为S=a(a|d)*(a|d) |可以化为S=a(a|d)*。故实验结果正确。对于正规文法SaB；BbA|bB；Ac|cA；其正规式应为S=abb*c*c.实验为S= abb*c*c.故实验结果正确。19 / 19
