编译原理实验（三）——LR（0）语法分析

古城微笑少年丶 2023-05-30 09:16 107阅读 0赞

### 编译原理实验（三）——LR（0）语法分析 ###

*   *   *  实验要求
         *  参考程序
         *  实验结果
         *   *  程序输入说明
             *  截图

### 实验要求 ###

根据LR(0)分析法编写一个语法分析程序 直接输入根据已知文法构造的分析表M;对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。

### 参考程序 ###

#include <iostream>
    #include <string>
    #include <map>
    #include <vector>
    #include <iomanip>
    using namespace std;
    
    const int maxSize = 20; //输入规模的最大大小
    const string errorstr = "你输入的语言该文法无法识别";
    const int outWidth = 20; //设置输出字符串所占宽度
    
    int terminatorNum;    //输入终结符的数量
    int nonterminatorNum; //输入非终结符的数量
    int stateNum;         //输入状态数
    int num;              //输入产生式个数
    int Goto[maxSize][maxSize];
    char action[maxSize][maxSize];
    int terAction[maxSize][maxSize];
    string chang[maxSize];           //产生式
    map<char, int> terminatorSet;    //输入终结符的集合，用map 映射表示在分析表的第几列
    map<char, int> nonterminatorSet; //输入非终结符的集合，用map 映射表示在分析表的第几行
    vector<char> signStack;          // 符合栈为了更好的输出栈中的内容，用vector数组模拟栈行为
    vector<int> stateStack;          // LR0文法状态栈
    
    void analysisProcess(string); //对输入的语言用LL1预测分析表进行分析
    string intToString(int);      //将整数转化为字符串，并且大于9的数+()
    
    int main()
    { 
        cout << "请输入产生式的个数：";
        cin >> num;
        cout << "请按顺序输入产生式：\n";
        for (int i = 1; i <= num; ++i)
            cin >> chang[i];
        cout << "请输入终结符的个数：";
        cin >> terminatorNum;
        char str;
        cout << "请依次按照分析表输入终结符(包含结束符#)：" << endl;
        for (int i = 1; i <= terminatorNum; ++i)
        { 
            cin >> str;
            terminatorSet[str] = i;
        }
        cout << "请输入非终结符的个数：";
        cin >> nonterminatorNum;
        cout << "请依次按照分析表输入终结符：" << endl;
        for (int i = 1; i <= nonterminatorNum; ++i)
        { 
            cin >> str;
            nonterminatorSet[str] = i;
        }
        cout << "请输入最后一个状态数（从0开始）：";
        cin >> stateNum;
        cout << "请依次输入非终结符goto表的内容，对于出错错误的请输入-1:\n";
        for (int i = 0; i <= stateNum; ++i)
        { 
            for (int j = 1; j <= nonterminatorNum; ++j)
            { 
                cin >> Goto[i][j];
            }
        }
        cout << "请依次输入终结符action的内容，对于出错错误的请输入-1:\n";
        cout << "输入格式按照 移进(S state) 规约(R state) 接受(A -1) 出错(E -1),state代表状态数\n";
        for (int i = 0; i <= stateNum; ++i)
        { 
            for (int j = 1; j <= terminatorNum; ++j)
            { 
                cin >> action[i][j] >> terAction[i][j];
            }
        }
        cout << "请输入要分析语言: ";
        string L;
        cin >> L;
        analysisProcess(L);
    }
    
    void analysisProcess(string str)
    { 
        str += "#";
        cout << setw(outWidth) << setiosflags(ios::left) << "步骤";
        cout << setw(outWidth) << setiosflags(ios::left) << "状态栈";
        cout << setw(outWidth) << setiosflags(ios::left) << "符号栈";
        cout << setw(outWidth) << setiosflags(ios::left) << "产生式"
             << "输入串" << endl;
        signStack.clear();
        stateStack.clear(); //清空状态栈，符合栈
        signStack.push_back('#');
        stateStack.push_back(0);        //初始化符合栈，状态栈
        int i = 0, ip = 0;              //i代表进行到第几步 a是分析到输入语言字符串第几个
        int Sm;                         //当前状态栈栈顶状态
        int a = terminatorSet[str[ip]]; //当前剩余输入串的首字符在输入终结符表的位置
        cout << setw(outWidth) << setiosflags(ios::left) << (++i);
        cout << setw(outWidth) << setiosflags(ios::left) << "0";
        cout << setw(outWidth) << setiosflags(ios::left) << "#";
        cout << setw(outWidth) << setiosflags(ios::left) << " " << str << endl;
        string outStr;
        while (++i)
        { 
            Sm = stateStack.back();
            if (action[Sm][a] == 'S')
            { 
                /* 移进：当前输入符号ai移进符号栈，将action表中指出的状态S进状态栈 */
                //cout<<terAction[Sm][a];
                stateStack.push_back(terAction[Sm][a]);
                signStack.push_back(str[ip]);
                a = terminatorSet[str[++ip]];
                cout << setw(outWidth) << setiosflags(ios::left) << i;
                outStr = "";
                for (int t = 0; t < stateStack.size(); ++t)
                    outStr += intToString(stateStack[t]);
                cout << setw(outWidth) << setiosflags(ios::left) << outStr;
                outStr = "";
                for (int t = 0; t < signStack.size(); ++t)
                    outStr += signStack[t];
                cout << setw(outWidth) << setiosflags(ios::left) << outStr;
                cout << setw(outWidth) << setiosflags(ios::left) << " " << str.substr(ip) << endl;
            }
            else if (action[Sm][a] == 'R')
            { 
                int j = terAction[Sm][a];
                int size = chang[j].size() - 3;
                if (chang[j][3] == '@')
                    size = 0; //为空产生式
                for (int t = 0; t < size; ++t)
                    stateStack.pop_back();
                for (int t = 0; t < size; ++t)
                    signStack.pop_back();
                Sm = stateStack.back();
                char A = chang[j][0]; //规约符号
                signStack.push_back(A);
                stateStack.push_back(Goto[Sm][nonterminatorSet[A]]);
                cout << setw(outWidth) << setiosflags(ios::left) << i;
                outStr = "";
                for (int t = 0; t < stateStack.size(); ++t)
                    outStr += intToString(stateStack[t]);
                cout << setw(outWidth) << setiosflags(ios::left) << outStr;
                outStr = "";
                for (int t = 0; t < signStack.size(); ++t)
                    outStr += signStack[t];
                cout << setw(outWidth) << setiosflags(ios::left) << outStr;
                cout << setw(outWidth) << setiosflags(ios::left) << chang[j] << str.substr(ip) << endl;
            }
            else if (action[Sm][a] == 'A')
            { 
                cout << "该文法识别该语言" << endl;
                return;
            }
            else
            { 
                cout << errorstr << endl;
                return;
            }
        }
    }
    
    string intToString(int num)
    { 
        int j = num;
        if (j == 0)
            return "0";
        string str = "";
        while (j)
        { 
            str += char(j % 10 + '0');
            j /= 10;
        }
        str.reserve();
        if (num > 9)
            str = "(" + str + ")";
        return str;
    }

