[C++知识库]c++消除左递归算法

[`原文网址](https://blog.csdn.net/qq_24451605/article/details/50075467)

课程设计选这个题，然后找到了上述文章。拿去vs一跑发现不少错误。主要是指针越界的错误。
故稍作修改，起码能跑。还添加了一些注释，方便像我一样的混子看懂
删除了化简和dfs函数，因为没啥用。。。。
下面是输入：

说实话，这个输入不是很方便，明明可以一次输入R->Sa|a，非要自找麻烦输入两次。
不说了，上代码！
``

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cctype>
#include <map>
#include <set>
#define MAX 500

using namespace std;

class WF  //定义一个用于存放p的类
{
public:
    string left; //产生式左部
    set<string> right; //右部
    WF(const string& temp) //默认构造函数
    {
        left = temp;
        right.clear();
    }
    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());
        puts("");//输出字符串
    }
    void insert(const string& temp)//右部插入
    {
        right.insert(temp);
    }
};

map<string, int> VN_dic;//下标类型为string，数组每一个元素的类型为int的数组
vector<WF> VN_set;//存放文法G的容器
string start;
bool used[MAX];

//消除间接左递归
void remove1()
{
    //如果j的左部字母出现在i的右部，就把j的右部代入到i的右部，直到i是最后一个产生式
    for (int i = 0; i < VN_set.size(); i++)
        for (int j = 0; j < i; j++)
        {
            vector<string> cont;  //代入后的右部
            set<string>& right1 = VN_set[i].right;   //获取第i个产生式的右部
            set<string>& right2 = VN_set[j].right;   //获取第j个产生式的右部
            char ch = VN_set[j].left[0];    //j的左部字母
            set<string>::iterator it1 = right1.begin(); //遍历i的右部
            set<string>::iterator it2;
            for (; it1 != right1.end(); it1++)
                if (it1->at(0) == ch) //是否代入
                    for (it2 = right2.begin(); it2 != right2.end(); it2++)
                        //substr（a）截取下标a后的字符串
                        //截取的字符串加入到cont中
                        cont.push_back(*it2 + it1->substr(1)); 
            int nn = right1.size();
            while (nn--)
            {
                //i的右部中可以代入的字母所在式子删除
                if (right1.begin()->at(0) == ch) 
                    right1.erase(right1.begin()); 
                else
                {
                    //更新cont，删除i的第一个右部式子，直到i的右部被删除完毕
                    cont.push_back(*right1.begin());
                    right1.erase(right1.begin());
                }
            }
            //把代入完成的i的右部cont插入到i的右部
            for (int i = 0; i < cont.size(); i++)
                right1.insert(cont[i]);
        }
}

//消除直接左递归
void remove2()
{
    for (int i = 0; i < VN_set.size(); i++)
    {
        char ch = VN_set[i].left[0];    //获取i的左部字母
        set<string>& temp = VN_set[i].right;    //获取i的右部指针
        set<string>::iterator it = temp.begin();//遍历
        //新产生式左部为原左部字母加'
        string tt = VN_set[i].left.substr(0, 1) + "\'";    
        bool flag = true;
        //当遍历到左部字母时，添加新产生式
        for (; it != temp.end(); it++)
            if (it->at(0) == ch)
            {
                VN_set.push_back(WF(tt));
                VN_dic[tt] = VN_set.size();
                flag = false;
                break;
            }
        //获取i的右部指针
        set<string>& tempp = VN_set[i].right;
        int x = VN_dic[tt] - 1;
        if (flag) continue;
        vector<string> cont;//原产生式的右部
        //获取新产生式的右部
        set<string>& ss = VN_set[x].right;
        ss.insert("~");
        while (!tempp.empty())
        {   
            //右部按第一个字母是否为左部字母分别处理
            if (tempp.begin()->at(0)==ch)
                //新式添加的右部为原式右部第二个元素开始字符串+新式左部字母
                ss.insert(tempp.begin()->substr(1) + tt);
            else
            {
                //原式右部为原右部+新式左部字母
                cont.push_back(tempp.begin()->substr(0) + tt);
            }
            //删除右部第一个式子
            tempp.erase(tempp.begin());
        }
        puts("");
        //更新原产生式的右部
        for (int i = 0; i < cont.size(); i++)
        {
            tempp.insert(cont[i]);
        }
    }
}

void  print()
{
    cout << "**********消除左递归后的结果********" << endl;
    for (int i = 0; i < VN_set.size(); i++)
        VN_set[i].print();
    puts("");
}

//  P->Pa     R->Sa       R->a      
//  P->a      S->Qb       S->b      Q->Rc       Q->c

int main()
{
    char buf[MAX];
    int n;
    VN_dic.clear();
    VN_set.clear();
    start = "S";
    cout << "请输入文法G[S]的产生式数量：";
    cin >> n;
        while (n--)
        {
            cin >> buf;
            int len = strlen(buf), i;//返回buf长度
            for (i = 0; i < len; i++)
                if (buf[i] == '-')
                {
                    buf[i] = 0;
                    break;
                }
            string temp = buf;
            if (!VN_dic[temp])
            {
                //添加左部字母
                VN_set.push_back(WF(temp));
                VN_dic[temp] = VN_set.size();
            }
            //添加右部式子Pa和a都算是式子
            int x = VN_dic[temp] - 1;
            int j = 3; string tempp;
            while (buf[j] != '\0') {
                string buf(1, buf[j]);
                tempp = tempp + buf;
                j++;
            }
            temp = tempp;
            VN_set[x].insert(temp);
        }
        cout << endl << "完整的G文法：" << endl;
        for (int i = 0; i < VN_set.size(); i++)
            VN_set[i].print();
      
        remove1();
        remove2();
        print();
        
        return 0;
}