2022年安徽大学编译原理实验二消除文法左递归 .pdf

《2022年安徽大学编译原理实验二消除文法左递归 .pdf》由会员分享，可在线阅读，更多相关《2022年安徽大学编译原理实验二消除文法左递归 .pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验二：消除文法左递归实验日期： 2012.4.27 教师签字：成绩：实验名称：由正规文法构造正规式实验目的：一.掌握上下文无关文法类型的定义，及与其他类型文法的区别；二.熟悉上下文无关文法类型的判断，能够快速按照要求写出对应文法类型的文法用例；三.给出一个上下文无关文法类型，能够正确判断其是否存在左递归，若存在则消除直接、间接左递归。实验内容：运行结果：1. 消除直接左递归：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 2

2、.消除间接左递归：程序代码：/* *Copyright (c) 2012 Part of Elimination of Left Recursion *Filename killzdg.cpp *Author Yangxiangyu *Sid E10914012 *Description 2012/04/25 */ #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - #include #include #incl

3、ude #include #include #define _CLR(a) memset(a,0,sizeof(a) using namespace std; class grammar private: typedef unsigned char uchar; typedefmultimap:iterator MMAPI; typedef pair MMAPE; typedef map:iterator MAPI; typedef pairMMAPRange; private: multimap production;/key is the nonterminal mapsymbolidx;

4、 mapsymboltable; mapsymbolmark; intsymbnum; intgenint; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - void addSymbol(uchar _c) if(symbolidx_c0)return; symbnum+; symbolidx_c=symbnum; symboltablesymbnum=_c; symbolmark_c=false; uchargenSymbo

5、l() genint+; addSymbol(genint); return genint; booleliminatProduction(uchar key) bool mark=false; for(MMAPI s=production.lower_bound(key);s!=production.upper_bound(key);s+) if(s-second)0=key) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - -

6、 mark=true; break; if(!mark)return false; uchargenkey=genSymbol(); production.insert(MMAPE(genkey, );/ 空产生式Unicode字符,可能会引起错误for(MMAPI s=production.lower_bound(key);s!=production.upper_bound(key);) string tstr=s-second; if(tstr0=key) tstr.erase(tstr.begin(); tstr.insert(tstr.end(),genkey); production

7、.insert(MMAPE(genkey,tstr); production.erase(s+); else s-second.insert(s-second).end(),genkey); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - s+; return true; void addProductionPhase1(string &_tstr) void addProductionPhase2(ucharkeymulti

8、map,string&_tstr) string:iterator s,t; for(s=t=_tstr.begin();s+) if(s=_tstr.end()| *s=| ) production.insert(make_pair(keymultimap,string(t,s); if(s=_tstr.end()break; else t=s+1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - void dfsnMark

9、(char key) MMAPRange _range=production.equal_range(key); for(MMAPI i=_range.first;i!=_range.second;i+) for(int j=0;jsecond).size();j+) if(symbolidx.count(i-second)j)0 & !symbolmark(i-second)j) symbolmark(i-second)j=true; dfsnMark(key); void removeUselessProduction() symbolmarkS=true; dfsnMark(S); pu

10、blic: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - grammar() genint=127; symbnum=0; production.clear(); symboltable.clear(); symbolidx.clear(); symbolmark.clear(); boolAddProduction(string rawstr) string _tstr(rawstr.begin()+3,rawstr.en

11、d(); ucharkeymultimap=rawstr0; addSymbol(keymultimap); addProductionPhase1(_tstr); addProductionPhase2(keymultimap,_tstr); return true; void EliminatAll() for(MAPI i=symboltable.begin();i!=symboltable.end();i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13

12、页 - - - - - - - - - for(MAPI j=symboltable.begin();j!=i;j+) MMAPRange _range=production.equal_range(i-second); MMAPRange _range1=production.equal_range(j-second); for(MMAPI m=_range.first;m!=_range.second;) if(m-second)0=j-second) for(MMAPI k=_range1.first;k!=_range1.second;k+) string _str=m-second;

13、 _str.erase(_str.begin(); _str.insert(_str.begin(),(k-second).begin(),(k-second).end(); production.insert(MMAPE(i-second,_str); production.erase(m+); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - m+; eliminatProduction(i-second); re

14、moveUselessProduction(); void AnsOutput() for(MAPI i=symboltable.begin();i!=symboltable.end();i+) if(!symbolmarki-second)continue; MMAPRange _range=production.equal_range(i-second); boolmark_first=false; coutsecond; for(MMAPI m=_range.first;m!=_range.second;m+) if(mark_first) cout|; else mark_first=

15、true; coutsecond; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - coutendl; ; void ConsoleOutput(intidx) switch(idx) case 0: coutElimiation of Left Recursion (Author:Zhizhuo Data:2011-11-02)nAssume all the input are legal.n; break; case 1

16、: coutNumber of productionn; break; case 2: coutProductionn; break; case 3: coutElimiated Productionsnofp; ConsoleOutput(2); while(nofp-) cinstr; grm.AddProduction(str); grm.EliminatAll(); ConsoleOutput(3); grm.AnsOutput(); system(PAUSE); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -