编译原理：基于SLR(1)分析法的语法制导翻译及中间代码生成

原创文章，转载、引用请注明出处！

---

写在前面

此为编译原理课程的最后一个与算法有关的实验博客。

总的来说还是很不容易的。5个算法，难度依次递增，coding时间、代码量也是依次递增，不过写出它们的快乐也是依次递增的。说起来也是自己给自己增加coding难度，为了在所有代码中保持贯穿一致的数据结构，多做了很多的工作。不过写到现在也觉得这些工作是非常值得的，不管是看起来还是用起来都是十分赏心悦目的。

尤其是这一次，大概是几个实验中bug最少的一个了。当我把用代码生成的DFA和我手写的DFA进行对比，发现完全一模一样的时候，那真的是非常开心了！写到现在，对于C++ STL的运用也更加的娴熟，这也是我学习这门课程的意外收获之一。

本博客会对之前4个博客的内容做综合总结。

---

目标任务

要求

完成以下描述赋值语句 SLR(1)文法语法制导生成中间代码四元式的过程。

G[E]:
A -> V=E
E -> E+T∣E-T∣T
T -> T*F∣T/F∣F
F -> (E)∣i
V -> i

设计说明

终结符号i为用户定义的简单变量，即标识符的定义。

设计要求

• (1) 构造文法的 SLR(1)分析表，设计语法制导翻译过程，给出每一产生式对应的语义动作;

• (2) 设计中间代码四元式的结构;

• (3) 输入串应是词法分析的输出二元式序列，即某赋值语句“专题1”的输出结果，输出为赋值语句的四元式序列中间文件;

• (4) 设计两个测试用例(尽可能完备，正确和出错)，并给出测试结果;

---

解答

SLR(1)分析法

概念

由于大多数适用的程序设计语言的文法不能满足LR(O)文法的条件，即使是描述一个实数变量说明的这样一个简单文法也不一定是LR(O)文法。因此对于LR(O)规范族中有冲突的项目集(状态)用向前查看一个符号的办法进行处理，以解决冲突。这种办法将能满足一些文法的需要，因为只对有冲突的状态才向前查看一个符号，以确定做那种动作，因而称这种分析方法为简单的LR(1)分析法，用SLR(1)表示。

SLR(1)分析法属于LR分析法中的一种，是通过使用输入串中下一个记号来指导它的动作，它大大地提高了LR(0)分析的能力。

它通过两种方法做到这一点：

• 首先，它在一个移进之前先考虑输入记号以确保存在着一个恰当的DFA 。

• 其次，使用构造的非终结符的Follow集合来决定是否应执行一个归约。

流程

对于给定文法G和一语句，若要进行SLR(1)分析，一般需要进行以下步骤：

• (1) 写出已知文法G的扩展文法G’

• (2) 写出扩展文法G’的初始项目集

• (3) 根据状态转移构建识别G’活前缀的DFA（项目集编号为I0-IN）

• (4) 求得文法G的FOLLOW集合

• (5) 根据步骤(3)和(4)构建SLR(1)分析表

文法扩展

所谓G的拓展文法G’，即映入一个新的开始符号，并添加一个新的产生式：将新的开始符号作为新产生的左部，将原开始符号作为产生式的右部。

设新增的开始符号为Z，对于本实验所给文法，拓展文法G’中新增如下产生式：

Z -> A

扩展文法G’的LR(0)项目集

构成识别一个文法活前缀的DFA项目集(状态)的全体，称之为这个文法的LR(0)项目集规范族。

对于活前缀，定义为：对于任一文法G[S]，若新的开始符号经过任意次推导得到αAω，继续经过一次推导得到αβω，若γ是αβ的前缀，则称γ是G的一个活前缀。

设分割符为“.”，对上述扩展文法G’，其全部的LR(0)项目为：

Z=.A  Z=A.
A -> .V=E  A -> V.=E  A -> V=.E  A -> V=E.
E -> .E+T  E -> E.+T  E -> E+.T  E -> E+T.
E -> .E-T  E -> E.-T  E -> E-.T  E -> E-T.
E -> .T  E -> T.
T -> .T*F  T -> T.*F  T -> T*.F  T -> T*F.
T -> .T/F  T -> T./F  T -> T/.F  T -> T/F.
T -> .F  T -> F.
F -> .(E)  F -> (.E)  F -> (E.)  F -> (E).
F -> .i  F -> i.
V -> .i  V -> i.

