编译原理实验5《LR(1)分析法设计与实现》

迈不过友情╰ 2021-11-11 06:46 815阅读 0赞

#### 实验5《LR(1)分析法设计与实现》 ####

##### 一、实验目的 #####

构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

##### 二、实验内容 #####

程序输入/输出示例（以下仅供参考）：  
  对下列文法，用LR（1）分析法对任意输入的符号串进行分析：

（1）E-E+T
    （2）E-E—T
    （3）T-T*F
    （4）T-T/F
    （5）F-(E)
    （6）F-i

输出的格式如下：  
  (1)LR（1）分析程序，**编制人：姓名，学号，班级**  
  (2)输入一个以\#结束的符号串(包括+—\*/（）i\#)：**在此位置输入符号串**  
  (3)输出过程如下：

<table> 
 <thead> 
  <tr> 
   <th>步骤</th> 
   <th>状态栈</th> 
   <th>符号栈</th> 
   <th>剩余输入串</th> 
   <th>动作</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>0</td> 
   <td>#</td> 
   <td>i+i*i#</td> 
   <td>移进</td> 
  </tr> 
 </tbody> 
</table>

(4)**输入符号串**为非法符号串(或者为合法符号串)  
  备注：  
  1.在“**所用产生式**”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。  
  2.**在此位置输入符号串**为用户自行输入的符号串。  
  注意：  
  1.表达式中允许使用运算符（±\*/）、分割符（括号）、字符i，结束符\#；  
  2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；  
  3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照。

##### 三、实验方法 #####

1．实验采用C++程序语言进行设计，文法写入程序中，用户可以自定义输入语句；  
  2．实验开发工具为Visual Studio Code。

##### 四、实验步骤 #####

