安徽大学编译原理实验二消除文法左递归文档格式.docx
- 文档编号:6811229
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:10
- 大小:74.12KB
安徽大学编译原理实验二消除文法左递归文档格式.docx
《安徽大学编译原理实验二消除文法左递归文档格式.docx》由会员分享,可在线阅读,更多相关《安徽大学编译原理实验二消除文法左递归文档格式.docx(10页珍藏版)》请在冰点文库上搜索。
#include<
iostream>
cstdio>
map>
string>
vector>
algorithm>
#define_CLR(a)memset(a,0,sizeof(a))
usingnamespacestd;
classgrammar
{
private:
typedefunsignedcharuchar;
typedefmultimap<
uchar,string>
:
iteratorMMAPI;
typedefpair<
int,string>
MMAPE;
typedefmap<
int,uchar>
iteratorMAPI;
MMAPI,MMAPI>
MMAPRange;
multimap<
production;
//keyisthenonterminal
map<
uchar,int>
symbolidx;
symboltable;
uchar,bool>
symbolmark;
intsymbnum;
intgenint;
voidaddSymbol(uchar_c)
{
if(symbolidx[_c]>
0)return;
symbnum++;
symbolidx[_c]=symbnum;
symboltable[symbnum]=_c;
symbolmark[_c]=false;
}
uchargenSymbol()
genint++;
addSymbol(genint);
returngenint;
booleliminatProduction(ucharkey)
boolmark=false;
for(MMAPIs=production.lower_bound(key);
s!
=production.upper_bound(key);
s++)
{
if((s->
second)[0]==key)
{
mark=true;
break;
}
}
if(!
mark)returnfalse;
uchargenkey=genSymbol();
production.insert(MMAPE(genkey,"
ε"
));
//空产生式Unicode字符,可能会引起错误
)
stringtstr=s->
second;
if(tstr[0]==key)
tstr.erase(tstr.begin());
tstr.insert(tstr.end(),genkey);
production.insert(MMAPE(genkey,tstr));
production.erase(s++);
else
s->
second.insert((s->
second).end(),genkey);
s++;
returntrue;
voidaddProductionPhase1(string&
_tstr)
voidaddProductionPhase2(ucharkeymultimap,string&
string:
iterators,t;
for(s=t=_tstr.begin();
;
if(s==_tstr.end()||*s=='
|'
)
production.insert(make_pair(keymultimap,string(t,s)));
if(s==_tstr.end())break;
elset=s+1;
voiddfsnMark(charkey)
MMAPRange_range=production.equal_range(key);
for(MMAPIi=_range.first;
i!
=_range.second;
i++)
for(intj=0;
j<
(i->
second).size();
j++)
if(symbolidx.count((i->
second)[j])>
0&
&
!
symbolmark[(i->
second)[j]])
{
symbolmark[(i->
second)[j]]=true;
dfsnMark(key);
}
voidremoveUselessProduction()
symbolmark['
S'
]=true;
dfsnMark('
);
public:
grammar()
genint=127;
symbnum=0;
production.clear();
symboltable.clear();
symbolidx.clear();
symbolmark.clear();
boolAddProduction(stringrawstr)
string_tstr(rawstr.begin()+3,rawstr.end());
ucharkeymultimap=rawstr[0];
addSymbol(keymultimap);
addProductionPhase1(_tstr);
addProductionPhase2(keymultimap,_tstr);
voidEliminatAll()
for(MAPIi=symboltable.begin();
=symboltable.end();
{
for(MAPIj=symboltable.begin();
j!
=i;
MMAPRange_range=production.equal_range(i->
second);
MMAPRange_range1=production.equal_range(j->
for(MMAPIm=_range.first;
m!
if((m->
second)[0]==j->
second)
{
for(MMAPIk=_range1.first;
k!
=_range1.second;
k++)
{
string_str=m->
_str.erase(_str.begin());
_str.insert(_str.begin(),(k->
second).begin(),(k->
second).end());
production.insert(MMAPE(i->
second,_str));
}
production.erase(m++);
}
else
m++;
eliminatProduction(i->
removeUselessProduction();
voidAnsOutput()
if(!
symbolmark[i->
second])continue;
MMAPRange_range=production.equal_range(i->
boolmark_first=false;
cout<
<
i->
second<
"
->
for(MMAPIm=_range.first;
m++)
if(mark_first)cout<
|"
elsemark_first=true;
cout<
m->
endl;
};
voidConsoleOutput(intidx)
switch(idx)
case0:
cout<
ElimiationofLeftRecursion(Author:
ZhizhuoData:
2011-11-02)\nAssumealltheinputarelegal.\n"
break;
case1:
[Numberofproduction]\n"
case2:
[Production]\n"
case3:
[ElimiatedProductions]"
}
intmain()
ConsoleOutput(0);
grammargrm;
stringstr;
intnofp;
ConsoleOutput
(1);
cin>
>
nofp;
ConsoleOutput
(2);
while(nofp--)
cin>
str;
grm.AddProduction(str);
grm.EliminatAll();
ConsoleOutput(3);
grm.AnsOutput();
system("
PAUSE"
return0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 安徽大学 编译 原理 实验 消除 文法 递归
![提示](https://static.bingdoc.com/images/bang_tan.gif)