LR0算法设计及实现.docx
《LR0算法设计及实现.docx》由会员分享，可在线阅读，更多相关《LR0算法设计及实现.docx（47页珍藏版）》请在冰点文库上搜索。
LR0算法设计及实现
数据结构设计
1、设计数据结构FormulaType，用于存储产生式：
typedefstruct
{
charleft;//产生式左部
charright[10];//产生式右部
intrightnum;//产生式右部字符数
}FormulaType;
2、设计数据结构GrammerType,用于存储文法
typedefstruct
{
FormulaTypeformula[20];//存储文法中的产生式
intformulanum;//存储文法中的产生式个数
charvt[10];//存储文法中的终结符
charvn[10];//存储文法中的非终结符
intvtnum;//存储文法中的终结符个数
intvnnum;//存储文法中的非终结符个数
charstartv;//存储文法的开始符号
}GrammerType;//文法存储结构
3、设计数据结构ItemType,用于项目
typedefstruct
{
intfno;//产生式编号
intpoint;//圆点位置
}ItemType;//项目结构
4、设计数据结构ItemType,用于存储项目集
typedefstruct
{
intitemsetno;//项目集编号
intitemnum;//项目集中的项目数
ItemTypeitem[10];//项目集中的项目
}ItemSetType;//项目集存储结构
5、设计数据结构ItemSetsType,用于存储项目集族
typedefstruct
{
ItemSetType*set[20];//项目集指针
intitemsetnum;//项目集数
}ItemSetsType;//项目集簇
6、设计数据结构ActionType,用于存储分析表中的动作类型及状态
typedefstruct
{
charact;//动作
intstate;//状态
}ActionType;//ACTION表结构
7、设计数据结构LRlistType，用于存储分析表
typedefstruct
{
ActionTypeactiontable[20][10];//存储分析表中的actiontable表
intgototable[20][10];//存储分析表中的gototable表
}LRlistType;//分析表
8、设计数据结构stacktype,用于存储分析栈的类型
typedefstructStackType//分析表中，栈的类型
{
intstate;//存储状态
charch;//存储字符
}stacktype;
9、设计数据结构stack,用于定义分析栈
typedefstructStack//用来定义栈
{
stacktypestackarry[maxsize];
inttop;
}stack;
代码实现
#include
#include
#definemaxsize50
/*****************************************************/
//
//存储结构
/***************************************************/
typedefstruct
{
charleft;//产生式左部
charright[10];//产生式右部
intrightnum;//产生式右部字符数
}FormulaType;
typedefstruct
{
FormulaTypeformula[20];
intformulanum;
charvt[10];
charvn[10];
intvtnum;
intvnnum;
charstartv;
}GrammerType;//文法存储结构
typedefstruct
{
intfno;//产生式编号
intpoint;//圆点位置
}ItemType;//项目结构
typedefstruct
{
intitemsetno;//项目集编号
intitemnum;//项目集中的项目数
ItemTypeitem[10];//项目集中的项目
}ItemSetType;//项目集存储结构
typedefstruct
{
ItemSetType*set[20];//项目集指针
intitemsetnum;//项目集数
}ItemSetsType;//项目集簇
typedefstruct
{
charact;//动作
intstate;//状态
}ActionType;//ACTION表结构
typedefstruct
{
ActionTypeactiontable[20][10];
intgototable[20][10];
}LRlistType;//分析表
typedefstructStackType//分析表中，栈的类型
{
intstate;
charch;
}stacktype;
typedefstructStack//用来定义栈
{
stacktypestackarry[maxsize];
inttop;
}stack;
typedefstructwords
{
charword[10];
charch;
}Dword;
/*****************************************************/
//
//函数声明
/***************************************************/
voidinitgrammer（）;//初始化文法
voidinitformula（）;//产生式初始化
voidreadvt（）;//读产生式的终结符
voidreadvn（）;//读产生式的非终结符
voidreadgrammer（）;//读入产生式
voidreadformular（charformular[]）;//读入产生式
voiddispose（charformular[]）;//处理输入的产生式
voidprintgrammer（）;//输出文法G，检测文法处理格式是否正确
voidinitsets（ItemSetsType*Cp）;//初始化项目集族
ItemSetType*closure（ItemSetType*I）;//求项目集I的闭包
ItemSetType*allotmem（ItemSetType*I）;//为项目集I分配内存空间
intindex_vt（charch）;//判断ch是否是终结符，如果是则返回终结符在vt[]中的位置，如果不是则返回-1
intindex_vn（charch）;//判断ch是否是非终结符，如果是则返回非终结符在vn[]中的位置，如果不是则返回-1
intisbelongitem（ItemSetType*I,intj）;//判断第j可产生式，圆点位置为0的项目是否在项目集I中
voidprintitemset（ItemSetType*I）;//打印生成后的项目集
intindexitemset（ItemSetType*Ip）;//判断项目集是否属项目集族C,如果IP输入C则返回Ip在C中的编号，否则返回-1
boolisbelong（ItemSetType*I,ItemTypep）;//判断项目P是否在项目集I中，如果在返回1，否则返回0
intselect（charinput[],inti）;//选出第i个项目集面临的输入符号，放入input[]中，并返回input[]中的字符
boolisbelonginput（charinput[],charch）;//判断字符ch是否在字符数组input[]中，如果在则返回1，否则返回0
ItemSetType*go（ItemSetType*I,charch,ItemSetType*IP）;//项目集I面临输入字符ch时，产生式的闭包集放入IP中
voiditemsets（）;//建立分析表
voidprintitemset（ItemSetType*I）;//打印生成后的项目集
voidinitRlist（）;//初始化分析
voidprintRlist（）;//打印分析表表
voidreadstring（charstr[]）;//输入要判断的句子
voidinitstring（charstr[],intnum）;//初始化要输入的字符串
voidinitstack（stack&st）;//初始化栈
intisEmpty（stackst）;//判断栈是否为空,空时返回1，否则返回0
intpush（stack&st,intstate,charch）;//把状态为state,字符为ch压入栈st中
intpop（stack&st）;//出栈操作
intgettop（stackst）;//得到栈顶状态元素
voidinitanlayse（）;//初始化分析栈
voidcontrol（chartemp[]）;//分析输入的是否正确
voidprintstack（stackst,charstr[],intposition）;
voiddefaultinput（）;//此时用默认的文法
voidenterinput（）;//此时要输入文法才能判
voidread（）;
voidinitDword（）;
char*dispose2（char*input）;
voidjudgesentence（）;
intjudge（charch1[],charch2[]）;
voiddefaultgrammer（）;
/*****************************************************/
//
//全局变量
/***************************************************/
GrammerTypeG;//定义全局变量文法G
ItemSetsTypeC;//定义全局变量项目集族C
LRlistTypeL;//定义全局变量分析表L
stackstackexample;//定义全局变量，分析栈
DwordW[4];
chartemp[10]={'\0'};
charsentence[100]={'\0'};
/*****************************************************/
//
//文法的输入及处理
/***************************************************/
voidinitgrammer（）//初始化文法
{
G.formula[0].left='$';
G.formulanum=0;
G.startv='$';
G.vnnum=0;
G.vtnum=0;
for（inti=0;i<10;i++）
{
G.vn[i]='\0';
G.vt[i]='\0';
}
initformula（）;//对产生式结构进行初始化
}
voidinitformula（）//产生式初始化
{
intj=1;
for（inti=0;i<20;i++）//对产生式进行遍历
{
G.formula[i].rightnum=0;//对产生式右部个数进行初始化
G.formula[j].left='\0';//对产生式左部进行初始化
j++;
for（intk=0;k<10;k++）//对产生式右部进行初始化
{
G.formula[i].right[k]='\0';
}
}
}
voidreadvt（）//读产生式的终结符
{
charch;
inti=0;
G.vtnum=0;
printf（"pleaseinputgrammer\'svt:
"）;
ch=getchar（）;
while（'#'!
=ch）
{
if（ch>='a'&&ch<='z'）
{
G.vt[i]=ch;
i++;
G.vtnum++;
}
ch=getchar（）;
}
G.vt[i]='#';//以#号为输入字符串的结束符
G.vtnum++;
setbuf（stdin,NULL）;
}
voidreadvn（）//读产生式的非终结符
{
charch;
inti=0;
G.vnnum=0;
printf（"pleaseinputgrammer\'svn:
"）;
ch=getchar（）;
while（'#'!
=ch）
{
if（ch>='A'&&ch<='Z'）
{
G.vn[i]=ch;
i++;
G.vnnum++;
}
ch=getchar（）;
}
setbuf（stdin,NULL）;
/*printf（"vn\'snumberis:
%d\n",G.vnnum）;
for（i=0;iputchar（G.vn[i]）;
printf（"\n"）;*/
}
voidreadgrammer（）//读入文法
{
charch='\0';
intformularnumber;
printf（"pleaseintputthegrammer\'snumber:
"）;
scanf（"%d",&formularnumber）;//读入要输入的产生式个数，放入文法G.formularnum中
for（inti=0;i{
charformular[20]={'\0'};//缓存清空
printf（"pleaseinputthe%dformular:
",i+1）;
readformular（formular）;
dispose（formular）;
}
}
voidreadformular（charformular[]）//读入产生式
{
charch;
inti=0;
ch=getchar（）;
while（'#'!
=ch）
{
if（（ch>='a'&&ch<='z'）||（ch>='A'&&ch<='Z'）||（ch=='-'）||（ch=='>'）||（ch=='|'））//判断读入的符号是否合法
{
formular[i]=ch;
i++;
}
ch=getchar（）;
}
}
voiddispose（charformular[]）//处理读入放入formular[]内的产生式
{
if（G.formulanum==0）//如果输入的是第一个产生式，则做特殊处理
{
G.formula[0].right[0]=formular[0];
G.formula[0].rightnum=1;
G.formulanum++;
}
inti=3;
while（'\0'!
=formular[i]）
{
G.formula[G.formulanum].left=formular[0];
intj=0;
while（'|'!
=formular[i]&&'\0'!
=formular[i]）
{
G.formula[G.formulanum].right[j]=formular[i];
i++;
j++;
}
G.formula[G.formulanum].rightnum=j;//产生式右边的个数
printf（"\n"）;
G.formulanum++;
if（'\0'!
=formular[i]）
i++;
}
/*intm=0;
printf（"thegrammer\'snumberis:
%d\n",G.formulanum）;
for（m=0;m{
printf（"thegrammer\'s%dformularis:
",m）;
printf（"产生式右部符号个数是:
%d",G.formula[m].rightnum）;
printf（"\n%c->",G.formula[m].left）;//输出产生式的左部符号
intk=0;
for（k=0;kprintf（"%c",G.formula[m].right[k]）;
printf（"\n"）;
}*/
}
voidprintgrammer（）//输出文法G，检测文法处理格式是否正确
{
printf（"thegrammer\'sstartvis:
%c\n",G.startv）;
printf（"thegrammer\'svnis:
"）;
for（inti=0;iprintf（"%3c",G.vn[i]）;
printf（"\n"）;
printf（"thegrammer\'svtis:
"）;
for（i=0;iprintf（"%3c",G.vt[i]）;
printf（"\n"）;
intj=0;
printf（"thegrammer\'snumberis:
%d\n",G.formulanum）;
for（j=0;j{
printf（"thegrammer\'s%dformularis:
",j）;
printf（"%c->",G.formula[j].left）;//输出产生式的左部符号
intk=0;
for（k=0;kprintf（"%c",G.formula[j].right[k]）;
printf（"右部有%d个符号",G.formula[j].rightnum）;
printf（"\n"）;
}
}
/*****************************************************/
//
//分析表的生成
/***************************************************/
intindex_vn（charch）//判断ch是否是非终结符，如果是则返回非终结符在vn[]中的位置，如果不是则返回-1
{
inti=0;
while（'\0'!
=G.vn[i]&&G.vn[i]!
=ch）
{
i++;
}
if（i==G.vnnum）
return-1;
else
returni;
}
intindex_vt（charch）//判断ch是否是终结符，如果是则返回终结符在vt[]中的位置，如果不是则返回-1
{
inti=0;
while（'\0'!
=G.vt[i]&&G.vt[i]!
=ch）
{
i++;
}
if（i==G.vtnum）
return-1;
else
returni;
}
ItemSetType*allotmen（ItemSetType*I）//为项目集I分配内存空间
{
I=（ItemSetType*）malloc（sizeof（ItemSetType））;
I->itemsetno=-1;
I->itemnum=0;
for（intj=0;j<10;j++）
{
I->item[j].fno=-1;
I->item[j].point=-1;
}
returnI;
}
voidinitsets（）//初始化项目集族
{
C.set[0]=allotmen（C.set[0]）;
C.set[0]->itemsetno=0;
C.set[0]->item[0].fno=0;
C.set[0]->item[0].point=0;
C.set[0]->itemnum=1;
C.set[0]=closure（C.set[0]）;
C.itemsetnum=1;
}
ItemSetType*closure（ItemSetType*I）//求项目集I的闭包
{
intf;//存放产生式编号
intp;//存放圆点位置
intx;//指向下一个空的项目
//printf（"closure函数内\n"）;
//system（"pause"）;
for（inti=0;iitemnum;i++）
{
f=I->item[i].fno;
p=I->item[i].point;
x=I->itemnum-1;
if（index_vn（G.formula[f].right[p]）!
=-1）
{
for（intj=0;j{
if（（G.formula[f].right[p]==G.formula[j].left）&&!
isbelongitem（I,j））
{
x++;
I->item[x].fno=j;
I->item[x].point=0;
I->itemnum++;
}//endif
}//endfor
}//endif
}//endfor
//printitemset（I）;
returnI;
}//endfuction
intisbelongitem（ItemSetType*I,intj）//判断第j个产生式，圆点位置为0的项目是否在项目集I中
{
inti=0;
while（iitemnum）
{
if（I->item[i].fno==j&&I->item[i].point==0）
break;
else
i++;
}
if（i==I->itemnum）
return0;//不在项目集I中
else
return1;//在项目集中I中
}
voidprintitemset（ItemSetType*I）//打印生成后的项目集
{
printf（"theitemset\'sorderis:
%d
升级会员 