1．定义LR(1)分析法实验设计思想及算法  
  ①若ACTION\[sm , ai\] = s则将s移进状态栈，并把输入符号加入符号栈，则三元式变成为：(s0s1…sm s , \#X1X2…Xm ai , ai+1…an\#)；  
  ②若ACTION\[sm , ai\] = rj则将第j个产生式A->β进行归约。此时三元式变为(s0s1…sm-r s , \#X1X2…Xm-rA , aiai+1…an\#)；  
  ③若ACTION\[sm , ai\]为“接收”，则三元式不再变化，变化过程终止，宣布分析成功；  
  ④若ACTION\[sm , ai\]为“报错”，则三元式的变化过程终止，报告错误。  
  2．定义语法构造的代码，与主代码分离，写为头文件LR.h。  
  3．编写主程序利用上文描述算法实现本实验要求。

##### 五、实验结果 #####

1. 实验文法为程序既定的文法，写在头文件LR.h中，运行程序，用户可以自由输入测试语句。  
  2. 实验测试结果：  
  测试结果符合预期结果，程序能够对用户的语句利用LR（1）分析法构建分析表，利用分析栈进行正误分析。实验截图如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 1]

##### 六、实验结论 #####

1．实验利用自定义的源程序进行测试，结果正确，符合预期结果，测试源码及结果截图和说明如上所示。  
  2．实验源码码分为头文件（LR.h）和主文件（test5.cpp）。均如下所示：  
  **LR.h**

#ifndef _LR_
    #define _LR_
     
    using namespace std;
     
    class Grammar{ 
    public:
        //产生式的个数
        int grammarNum ;
        //定义产生式数组
        string formula[100] = { " ","E->E+T","E->T","T->T*F","T->F","F->(E)","F->i"};
     
        Grammar(){ 
            grammarNum = 6;
        }
    };
    //定义LR文法的分析表
    class LRAnalyseTable{ 
    public:
        char terminalChar[100]={ 'i','+','*','(',')','#'};
        //定义终结符的个数
        int terNum =6;
        char nonTerminalChar[100]={ 'E','T','F'};
        //定义非终结符的个数
        int nonTerNum = 3;
        //定义状态数
        int statusNum = 12;
        string action[12][6]={ { "s5","","","s4","",""},{ "","s6","","","","acc"},{ "","r2","s7","","r2","r2"},{ "","r4","r4","","r4","r4"},{ "s5","","","s4","",""},{ "","r6","r6","","r6","r6"},{ "s5","","","s4","",""}
        ,{ "s5","","","s4","",""},{ "","s6","","","s11",""},{ "","r1","s7","","r1","r1"},{ "","r3","r3","","r3","r3"},{ "","r5","r5","","r5","r5"}};
        int goTo[12][3] = { { 1,2,3},{ -1,-1,-1},{ -1,-1,-1},{ -1,-1,-1},{ 8,2,3},{ -1,-1,-1},{ -1,9,3},{ -1,-1,10},{ -1,-1,-1},{ -1,-1,-1},{ -1,-1,-1},{ -1,-1,-1}};
       //获取终结符的索引
        int getTerminalIndex(char var){ 
            for(int i=0;i<terNum;i++){ 
                if(terminalChar[i] == var){ 
                    return i;
                }
            }
            return -1;
        }
        //获取非终结符的索引
        int getNonTerminalIndex(char var){ 
            for(int i=0;i<nonTerNum;i++){ 
                if(nonTerminalChar[i] == var){ 
                    return i;
                }
            }
            return -1;
        }
    };
     
    #endif // _LR_

**test5.cpp**

/************************** Compiler Principle test5 LR(1)分析法设计与实现 author:zz vs code 2019.05.14 ***************************/
    #include <iostream>
    #include <vector>
    #include <iomanip>
    #include <cstring>
    #include <sstream>
    #include "LR.h"
     
    using namespace std;
     
    //定义状态栈
    vector<int> status;
    //定义符号栈
    vector<char> sign;
    //定义输入的字符串
    vector<char> inputStr;
    //记录输入的字符串
    string inputVal;
    //定义文法
    Grammar grammar;
    //定义LR分析表
    LRAnalyseTable analyseTable;
    //读取输入的字符串
    void readStr();
    //对栈容器进行输出,i=0,返回status中的字符串,i=1,返回sign中的字符串，i=2返回inputStr
    string vectTrancStr(int i);
    //总控，对输入的字符串进行分析
    void LRAnalyse();
     
    int main()
    { 
        readStr();
        LRAnalyse();
        return 0;
    }
    //读取输入的字符串
    void readStr(){ 
        char ch;
        cout<<"LR（1）分析程序，编制人：张政，3901170115，软件工程1701班"<<endl;
        cout<<"请输入分析的字符串：";
        cin>>ch;
        while( ch != '#'){ 
            inputVal += ch;
            inputStr.push_back(ch);
            cin>>ch;
        }
       //把#加入容器
       inputStr.push_back('#');
       inputVal += '#';
    }
    //对栈容器进行输出,i=0,返回status中的字符串,i=1,返回sign中的字符串，i=2返回inputStr中的字符串
    string vectTrancStr(int i){ 
        char buf[100];
        int count = 0;
        //输出状态栈
        if(i == 0){ 
            vector<int>::iterator it =status.begin();
            //将数字转化为字符串
            string str,tempStr;
            for(it;it!= status.end();it++){ 
                stringstream ss;
                ss << *it;
                ss >> tempStr;
                str+=tempStr;
            }
            return str;
        }
        //输出符号栈
        else if(i == 1){ 
            vector<char>::iterator it = sign.begin();
            for(it ; it != sign.end() ;it++){ 
                buf[count] = *it;
                count++;
            }
        }
        //输出待分析的字符串
        else{ 
            vector<char>::iterator it = inputStr.begin();
            for(it ; it != inputStr.end();it++){ 
                buf[count] = *it;
                count++;
            }
        }
        buf[count] = '\0';
        string str(buf);
        return str;
    }
    //总控，对输入的字符串进行分析
    void LRAnalyse(){ 
        //步骤
        int step = 1;
        //把状态0入栈
        status.push_back(0);
        //把#加入符号栈
        sign.push_back('#');
        //输出初始栈状态
        cout<<setw(10)<<"步骤"<<setw(10)<<"状态栈"<<setw(10)<<"符号栈"<<setw(10)<<"输入串"<<setw(25)<<"动作说明"<<endl;
        //初始状态
        int s =0;
        //保存之前的状态
        int oldStatus;
        //获取初始符号
        char ch = inputStr.front();
        //如果action[s][ch] =="acc" ，则分析成功
        while(analyseTable.action[s][analyseTable.getTerminalIndex(ch)] != "acc"){ 
            //获取字符串
            string str = analyseTable.action[s][analyseTable.getTerminalIndex(ch)];
            //如果str为空，报错并返回
            if(str.size() == 0){ 
                cout<<"出错"<<endl;
                cout<<inputVal<<"为非法符号串"<<endl;
                return ;
            }
            //获取r或s后面的数字
            stringstream ss;
            ss << str.substr(1);
            ss >> s;
            //如果是移进
            if(str.substr(0,1) == "s"){ 
                cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0)<<setw(10)<<vectTrancStr(1)<<setw(10)<<vectTrancStr(2)<<setw(10)<<"A"<<"CTION["<<status.back()<<","<<ch<<"]=S"<<s<<","<<"状态"<<s<<"入栈"<<endl;
                //输入符号入栈
                sign.push_back(ch);
                inputStr.erase(inputStr.begin());
                //将状态数字入栈
                status.push_back(s);
            }
            //如果是归约
            else if(str.substr(0,1) == "r"){ 
                //获取第S个产生式
                string formu = grammar.formula[s];
                //cout<<s<<endl;
                int strSize = formu.size();
                //将产生式转化为字符数组
                char buf[100];
                strcpy(buf,formu.c_str());
                //获取产生式的首字符
                char nonTerCh = buf[0];
                //获取符号栈的出栈次数
                int popCount = strSize - 3;
                //反向迭代
                vector<int>::reverse_iterator rit = status.rbegin();
                int i= 0;
                for(rit;rit != status.rend();rit++){ 
                    i++;
                    if(i == popCount+1){ 
                        oldStatus = * rit;
                        break;
                    }
                }
                int r = s;
                //修改s
                s = analyseTable.goTo[oldStatus][analyseTable.getNonTerminalIndex(nonTerCh)];
                cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0)<<setw(10)<<vectTrancStr(1)<<setw(10)<<vectTrancStr(2)<<setw(10)<<"r"<<r<<(string)":"+grammar.formula[r]+(string)"归约,GOTO{"<<oldStatus<<","<<nonTerCh<<")="<<s<<"入栈"<<endl;
                //对符号栈进行出栈和状态栈进行出栈
                for(int i=0 ;i< popCount;i++){ 
                    sign.pop_back();
                    status.pop_back();
                }
                //再对产生式的开始符号入栈
                sign.push_back(nonTerCh);
                //再把新的状态入栈
                status.push_back(s);
            }
            else{ 
               //什么都不处理
            }
            //步骤数加1
            step++;
     
            //获取栈顶状态
            s = status.back();
            //获取输入的字符
            ch = inputStr.front();
        }
        cout<<setw(10)<<step<<setw(10)<<vectTrancStr(0)<<setw(10)<<vectTrancStr(1)<<setw(10)<<vectTrancStr(2)<<setw(10)<<"A"<<"cc:分析成功"<<endl;
        cout<<inputVal<<"为合法符号串"<<endl;
    }

