2022年正规文法-正规式收集 .pdf

《2022年正规文法-正规式收集 .pdf》由会员分享，可在线阅读，更多相关《2022年正规文法-正规式收集 .pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、由正规文法构造正规式年级专业学号姓名名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - 一、实验目的要求输入：任意的正规文法。输出：相应的正规式。二、实验原理一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于 := 0/1/2/ /9，由非终 结 符 数 字 所 产 生 的 字 符 串 集 合 与 正 则 表 达 式0/1/2/

2、9 所定义的字符串集合是相同的。正则集，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。三、实验代码：#include #include #include #include using namespace std; struct Rule 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - - string left; /规则左部 ,因为输入的为 2 型文法, string right; /规则右部; struct

3、 RuleData string left; vector right; ; class Grammar private: vector grammar; /文法Rule rule; /规则vector Dleft; RuleData ruledata; public: Grammar() Grammar() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - void ChangeInput (string input); /输

4、入分析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; 名师资料总结 - - -精品资料欢迎

5、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - if (help1 != 1) cout不符合要求 !; exit(0); help1 = help1 + 2; for (int j = help1; j 复杂 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - int l = 0; grammar

6、data.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

7、.erase(); rule.right.erase(); rule.left = grammardatai.left; for (j = 0; j int (grammardatai.right.size(); j+) rule.right = grammardatai.right.at(j); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - grammar.push_back (rule); void Grammar:Sh

8、ow() cout输入的文法的正规式为 :endl; for (int i=0; i int (grammar.size(); i+) coutgrammari.left=grammari.rightendl; class GenerateGtoE: public Grammar / 正规文法转正规式 private: public: GenerateGtoE() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - - - - Generat

9、eGtoE() void Generating (); ; void GenerateGtoE:Generating () DataChange (0); /STEP 1 /将文法 G 的所有非终结符形如a1A|a2A|.的候选式/归并为 (a1|a2|.)A 的侯选式，其中 aVt,A Vn string 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 (

10、grammardatai.right.size(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - 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.r

11、ight.at(j).substr(0, cj); grammardatai.right.at(j) = help2 + help1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - + Z3 + Aj; else help1 = Z1 + grammardatai.right.at(k).substr(0, ck); help2 = grammardatai.right.at(j).substr(0, cj-1); gram

12、mardatai.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 =

13、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

14、) help2 = Z2 + help2 + Z3; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - 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;

15、 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; 名师资料总结 - - -精品资料欢迎下载 - -

16、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - 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(input); 名师资

17、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - 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)* 。故实验结果正确。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

18、- - - - - - 第 16 页，共 18 页 - - - - - - - - - 对于正规文法SaB；BbA|bB ；Ac|cA ；其正规式应为S=abb*c*c. 实验为S= abb*c*c. 故实验结果正确。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -