LR(0)

#include<iostream>
#include<string>
#include<malloc.h>
using namespace std;
#define MaxSize 100
//符号栈
typedef struct
{
 char data[MaxSize];
 int top;    //栈指针
} SqStack;     //顺序栈类型
//状态栈
typedef struct
{
 int data[MaxSize];
 int top;    
} SqStack1; 
//字符栈
void show(SqStack*s) {
 for (int i = 0; i <= s->top; i++) {
  cout << s->data[i];
 }
 cout << "\t\t";
}
void InitStack(SqStack *&s)
{
 s = (SqStack *)malloc(sizeof(SqStack));
 s->top = -1;
}
bool StackEmpty(SqStack *s)
{
 return(s->top == -1);
}
bool Push(SqStack *&s, char e)
{
 if (s->top == MaxSize - 1)    //栈满的情况，即栈上溢出
  return false;
 s->top++;
 s->data[s->top] = e;
 return true;
}
bool Pop(SqStack *&s, char &e)
{
 if (s->top == -1)  //栈为空的情况，即栈下溢出
  return false;
 e = s->data[s->top];
 s->top--;
 return true;
}
bool GetTop(SqStack *s, char &e)
{
 if (s->top == -1)   //栈为空的情况，即栈下溢出
  return false;
 e = s->data[s->top];
 return true;
}
//状态栈
void show1(SqStack1*s) {
 for (int i = 0; i <= s->top; i++) {
  cout << s->data[i];
 }
 cout << "\t\t";
}
void InitStack1(SqStack1 *&s)
{
 s = (SqStack1 *)malloc(sizeof(SqStack1));
 s->top = -1;
}
bool StackEmpty1(SqStack1 *s)
{
 return(s->top == -1);
}
bool Push1(SqStack1 *&s, int e)
{
 if (s->top == MaxSize - 1)    //栈满的情况，即栈上溢出
  return false;
 s->top++;
 s->data[s->top] = e;
 return true;
}
bool Pop1(SqStack1 *&s, int &e)
{
 if (s->top == -1)  //栈为空的情况，即栈下溢出
  return false;
 e = s->data[s->top];
 s->top--;
 return true;
}
bool GetTop1(SqStack1 *s, int &e)
{
 if (s->top == -1)   //栈为空的情况，即栈下溢出
  return false;
 e = s->data[s->top];
 return true;
}

int Action[12][6] = {
 15,-1,-1,14,-1,-1,
 -1,16,-1,-1,-1,10,
 -1,2,17,-1,2,2,
 -1,4,4,-1,4,4,
 15,-1,-1,14,-1,-1,
 -1,6,6,-1,6,6,
 15,-1,-1,14,-1,-1,
 15,-1,-1,14,-1,-1,
 -1,16,-1,-1,21,-1,
 -1,1,17,-1,1,1,
 -1,3,3,-1,3,3,
 -1,5,5,-1,5,5
};

int Goto[12][3] = {
 1,2,3,
 -1,-1,-1,
 -1,-1,-1,
 -1,-1,-1,
 8,2,3,
 -1,-1,-1,
 -1,9,3,
 -1,-1,10,
 -1,-1,-1,
 -1,-1,-1,
 -1,-1,-1,
 -1,-1,-1
};