##### 七、实验小结 #####

1．本次实验是利用LR（1）分析法进行语法分析，通过代码实现后更加了解了LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。  
  2．LR分析法小结：  
   LR(0)构造的DFA，但是由LR（0）的DFA来构造分析表往往是不可行的，也就是说很少有语言是LR(0)的。  
   如果LR(0)的冲突可以根据当前输入的字符来解决，则构造的分析表为SLR分析表，SLR分析表跟LR(0)的dfa是相同的。  
   LR(1)构造的DFA考虑当前输入的字符，所以构造的DFA中存在的冲突比较少，也就是说它接受的语言就比较多。构造分析表时，不用额外的约束，因为它在构造dfa时就已经考虑了当前的输入字符。  
   考虑到LR(1)的dfa包含的状态太多，而且许多状态的不同仅仅是因为预测符的不同而已。通过合并不会产生冲突的状态，可以减少dfa的状态数，这就产生了LALR分析法。所以说LALR分析法只是对LR(1)的一种简化：通过合并同心集。  
   分析法的分析能力比较：LR(1)>LALR>SLR(1)>LR(0)。

参考文章：【1】[LR(1)分析法的总控的实现（C++实现）][LR_1_C]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]: /images/20211109/ba58a943b1a94081a4c231fd5bc13280.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 1]: /images/20211109/5c9b7b29042541f5b91830bac0e6d776.png
[LR_1_C]: https://blog.csdn.net/qq_39559641/article/details/84103000