main.cpp

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long LL;
const int INF=0x7fffffff;
const int MAX_N=10000;

int num_of_a,num_of_A,num_of_S,totalnum;
//小写字母个数、大写字母个数、推导式个数、最终结点总数
char a[50];//字母
char S[50][50];//推导式
bool pushed[100];//访问一个结点的时候，再往外拓展时记录非终结符是否已经被push过
int ans[100][100];
char analyse[50];//分析串
int stack1[50];
char stack2[50];
char stack3[50];
int L1,L2,L3;//三个栈的长度
map<char,int>M;
map<char,int>::iterator m;

struct node{//结点
    int id;//编号
    int num;//包含的推导式个数
    char s[20][50];
};
queue<node>q;//结点型队列
node N[100];
int numN=0;

void outputnd(node k){//输出一个结点的s
    for(int i=0;i<k.num;i++){
        cout<<k.s[i]<<endl;
    }
}

void outputlb(){//输出一个数组的s
    cout<<"链表"<<endl;
    for(int i=0;i<numN;i++){
        outputnd(N[i]);
        cout<<endl;
    }
}

bool samenode(node x,node y){//比较两个node是否一样
     if(x.num!=y.num)return 0;//如果两个node包含的s数量不同直接输出不同
     for(int i=0;i<x.num;i++){//暴力比较
        int flag=0;
        for(int j=0;j<y.num;j++){
            if(strcmp(x.s[i],y.s[j])==0){
                flag=1;
                break;
            }
        }
        if(flag==0)return 0;
     }
     return 1;
}

void init(){//初始化
    totalnum=0;//结点数量
    while(!q.empty())q.pop();//情况队列
    memset(S,0,sizeof(S));
    for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            ans[i][j]=-10000;
        }
    }
    M.clear();//清空映射
}

void input(){//顾名思义，输入数据
    printf("请输入终结符的个数：");
    scanf("%d",&num_of_a);
    printf("请输入%d个终结符（小写字母）：",num_of_a);
    for(int i=0;i<num_of_a;i++){
        scanf(" %c",&a[i]);
        M.insert(make_pair(a[i],i));//建立映射
    }
    a[num_of_a]='#';
    M.insert(make_pair(a[num_of_a],num_of_a));
    printf("请输入非终结符的个数（不包含起始符）：");
    scanf("%d",&num_of_A);
    printf("请输入%d个非终结符（大写字母）：",num_of_A);
    for(int i=0;i<num_of_A;i++){
        scanf(" %c",&a[num_of_a+1+i]);
        M.insert(make_pair(a[num_of_a+1+i],num_of_a+1+i));
    }
    printf("请输入初始推导式的个数：");
    scanf("%d",&num_of_S);
    printf("下面%d行每行请输入1个推导式：前后用下划线“_”链接（起始为S）:\n",num_of_S);
    for(int i=0;i<num_of_S;i++){
        scanf("%s",S[i]);
        for(int j=strlen(S[i]);j>=3;j--){
            S[i][j]=S[i][j-1];
        }
        S[i][2]='.';
    }
}

node pushback(char p,node f){//node f里把所有p开头的推导式push进去
    for(int i=0;i<num_of_S;i++){
        if(S[i][0]==p){
            strcpy(f.s[f.num++],S[i]);
        }
    }
    return f;
}

