安徽大学编译原理实验二消除文法左递归.docx
- 文档编号:4645694
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:10
- 大小:74.12KB
安徽大学编译原理实验二消除文法左递归.docx
《安徽大学编译原理实验二消除文法左递归.docx》由会员分享,可在线阅读,更多相关《安徽大学编译原理实验二消除文法左递归.docx(10页珍藏版)》请在冰点文库上搜索。
安徽大学编译原理实验二消除文法左递归
实验二:
消除文法左递归
实验日期:
2012.4.27教师签字:
成绩:
实验名称:
由正规文法构造正规式
实验目的:
一.掌握上下文无关文法类型的定义,及与其他类型文法的区别;
二.熟悉上下文无关文法类型的判断,能够快速按照要求写出对应文法类型的文法用例;
三.给出一个上下文无关文法类型,能够正确判断其是否存在左递归,若存在则消除直接、间接左递归。
实验内容:
运行结果:
1.消除直接左递归:
2.消除间接左递归:
程序代码:
/*
*Copyright(c)2012PartofEliminationofLeftRecursion
*Filenamekillzdg.cpp
*AuthorYangxiangyu
*SidE10914012
*Description2012/04/25
*/
#include
#include
#include
#include
#include
#include
#define_CLR(a)memset(a,0,sizeof(a))
usingnamespacestd;
classgrammar
{
private:
typedefunsignedcharuchar;
typedefmultimap
:
iteratorMMAPI;
typedefpair
typedefmap
:
iteratorMAPI;
typedefpair
private:
multimap
map
map
map
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字符,可能会引起错误
for(MMAPIs=production.lower_bound(key);s!
=production.upper_bound(key);)
{
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&_tstr)
{
string:
:
iterators,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;
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('S');
}
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);
returntrue;
}
voidEliminatAll()
{
for(MAPIi=symboltable.begin();i!
=symboltable.end();i++)
{
for(MAPIj=symboltable.begin();j!
=i;j++)
{
MMAPRange_range=production.equal_range(i->second);
MMAPRange_range1=production.equal_range(j->second);
for(MMAPIm=_range.first;m!
=_range.second;)
{
if((m->second)[0]==j->second)
{
for(MMAPIk=_range1.first;k!
=_range1.second;k++)
{
string_str=m->second;
_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->second);
}
removeUselessProduction();
}
voidAnsOutput()
{
for(MAPIi=symboltable.begin();i!
=symboltable.end();i++)
{
if(!
symbolmark[i->second])continue;
MMAPRange_range=production.equal_range(i->second);
boolmark_first=false;
cout<
for(MMAPIm=_range.first;m!
=_range.second;m++)
{
if(mark_first)cout<<"|";
elsemark_first=true;
cout<
}
cout< } } }; voidConsoleOutput(intidx) { switch(idx) { case0: cout<<"ElimiationofLeftRecursion(Author: ZhizhuoData: 2011-11-02)\nAssumealltheinputarelegal.\n"; break; case1: cout<<"[Numberofproduction]\n"; break; case2: cout<<"[Production]\n"; break; case3: cout<<"[ElimiatedProductions]"< break; } } 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文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 安徽大学 编译 原理 实验 消除 文法 递归