c++实现LL1文法

港控/mmm° 2023-06-12 11:25 1阅读 0赞

### c++实现LL1文法 ###

*   *   *  简介
         *  参考代码
         *  测试
         *   *  输入数据
             *  截屏

### 简介 ###

利用c++计算文法的firsr,follow,select 集合，然后判断文法是否为LL1文法，并构造预测分析表，对输入字符串进行分析

### 参考代码 ###

#include <iostream>
    #include <map>
    #include <vector>
    #include <set>
    #include <list>
    #include <cstdio>
    #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 leftPart;          //左部非终结符的索引
        vector<int> rightPart; // 右边产生式索引
        vector<bool> flag;     //标记右边相关产生式是终结符（false），非终结符（false)
    };
    vector<Production> pro; //产生式
    vector<int> *nontPro;   // 各个非终结符的产生式的集合
    vector<bool> proEmpty;  //记录各个产生式能否推出空 true能，false不能
    set<int> *First;        //各个非终结符的First集合
    #define FirstIt(x) for (itSet = First[(x)].begin(); itSet != First[(x)].end(); ++itSet)
    set<int> *Follow; // 各个非终结符的Follow集合
    #define FollowIt(x) for (itSet = Follow[(x)].begin(); itSet != Follow[(x)].end(); ++itSet)
    set<int> *Select; //各个产生式的Select的集合
    #define SelectIt(x) for (itSet = Select[(x)].begin(); itSet != Select[(x)].end(); ++itSet)
    set<int>::iterator itSet; // set迭代集合
    struct edge
    { 
        int v, s; //u->v一条边 s代表状态，1 终结符,
        edge(int v, int s) : v(v), s(s) { }
    };                         //利用关系图法求解First
    vector<int> *graph;        //图
    int *inDe;                 //计算入度
    vector<int> top;           //定义出栈顺序，即计算顺序
    vector<int> nontEmpty;     //能否推出空，0未定，1代表是，2代表否
    vector<int> *analyzeTable; //构造LL1文法的预测分析表
    struct Sign
    { 
        int Inx;
        bool flag; //符合索引 表示文法分析栈中的字符是否为非终结符 true 非终结符
        Sign(int a, bool b) : Inx(a), flag(b) { }
        Sign() { }
    };
    vector<Sign> analysisStack; //用数组模拟LL1文法分析栈
    #define out(width, str) cout << setw((width)) << setiosflags(ios::left) << ((str))
    void getEmpty();        //求非终结符能否推出空集
    void geFirst();         //计算文法First集合
    void getFollow();       //计算文法Follow集合
    void getSelect();       //计算产生式的Select集合
    bool judegLL1();        //判断是否为LL1文法
    void getAnalyzeTable(); //得到LL1文法的预测分析表
    void analysis();        //对所得语言进行分析
    int main()
    { 
        cout << "请输入文法开始符合：";
        cin >> start;
        cout << "请输入非终结符的数目：";
        cin >> nontNum;
        First = new set<int>[nontNum];
        Follow = new set<int>[nontNum];
        nontPro = 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;
        Select = new set<int>[proSize];
        proEmpty.insert(proEmpty.begin(), proSize, false);
        cout << "请依次输入产生式：";
        int t;
        Production p;
        for (int i = 0; i < proSize; ++i)
        { 
            cin >> S >> t;
            p.leftPart = nonter[S];
            nontPro[p.leftPart].push_back(i);
            for (int j = 0; j < t; ++j)
            { 
                cin >> S;
                if (nonter.find(S) != nonter.end())
                { 
                    p.rightPart.push_back(nonter[S]);
                    p.flag.push_back(true);
                }
                else
                { 
                    p.rightPart.push_back(ter[S]);
                    p.flag.push_back(false);
                }
            }
            pro.push_back(p);
            p.rightPart.clear();
            p.flag.clear();
        }
        getEmpty();
        geFirst();
        getFollow();
        getSelect();
        if (judegLL1() == false)
            return 0;
        getAnalyzeTable();
        cout << "请输入要分析的语言的长度: ";
        cin >> Lsize;
        cout << "请输入要分析的语言(带输入结束符)：";
        for (int i = 0; i < Lsize; ++i)
        { 
            cin >> S;
            language.push_back(S);
        }
        analysis();
    }
    void getEmpty()
    { 
        nontEmpty.clear();
        nontEmpty.insert(nontEmpty.begin(), nontNum, 0); //初始化
        vector<int> nonProNum(nontNum, 0);
        list<int> wait;
        int nul = terNum - 2, j, i, ltmp;
        for (int i = 0; i < proSize; ++i)
        { 
            for (j = 0, ltmp = pro[i].leftPart; j < pro[i].flag.size(); ++j)
            { 
                if (pro[i].flag[j] == false && pro[i].rightPart[j] == nul)
                    nontEmpty[ltmp] = 1;
                if (pro[i].flag[j] == false)
                    break;
            }
            if (j == pro[i].flag.size())
            { 
                wait.push_front(i);
                nonProNum[ltmp]++;
            }
        }
        for (int i = 0; i < nontNum; ++i)
        { 
            if (nontEmpty[i] == 0 && nonProNum[i] == 0)
                nontEmpty[i] = 2;
        }
        list<int>::iterator itlist = wait.begin();
        while (itlist != wait.end())
        { 
            ltmp = pro[*itlist].leftPart;
            if (nontEmpty[ltmp])
                itlist = wait.erase(itlist), nonProNum[ltmp]--;
            else
                ++itlist;
        }
        itlist = wait.begin();
        while (!wait.empty())
        { 
            if (itlist == wait.end())
                itlist = wait.begin();
            ltmp = pro[*itlist].leftPart;
            if (nontEmpty[ltmp])
            { 
                itlist = wait.erase(itlist);
                continue;
            }
            for (j = 0, i = *itlist; j < pro[i].flag.size(); ++j)
            { 
                if (nontEmpty[pro[i].rightPart[j]] == 2)
                { 
                    itlist = wait.erase(itlist);
                    nonProNum[ltmp]--;
                    if (nonProNum[ltmp] == 0)
                        nontEmpty[ltmp] = 2;
                    break;
                }
                else if (nontEmpty[pro[i].rightPart[j]] == 0)
                { 
                    itlist++;
                    break;
                }
            }
            if (j == pro[i].flag.size())
            { 
                nontEmpty[ltmp] = 1;
                itlist = wait.erase(itlist);
            }
        }
    }
    void topSort()
    { 
        int *sta = new int[nontNum];
        int p = 0, v, u;
        top.clear();
        for (int i = 0; i < nontNum; ++i)
            if (inDe[i] == 0)
                sta[p++] = i;
        while (p)
        { 
            v = sta[--p];
            top.push_back(v);
            for (int i = 0; i < graph[v].size(); ++i)
            { 
                u = graph[v][i];
                inDe[u]--;
                if (!inDe[u])
                    sta[p++] = u;
            }
        }
    }
    void geFirst()
    { 
        int i, j, ltmp, rtmp;
        delete[] graph;
        graph = new vector<int>[nontNum];
        delete[] inDe;
        inDe = new int[nontNum];
        for (i = 0; i < nontNum; ++i)
            inDe[i] = 0;
        for (i = 0; i < proSize; ++i)
        { 
            for (j = 0, ltmp = pro[i].leftPart; j < pro[i].flag.size(); ++j)
            { 
                rtmp = pro[i].rightPart[j];
                if (pro[i].flag[j])
                { 
                    graph[rtmp].push_back(ltmp);
                    inDe[ltmp]++;
                    if (nontEmpty[rtmp] == 2)
                        break;
                }
                else if (rtmp != terNum - 2)
                { 
                    First[ltmp].insert(rtmp);
                    break;
                }
            }
        }
        topSort();
        for (i = 0; i < top.size(); ++i)
        { 
            for (ltmp = top[i], itSet = First[ltmp].begin(); itSet != First[ltmp].end(); ++itSet)
            { 
                for (j = 0; j < graph[ltmp].size(); ++j)
                    First[graph[ltmp][j]].insert(*itSet);
            }
        }
        for (int i = 0; i < nontNum; ++i)
            if (nontEmpty[i] == 1)
                First[i].insert(terNum - 2);
        cout << "各个非终结符的First集为: " << endl;
        for (int i = 0; i < nontNum; ++i)
        { 
            cout << "First( " << nontInx[i] << " ) = { ";
            FirstIt(i) cout << terInx[*itSet] << " ";
            cout << "}\n";
        }
    }
    void getFollow()
    { 
        int i, j, ltmp, rtmp, folFlag;
        delete[] graph;
        graph = new vector<int>[nontNum];
        delete[] inDe;
        inDe = new int[nontNum];
        for (i = 0; i < nontNum; ++i)
            inDe[i] = 0;
        Follow[nonter[start]].insert(terNum - 1);
        for (i = 0; i < proSize; ++i)
        { 
            folFlag = true;
            ltmp = pro[i].leftPart;
            for (j = pro[i].flag.size() - 1; j > 0; --j)
            { 
                rtmp = pro[i].rightPart[j];
                if (pro[i].flag[j - 1])
                { 
                    if (pro[i].flag[j])
                    { 
                        FirstIt(rtmp) if (*itSet != terNum - 2) Follow[pro[i].rightPart[j - 1]].insert(*itSet);
                    }
                    else
                        Follow[pro[i].rightPart[j - 1]].insert(rtmp), folFlag = false;
                }
                if (folFlag)
                { 
                    graph[ltmp].push_back(rtmp);
                    inDe[rtmp]++;
                    if (nontEmpty[rtmp] == 2)
                        folFlag = false;
                }
            }
            if (pro[i].flag[0] && folFlag)
            { 
                graph[ltmp].push_back(pro[i].rightPart[0]);
                inDe[rtmp]++;
            }
        }
        inDe[nonter[start]] = 0;
        topSort();
        for (i = 0; i < top.size(); ++i)
        { 
            for (ltmp = top[i], itSet = Follow[ltmp].begin(); itSet != Follow[ltmp].end(); ++itSet)
            { 
                for (j = 0; j < graph[ltmp].size(); ++j)
                    Follow[graph[ltmp][j]].insert(*itSet);
            }
        }
        cout << "各个非终结符的Follow集为: " << endl;
        for (i = 0; i < nontNum; ++i)
        { 
            cout << "Follow( " << nontInx[i] << " ) = { ";
            FollowIt(i) cout << terInx[*itSet] << " ";
            cout << "}\n";
        }
    }
    
    void getSelect()
    { 
        int i, j, ltmp, rtmp;
        for (i = 0; i < proSize; ++i)
        { 
            for (j = 0, ltmp = pro[i].leftPart; j < pro[i].flag.size(); ++j)
            { 
                if (pro[i].flag[j])
                { 
                    rtmp = pro[i].rightPart[j];
                    FirstIt(rtmp) Select[i].insert(*itSet);
                    if (nontEmpty[rtmp] == 2)
                        break;
                }
                else
                { 
                    Select[i].insert(pro[i].rightPart[j]);
                    break;
                }
            }
            if (pro[i].flag[0] == false && pro[i].rightPart[0] == terNum - 2)
            { 
                FollowIt(ltmp) Select[i].insert(*itSet);
                proEmpty[i] = true;
            }
            if (j == pro[i].flag.size())
            { 
                FollowIt(ltmp) Select[i].insert(*itSet);
                proEmpty[i] = true;
            }
            Select[i].erase(terNum - 2);
        }
        cout << "各个产生式的Select集为: " << endl;
        for (i = 0; i < proSize; ++i)
        { 
            cout << "Select( " << nontInx[pro[i].leftPart] << "->";
            for (j = 0; j < pro[i].flag.size(); ++j)
                if (pro[i].flag[j])
                    cout << nontInx[pro[i].rightPart[j]];
                else
                    cout << terInx[pro[i].rightPart[j]];
            cout << ") = { ";
            SelectIt(i) cout << terInx[*itSet] << " ";
            cout << "}\n";
        }
    }
    
    bool judegLL1()
    { 
        for (int i = 0; i < nontNum; ++i)
        { 
            for (int j = 0; j < nontPro[i].size() - 1; ++j)
            { 
                for (int t = j + 1; t < nontPro[i].size(); ++t)
                { 
                    if (proEmpty[j] && proEmpty[t])
                        continue; //两个产生式都能产生空
                    for (itSet = Select[nontPro[i][j]].begin(); itSet != Select[nontPro[i][j]].end(); ++itSet)
                    { 
                        if (Select[nontPro[i][t]].find(*itSet) != Select[nontPro[i][t]].end())
                        { 
                            cout << terInx[*itSet] << "是产生式" << nontPro[i][j] << "和" << nontPro[i][t] << "的Select集合的交集，不是LL1文法\n";
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
    void getAnalyzeTable()
    { 
        analyzeTable = new vector<int>[nontNum]; //初始化-1，nontNum-1 表示#
        for (int i = 0; i < nontNum; ++i)
            analyzeTable[i].insert(analyzeTable[i].begin(), terNum, -1);
        for (int i = 0; i < proSize; ++i)
        { 
            SelectIt(i) analyzeTable[pro[i].leftPart][*itSet] = i;
        }
        cout << "该文法的预测分析表为：\n";
        out(10, " ");
        string outStr;
        for (int i = 0; i < terNum; ++i)
            out(10, terInx[i]);
        cout << endl;
        for (int i = 0; i < nontNum; ++i)
        { 
            out(10, nontInx[i]);
            for (int j = 0; j < terNum; ++j)
                if (analyzeTable[i][j] == -1)
                    out(10, " ");
                else
                { 
                    outStr = "->";
                    for (int t = analyzeTable[i][j], c = 0; c < pro[t].flag.size(); ++c)
                        if (pro[t].flag[c])
                            outStr += nontInx[pro[t].rightPart[c]];
                        else
                            outStr += terInx[pro[t].rightPart[c]];
                    out(10, outStr);
                }
            cout << endl;
        }
    }
    
    void analysis()
    { 
        int i = 0, ip = 0, outW = 30;
        Sign X;
        string outS = "";
        out(10, "步骤");
        out(outW, "分析栈");
        out(outW, "剩余输入串");
        out(outW, "所用产生式");
        cout << endl;
        analysisStack.clear();
        analysisStack.push_back(Sign(terNum - 1, false));
        analysisStack.push_back(Sign(nonter[start], true)); //对分析栈进行初始化
        while (++i)
        { 
            X = analysisStack.back();
            analysisStack.pop_back();
            if (X.flag == false && X.Inx == terNum - 1)
            { 
                if (terInx[X.Inx] == language[ip])
                { 
                    out(10, i);
                    out(outW, terInx[terNum - 1]);
                    out(outW, terInx[terNum - 1]);
                    out(outW, "接受");
                    cout << "\n";
                    return;
                }
                else
                { 
                    cout << "你输入的语言该文法无法识别\n";
                    return;
                }
            }
            else if (X.flag == false)
            { 
                if (terInx[X.Inx] == language[ip])
                { 
                    outS = "";
                    for (int t = 0; t < analysisStack.size(); ++t)
                        if (analysisStack[t].flag)
                            outS += nontInx[analysisStack[t].Inx];
                        else
                            terInx[analysisStack[t].Inx];
                    outS += terInx[X.Inx];
                    out(10, i);
                    out(outW, outS);
                    outS = "";
                    for (int t = ip; t < language.size(); ++t)
                        outS += language[t];
                    out(outW, outS);
                    outS = "";
                    outS += language[ip];
                    out(outW, outS + "匹配");
                    cout << endl;
                    ++ip;
                }
                else
                { 
                    cout << "你输入的语言该文法无法识别\n";
                    return;
                }
            }
            else
            { 
                int pos = analyzeTable[X.Inx][ter[language[ip]]];
                if (pos == -1)
                { 
                    cout << "你输入的语言该文法无法识别\n";
                    return;
                }
                outS = "";
                for (int t = 0; t < analysisStack.size(); ++t)
                    if (analysisStack[t].flag)
                        outS += nontInx[analysisStack[t].Inx];
                    else
                        terInx[analysisStack[t].Inx];
                outS += terInx[X.Inx];
                out(10, i);
                out(outW, outS);
                outS = "";
                for (int t = ip; t < language.size(); ++t)
                    outS += language[t];
                out(outW, outS);
                outS = "";
                outS += nontInx[X.Inx];
                outS += "->";
                for (int t = 0; t < pro[pos].flag.size(); ++t)
                    if (pro[pos].flag[t])
                        outS += nontInx[pro[pos].rightPart[t]];
                    else
                        outS += terInx[pro[pos].rightPart[t]];
                out(outW, outS);
                cout << endl;
                if (pro[pos].flag[0] == false && proEmpty[pos])
                    continue;
                for (int t = pro[pos].flag.size() - 1; t >= 0; --t)
                    if (pro[pos].flag[t])
                        analysisStack.push_back(Sign(pro[pos].rightPart[t], true));
                    else
                        analysisStack.push_back(Sign(pro[pos].rightPart[t], false));
            }
        }
    }

### 测试 ###

#### 输入数据 ####

S 
    5   S A B C D
    5   a b c @ # 
    10
    S 2 A B
    S 2 b C
    A 1 @
    A 1 b
    B 1 @
    B 2 a D
    C 2 A D
    C 1 b
    D 2 a S
    D 1 c

#### 截屏 ####

![在这里插入图片描述][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]: https://img-blog.csdnimg.cn/20191113145038855.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/20191113145053280.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70