识别G’活前缀的DFA

首先引入如下概念：LR(0)项目集的闭包函数CLOSURE和状态转换函数GO：

LR(0)项目集的闭包函数CLOSURE

闭包函数CLOSURE(I)的定义如下： 　　

• (1) I的项目均在CLOSURE(I)中。 　　
• (2) 若A -> α·Bβ属于CLOSURE(I)，则每一形如B -> ·γ的项目也属于CLOSURE(I)。 　　
• (3) 重复b)直到不出现新的项目为止。即CLOSURE(I)不再扩大。

LR(0)项目集的状态转换函数GO

转换函数GO(I，X)的定义： 　　

• GO(I，X)＝CLOSURE(J)

其中：I为包含某一项目的状态，J＝{任何形如A -> αX·β的项目| A -> α·Xβ属于I}。

这样就可以使用闭包函数和转换函数构造文法G′的LR(0)项目集规范族。

LR(0)项目集规范族

使用闭包函数和转换函数构造文法G′的LR(0)项目集规范族，步骤如下： 　　

• (1) 置项目【新开始符号 -> ·原开始符号】为初态集的核，然后对核求闭包，得到初态的项目集。

• (2) 对初态集或其它所构造的项目集应用转换函数GO(I，X)=CLOSURE(J)，求出新状态J的项目集。

• (3) 重复(2)直到不出现新的项目为止。

DFA

至此，我们所要构造的识别文法全部或前缀的DFA为：

M={C,V,GO,I0,C}

其中，C为M的状态集也就是文法的LR(0)项目集规范族；V是M的字母表也就是文法的字汇表；GO为M的映像也就是如上定义的状态转换函数GO。

对上述扩展文法G’，识别文法全部或前缀的DFA为：

其中，蓝色编号为项目集的编号，绿色编号为有向边。

在本文法的DFA中，共有20个项目集和38条有向边。

文法G的FOLLOW集合

在构建SLR分析表的时候，文法G的FOLLOW集合用来构建归约过程。对于文法的FOLLOW集合求取，步骤见《编译原理：LL(1)语法分析》。

对于上述文法G，其FOLLOW集合为：

构建SLR(1)分析表

LR(0)分析表的构造

LR(0)分析表的ACTION表项和GOTO表项可按如下方法构造：

• (1)若项目A ->α • aβ属于 Ik 且 GO (Ik, a)= Ij, 期望字符a 为终结符，则置ACTION[k, a] =sj (j表示新状态Ij);
  【如果圆点不在项目k最后且圆点后的期待字符a为终结符，则ACTION[k, a] =sj (j表示新状态Ij)】

• (2)若项目A ->α • Aβ属于 Ik，且GO (Ik, A)= Ij,期望字符 A为非终结符，则置GOTO(k, A)=j (j表示文法中第j个产生式);
  【如果圆点不在项目k最后且圆点后的期待字符A为非终结符，则GOTO(k, A)=j (j表示文法中第j个产生式)】

• (3)若项目A ->α •属于Ik, 那么对任何终结符a, 置ACTION[k, a]=rj；其中，假定A->α为文法G 的第j个产生式；
  【如果圆点在项目k最后且k不是S’ ->S，那么对所有终结符a，ACTION[k, a]=rj (j表示文法中第j个产生式)】

