正规文法-正规式.doc

由正规文法构造正规式年级专业学号 姓名一、实验目的要求输入：任意的正规文法。输出：相应的正规式。二、实验原理一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于 := 0/1/2/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/9所定义的字符串集合是相同的。正则集，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。三、实验代码：#include #include #include #includeusing namespace std;struct Rulestring left; /规则左部,因为输入的为2型文法,string right; /规则右部;struct RuleDatastring left;vector right;class Grammarprivate:vector grammar; /文法Rule rule; /规则vector Dleft; RuleData ruledata;public:Grammar()Grammar()void ChangeInput (string input); /输入分析void Show(); /void DataChange (int C); /存储结构转换vector 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 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 简单 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+) coutgrammari.left=grammari.rightendl;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 = 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 (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 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;coutN;cout请输入规则:endl; for (int i=0; iinput; gg_e.ChangeInput(inpu