www.pudn.com > 编译原理LALR(1)文法分析器.zip > GRAMA.cpp
#include
#include
#include
#include "GRAMA.h"
CGRAMA::CGRAMA():start_symbol(-5) //构造函数
{
char *buf,ch;
List buflist;
int i=0;
ifstream fin("grama.txt",ios::nocreate); //打开文件
if(!fin){
cout<<"file not found!\n";
exit(0);
}
fin>>vnnum>>vtnum>>gncount;
vnstring=new char[vnnum];
vtstring=new char[vtnum];
vn=new int[vnnum];
vt=new int[vtnum];
for(i=0;i>vnstring[i];
vn[i]=-10-5*i;
}
for(i=0;i>vtstring[i];
vt[i]=10+5*i;
}
Gener first_gener; //对文法进行拓广
first_gener.vn=start_symbol; //-5是文法开始符号
first_gener.sentence=new int[2];
first_gener.sentence[0]=vn[0];
first_gener.sentence[1]=END;
gn_list.Insert(first_gener);
fin.get(ch);
for(i=0;i temp_list;
gener.vn=EncodeVn(*pS); //产生式左部的编码
pS=pS+3; //跳过"->"
int length=::GetStrLen(buf)-3; //length为产生式右部的最大长度
gener.sentence=new int[length+1]; //堆内存分配
for(int i=0;i *p=temp_list.first;p;p=p->link)
{
length=p->data.GetRightLength();
flag=0;
for(i=0;idata.sentence[i]==-1)
{
flag=1;
break;
}
}
g1.vn=p->data.vn;
if(flag==1) g1.sentence=new int[i+1];
else g1.sentence=new int[length];
for(int j=0;jdata.sentence[j];
g1.sentence[i]=END;
gn_list.Insert(g1);
if(flag==1){
g2.vn=p->data.vn;
g2.sentence=new int[length-i];
for(j=0;jdata.sentence[j+i+1];
g2.sentence[length-i-1]=END;
temp_list.Insert(g2);
}
}
}
int CGRAMA::EncodeVn(char ch) //查找非终结符号表
{
for(int i=0;i *p=gn_list.first;p;p=p->link)
{
gener_len=p->data.GetRightLength();
p->data.GenToItem(item_list,gener_len);
}
}
void CGRAMA::Closure(List &kernel) //CLOSURE(I)函数
{
Queue queue,item_q;
ListNode *p,*q;
CItem item,mid_item;
int code,pos;
List f_set;
for(p=kernel.first;p;p=p->link)
{
if(p->data.vn==-5)
{
p->data.string.MakeEmpty();
p->data.string.Insert(5);
}
queue.QInsert(p->data);
item_q.QInsert(p->data);
}
kernel.MakeEmpty();
while(!queue.QueueEmpty())
{
item.string.MakeEmpty();
item=queue.QDelete();
if(item.IsForReduce())
{
pos=item.GetDotPos();
f_set.MakeEmpty();
FirstX(item.sentence+pos+2,f_set);
for(q=item_list.first;q;q=q->link)
{
if(q->data.vn==item.sentence[pos+1]&&q->data.sentence[0]==1)
{
mid_item=q->data;
if(f_set.IsEmpty()) mid_item.string.Add(item.string);
else mid_item.string.Add(f_set);
item.string.MakeEmpty();
code=item_q.GetCode(mid_item);
if(code==0){
queue.QInsert(mid_item);
item_q.QInsert(mid_item);
}
else if(!(mid_item.string==item_q.queue[code].string))
item_q.queue[code].Merge(mid_item);
}
}//end for
}//end if
}
for(int i=1;i<=item_q.rear;i++) kernel.Insert(item_q.queue[i]);
}
void CGRAMA::FromItoJ(CItem &item,List &J) //由A->a.Br找出
{ //形如A->aB.r的式子
int pos=item.GetDotPos();
int temp=item.sentence[pos+1];
for(ListNode *p=item_list.first;p;p=p->link)
{
if(p->data.vn==item.vn)
{
int pos1=p->data.GetDotPos();
if(p->data.sentence[pos1-1]==temp&&pos1-pos==1){
if(!p->data.string.IsEmpty())
p->data.string.MakeEmpty();
p->data.string.Add(item.string);
J.Insert(p->data);
}
}
}
}
int CGRAMA::GO(const List &I,int X,List &J) //GO(I,X)函数
{
int pos;
for(ListNode *p=I.first;p;p=p->link)
{
pos=p->data.GetDotPos();
if(p->data.sentence[pos+1]==X)
FromItoJ(p->data,J);
}
Closure(J);
if(J.IsEmpty()) return 0;
return 1;
}
void CGRAMA::GetSymbol(List &item_set,List &symbol_list)
{
int pos,temp;
symbol_list.MakeEmpty();
for(ListNode *q=item_set.first;q;q=q->link)
{
pos=q->data.GetDotPos();
temp=q->data.sentence[pos+1];
if(temp!=END) symbol_list.Insert(temp);
}
symbol_list.DelRepeated(); //必须放到For的外面!
}
void CGRAMA::OutPut(List &list)
{
List char_list;
char ch;
for(ListNode *p=list.first;p;p=p->link)
{
char_list.MakeEmpty();
ch=Decode(p->data.vn);
char_list.Insert(ch);
char_list.Insert('-');
char_list.Insert('>');
if(p->data.sentence!=NULL){
for(int i=0;p->data.sentence[i]!=END;i++)
{
ch=Decode(p->data.sentence[i]);
char_list.Insert(ch);
}
}
char_list.Print();
cout<<" \t";
for(ListNode *q=p->data.string.first;q;q=q->link)
cout<data)<<" ";
cout< > q; //q1是分析中用
List start_set;
start_set.Insert(item_list.first->data);
Closure(start_set);
q.QInsert(start_set);
state_queue.QInsert(start_set);
List sym_list;
List go_list;
List temp_list;
CItem item;
cout<<"********* LALR(1)文法分析程序 *********:\n";
List change_list;
while(!q.QueueEmpty()) //用队列来实现
{
temp_list.MakeEmpty();
temp_list=q.QDelete();
GetSymbol(temp_list,sym_list); //把求的的 X 存入链表
for(ListNode *p=sym_list.first;p;p=p->link)//对项目集中各个文法符号X用GO(I,X)
{
if(GO(temp_list,p->data,go_list))
{
int code=state_queue.GetCode(go_list);
if(code==0)
{
q.QInsert(go_list); //如果Ix还未出现过则进队列
state_queue.QInsert(go_list);
}
else{
state_queue.queue[code].MergeString(go_list);
change_list.Insert(code);
}
item.vn=state_queue.GetCode(temp_list);
item.sentence=new int[2];
item.sentence[0]=p->data;
item.sentence[1]=state_queue.GetCode(go_list);
convert_list.Insert(item); //convert_list记录转换关系
go_list.MakeEmpty();
}
}
}
for(int k=1;k *p=sym_list.first;p;p=p->link)//对项目集中各个文法符号X用GO(I,X)
{
go_list.MakeEmpty();
if(GO(state_queue.queue[k],p->data,go_list))
{
int code=state_queue.GetCode(go_list);
state_queue.queue[code].MergeString(go_list);
}
}
}
}
cout<<"\nDFA中所有状态列表:\n[X代表拓广文法开始符号]\n";
for(int i=1;i<=state_queue.rear;i++) //把DFA中所有状态输出
{
cout<<"STATE "< *p;
int newline=0;
cout<<"\n状态间转换关系:\n";
for(p=convert_list.first;p;p=p->link) //打印转换关系
{
cout<<"I"<data.vn<<"--- "<data.sentence[0])
<<" --> "<<"I"<data.sentence[1]<<" "<<"\t";
newline++;
if(newline%2==0)
cout< char_list;
char ch;
int count=0;
for(ListNode *p=item_list.first;p;p=p->link)
{
if(p->data.IsReduce())
rule_list.Insert(p->data);
}
ofstream ofstr("rule.txt");
ofstr<<"规则列表:"<link,count++)
{
char_list.MakeEmpty();
ch=Decode(p->data.vn);
char_list.Insert(ch);
char_list.Insert('-');
char_list.Insert('>');
for(int i=0;p->data.sentence[i]!=END;i++)
{
ch=Decode(p->data.sentence[i]);
char_list.Insert(ch);
}
ofstr< *q=char_list.first;q;q=q->link)
ofstr<data;
ofstr< &first_set) //递归求FIRST集合
{
if(symbol>0){ //symbol为终结符的情况
first_set.Insert(symbol);
return;
}
List temp,mid;
for(ListNode *p=gn_list.first;p;p=p->link) //先不考虑A->A…的情况
if(p->data.vn==symbol&&p->data.sentence[0]!=symbol) //找到形如A->…的产生式
{
if(p->data.sentence[0]>=0){ //A->a…的情况
first_set.Insert(p->data.sentence[0]);
continue;
}//end if
else{ //A->X1…Xn的情况
for(int i=0;p->data.sentence[i]!=END;i++)
{
temp.MakeEmpty();
First(p->data.sentence[i],temp);
mid=temp;
if(p->data.sentence[i+1]!=END) mid.Remove(0);
first_set.Add(mid); //First(Xi)=>First(symbol)
mid.MakeEmpty();
if(temp.Contains(0)) continue; //First(Xi)包含ε则继续求
else break;
}
}//end else
}
for(p=gn_list.first;p;p=p->link)
{
if(p->data.vn==symbol&&p->data.sentence[0]==symbol){
if(first_set.Contains(0)){
FirstX(p->data.sentence+1,mid);
first_set.Add(mid);
mid.MakeEmpty();
}
}
}
first_set.DelRepeated();
}
void CGRAMA::FirstX(int *array,List &first_set) //First(X1…Xn)
{
first_set.MakeEmpty();
if(*array==END) return;
List temp;
First(*array,temp);
if(!temp.Contains(0)){
first_set.Add(temp);
return;
}
temp.Remove(0);
first_set.Add(temp);
FirstX(array+1,first_set);
first_set.DelRepeated();
}
void CGRAMA::PrintTable() //打印分析表
{
int i;
ListNode *p;
ofstream ofstr("table.txt");
ofstr<<"LALR(1)分析表:\n";
for(i=0;i<(vtnum+vnnum+1);i++) ofstr<<"________";
ofstr<<"__"< *pItem;
for(i=1;i<=state_queue.count;i++)
{
ofstr<<"I"<data.IsReduce()&&pItem->data.string.Contains(vt[j]))
ofstr<<"r"<data);
for(p=convert_list.first;p;p=p->link)
if(p->data.sentence[0]==vt[j]&&p->data.vn==i)
ofstr<<"s"<data.sentence[1];
ofstr<<" \t";
}
if(pItem->data.IsReduce()&&pItem->data.string.Contains(5))
{
if(pItem->data.IsAccept()) ofstr<<"acc";
else ofstr<<"r"<data);
}
ofstr<<"\t";
/************GOTO部分************/
for(j=0;jlink)
if(p->data.sentence[0]==vn[j]&&p->data.vn==i)
ofstr<data.sentence[1];//<<"\t";
ofstr<<"\t";
}
ofstr<