void bfs(){//宽度优先搜索
    node aa;//声明一个空的状态
    aa.num=0;
    aa.id=totalnum++;//初始化num和id
    aa=pushback('S',aa);//把S开头的推导式放到这个起始结点里
    memset(pushed,0,sizeof(pushed));//用于记录哪些字母被一次性push过，避免重复push
    for(int j=0;j<aa.num;j++){//把需要push的大写字母开头的推导式push进去
        if(aa.s[j][3]>='A'&&aa.s[j][3]<='Z'&&pushed[aa.s[j][3]]==0){
            aa=pushback(aa.s[j][3],aa);
            pushed[aa.s[j][3]]=1;
        }
    }
    q.push(aa);//把起始点放入队列
    N[numN++]=aa;//这个东西记录已经存在过的node
    while(!q.empty()){//只要队列不为空，就一直运行，下面就是宽搜了
        node cur=q.front();
        q.pop();//取出头结点保存然后pop掉
        for(int i=0;i<num_of_a+num_of_A+1;i++){//搜索所有字母
            if(i==num_of_a)continue;//这个位置存储#，所以为了提高程序运行效率，直接过掉
            node newnode;//声明一个可能要添加的新结点
            newnode.num=0;
            newnode.id=-1;
            memset(pushed,0,sizeof(pushed));
            for(int j=0;j<cur.num;j++){//搜索当前刚取出的队列头结点的所有推导式
                for(int k=2;k<strlen(cur.s[j]);k++){//对于每个推导式从左到右爆搜
                    if(cur.s[j][strlen(cur.s[j])-1]=='.')continue;//如果最后一个位置是“.”直接continue
                    if(cur.s[j][k]=='.'&&cur.s[j][k+1]==a[i]){//如果“.”后面正好是当前要搜索的字母
                        if(newnode.id==-1)newnode.id=-2;//这个node可能要被添加了，一个字母加一遍就好，以前没加过就是-1
                        char news[50];//声明一个新的字符串
                        strcpy(news,cur.s[j]);//保留现场，先把找到的这条copy下来
                        swap(news[k],news[k+1]);//把“.”和它后面的字母互换位置
                        strcpy(newnode.s[newnode.num++],news);//把处理好的news粘贴到newnode里面
                        if(news[k+2]>='A'&&news[k+2]<='Z'&&pushed[news[k+2]]==0){//如果发现“.”后面的后面跟着大写字母还要麻烦一下
                            newnode=pushback(news[k+2],newnode);//把所有的以这个大写字母开头的推导式push到newnode里面
                            pushed[news[k+2]]=1;//之前没注释的memset(pushed,0,sizeof(pushed));此时派上了用场
                        }
                    }
                }
            }
            if(newnode.id!=-1){//如果找到了可能需要push的结点
                int flag=-1;//我还需要看看这个结点是否已经存在过，是不是形成了环
                for(int p=0;p<numN;p++){//爆搜一下曾经的结点
                    if(samenode(newnode,N[p])==1){//比较一下是不是一样
                        flag=p;//如果找到一样的，就break，并且保留那个一样的结点的位置
                        break;
                    }
                }
                if(flag!=-1){//发现了一样的结点
                    ans[cur.id][i]=N[flag].id;//最终结果里体现一下
                }
                if(flag==-1){//没发现有一样的，那就是新的结点了，把他push到队列里面去
                    newnode.id=totalnum++;
                    q.push(newnode);
                    N[numN++]=newnode;
                    ans[cur.id][i]=newnode.id;
                }
            }
        }
    }
}

void build_table(){//处理表格
    for(int i=0;i<totalnum;i++){
        int flag=0;
        for(int j=0;j<num_of_A+num_of_a+1;j++){
            if(ans[i][j]!=-10000){
                flag=1;
                break;
            }
        }
        if(flag==0){
            char news[50];
            strcpy(news,N[i].s[0]);
            news[strlen(news)+1]='\0';
            for(int k=strlen(news)-1;k>=3;k--){
                news[k]=news[k-1];
            }
            news[2]='.';
            for(int j=0;j<num_of_S;j++){
                if(!strcmp(news,S[j])){
                    if(j!=0){
                        for(int k=0;k<num_of_a+1;k++){
                            ans[i][k]=-1*j;
                        }
                        break;
                    }
                    for(int k=0;k<num_of_a+1;k++){//r0 用-9999表示，s0用0表示
                        ans[i][k]=-9999;
                    }
                    break;
                }
            }
        }
    }
}

void output_action(int act){
    if(act>=0)cout<<"S"<<setw(3)<<act;
    else if(act==-10000){
        cout<<setw(4)<<" ";
    }
    else if(act==-9999){
        cout<<setw(4)<<"r0";
    }
    else{
        cout<<"r"<<setw(3)<<-1*act;
    }
}