### 实验结果 ###

#### 程序输入说明 ####

输入的终结符与终结符都为单个字符  
空( ε \\varepsilon ε)用@表示  
参考文法:  
![在这里插入图片描述][20191109091451259.png]  
分析表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]  
输入数据案例

4
    S->aAcBe
    A->b
    A->Ab
    B->d
    
    6
    a c e b d #
    
    3 
    S A B
    
    9
    1 -1 -1
    -1 -1 -1
    -1 3 -1
    -1 -1 -1
    -1 -1 -1
    -1 -1 7
    -1 -1 -1
    -1 -1 -1
    -1 -1 -1
    -1 -1 -1
    
    S  2 E -1 E -1	E -1	E -1	E -1
    E -1	E -1	E -1	E -1	E -1	A -1
    E -1	E -1	E -1	S 4	E -1	E -1
    E -1	S 5	E -1	S 6	E -1	E -1
    R 2	R 2	R 2	R 2	R 2	R 2
    E -1	E -1	E -1	E -1	S 8	E -1
    R 3	R 3	R 3	R 3	R 3	R 3
    E -1	E -1	S 9	E -1	E -1	E -1
    R 4	R 4	R 4	R 4	R 4	R 4
    R 1	R 1	R 1	R 1	R 1	R 1
    
    abbcde

#### 截图 ####

![在这里插入图片描述][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]

[20191109091451259.png]: https://img-blog.csdnimg.cn/20191109091451259.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191109091515894.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/20191109091634212.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/20191109091647211.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70