编译原理：LL(1)语法分析

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

---

目标任务

要求

完成以下描述赋值语句的 LL(1)文法的 LL(1)分析过程。

G[A]: S->V=E
E->TE’
E’->ATE’|ε
T->FT’
T’->MFT’|ε
F-> (E)|i
A->+|-
M->*|/
V->i

设计说明

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

设计要求

• (1)输入串应是词法分析的输出二元式序列，即某算术表达式“专题1”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果;

• (2)LL(1)分析过程应能发现输入串出错;

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

• (4)考虑根据LL(1)文法编写程序构造LL(1)分析表，并添加到你的LL(1)分析程序中。

---

解答

LL(1)分析

专题2中要求我们实现递归下降语法分析。在实践过程中，可以发现：这种带回溯的自顶向下的分析方法实际上是一种穷举的不断试探的过程，分析效率极低。

实际上，递归下降分析在实际的编译程序中极少使用。

相较于递归下降分析，LL(1)分析法又称预测分析法，是一种不带回溯的非递归自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

该方法的显著特点是使用显式栈，该算法在本质上就是用栈来显式地实现非递归版本的递归下降分析，或者说非递归版本的树的遍历的一个过程。

设计思想

递归下降分析器的构造方法同样非常简单，就是为每一个非终结符寻找到FIRST集合和FOLLOW集合，并由这两个集合构造LL(1)分析表，最后根据分析表进行对指定的句子打印出分析栈的分析过程。

需要注意的是，在进行递归下降分析之前需要对不是LL(1)的文法进行处理。

左递归的消除

由于所给的文法为标准的LL（1）文法，这一步可省略。

FIRST集合

FIRST(A)集合是非终结符号A的所有可能推导出的开头终结符或ε组成的集合。称FIRST(A)为A的开始符号集或首符号集。

对于大部分文法而言，存在一个产生式存在多个候选式的情况，而选择哪一个候选式是不确定的，所以这就产生了回溯。回溯需要消耗大量的计算、存储空间，所以我们需要消除回溯。而消除回溯的其中一种方法叫作“预测”，即根据栈顶非终结符去预测后面的候选式，那预测方法就是求第一个非终结符，来判断是否和读头匹配，以达到预测的效果。

计算FIRST集合需要经过以下步骤：

• （1）若X ∈ VT，则FIRST(X) = {X}；
  【终结符自己就是自己的FIRST集合】

• （2）若X ∈ VN，且有产生式X -> a……， a ∈ VT，则a ∈ FIRST(X)；
  【非终结符，选第一个终结符加入】

• （3）若X ∈ VN，X -> ε，则 ε ∈ FIRST(X)；
  【能直接推出ε，ε加入FIRST】

• （4）若X,Y1,Y2,……,Yn ∈ VN，而有产生式X -> Y1,Y2,……,Yn。当Y1,Y2,……,Y(i-1)直接推出ε时，则FIRST(Y1) - ε, FIRST(Y2) - ε, …… , FIRST(Y(i-1) - ε) ,FIRST(Yi) 都包含在FIRST(X)中；
  【位于中间的ε是不可加入进去】

• （5）当（4）中所有Yi 都推出 ε时，则最后的FIRST(X) = FIRST(Y1) ∪ FIRST(Y2) ∪ …… ∪ FIRST(Yn) ∪ {ε}；

反复运用（2）-（5）步骤，直到每个符号的FIRST集合不再增大为止。