void output_table(){//输出表格
    cout<<left<<"项目  ";
    for(int i=0;i<num_of_A+num_of_a+1;i++){
        cout<<setw(4)<<a[i];
    }cout<<endl;
    for(int i=0;i<totalnum;i++){
        cout<<setw(6)<<i;
        for(int j=0;j<num_of_A+num_of_a+1;j++){
            output_action(ans[i][j]);
        }cout<<endl;
    }
}

int step,action,GOTO;

void output_stacks(){
    cout<<endl<<"步骤："<<step++<<endl;
    cout<<"状态栈/符号栈/输入串：";
    for(int j=0;j<L1;j++){
        cout<<stack1[j]<<" ";
    }cout<<"     ";
    for(int j=0;j<L2;j++){
        cout<<stack2[j];
    }cout<<"     ";
    for(int j=L3-1;j>=0;j--){
        cout<<stack3[j];
    }cout<<endl;
}

int judge(){
    m=M.find(stack3[L3-1]);//用映射的方式找到要分析的字母是第几个,节省时间提升程序运行效率
    if(m==M.end()){
        return 0;
    }
    action=ans[stack1[L1-1]][m->second];
    if(action==-10000)return 0;
    if(action>=0){
        GOTO=-10000;
        return 1;
    }
    if(action<0&&action>-9999){
        return 2;
    }
    if(action==-9999){
        return 3;
    }
    return 0;
}

void solve(){
    cout<<endl<<"分析字符串"<<endl;
    char c;
    while(1){
        cout<<endl<<"输入一行字符串并且以#结尾:"<<endl;
        memset(analyse,0,sizeof(analyse));
        int i=0;
        while(scanf(" %c",&c)&&c!='#'){
            analyse[i++]=c;
        }
        step=1;
        memset(stack1,0,sizeof(stack1));
        memset(stack2,0,sizeof(stack2));
        memset(stack3,0,sizeof(stack3));
        L1=0,L2=0,L3=0;
        stack1[L1++]=0;
        stack2[L2++]='#';
        stack3[L3++]='#';
        for(int j=strlen(analyse)-1;j>=0;j--){
            stack3[L3++]=analyse[j];
        }
        while(1){
            int oprt=judge();
            if(oprt==0){
                cout<<"error!"<<endl;
                break;
            }
            if(oprt==1){
                output_stacks();
                cout<<"ACTION:";
                output_action(action);
                cout<<"     GOTO:blank"<<endl;
                stack1[L1++]=action;
                stack2[L2++]=stack3[--L3];
            }
            if(oprt==2){
                output_stacks();
                cout<<"ACTION:";
                output_action(action);
                int ct=0;
                for(int j=strlen(S[action*-1])-1;j>=0;j--){
                    if(S[action*-1][j]!='.')ct++;
                    if(S[action*-1][j]=='.')break;
                }
                L1-=ct;
                L2-=ct;
                stack2[L2++]=S[-1*action][0];
                m=M.find(stack2[L2-1]);
                GOTO=ans[stack1[L1-1]][m->second];
                stack1[L1++]=GOTO;
                cout<<"     GOTO:"<<GOTO<<endl;
            }
            if(oprt==3){
                output_stacks();
                if(L3==1){
                    cout<<"ACTION:acc!"<<endl;
                }
                else{
                    cout<<"error!"<<endl;
                }
                break;
            }
        }
    }
}

int main(){
    init();//初始化
    input();//输入
    bfs();//核心程序宽度优先搜索生成表格
    build_table();
    output_table();//输出表格
    solve();
    return 0;
}

//测试数据
/*

4
abcd
3
EAB
7
S_E
E_aA
E_bB
A_cA
A_d
B_cB
B_d
bccd#

4
abcd
3
EAB
7
S_E
E_aB
E_bA
B_bB
A_aA
B_d
A_c


5
abcde
3
EAB
8
S_E
E_aB
E_bB
B_cA
B_cB
A_dB
A_d
B_e

*/