编译原理.txt

编译原理

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<fstream>
#include<string>
#include<cmath>
using namespace std;

/*********************下面是一些重要数据结构的声明***************************/

struct token//词法 token结构体
{
 int code;//编码
 int num;//递增编号
 token *next;
};
token *token_head,*token_tail;//token队列
struct str//词法 string结构体
{
 int num;//编号
 string  word;//字符串内容
 str *next;
};
str *string_head,*string_tail;//string队列
struct ivan//语法 产生式结构体
{
 char left;//产生式的左部
 string right;//产生式的右部
 int len;//产生式右部的长度
};
ivan css[20];//语法 20个产生式
struct pank//语法 action表结构体
{
 char sr;//移进或归约
 int state;//转到的状态编号
};
pank action[46][18];//action表
int go_to[46][11];//语法 go_to表
struct ike//语法 分析栈结构体，双链
{
 ike *pre;
 int num;//状态
 int word;//符号编码
 ike *next;
};
ike *stack_head,*stack_tail;//分析栈首尾指针
struct L//语义四元式的数据结构
{
 int k;
 string op;//操作符
 string op1;//操作数
 string op2;//操作数
 string result;//结果
 L *next;//语义四元式向后指针
 L *Ltrue;//回填true链向前指针
 L *Lfalse;//回填false链向前指针
};
L *L_four_head,*L_four_tail,*L_true_head,*L_false_head;//四元式链，true链，false链
struct symb//语义输入时符号表
{
 string word;//变量名称
 int addr;//变量地址
 symb *next;
};
symb *symb_head,*symb_tail;//语义符号链表

/*********************下面是与词法分析相关的一些函数的声明***************************/

void scan();//按字符读取源文件
void cifa_main();//词法分析主程序
int judge(char ch);//判断输入字符的类型
void out1(char ch);//写入token.txt
void out3(char ch,string word);//写入string.txt
void input1(token *temp);//插入结点到队列token
void input3(str *temp);//插入结点到队列string
void output();//输出三个队列的内容
void outfile();//输出三个队列的内容到相应文件中

/*********************下面是与语法分析相关的一些函数的声明***************************/

void yufa_main();//语法分析主程序
void yufa_initialize();//初始化语法分析数据结构
int yufa_SLR1(int a);//语法分析主体部分
int ID1(int a);//给输入字符编号，转化成action表列编号
string ID10(int i);//给输入字符反编号
int ID2(char ch);//给非终结状态编号，转化成go_to表列编号
int ID20(char ch);//给非终结状态编号
char ID21(int j);//给非终结状态反编号
void add(ike *temp);//给ike分析栈链表增加一个结点
void del();//给ike分析栈链表删除一个结点

/*********************下面是与语义分析相关的一些函数的声明***************************/

void yuyi_main(int m);//语义分析主程序
void add_L_four(L *temp);//向四元式链中加一个结点
void add_L_true(L *temp);//向true链中加一个结点
void add_L_false(L *temp);//向false链中加一个结点
void add_symb(symb *temp);//向语义符号表链中加一个结点
void output_yuyi();//输出中间代码四元式和最后符号表
string newop(int m);//把数字变成字符串
string id_numtoname(int num);//把编号转换成相应的变量名
int lookup(string m);//变量声明检查

/*********************下面是一些全局变量的声明***************************/

FILE *fp;//文件指针
int wordcount;//标志符计数
int err;//标志词法分析结果正确或错误
int nl;//读取行数
int yuyi_linshi;//语义临时变量
string E_name,T_name,F_name,M_name,id_name,id1_name,id2_name,errword;//用于归约时名称传递和未声明变量的输出
int id_num,id1_num,id2_num,id_left,id_while,id_then,id_do;//用于记录一些特殊的字符位置信息

/****************************主程序开始**************************/