• (4)若项目S’ ->S • 属于Ik, 则置ACTION[k, #]为“acc”;
  【如果圆点在项目k最后且k是S’ ->S，则ACTION[k, #]为“acc”】

• (5)分析表中凡不能用上述规则填入信息的空白格均置上“出错标志”.

SLR(1)分析表的构造

当LR(0)出现多重定义分析动作的时候，对于含有冲突的项目集：

I(i)={B->α • Aβ, A->α •, C->α •}

对于任何输入符号a，可运用如下规则消去冲突：

• (1) 当a=b时，置[i,b]=”移进”；

• (2) 当a属于FOLLOW(A)时，置[i,a]={按产生式A->α •规约}；

• (3) 当a属于FOLLOW(C)时，置[i,a]={按产生式C->α •规约}；

• (4) 当a不属于上述三种情况之一时，置[i,a]=”ERROR”。

需要注意的是，对于是LR(0)文法的文法来说，其LR(0)分析表和SLR(1)分析表是一样的（因为没有可消去的冲突，其余的构造方法又是一致的）。

对于上述文法G’，根据DFA和FOLLOW集合构造SLR(1)分析表，如下：

上述结果为本次实验代码生成的SLR分析表和对产生式的编号。
实际上是我懒得再把表格敲一编到这儿了就直接拿截图代替了233333

根据构造好的SLR(1)分析表进行分析

SLR(1)分析分析流程同LR分析，流程图如下：

生成中间代码四元式

在做SLR（1）分析时，在归约动作进行的同时，需要执行语义动作，并生成生成中间代码四元式子。

四元式结构

定义四元式结构如下：

• (op, agr1, arg2, result)

其中，op为二元运算符；result为两运算对象arg1、arg2通过运算符op进行运算所得到的结果变量；arg1和arg2分别为op左边和右边的运算对象，该对象可以是产生式中的非终结符号，也可以是先前产生的result临时变量。

如何产生四元式？

一般的，语句中有多少个运算符，对应就要产生多少个中间代码四元式。对于含有运算符的产生式来说，如果发生的归约动作使用了这个产生式，那么就把该产生式的左部和右部按照上述结构进行记录：

op=产生式右部的运算符
arg1=产生式右部的运算符的左边的运算对象
arg2=产生式右部的运算符的右边的运算对象
result=产生式左部的非终结符号

如果按照产生式中的进行记录，那么对于所有的四元式来说，无法看出它们之间的关系。对应的做法是按照顺序记录这些四元式，在所有记录都完成之后，按照从上到下的顺序将任意四元式的运算对象arg1、arg2替换为上面一个四元式的result。这里需要注意的是，在记录的时候一定要按照语法分析的顺序进行记录，否则就无法进行顺序替换：按语法顺序进行的记录就是该四元式在原语句中的映射顺序记录。

文件结构及函数简介

本专题大部分文件和功能函数与专题1同名，具体的文件结构和功能函数简介见《编译原理：词法分析程序》。

新增文件SLR.h，内含的函数用SLR分析表的构造及文法的扩充等。

文件firstAndFollow.h同《编译原理：LL(1)语法分析》所实现的功能一致。

代码分析

详细的主函数流程如下：

int main(int argc, const char * argv[]) {
    //初始化参数
    initAll();
    //读取lab1中输出的二元组结果文件
    readFile_Result();
    //读取lab1中输出的标识符结果文件
    readFile_Identifier();
    //过滤读取结果，得到纯粹的标识符内容
    getPureMorphemeAndSentence();
    //输出过滤后的语句
    printSentenceInfo();
    //读取文法，求得包含所有的非终结符号的不重复集合
    readFile_Formula();
    //求得包含所有的终结符号的不重复集合
    getAllVT();
    //求得文法的first集合和follow集合以及由此构造分析表，并写入txt文件中
    getFirstAndFollow();
    //文法扩充
    grammarExpand();
    //求识别文法全部活前缀的DFA
    DFA();
    //将所求的DFA写入txt文件中
    writeFile_DFA();
    //构造SLR分析表
    getSLRAnalyseTable();
    //将所求的SLR分析表写入txt文件中
    writeFile_SLR1AnalyseTable();
    //进行分析
    if(getAnalyseResult()){
        cout<<"匹配成功!"<<endl;
        //匹配成功，输出分析栈结果
        printAnalyseResultInfo();
    }else{
        //匹配失败，输出错误位置信息
        cout<<"匹配失败!"<<endl;
        printError();
    }
    return 0;
}

构造识别文法所有活前缀的DFA，首先需要构造好初态I(0)：即把【新开始符号 -> ·原开始符号】加入I(0)中。然后执行循环。循环的内容为：从第0个状态开始先求取状态的闭包，然后读取所有可读取的符号，并把读取过后构造的不重复新状态加入到项目集中，等待接下来的读取。跳出循环的条件为：当项目集的个数不再增大且所有的项目集都经过求取闭包和符号移进。

void DFA(){
    dfaCounter+=1;
    multimap<char,string>::iterator itBegin;
    itBegin=Sentence.find(newBegin);
    //0状态的初始化： [新开始符号->.原开始符号]
    dfaForG_prim[0].dfa.insert(make_pair(newBegin, fenGe+itBegin->second));
    //对0状态求闭包
    dfaForG_prim[0].dfa=closure(dfaForG_prim[0].dfa);
    //从0状态开始循环
    for(int i=0;i<dfaCounter;i++){
        //读取所有可读取的字符，作为新状态，并对新状态求闭包
        //不重复的新状态则加入dfa中，等待之后的读取
        getNextSta(i);
    }
}

函数**void getNextSta(int dfaCount)**用来求当前状态的闭包和对该闭包进行读取移进的工作：

void getNextSta(int dfaCount){
    //将该状态中全部可以读取的字符做成集合
    //可以读取的字符：所有产生式中的紧挨着分割符的下一个字符
    set<char> nextChar;
    for(multimap<char,string>::iterator it_1=dfaForG_prim[dfaCount].dfa.begin();it_1!=dfaForG_prim[dfaCount].dfa.end();it_1++){
        for(int i=0;i<it_1->second.length()-1;i++){
            if(it_1->second[i]==fenGe[0]){
                nextChar.insert(it_1->second[i+1]);
            }
        }
    }
    //没有可以读取的字符，该状态是终结状态
    if(nextChar.size()==0){
        return;
    }
    //有可以读取的字符，按上述所求得的集合中的内容读取
    for(set<char>::iterator it_1=nextChar.begin();it_1!=nextChar.end();it_1++){
        multimap<char,string> temp;
        for(multimap<char,string>::iterator it_2=dfaForG_prim[dfaCount].dfa.begin();it_2!=dfaForG_prim[dfaCount].dfa.end();it_2++){
            for(int i=0;i<it_2->second.length()-1;i++){
                if(it_2->second[i]==fenGe[0]&&it_2->second[i+1]==*it_1){
                    string tempString=it_2->second;
                    //分隔符移进（读取）
                    //使用位操作交换第i个位置内容(分隔符)和第i+1个位置的内容
                    tempString[i]=tempString[i]^tempString[i+1];
                    tempString[i+1]=tempString[i]^tempString[i+1];
                    tempString[i]=tempString[i]^tempString[i+1];
                    temp.insert(make_pair(it_2->first,tempString));
                    break;
                }
                
            }
        }
        //对移进之后的产生式求取闭包temp
        temp=closure(temp);
        bool ifRepeat=false;
        //对temp查重
        //如果temp和现在dfa中的任意一个状态重合，则该temp不加入dfa状态中
        for(int i=0;i<dfaCounter;i++){
            if(temp.size()==dfaForG_prim[i].dfa.size()){
                vector<string> rComPare1;
                vector<string> rComPare2;
                for(multimap<char,string>::iterator it_3=dfaForG_prim[i].dfa.begin(), it_4=temp.begin();it_3!=dfaForG_prim[i].dfa.end();it_3++,it_4++){
                    //将所对比的两个状态的左右部全部加入向量中，便于比较
                    rComPare1.push_back(it_3->second);
                    rComPare1.push_back(""+it_3->first);
                    rComPare2.push_back(it_4->second);
                    rComPare2.push_back(""+it_4->first);
                }
                if(rComPare1==rComPare2){
                    //当前temp有重复
                    ifRepeat=true;
                    //重复的内容有边连到当前状态
                    dfaLine[dfaLineCounter].from=dfaCount;
                    dfaLine[dfaLineCounter].read=*it_1;
                    dfaLine[dfaLineCounter].to=i;
                    dfaLineCounter+=1;
                    break;
                }
            }
        }
        if(!ifRepeat){
            //当前temp不重复
            //当前temp有边指向下一个temp
            dfaLine[dfaLineCounter].from=dfaCount;
            dfaLine[dfaLineCounter].read=*it_1;
            dfaLine[dfaLineCounter].to=dfaCounter;
            dfaLineCounter+=1;
            //当前temp加入dfa中成为一个新状态
            dfaForG_prim[dfaCounter].dfa=temp;
            dfaCounter+=1;
        }
    }
}

上述函数过程中调用了closure函数，用来求取当前状态的闭包：

multimap<char,string> closure(multimap<char,string> a){
    //int oldSize=a.size();
    for(;;){
        //记录集合的大小
        int oldSize=a.size();
        //求取闭包temp
        //紧挨着分割符的下一个字符如果是非终结字符，则把以该非终结字符作为左部的所有产生式加入该状态，并使其右部的第一个位置加入分割符
        multimap<char,string> temp=a;
        for(multimap<char,string>::iterator it_a=a.begin();it_a!=a.end();it_a++){
            for(int i=0;i<it_a->second.length()-1;i++){
                if(it_a->second[i]==fenGe[0]){
                    if(isCaptain(it_a->second[i+1])){
                        for(multimap<char,string>::iterator it_1=Sentence.begin();it_1!=Sentence.end();it_1++){
                            if(it_1->first==it_a->second[i+1]){
                                // 左 -> 分割符 + 右
                                temp.insert(make_pair(it_1->first, fenGe+it_1->second));
                            }
                        }
                        break;
                    }
                }
            }
        }
        //temp内部去重
        //去除重复的产生式
        int tempSize=temp.size();
        for(;;){
            for(multimap<char,string>::iterator it_1=temp.begin();it_1!=temp.end();it_1++){
                for(multimap<char,string>::iterator it_2=it_1;it_2!=temp.end();it_2++){
                    if(it_1!=it_2&&it_1->first==it_2->first&&!it_1->second.compare(it_2->second)){
                        //erase擦去重复的产生式
                        temp.erase(it_2);
                    }
                }
            }
            if(tempSize==temp.size()){
                break;
            }else{
                tempSize=temp.size();
            }
        }
        a=temp;
        //状态不再扩大，证明是闭包，跳出
        if(oldSize==a.size()){
            break;
        }
    }
    return a;
}

构造SLR分析表和进行分析则完全按照上述算法进行，不再赘述。

结果分析

依据所给文法写出给出两正确语句，并验证结果：

var_d=var_a+var_b*var_c

将此表达式写入专题1中的SourceProgram.txt文件，运行专题1程序：

查看标识符文件Identifier.txt：

查看词素二元组文件ResultofLexicalAnalysis.txt：

可以看到对于专题1来说，该语句是符合要求的。

接下来运行本专题的SLR(1)分析及中间代码生成程序：

查看生成的DFA文件DFA.txt：

生成的SLR分析表文件SLR1AnalyseTable.txt见【3.6.1 SLR(1)分析表的构造】。

var_a=var_b-(var_c+var_d/var_e)*var_f

将此表达式写入专题1中的SourceProgram.txt文件，运行专题1程序：

查看标识符文件Identifier.txt：

查看词素二元组文件ResultofLexicalAnalysis.txt：

可以看到对于专题1来说，该语句是符合要求的。

接下来运行本专题的SLR(1)分析及中间代码生成程序：

上述测试结果证明了两个程序可按设计本意顺利完成功能。

总结

至此，编译原理与算法有关的代码编写及博客写作就告一段落。纵观所有内容，将优缺点及后续需要改进的地方进行总结：

优点

• 使用编程语言统一（c++）、数据结构统一、输入内容统一（实验要求）、输出方式统一（包括控制台输出与文件输出）；

• 语法分析的4个程序的代码整体架构统一，具体为：总控程序+分析依据构造+分析算法；

• 细节功能封装体现的较为到位；

• 功能操作方便、代码泛用性高：在循环中经常使用的变量或常量均设置了全局变量，对不同规模、不同内容的文法或语句进行测试或者在别的工程中引用当前工程功能的时候，无需再次修改代码，仅需要修改txt文件即可。

不足

• 代码不够简洁：主要体现在对数据结构的遍历中（循环嵌套严重、为了方便循环不设置跳出等）；

• 在进行词法分析程序（1）编写的时候没有考虑到后面的内容，导致了很多无用或者费力的代码。

以后要做的事情

• 程序整合：整合所有功能，精简无用、重复代码；

• 进一步进行功能函数的封装；

• 可视化前端编写。
  有时间有心情我就写

---

最后，庆祝历时两个多月的编译原理的算法相关coding的完成！

记录时间：2019年4月——2019年5月31日17时37分

最后的最后，我还想说一句，编译原理这些个东西也太难理解太难写了，我终于写完了2333～～
接下来的实验6是1和5的整合相当于白给，博客也懒得再写太多了都是些重复的东西，实验7是选做也相当于白给以后再说吧233333～～