编译原理实验（二）——LL（1）文法语法分析

小咪咪 2023-05-30 09:15 9阅读 0赞

### 编译原理实验（二）——LL（1）文法语法分析 ###

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

### 实验要求 ###

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

### 参考程序 ###

#include <iostream>
    #include <string>
    #include <map>
    #include <stack>
    #include <vector>
    #include <iomanip>
    using namespace std;
    
    const int maxSize = 10; //定义分析表的最大大小
    const string errorstr = "你输入的语言该文法无法识别";
    const int outWidth = 30; //设置输出字符串所占宽度
    
    string LL1ForecastAnalysisTable[maxSize][maxSize]; //分析表的具体的内容
    int terminatorNum;                                 //输入终结符的数量
    int nonterminatorNum;                              //输入非终结符的数量
    map<char, int> terminatorSet;                      //输入终结符的集合，用map 映射表示在分析表的第几列
    map<char, int> nonterminatorSet;                   //输入非终结符的集合，用map 映射表示在分析表的第几行
    vector<char> analysisStack;                        //为了更好的输出栈中的内容，用vector数组模拟栈行为
    
    void analysisProcess(string); //对输入的语言用LL1预测分析表进行分析
    char S;
    
    int main()
    { 
        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 << "请输入开始符合：";
        cin >> S;
        cout << "请依次输入分析表的内容，对于出错错误的请输入单个英文字符_:\n";
        for (int i = 1; i <= nonterminatorNum; ++i)
        { 
            for (int j = 1; j <= terminatorNum; ++j)
            { 
                cin >> LL1ForecastAnalysisTable[i][j];
            }
        }
        cout << "请输入要分析语言: ";
        string L;
        cin >> L;
        analysisProcess(L);
    }
    
    void analysisProcess(string str)
    { 
        cout << " 步骤 分析栈 剩余输入串 所用产生式" << endl;
        int i = 0, ip = 0;     //i代表进行到第几步 a是分析到输入语言字符串第几个
        char X, a = str[ip];   //分析栈栈顶符号
        str += "#";            //在语言末尾加入输入结束符
        analysisStack.clear(); //使分析栈为空
        analysisStack.push_back('#');
        analysisStack.push_back(S); //初始化将’#’压入堆栈中，将开始符号S压入栈中
        string outStack, outStr;
        while (++i)
        { 
            X = analysisStack.back();
            analysisStack.pop_back();
            if (X == '#')
            { 
                if (X == a)
                { 
                    cout << setw(10) << setiosflags(ios::left) << i << setw(outWidth);
                    cout << setiosflags(ios::left) << "#" << setw(outWidth) << setiosflags(ios::left) << "#"
                         << "接受\n";
                }
                else
                { 
                    cout << errorstr << endl;
                }
                return;
            }
            else if (terminatorSet[X])
            { 
                if (X == a)
                { 
                    outStack = "";
                    for (int i = 0; i < analysisStack.size(); ++i)
                        outStack += analysisStack[i];
                    outStack += X;
                    cout << setw(10) << setiosflags(ios::left) << i << setw(outWidth) << setiosflags(ios::left) << outStack;
                    outStr = "";
                    for (int t = ip; t < str.size(); ++t)
                        outStr += str[t];
                    cout << setw(outWidth) << setiosflags(ios::left) << outStr << a << "匹配\n";
                    a = str[++ip];
                }
                else
                { 
                    cout << errorstr << endl;
                    return;
                }
            }
            else
            { 
                int row = nonterminatorSet[X], col = terminatorSet[a];
                string f = LL1ForecastAnalysisTable[row][col]; //获取文法产生式
                if (f == "_")
                { 
                    cout << errorstr << endl;
                    return;
                }
                outStack = "";
                for (int i = 0; i < analysisStack.size(); ++i)
                    outStack += analysisStack[i];
                outStack += X;
                cout << setw(10) << setiosflags(ios::left) << i << setw(outWidth) << setiosflags(ios::left) << outStack;
                outStr = "";
                for (int t = ip; t < str.size(); ++t)
                    outStr += str[t];
                cout << setw(outWidth) << setiosflags(ios::left) << outStr << X << "->" << f << endl;
                if (f != "@")
                    for (int j = f.size() - 1; j >= 0; --j)
                        analysisStack.push_back(f[j]);
            }
        }
    }

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

输入的终结符与终结符都为单个字符  
空( ε \\varepsilon ε)用@表示

#### 实验结果 ####

对于文法  
E->TA  
A->+TA|@  
T->FB  
B->\*FB|@  
F->(E)|i  
分析表为  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]  
输入数据为

6 
    i + * (  ) #
    5
    E A T B F
    E
    
    TA _ _ TA _ _ 
    _ +TA _ _ @ @
    FB _ _ FB _ _
    _ @ *FB _ @ @
    i _ _ (E) _ _
    
    i+i*i

##### 截图 #####

![在这里插入图片描述][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/20191109090236146.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/20191109090401668.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70