int main()
{
 cout<<"************************"<<endl;
 cout<<"*  说明：              *"<<endl;
 cout<<"*  第一部分：词法分析  *"<<endl;
 cout<<"*  第二部分：语法分析  *"<<endl;
 cout<<"*  第三部分：语义分析  *"<<endl;
 cout<<"************************"<<endl;
 cifa_main();//词法
 yufa_main();//语法
 output_yuyi();//语义
 cout<<endl;
 system("pause");
 return(0);
}

/****************************以上是主程序，以下是词法**************************/

void cifa_main()
{
 token_head=new token;
 token_head->next=NULL;
 token_tail=new token;
 token_tail->next=NULL;
 string_head=new str;
 string_head->next=NULL;
 string_tail=new str;
 string_tail->next=NULL;//初始化三个队列的首尾指针
 L_four_head=new L;
 L_four_head->next=NULL;
 L_four_tail=new L;
 L_four_tail->k=0;
 L_four_tail->next=NULL;
 L_true_head=new L;
 L_true_head->Ltrue=NULL;
 L_false_head=new L;
 L_false_head->Lfalse=NULL;
 symb_head=new symb;
 symb_head->next=NULL;
 symb_tail=new symb;
 symb_tail->next=NULL;
 yuyi_linshi=-1;
 id_num=0;
 wordcount=0;//初始化字符计数器
 err=0;//初始化词法分析错误标志
 nl=1;//初始化读取行数
 scan();
 if(err==0)
 {
  char m;
  output();
  cout<<"词法分析正确完成!"<<endl<<endl<<"如果将结果保存到文件中请输入 y ，否则请输入其它字母：";
  cin>>m;
  cout<<endl;
  if(m=='y')
  {
   outfile();
   cout<<"结果成功保存在token.txt和sting.txt两个文件中，请打开查看"<<endl;
   cout<<endl;
  }
 }
}
void scan()
{
 cout<<endl;
 system("pause");
 cout<<endl;
 char ch;
 string word;
 char document[50];
 int flag=0;
 cout<<"请输入源文件路径及名称:";
 cin>>document;
 cout<<endl;
 cout<<"************************"<<endl;
 cout<<"*  第一部分：词法分析  *"<<endl;
 cout<<"************************"<<endl;
 if((fp=fopen(document,"rt"))==NULL)
 {
  err=1;
  cout<<"无法找到该文件!"<<endl;
  return;
 }
 while(!feof(fp))
 {
  word="";
  ch=fgetc(fp);
  flag=judge(ch);
  if(flag==1)
   out1(ch);
  else if(flag==3)
   out3(ch,word);
  else if(flag==4 || flag==5 ||flag==6)
   continue;
  else
  {
   cout<<nl<<"行  "<<"错误:非法字符!  "<<ch<<endl;
   err=1;
  }
 }
 fclose(fp);
}
int judge(char ch)
{
 int flag=0;
 if(ch=='=' || ch=='+' || ch=='*' || ch=='>' || ch==':' || ch==';' || ch=='{' || ch=='}' || ch=='(' || ch==')')
  flag=1;//界符
 else if(('a'<=ch && ch<='z') || ('A'<=ch && ch<='Z'))
  flag=3;//字母
 else if(ch==' ')
  flag=4;//空格
 else if(feof(fp))
  flag=5;//结束
 else if(ch=='\n')
 {
  flag=6;//换行
  nl++;
 }
 else
  flag=0;//非法字符
 return(flag);
}
void out1(char ch)
{
 int id;
 switch(ch)
 {
 case '=' : id=1;break;
 case '+' : id=2;break;
 case '*' : id=3;break;
 case '>' : id=4;break;
 case ':' : id=5;break;
 case ';' : id=6;break;
 case '{' : id=7;break;
 case '}' : id=8;break;
 case '(' : id=9;break;
 case ')' : id=10;break;//界符编码
 default : id=0;
 }
 token *temp;
 temp=new token;
 temp->code=id;
 temp->num=-1;
 temp->next=NULL;
 input1(temp);
 return;
}
void out3(char ch,string word)
{
 token *temp;
 temp=new token;
 temp->code=-1;
 temp->num=-1;
 temp->next=NULL;
 str *temp1;
 temp1=new str;
 temp1->num=-1;
 temp1->word="";
 temp1->next=NULL;
 int flag=0;
 word=word+ch;
 ch=fgetc(fp);
 flag=judge(ch);
 if(flag==1 || flag==4 || flag==5 || flag==6)
 {
  if(word=="and" || word=="if" || word=="then" || word=="while" || word=="do" || word=="int")
  {
   if(word=="and")
    temp->code=31;
   else if(word=="if")
    temp->code=32;
   else if(word=="then")
    temp->code=33;
   else if(word=="while")
    temp->code=35;
   else if(word=="do")
    temp->code=36;
   else if(word=="int")
    temp->code=37;//关键字编码
   input1(temp);
   if(flag==1)
    out1(ch);
   else if(flag==4 || flag==5 || flag==6)
    return;
  }
  else if(flag==1)
  {
   wordcount++;
   temp->code=25;
   temp->num=wordcount;
   input1(temp);
   temp1->num=wordcount;
   temp1->word=word;
   input3(temp1);
   out1(ch);
  }
  else if(flag==4 || flag==5 || flag==6)
  {
   wordcount++;
   temp->code=25;
   temp->num=wordcount;
   input1(temp);
   temp1->num=wordcount;
   temp1->word=word;
   input3(temp1);
  }
  return;
 }
 else if(flag==2 || flag==3)
  out3(ch,word);//形成字符串
 else
 {
  err=1;
  cout<<nl<<"行  "<<"错误:非法字符!  "<<ch<<endl;
  return;
 }
}
void input1(token *temp)
{
 if(token_head->next == NULL)
 {
  token_head->next=temp;
  token_tail->next=temp;
 }
 else
 {
  token_tail->next->next=temp;
  token_tail->next=temp;
 }
}
void input3(str *temp)
{
 if(string_head->next == NULL)
 {
  string_head->next=temp;
  string_tail->next=temp;
 }
 else
 {
  string_tail->next->next=temp;
  string_tail->next=temp;
 }
}
void output()
{
 cout<<"token表内容如下："<<endl;
 token *temp1;
 temp1=new token;
 temp1=token_head->next;
 while(temp1!=NULL)
 {
  cout<<temp1->code;
  if(temp1->num == -1)
  {
   cout<<endl;
  }
  else
  {
   cout<<"   "<<temp1->num<<endl;
  }
  temp1=temp1->next;
 }
 cout<<"符号表内容如下："<<endl;
 str *temp3;
 temp3=new str;
 temp3=string_head->next;
 while(temp3!=NULL)
 {
  cout<<temp3->num<<"   "<<temp3->word<<endl;
  temp3=temp3->next;
 }
}
void outfile()
{
 ofstream fout1("token.txt");//写文件
 ofstream fout3("string.txt");
 token *temp1;
 temp1=new token;
 temp1=token_head->next;
 while(temp1!=NULL)
 {
  fout1<<temp1->code;
  if(temp1->num == -1)
   fout1<<endl;
  else
   fout1<<"   "<<temp1->num<<endl;
  temp1=temp1->next;
 }
 str *temp3;
 temp3=new str;
 temp3=string_head->next;
 while(temp3!=NULL)
 {
  fout3<<temp3->num<<"   "<<temp3->word<<endl;
  temp3=temp3->next;
 }
}

