#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=100+5;
char buf[maxn];   //输入产生式
int n;   //产生式的数量
class node{
public:
    string left;
    set<string> right;
    node(const string& str){
        left=str;
        right.clear();
    }
    void push(const string& str){
        right.insert(str);
    }
    void print(){
        printf("%s->",left.c_str());
        set<string>::iterator it = right.begin();
        printf("%s",it->c_str());
        it++;
        for (;it!= right.end();it++ )
            printf("|%s",it->c_str());
        cout<<endl;
    }
};
map<string,int> mp;  //记录每个node的下标
vector<node> vnode;  //每一个产生式
string start;   //文法G[s]
bool used[maxn];  //用于去掉无用产生式
//初始化工作
void init(){
    mp.clear();
    vnode.clear();
    start="S";
}
//消除间接左递归
void eliminateIndirectLeftRecursion(){
    for(int i=0;i<vnode.size();i++){
        for(int j=0;j<i;j++){
            vector<string> ans;
            set<string>& righti=vnode[i].right;
            set<string>& rightj=vnode[j].right;
            char ch=vnode[j].left[0]; //取所有Aj产生式的左部的非终结符
            set<string>::iterator iti,itj;
            for(iti=righti.begin();iti!=righti.end();iti++){
                if(iti->at(0)==ch) //如果当前产生式右部的非终结符和Aj相同
                    for(itj=rightj.begin();itj!=rightj.end();itj++)
                        ans.push_back(*itj+iti->substr(1));   //进行替换操作,先存储起来
            }
            while(!righti.empty()){
                if(righti.begin()->at(0)!=ch) //存储当前没有替换的产生式右部
                    ans.push_back(*righti.begin());
                righti.erase(righti.begin());  //被替换过的产生式右部也删除掉
            }
            for(int k=0;k<ans.size();k++)  //将替换过的产生式右部进行更新操作
                righti.insert(ans[k]);
        }
    }
    cout<<"消除间接左递归后的结果："<<endl;
    for(int k=0;k<vnode.size();k++)
            vnode[k].print();
    cout<<endl;
}
//消除直接左递归
void eliminateDirectLeftRecursion(){
    for(int i=0;i<vnode.size();i++){
        char ch=vnode[i].left[0];
        set<string>& right=vnode[i].right;
        set<string>::iterator it;
        string tmp=vnode[i].left.substr(0,1)+"\'";
        bool flag=true;
        for(it=right.begin();it!=right.end();it++){
            if(it->at(0)==ch){
                vnode.push_back(node(tmp));
                mp[tmp]=vnode.size();
                flag=false;
                break;
            }
        }
        int idx=mp[tmp]-1;
        if(flag) continue; //对于非终结符不相同的产生式我们需要跳过
        vector<string> ans;
        set<string>& tmpSet=vnode[idx].right;
        tmpSet.insert("~");  //添加空字符
        while(!right.empty()){
            if(right.begin()->at(0)==ch)
                tmpSet.insert(right.begin()->substr(1)+tmp);
            else
                ans.push_back(right.begin()->substr(0)+tmp);
            right.erase(right.begin());
        }
        for(int k=0;k<ans.size();k++)
            right.insert(ans[k]);
    }
    cout<<endl;
    cout<<"消除直接左递归后的结果："<<endl;
    for(int k=0;k<vnode.size();k++)
            vnode[k].print();
    cout<<endl;
}
//搜索
void dfs(int x){
    if(used[x]) return;
    used[x]=1;
    set<string>::iterator it=vnode[x].right.begin();
    for(;it!=vnode[x].right.end();it++){
        for(int i=0;i<it->length();i++){
            if(isupper(it->at(i))){
                if(i+1<it->length() && it->at(i+1)=='\'')
                    dfs(mp[it->substr(i,2)]-1);
                else
                    dfs(mp[it->substr(i,1)]-1);
            }
        }
    }
}
//去掉无用产生式
void removeUselessProduction(){
    memset(used,0,sizeof(used));
    int idx=mp[start]-1;
    dfs(idx);
    cout<<"最终文法："<<endl;
    vector<node> res;
    for(int i=0;i<vnode.size();i++)
        if(used[i])
            res.push_back(vnode[i]);
    vnode.clear();
    vnode=res;
}
int main(){
    cout<<"请输入文法G[S]的产生式数量："<<endl;
    while(cin>>n){
        init(); //初始化
        getchar();
        cout<<"依次输入文法G[S]的产生式："<<endl;
        for(int i=0;i<n;i++){
            scanf("%s",buf); //输入产生式
            int len=strlen(buf),j;
            for(j=0;j<len;j++)
                if(buf[j]=='-'){
                    buf[j]=0;  //进行左部和右部切分
                    break;
                }
            string tmp=buf; //拿到产生式的左部
            if(!mp[buf]){
                vnode.push_back(node(tmp));
                mp[tmp]=vnode.size();
            }
            int idx=mp[tmp]-1;  //获取左部的下标
            tmp=buf+j+2;  //拿到产生式的右部
            vnode[idx].push(tmp);
        }
        //确定开始节点
        int idx=vnode.size()-1;
        start=vnode[idx].left[0];
        eliminateIndirectLeftRecursion(); //消除间接左递归
        eliminateDirectLeftRecursion(); //消除直接左递归
        removeUselessProduction(); //去掉无用产生式
        /*
        *test
        */
        /*cout<<"---------test---------"<<endl;
        for(int k=0;k<vnode.size();k++)
            vnode[k].print();*/
        for(int k=0;k<vnode.size();k++)
            vnode[k].print();
    }
    return 0;
}
