语法分析之LR0文法

灰太狼 2023-06-12 12:28 20阅读 0赞

### 语法分析之LR0文法 ###

*   *   *  算法参考书上的知识点
         *  参考代码
         *  测试数据

### 算法参考书上的知识点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]

### 参考代码 ###

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <iomanip>
    using namespace std;
    
    typedef char grammarType;
    grammarType start, S;                //开始符号,S用来作为输入
    map<grammarType, int> ter;           //终结符集合
    vector<grammarType> terInx;          //通过索引查找终结符
    map<grammarType, int> nonter;        //非终结符集合
    vector<grammarType> nontInx;         //通过索引查找非终结符
    vector<grammarType> language;        //需要进行分析的语言，即输入字符串
    int terNum, nontNum, proSize, Lsize; //终结符数目,非终结符数目,产生式数目,语言的长度
    struct Production
    { 
        int LP;         //左部非终结符的索引
        vector<int> RP; // 右边产生式索引
        vector<bool> F; //标记右边相关产生式是终结符（false），非终结符（false)
    }; // 产生式
    vector<Production> pro;     //产生式
    vector<int> *tpro;          //定义每个非终结符能推出的产生式
    vector<int> proIS;          //定义每个产生式的开始项目集编号
    vector<int> itp;            //记录每个项目所在的位置
    vector<set<int> > C;         //计算LR(0)项目集规范族
    set<int>::iterator itSet;   //set迭代器
    vector<vector<int>> action; // 终结符的action表
    vector<bool> actionF;       //判断是该项目集移进还是规约 true为规约0
    vector<vector<int>> Goto;   // 非终结符goto表
    vector<grammarType> sign;   //定义LR分析中的符合栈
    vector<int> state;          //定义LR分析中的状态栈
    #define Setit(s) for (itSet = (s).begin(); itSet != (s).end(); ++itSet)
    void closuer(set<int> &);                    //计算项目集的闭包
    set<int> &go(set<int> &, int, bool);         //定义go=closure (move(I,X))运算
    bool getCanonicalSet();                      //得到项目集规范族 并且判断是否LR0文法，过程中得到分析表
    void analysis();                             //对所得语言进行分析
    bool isSetEqual(set<int> &s1, set<int> &s2); //判断集合S1,S2内容是否一样
    string intToStr(int);                        //将int类型转成string类型
    string getReStr(int);                        //在文法分析过程中输入语言中的剩余内容
    string getState();                           //将状态状的内容进行输出
    string getSign();                            //将符合栈里面的内容进行输出
    string getPro(int);                          //输出一条产生式
    #define out(w, s) cout << setw((w)) << setiosflags(ios::left) << ((s))
    int main()
    { 
        cout << "请输入拓广文法开始符合：";
        cin >> start;
        cout << "请输入非终结符的数目：";
        cin >> nontNum;
        tpro = new vector<int>[nontNum];
        cout << "请依次输入非终结符："; // 输入以空格隔开
        for (int i = 0; i < nontNum; ++i)
        { 
            cin >> S; 
            nonter[S] = i;
            nontInx.push_back(S);
        }
        cout << "请输入终结符的数目：";
        cin >> terNum;
        cout << "请依次输入终结符(用二个符合表示空和结束符并放在末尾): ";
        for (int i = 0; i < terNum; ++i)
        { 
            cin >> S;
            ter[S] = i;
            terInx.push_back(S);
        }
        cout << "请依次输入产生式的数目：";
        cin >> proSize;
        itp.push_back(-1);
        cout << "请依次输入产生式：";
        int t, sum = 0;
        Production p;
        for (int i = 0; i < proSize; ++i)
        { 
            cin >> S >> t; // 输入非终结符 产生式右部符号数目
            p.LP = nonter[S];
            tpro[p.LP].push_back(i);
            for (int j = 0; j < t; ++j)
            { 
                cin >> S;
                if (nonter.find(S) != nonter.end())
                { 
                    p.RP.push_back(nonter[S]);
                    p.F.push_back(true);
                }
                else
                { 
                    p.RP.push_back(ter[S]);
                    p.F.push_back(false);
                }
            } 
            if (t == 1 && p.F[0] == false && p.RP[0] == terNum - 2)
                t = 0;
            for (int j = 0; j < t + 1; ++j)
                itp.push_back(i);
            proIS.push_back(sum + 1);
            sum += t + 1;
            pro.push_back(p);
            p.RP.clear();
            p.F.clear(); // 清空
        }
        if (getCanonicalSet() == false)
            return 0;
        cout << "请输入要分析的语言的长度: ";
        cin >> Lsize;
        cout << "请输入要分析的语言(带输入结束符)：";
        for (int i = 0; i < Lsize; ++i)
        { 
            cin >> S;
            language.push_back(S);
        }
        analysis();
    }
    /* 状态转换函数GO(I,X)的计算： GO(I,X) = Closure(J) I是一个项目集，X是一个文法符号 其中J = {任何形如A -> aX·b的项目| A->a·Xb 属于 I} */
    void closuer(set<int> &I)
    { 
        int px, pis, inx, tinx;
        itSet = I.begin();
        set<int> nontV;
        while (itSet != I.end())
        { 
            px = itp[*itSet];
            pis = proIS[px];
            inx = *itSet - pis;
            if (inx == pro[px].F.size())
            { 
                ++itSet;
                continue;
            }
            if (pro[px].F[inx])
            { 
                tinx = pro[px].RP[inx];
                if (nontV.find(tinx) == nontV.end())
                { 
                    for (int i = 0; i < tpro[tinx].size(); ++i)
                        I.insert(proIS[tpro[tinx][i]]);
                    itSet = I.begin();
                    nontV.insert(tinx);
                }
                else
                    ++itSet;
            }
            else
                ++itSet;
        }
    }
    bool isSetEqual(set<int> &s1, set<int> &s2)
    { 
        if (s1.size() != s2.size())
            return false;
        for (itSet = s1.begin(); itSet != s1.end(); ++itSet)
        { 
            if (s2.find(*itSet) == s2.end())
                return false;
        }
        return true;
    }
    string intToStr(int num)
    { 
        if (num == 0)
            return "0";
        string s = "";
        while (num)
        { 
            s += char(num % 10 + '0');
            num /= 10;
        }
        s.reserve();
        return s;
    }
    bool getCanonicalSet()
    { 
        set<int> I;
        /* 拓广文法：在原文法G[S]上增加一个产生式S' →S，这是为了得到唯一的接受状态S' →S · */
        I.insert(proIS[tpro[nonter[start]][0]]); // 拓广文法
        closuer(I); // 求拓广文法的闭包
        C.push_back(I); // 初始化项目集规范族C
        int px, pis, inx, j, i, t, f1, f2, ppos;
        vector<int> come;
        set<int> Vn, Vt;
        for (i = 0; i < C.size(); ++i)
        { 
            f1 = f2 = 0;
            Vn.clear();
            Vt.clear();
            come.clear();
            // 若一个项目集中同时含有移进和归约项目，出现了冲突。
            for (itSet = C[i].begin(); itSet != C[i].end(); ++itSet)
            { 
                px = itp[*itSet];
                pis = proIS[px];
                inx = *itSet - pis;
                // 归约项目：后继符号为空：即圆点在最右边
                if (inx == pro[px].F.size())
                { 
                    f1++;
                    ppos = px;
                    continue;
                }
                /* 对于A -> a·Xb 属于 Ik，则 GO(Ik,X)=Ij 若X 属于Vt，则置action[k,X]=Sj ,即把(j,a)移进栈 若X 属于Vn，则置goto[Ik,X]=j */
                if (false == pro[px].F[inx]) // 移进项目：后继符号为终结符
                { 
                    f2++;
                    Vt.insert(pro[px].RP[inx]);
                }
                else
                    Vn.insert(pro[px].RP[inx]);
            }
            /* LR(0)文法：若一个文法G的拓广文法G'的活前缀识别自动机中的每个状态不存在下述情况： (1) 既含移进又含归约的项目； (2) 含有多个归约项目。 */
            if ((f1 && f2) || (f1 > 1))
            { 
                cout << "项目集存在冲突不是LR0文法\n";
                return false;
            }
            if (f1 > 0)
            { 
                come.insert(come.begin(), terNum, px);
                action.push_back(come);
                actionF.push_back(true);
                Goto.push_back(vector<int>(nontNum, -1));
                continue;
            }
            else
                actionF.push_back(false);
            come.clear();
            for (j = 0; j < terNum; ++j)
            { 
                if (Vt.find(j) == Vt.end())
                { 
                    come.push_back(-1);
                    continue;
                };
                I.clear();
                for (itSet = C[i].begin(); itSet != C[i].end(); ++itSet)
                { 
                    px = itp[*itSet];
                    pis = proIS[px];
                    inx = *itSet - pis;
                    if (false == pro[px].F[inx] && pro[px].RP[inx] == j)
                        I.insert(*itSet + 1);
                }
                closuer(I);
                for (t = 0; t < C.size(); ++t)
                    if (isSetEqual(C[t], I))
                        break;
                if (t == C.size())
                    C.push_back(I);
                come.push_back(t);
            }
            action.push_back(come);
            come.clear();
            for (j = 0; j < nontNum; ++j)
            { 
                if (Vn.find(j) == Vn.end())
                { 
                    come.push_back(-1);
                    continue;
                }
                I.clear();
                for (itSet = C[i].begin(); itSet != C[i].end(); ++itSet)
                { 
                    px = itp[*itSet];
                    pis = proIS[px];
                    inx = *itSet - pis;
                    if (true == pro[px].F[inx] && pro[px].RP[inx] == j)
                        I.insert(*itSet + 1);
                }
                closuer(I);
                for (t = 0; t < C.size(); ++t)
                    if (isSetEqual(C[t], I))
                        break;
                if (t == C.size())
                    C.push_back(I);
                come.push_back(t);
            }
            Goto.push_back(come);
        }
        cout << "该LR(0)项目集规范族为：" << endl;
        for (i = 0; i < C.size(); ++i)
        { 
            cout << "S" + intToStr(i) << ": ";
            for (itSet = C[i].begin(); itSet != C[i].end(); ++itSet)
            { 
                if (itSet != C[i].begin())
                    cout << " , ";
                px = itp[*itSet];
                pis = proIS[px];
                inx = *itSet - pis;
                cout << nontInx[pro[px].LP] << "->";
                for (j = 0; j < pro[px].F.size(); ++j)
                { 
                    if (inx == j)
                        cout << "·";
                    if (pro[px].F[j])
                        cout << nontInx[pro[px].RP[j]];
                    else
                        cout << terInx[pro[px].RP[j]];
                }
                if (inx == pro[px].F.size())
                    cout << "·";
            }
            cout << endl;
        }
        cout << "LR(0)文法分析表为:\n";
        out(8, "状态");
        for (i = 0, j = terNum / 2 - 1; i < j; ++i)
            out(5, " ");
        out(15, "action");
        if (terNum % 2 == 0)
            out(5, " ");
        for (i = 0, j = terNum / 2 - 1; i < j; ++i)
            out(5, " ");
        for (i = 0, j = nontNum / 2; i < j; ++i)
            out(5, " ");
        out(5, "goto");
        if (nontNum % 2 == 0)
            out(5, " ");
        for (i = 0, j = nontNum / 2; i < j; ++i)
            out(5, " ");
        cout << endl;
        out(8, "");
        for (i = 0; i < terNum; ++i)
            out(5, terInx[i]);
        for (i = 0; i < nontNum; ++i)
            out(5, nontInx[i]);
        cout << endl;
        string oStr;
        for (i = 0; i < C.size(); ++i)
        { 
            if (actionF[i])
            { 
                out(8, "S" + intToStr(i));
                oStr = "r" + intToStr(action[i][0]);
                if (action[i][0])
                    for (j = 0; j < terNum; ++j)
                        out(5, oStr);
                else
                { 
                    for (j = 0; j < terNum - 1; ++j)
                        out(5, "");
                    out(5, "acc");
                }
                for (j = 0; j < nontNum; ++j)
                    out(5, " ");
                cout << endl;
                continue;
            }
            out(8, "S" + intToStr(i));
            for (j = 0; j < terNum; ++j)
                if (action[i][j] == -1)
                    out(5, " ");
                else
                    out(5, "S" + intToStr(action[i][j]));
            for (j = 0; j < nontNum; ++j)
                if (Goto[i][j] == -1)
                    out(5, " ");
                else
                    out(5, "S" + intToStr(Goto[i][j]));
            cout << endl;
        }
        return true;
    }
    string getReStr(int p)
    { 
        string s = "";
        for (int i = p; i < Lsize; ++i)
            s += language[i];
        return s;
    }
    string getState()
    { 
        string s = "", s1;
        for (int t = 0; t < state.size(); ++t)
        { 
            s1 = intToStr(state[t]);
            if (s1.size() > 1)
                s1 = "(" + s1 + ")";
            s += s1;
        }
        return s;
    }
    string getPro(int i)
    { 
        string s = "";
        s += nontInx[pro[i].LP];
        s += "->";
        for (int j = 0; j < pro[i].F.size(); ++j)
            if (pro[i].F[j])
                s += nontInx[pro[i].RP[j]];
            else
                s += terInx[pro[i].RP[j]];
        return s;
    }
    string getSign()
    { 
        string s = "";
        for (int i = 0; i < sign.size(); ++i)
            s += sign[i];
        return s;
    }
    void analysis()
    { 
        sign.clear();
        sign.push_back(terInx[terNum - 1]);
        state.clear();
        state.push_back(0);
        int i = 0, ip = 0, W = 20, Sm, a = ter[language[ip]];
        string oStr;
        out(8, "步骤");
        out(W, "状态栈");
        out(W, "符号栈");
        out(W, "产生式");
        cout << "输入串\n";
        out(8, ++i);
        out(W, "0");
        out(W, terInx[terNum - 1]);
        out(W, "");
        cout << getReStr(ip) << "\n";
        while (++i)
        { 
            Sm = state.back();
            if (actionF[Sm])
            { 
                if (action[Sm][0] == 0 && a == terNum - 1)
                { 
                    cout << "文法识别语言成功" << endl;
                    return;
                }
                else if (action[Sm][0] == 0)
                { 
                    cout << "文法识别语言失败" << endl;
                    return;
                }
                int j = action[Sm][0], size = pro[j].F.size();
                if (pro[j].F[0] == false && pro[j].RP[0] == terNum - 2)
                    size = 0;
                for (int t = 0; t < size; ++t)
                { 
                    state.pop_back();
                    sign.pop_back();
                }
                Sm = state.back();
                S = pro[j].LP;
                sign.push_back(terInx[S]);
                state.push_back(Goto[Sm][S]);
                out(8, i);
                out(W, getState());
                out(W, getSign());
                out(W, getPro(j));
                cout << getReStr(ip) << "\n";
            }
            else if (action[Sm][a] != -1)
            { 
                state.push_back(action[Sm][a]);
                sign.push_back(language[ip]);
                a = ter[language[++ip]];
                out(8, i);
                out(W, getState());
                out(W, getSign());
                out(W, "");
                cout << getReStr(ip) << "\n";
            }
            else
            { 
                cout << "文法识别语言失败" << endl;
                return;
            }
        }
    }

### 测试数据 ###

E 
    2 E S 
    5 a b c @ #
    4
    E 1 S
    S 2 a S
    S 2 b S
    S 1 c
    5 a a b c #

截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201230225609544.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201230225637187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201230225715969.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201230225803101.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191211185808655.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191211185823588.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70