/****************************以上是词法，以下是语法**************************/

void yufa_main()
{
 if(err==0)
 {
  system("pause");
  cout<<endl;
  cout<<"************************"<<endl;
  cout<<"*  第二部分：语法分析  *"<<endl;
  cout<<"************************"<<endl;
  yufa_initialize();//初始化语法分析数据结构
  token *temp;
  temp=new token;
  temp=token_head->next;
  int p,q;
  p=0;
  q=0;
  cout<<"语法分析过程如下："<<endl;
  while(temp!=NULL)
  {
   int w;
   w=ID1(temp->code);
   p=yufa_SLR1(w);
   if(p==1) break;
   if(p==0)
    temp=temp->next;
   if(temp==NULL) q=1;
  }//语法分析
  if(q==1)
   while(1)
   {
    p=yufa_SLR1(17);
    if(p==3) break;
   }//最后输入$来完成语法分析
 }
}
void yufa_initialize()
{ 
 stack_head=new ike;
 stack_tail=new ike;
 stack_head->pre=NULL;
 stack_head->next=stack_tail;
 stack_head->num=0;
 stack_head->word='!';
 stack_tail->pre=stack_head;
 stack_tail->next=NULL;//初始化栈分析链表
 css[0].left='Q';
 css[0].right="P";
 css[1].left='P';
 css[1].right="id()L;R";
 css[2].left='L';
 css[2].right="L;D";
 css[3].left='L';
 css[3].right="D";
 css[4].left='D';
 css[4].right="id:int";
 css[5].left='E';
 css[5].right="E+T";
 css[6].left='E';
 css[6].right="T";
 css[7].left='T';
 css[7].right="T*F";
 css[8].left='T';
 css[8].right="F";
 css[9].left='F';
 css[9].right="(E)";
 css[10].left='F';
 css[10].right="id";
 css[11].left='B';
 css[11].right="B and B";
 css[12].left='B';
 css[12].right="id>id";
 css[13].left='M';
 css[13].right="id=E";
 css[14].left='S';
 css[14].right="if B then M";
 css[15].left='S';
 css[15].right="while B do M";
 css[16].left='S';
 css[16].right="M";
 css[17].left='N';
 css[17].right="N;S";
 css[18].left='N';
 css[18].right="S";
 css[19].left='R';
 css[19].right="{N}";
 int i,j;
 for(i=0;i<20;i++)
 {
  char *css_len;
  css_len=&css[i].right[0];
  css[i].len=strlen(css_len);
 }
 css[1].len=6;
 css[4].len=3;
 css[10].len=1;
 css[11].len=3;
 css[12].len=3;
 css[13].len=3;
 css[14].len=4;
 css[15].len=4;//初始化产生式
 for(i=0;i<46;i++)
 {
  for(j=0;j<18;j++)
   action[i][j].sr='#';
 }//初始化action表
 for(i=0;i<46;i++)
 {
  for(j=0;j<11;j++)
   go_to[i][j]=-1;
 }//初始化go_to表
 /****************************以下是给action表和go_to表赋初值************************/
 action[0][0].sr='s';action[0][0].state=2;
 action[1][17].sr='@';//结束
 action[2][1].sr='s';action[2][1].state=3;
 action[3][2].sr='s';action[3][2].state=4;
 action[4][0].sr='s';action[4][0].state=5;
 action[5][4].sr='s';action[5][4].state=6;
 action[6][11].sr='s';action[6][11].state=7;
 action[7][3].sr='r';action[7][3].state=4;
 action[8][3].sr='r';action[8][3].state=3;
 action[9][3].sr='s';action[9][3].state=10;
 action[10][0].sr='s';action[10][0].state=5;
 action[10][9].sr='s';action[10][9].state=13;
 action[11][17].sr='r';action[11][17].state=1;
 action[12][3].sr='r';action[12][3].state=2;
 action[13][0].sr='s';action[13][0].state=14;
 action[13][13].sr='s';action[13][13].state=23;
 action[13][15].sr='s';action[13][15].state=27;
 action[14][8].sr='s';action[14][8].state=15;
 action[15][0].sr='s';action[15][0].state=36;
 action[15][1].sr='s';action[15][1].state=41;
 action[16][6].sr='s';action[16][6].state=43;
 action[16][3].sr='r';action[16][3].state=13;
 action[16][10].sr='r';action[16][10].state=13;
 action[17][3].sr='s';action[17][3].state=19;
 action[17][10].sr='s';action[17][10].state=18;