int main() {
 SqStack *charStack;
 SqStack1 *statusStack;
 InitStack(charStack);
 InitStack1(statusStack);
 Push(charStack, '#');
 Push1(statusStack, 0);
 char s,ch;
 char str[20];
 int length = 0, index=0, len, step = 1;
 int m,j, S, a;//S状态栈栈顶,a输入串头,j标识goto表的列号
 cout << "请输入字符串:";
 do {
  cin >> s;
  str[length++] = s;
 } while (s != '#');
 //取输入栈顶,状态栈栈顶，
 cout << "步骤\t\t状态栈\t\t符号栈\t\t输入串\t\tAction\t\tGoto\t\t\n";
 do {
  switch (str[index]) {
  case 'i':a = 0; break;
  case '+':a = 1; break;
  case '*':a = 2; break;
  case '(':a = 3; break;
  case ')':a = 4; break;
  case '#':a = 5; break;
  default:a = -1;break;
  }
  if (a != -1) {
   //LR0分析开始
   S = Action[statusStack->data[statusStack->top]][a];
   if (S > 10) {//移入
    //状态栈入栈S-10,输入串当前元素入符号栈，输入串后移
    cout << "(" << step << ")\t\t";
    show1(statusStack);
    show(charStack);
    for (m = index; m < length;m++) {
     cout << str[m];
    }
    cout << "\t\t"<<"S"<<(S-10)<<"\t\t\n";
    Push1(statusStack, S - 10);
    Push(charStack, str[index]);
    index++;
    step++;
   }
   else if (S<10 && S>-1) 
   {//归约
    //统计表达式右边元素个数，状态栈出栈相应个数，符号栈同
    cout << "(" << step << ")\t\t";
    show1(statusStack);
    show(charStack);
    for (m = index; m < length; m++) {
     cout << str[m];
    }
    switch (S) {
    case 1:
     ch = 'E'; len = 3;
     for (int i = 1; i <= len; i++) {
      Pop1(statusStack, statusStack->data[statusStack->top]);
      Pop(charStack, charStack->data[charStack->top]);
     }
     Push(charStack, 'E');
     break;
    case 2:ch = 'E'; len = 1;
     for (int i = 1; i <= len; i++) {
      Pop1(statusStack, statusStack->data[statusStack->top]);
      Pop(charStack, charStack->data[charStack->top]);
     }
     Push(charStack, 'E');
     break;
    case 3:ch = 'T'; len = 3;
     for (int i = 1; i <= len; i++) {
      Pop1(statusStack, statusStack->data[statusStack->top]);
      Pop(charStack, charStack->data[charStack->top]);
     }
     Push(charStack, 'T');
     break;
    case 4:ch = 'T'; len = 1;
     for (int i = 1; i <= len; i++) {
      Pop1(statusStack, statusStack->data[statusStack->top]);
      Pop(charStack, charStack->data[charStack->top]);
     }
     Push(charStack, 'T');
     break;
    case 5:ch = 'F'; len = 3;
     for (int i = 1; i <= len; i++) {
      Pop1(statusStack, statusStack->data[statusStack->top]);
      Pop(charStack, charStack->data[charStack->top]);
     }
     Push(charStack, 'F');
     break;
    case 6:ch = 'F'; len = 1;
     for (int i = 1; i <= len; i++) {
      Pop1(statusStack, statusStack->data[statusStack->top]);
      Pop(charStack, charStack->data[charStack->top]);
     }
     Push(charStack, 'F');
     break;
    }
    switch (ch) {
    case 'E':j = 0; break;
    case 'T':j = 1; break;
    case 'F':j = 2; break;
    }
    cout << "\t\t"<<"R"<<S<<"\t\t"<<Goto[statusStack->data[statusStack->top]][j]<<"\n";
    Push1(statusStack, Goto[statusStack->data[statusStack->top]][j]);
    step++;
   }
   else if (S == 10)
   {//acc
    cout << "(" << step << ")\t\t";
    show1(statusStack);
    show(charStack);
    for ( m= index; m < length; m++) {
     cout << str[m];
    }
    cout << "\t\tacc\t\t\n";
    cout << "文法接受该输入语句！"<<endl;
    index++;
    exit(0);
   }
   else{
    cout << "(" << step << ")\t\t";
    show1(statusStack);
    show(charStack);
    for (m = index; m < length; m++) {
     cout << str[m];
    }
    cout << "\t\t该输入语句文法不接受！"<<endl;
    exit(0);
   }
  }
  else {
   cout << "输入句不符合该文法" << endl;
   exit(0);
  }
 } while (str[index] != '\0');
 return 0;
}

LR(0)

浏览过的版块