1.cpp

编译原理中的编译器的一部分

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
//----------------------Global Declarition---------------------------------
#define SIZE 20
#define staNumber 12         //有12个状态
#define Act 6          //有6个非终结符
#define gSIZE 3          //要遇到的非终结符进行转移
#define proNumber 6         //有6个产生式
#define MAXSIZE 3
//---------------------Finish defining struct-------------------------------------
typedef struct Pro
{
        char head;       //左边的非终结符
        char gen[4];       //右边的推到出的表达式 
}Produce;//--------------------------------表达式的基本结构
typedef struct A
{
 int st[Act];       //移近数组
 int re[Act];       //规约 数组
}Action;//----------------------------------动作表数据结构
typedef struct G
{
 char head[gSIZE];      //非终结符E F T
 int gt[gSIZE];       //gSIZE=3,存放跳转到的状态
}GOTO;//------------------------------------转移状态结构
int status[SIZE];                          //状态栈数组                                 
int  staMark;           //top of stack of status  状态栈栈顶
char symbol[SIZE];                          //非终结符的栈
int  symMark;        //Current index of symbol stack
char string[SIZE];                      //存放输入的字符串数组
int  expMark;                             //index of inputed expression
int  exptop;        //输入的字符串顶部
int  step;         //在构造分析表的时候，用于标记步骤的
int  IsAccept = 0;       //分析表 accept flag to 0 /字符串被接受标志位置0
Produce gene[proNumber +1];
Action act[staNumber];
GOTO go[staNumber];

void GOTOForm(int sta, char symb);//GOTO表 Symb是非终结符

void Syntax(void)//将6个产生式输出
{
 
 printf("-------------LR(1) Syntax---------------\n");
 printf("--------------规定的文法-----------------\n");
 printf(" (0)E -> E + T\n (1)E -> T\n (2)T -> T*F\n (3)T -> F\n (4)F -> E\n (5)F -> (i)\n");
 printf("-----------------------------------------\n");
}

void InputString(void)//输入要分析的字符串
{
     char ch;
     printf("请输入分析串：");
     printf("[包括:{+ - * /( )i #}以'#'结束]:\n");
     expMark = 0;
  do                                
  {
     scanf("%c",&ch);
     if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='#')&&(ch!='(')&&(ch!=')'))
     {
     printf("输入的非终结符不符合要求：请按任意键跳出!\n");
     getchar();
     exit(0);
     }
     string[expMark++]=ch;
  }while(ch!='#');                       
  printf("---------字符串分析表---------\n");
  getchar();
}

void PrintString(void)//将输入的字符串输出
{
     int i = 0;
     printf("You have inputed below:\n");
     for(i = 0; i < expMark; i++)
     printf("%c",string[i]);
  printf("\n");
}

void PrintStatus(void)//将状态栈输出
{
 int i = 0;
 for(i = 0; i <= staMark; i++)//
 {
  printf("%d", status[i]);
 }
 printf("\t\t");
}

void PrintRestExp(void)//输出其他的非终结符
{
 int i = 0;
 for(i = 0; i < exptop; i++)
  printf(" ");
 for(i = exptop; i <= expMark; i++)
 {
  printf("%c", string[i]);
 }
 printf("\t\t");
}

void Format()
{
 printf("步骤 \t 状态栈 \t符号栈   \t 剩余输入串 \t 动作\n");
}



void Initlize(void)//将LR(1)的分析表建立出来
{
//将产生式放入数组行用到了数据结构中的引用
 gene[1].head = 'E';
 strcpy(gene[1].gen,"E+T");//Generate gene[geSIZE +1];
                           //Action act[sSIZE];
                           //GOTO go[sSIZE];
 gene[2].head = 'E';
 strcpy(gene[2].gen,"T");
 
 gene[3].head = 'T';
 strcpy(gene[3].gen,"T*F");
 
 gene[4].head = 'T';
 strcpy(gene[4].gen,"F");
 
 gene[5].head = 'F';
 strcpy(gene[5].gen,"(E)");
 
 gene[6].head = 'F';
 strcpy(gene[6].gen,"i");
 //-----------------------------------完成产生式的存储
 //----------------------------------- 产生式的动作表
 act[0].st[0] = 5;
 act[0].st[3] = 4;
 
 act[1].st[1] = 6;
// act[1].st[5] = 10;
 act[2].re[1] = 2;
 act[2].st[2] = 7;
 act[2].re[4] = 2;
 act[2].re[5] = 2;
 
 act[3].re[1] = 4;
 act[3].re[2] = 4;
 act[3].re[4] = 4;
 act[3].re[5] = 4;
 
 act[4].st[1] = 5;
 act[4].st[3] = 4;
 
 act[5].re[1] = 6;
 act[5].re[2] = 6;
 act[5].re[4] = 6;
 act[5].re[5] = 6;
 
 act[6].st[0] = 5;
 act[6].st[3] = 4;
 
 act[7].st[0] = 5;
 act[7].st[3] = 4;
 
 act[8].re[1] = 6;
 act[8].re[4] = 11;
 
 act[9].re[1] = 1;
 act[9].re[2] = 7;
 act[9].re[4] = 1;
 act[9].re[5] = 1;
 
 act[10].re[1] = 3;
 act[10].re[2] = 3;
 act[10].re[4] = 3;
 act[10].re[5] = 3;
 
 act[11].re[1] = 5;
 act[11].re[2] = 5;
 act[11].re[4] = 5;
 act[11].re[5] = 5;
 //-----------------------------------完成分析动作表
 //-----------------------------------分析表的GOTO状态
 go[0].head[0] = 'E';
 go[0].head[1] = 'T';
 go[0].head[2] = 'F';
 go[0].gt[0] = 1;
 go[0].gt[1] = 2;
 go[0].gt[2] = 3;
 
 go[4].head[0] = 'E';
 go[4].head[1] = 'T';
 go[4].head[2] = 'F';
 go[4].gt[0] = 8;//go[]shi 状态，gt[]是存放非终结符的，这个是代表4状态遇到分析表中的第一个非终结符转移到8状态
 go[4].gt[1] = 2;
 go[4].gt[2] = 3;
 
 go[6].head[1] = 'T';
 go[6].head[2] = 'F';
 go[6].gt[1] = 9;
 go[6].gt[2] = 3;
 
 go[7].head[2] = 'F';
 go[7].gt[2] = 10;
 //完成 Goto表
 //Initlize global vari
 staMark = 0;                       
 status[staMark] = 0;                
 step = 1;
 symMark = 0;
 symbol[symMark] = '#';
 IsAccept = 0;
 exptop = 0;
}