对本专题所给的文法求FIRST集合的过程如下：
【1】First(S) = First(V) = First(i) = {i}
【2】First(E) = First(T) = First(F) = First(() + First(i) = {(,i}
【3】First(R) = First(A) + First(ε) = First(+) + First(-) + First(ε) = {+,-,井}
【4】First(T) = First(F) = First(() + First(i) = {(,i}
【5】First(Y) = First(M) + First(ε) = First(*) + First( + First(ε) = First(*) + ) + First(ε) = {*,/,井}
【6】First(F) = First(() + First(i) = {(,i}
【7】First(A) = First(+) + First(-) = {+,-}
【8】First(M) = First(*) + First( = First(*) + ) = {*,/}
【9】First(V) = First(i) = {i}

注：为了方便代码的编写，对文法做如下字符的替换（之后所有用到如下规则的地方都做此替换，不再赘述）：

E’ -> R
T’ -> Y

FOLLOW集合

FOLLOW(A)集合是所有紧跟A之后的终结符或#所组成的集合（#是句尾的标志），称FOLLOW(A)是A的随符集。

当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的开始符号集两两不相交，并与在推导过程中紧跟该非终结符右部可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。因此，引入了文法符号的后跟符号集合FOLLOW。

计算FOLLOW集合需要经过以下步骤：

（1）对S，将井加入 FOLLOW(S)，然后再按后面的处理；

（2）若B -> aAb是G的产生式，则将FIRST(β)-ε加入FOLLOW(A)；

（3）若B -> aA是G的产生式，或B -> aAb是G的产生式（b 多次推导后得到ε ），则将FOLLOW(B) 加入到FOLLOW(A) 。
【将B用aA替换之后，B后面紧跟的字符就是A后面紧跟的字符】

反复使用（2）-（3）步骤，直到FOLLOW集合不再增大为止

对本专题所给的文法求FIRST集合的过程如下：
【1】Follow(S): S->S = {井}
【2】Follow(E): S->V=E、S->(E) = {井,)}
【3】Follow(R): S->TR、S->(E)->(R) = {井,)}
【4】Follow(T): S->TR->T+、S->TR->T-、S->TR->Tε、S->(E)->(T) = {+,-,井,)}
【5】Follow(Y): S->TR->FYR->Y+、S->TR->FYR->Y-、S->FY、S->(E)->(Y) = {+,-,井,)}
【6】Follow(F): S->FY->F*、S->FY->F/、S->FY->Fε、S->TR->F+、S->TR->F-、S->(E)->(F) = {*,/,井,+,-,)}
【7】Follow(A): S->ATR->A(R、S->ATR->AiR = {(,i}
【8】Follow(M): S->MFY->M(Y、S->MFY->MiY = {(,i}
【9】Follow(V): S->V=E = {=}

根据FIRST集合和FOLLOW集合构造LL(1)分析表

设M[A][a]是一个二维数组，其中行A表示的是栈顶符号，a表示的读头下的符号（A为非终结符，a为终结符），它们存放的是当前状态下所使用的候选式（或存放出错标志，指出A不该面临a的输入），称该数组M为文法的LL(1)分析表。

为了消除回溯，我们进行了FIRST集合和FOLLOW集合的求解。它们两个组合，达到了预测候选式的目的。为了使计算机比较好处理，把它们的预测结果统计成一张二维表。

构造LL(1)分析表需要经过如下步骤：

• （1）对任意终结符号a ∈First(A)，将 A -> a 填入M[A,a]；

• （2）如果存在ε ∈First(A)，则对任意终结符号a ∈Follow(A)，将 A -> a 填入M[A,a]；

• （3）将所有没有定义的M[A,b]设置为出错。

对本专题所给的文法构造LL(1)分析表如下：

	#	(	)	*	+	-	/	=	i
A					+	-
E		TR							TR
F		(E)							i
M				*			/
R	ε		ε		ATR	ATR
S									V=E
T		FY							FY
V
Y	ε		ε	MFY	ε	ε	MFY

该分析表中未填入内容的位置则表示该位置的非终结符号无法预测后跟该位置的终结符号。如果匹配到这样的位置，则证明表达式出错。

根据LL(1)分析表进行预测分析

构造好分析表之后，便可根据分析表进行预测分析。

流程如下：

文件结构及函数简介

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

新增文件FirstAndFollow.h，内含的函数用作预测分析的准备工作，即求文法的First集合、求文法的Follow集合和构造分析表。

代码分析

详细的主函数流程如下：

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

本专题要求的输入是专题1输出的词素结果二元组和标识符信息，读取函数介绍见《编译原理：递归下降分析》。

本次分析需要操作各种符号进行匹配比对，所以使用最多的操作就是查找和字符比较。为此，设置以下结构来存储该过程中的数据。使用C++ STL的原因是如map等的结构自带排序，且键值对的存储方式对于遍历操作十分友好；再如string，自带字符串比较函数compare，对于匹配操作也很友好。

//产生式
multimap<char, string> Sentence;
//产生式反向
multimap<string, char> ReverseSentence;
//非终结符集合
set<char> VN;
//终结符集合
set<char> VT;
//读取产生式的等号左部内容，一般都是单字符，所以用char
vector<char> Left;
//读取产生式的等号右部内容，长度不定，使用string
vector<string> Right;
//非终结符能否推出空
map<char, bool> VtToEmpty;
//求First和Follow集合是否成功的标志
bool IfFirstOrFollowSuccess;
//First集合，char对应的是每个非终结符号，set<char>对应每个非终结符号的每个First集合中的内容
map<char,set<char>> FirstSet;
//Follow集合，解释同上
map<char,set<char>> FollowSet;
//文法的开始符号
char Begin;
//LL(1)分析表
string AnalyseTable[100][100];
//分析过程四元组
string AnalyseProcess[100][4];
//分析步骤计数
int step;
//分析栈
stack<string> AnalyseStack;

对于first集合和follow集合，根据上面介绍的方法进行循环求解即可。需要注意的是要设置跳出的条件：当某一轮循环之后的集合大小与内容和上一轮循环无变化，则表明寻找完成，需要跳出。

根据first集合和follow集合构造分析表时需要注意的是，对于非终结符号X直接推导为单个终结符号a的情况，有两种处理情况：当该非终结符号仅有一种推导出单终结符号的情况，M[X,a]可写作{a}；当该非终结符号有多于一种的推导出单终结符号的情况（设所有情况为a1……ai），可按照每个终结符号的具体情况去设置，即M[X,ai]={ai}**，这种做法与第一种情况相同，或者使用另一个符号b去替代所有情况，即M[X,ai]={b}，这种做法需要将该非终结符号能产生的在所给语句中的所有非终结符号替换为b**。本专题中仅出现了第一种情况，故按照第一种情况去处理即可。

预测分析程序的流程见上面的流程图，具体代码及注释如下:

bool getAnalyseResult(){
    //#入栈
    AnalyseStack.push("#");
    //开始符号入栈
    string temp=&Begin;
    AnalyseStack.push(temp);
    //存储当前语句匹配位置的非终结符号，同a
    string pFormula="";
    //存储当前栈顶
    string X="";
    for(;;){
        //写入分析过程
        AnalyseProcess[step][0]=to_string(step+1);
        int stackSize=AnalyseStack.size();
        string stackTemp[100];
        for(int i=0;i<stackSize;i++){
            stackTemp[i]=AnalyseStack.top();
            AnalyseStack.pop();
        }
        for(int i=stackSize-1;i>=0;i--){
            AnalyseStack.push(stackTemp[i]);
            AnalyseProcess[step][1]+=stackTemp[i];
        }
        //X记录当前栈顶
        X=AnalyseStack.top();
        //pFormula记录语句当前匹配位置的内容
        if(matchIdentifier()){
            pFormula="i";
            pMorpheme-=1;
        }else{
            pFormula=morpheme[pMorpheme];
        }
        //写入分析过程
        for(int k=pMorpheme;k<morphemeCounter;k++){
            AnalyseProcess[step][2]+=morpheme[k];
        }
        //X是终结符号？
        if(matchVT(X)){
            //X=pFormula
            //X==#？
            if(!X.compare("#")){
                //X=#
                //X==pFormula？
                if(!X.compare(pFormula)){
                    //X=pFormula
                    //写入分析过程
                    AnalyseProcess[step][3]+="Success";
                    step+=1;
                    //分析成功
                    return true;
                }else{
                    //X!=pFormula
                    //分析失败
                    return false;
                }
            }
            //X==pFormula？
            if(!X.compare(pFormula)){
                //X=pFormula,当前符号匹配成功，记录步数
                step+=1;
                //栈顶符号出栈
                AnalyseStack.pop();
                //当前匹配语句指针后移
                pMorpheme+=1;
                //继续分析
                continue;
            }else{
                //分析失败
                return false;
            }
        }
        //M[X,a]有产生式？
        else if(ifHasFormula(X, pFormula)){
            //M[X,a]有产生式，查询并取出内容
            string f=getFormula(X, pFormula);
            //栈顶符号出栈
            AnalyseStack.pop();
            //写入分析过程
            AnalyseProcess[step][3]+=X+"->"+f;
            //将M[X,a]的内容反序入栈
            if(!f.compare("ε")){
                step+=1;
                continue;
            }
            for(int i=f.length()-1;i>=0;i--){
                char ff=f[i];
                string fff="";
                fff+=ff;
                AnalyseStack.push(fff);
            }
            //记录步数
            step+=1;
            //继续分析
            continue;
        }else{
            //分析失败
            return false;
        }
    }
    return false;
}

结果测试

首先依据所给文法写出一正确的语句：

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

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

查看标识符文件Identifier.txt：

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

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

接下来运行本专题的LL(1)程序：

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

对于本专题来说，还有一个重要的功能是FIRST集合和FOLLOW集合的求解以及分析表的构造。对于此功能，文法输入文件为Formula.txt：

该文法输入文件的格式是：产生式的左右部以单空格区分；每一行仅含有一个单产生式；每一个字符代表一个终结符号或非终结符号，无双字符符号；将所有的大写字母看作是非终结符号，除此之外的所有符号看作终结符号；以“$”标志文件结束。

所求得的FIRST集合和FOLLOW集合输出到FirstAndFollow.txt：

构造好的分析表输出到AnalyseTable.txt：

综上，该程序的输入有二：一是专题1所输出的二元组文件，另一是经过手工处理的LL(1)文法内容文件。而输出有三：一是控制台输出分析结果：成功匹配则输出分析过程，失败匹配则输出出错位置；另一是输出所求得的FIRST集合和FOLLOW集合；再一是输出所构造的分析表。

接下来，修改我们所给出的正确的语句，使它变得”错误”。当然这里所说的错误指的是在本专题的情景下是错误的。这些语句无论如何修改，都必须符合专题1的情景。

• (1)var_a+var_error=((var_b+var_c*var_d)/(var_e-var_f/var_g))/var_i

• (2)var_a==((var_b+var_c*var_d)/(var_e-var_f/var_g))/var_i

• (3)var_a=((var_b+var_c*var_d)=(var_e-var_f/var_g))/var_i

标示出来的是我们添加的错误。

分别对如上情形进行测试：

• （1）:

• （2）:

• （3）:

根据上述结果可以看出，本程序可以实现所给LL（1）文法的LL(1)语法分析，并能指出具体错误的位置。