void Reduce(int sta, char symb,int col)//规约动作
{
unsigned int i = 0;
 for(i = 0; i < strlen(gene[act[sta].re[col]].gen); i++)//进行规约的时候从状态栈和符号栈去掉R个符号，即指针要减R
 {
  symbol[symMark--] = '\0';//符号栈自顶向下去掉strlen(gene[act[sta].re[col]].gen个符号
 }
 symbol[++symMark] = gene[act[sta].re[col]].head;//把产生式的左部给symbol[++symMark]进行规约
 for(i = 0; i < strlen(gene[act[sta].re[col]].gen) ; i++)
 {
  status[staMark - i] = '\0';//符号栈自顶向下去掉strlen(gene[act[sta].re[col]].gen个状态
 }
 staMark -= i; 
 GOTOForm(status[staMark], symbol[symMark]);//状态遇到（symbol[symMark]）非终结符进行转移
}



void ActionTable(int sta, char symb,int col)//动作表int col是
{
 if(sta == 1 && col == 5)//状态1遇到第6个终结符接受
 {
  printf("accept\n");
  IsAccept = 1;
  return;
 }
 if(act[sta].st[col] != 0)
 {
  printf(" S \n");
  status[++staMark] = act[sta].st[col];//状态进入状态栈，staMark相当于状态栈的指针
  symbol[++symMark] = symb;//符号进入符号栈，symMark相当于非终结符的指针
  exptop ++;
 }
 else if(act[sta].re[col] != 0)//进行规约处理
 {
  printf("  R  \n");
  Reduce(sta, symb, col);//规约是将规约成的非终结符放入符号栈，状态栈和符号栈先去掉字符在入栈
 }
 else
 {
  printf("error\n");//出错原因是某个状态后有固定的后跟非终结符。
  getchar();
  exit(1);
 }
  
}



void GOTOForm(int sta, char symb)//GOTO表 状态转换表
{
 int i = 0;
 for(i = 0; i < staNumber; i++)
 {
   if(go[sta].head[i] == symb)
  {
   //printf("Head %d\n",go[sta].gt[i]);
   status[++staMark] = go[sta].gt[i];
   return;
  }
 }
}


void Launch(void)
{
 int s = status[staMark];
 char exp = string[exptop];//栈顶元素
 char sym = symbol[symMark];//符号
 while(IsAccept != 1)//没有被接受的时候发生的事情，即移近，规约，接受，报错
 {
  s = status[staMark];
  exp = string[exptop];//栈顶元素
  sym = symbol[symMark];
  printf("%d\t ",step++);
  PrintStatus();//输出状态栈
  printf(" %s\t\t", symbol);//输出符号栈的内容
  PrintRestExp();
  switch(exp)
  {
   case 'i':
    ActionTable(s, exp, 0); 
    break;
   case '+':
    ActionTable(s, exp, 1);
    break;
   case '*':
    ActionTable(s, exp, 2);
    break;
   case '(':
    ActionTable(s, exp, 3);
    break;
   case ')':
    ActionTable(s, exp, 4);
    break;
   case '#':
    ActionTable(s, exp, 5);
    break;
  }
 }
}


int main()
{
  Syntax();
  InputString();//输入字符串
  //PrintExpression();
  Initlize();//建立LR（1）的分析表
  Format();//输出对串分析的时候的常用符号
  Launch();//对表进行分析
  getchar();
  return 1;
}