实验三. 自上而下语法分析
设计思想
根据对自下而上语法分析的理论知识的学习，可以知道自下而上语法分析的两种实现方法：算符优先分析法和LR分析法，本实验采用后者LR分析法
本实验对PL0文法的表达式文法进行设计自下而上语法分析，表达式巴斯克范式如下：
文法的初始化
$\begin{aligned}
    & <表达式>      ::= [+|-]<项>\{<加法运算符> <项>\} \\
    & <项>         ::= <因子>\{<乘法运算符> <因子>\} \\
    & <因子>       ::= <标识符>|<无符号整数>| '('<表达式>')' \\
    & <加法运算符>  ::= +|- \\
    & <乘法运算符>  ::= *|/
\end{aligned}$
对以上文字描述的文法可以给出对应的英文表示，以及对应的非终结符的 $First集合$ 和 $Follow集合$ ：
$\begin{aligned}
    & <Expression>  ::= [+|-]<Term>\{<Addop> <Term>\} \\
    & <Term>        ::= <Factor>\{<Mulop> <Factor>\} \\
    & <Factor>      ::= <Ident> | <UnsignInt> | (<Expression>) \\
    & <Addop>       ::= + | - \\
    & <Mulop>       ::= * | / \\
\end{aligned}$

该文法的非终结符结合以及终结符集合如下：

$\begin{aligned}
    & V_T = \{+, -, *, /, (, ), Ident, UnsignInt\} \\
    & V_N = \{Expression, Term, Addop, Factor, Mulop\} \\
\end{aligned}$
$First集合$ :
$\begin{aligned}
    & First(Expression) = \{+, -, Ident, UnsignInt, (\} \\
    & First(Term)       = \{Ident, UnsignInt, (\} \\
    & First(Factor)     = \{Ident, UnsignInt, (\} \\
    & First(Addop)      = \{+, -\} \\
    & First(Mulop)      = \{*, /\} \\
\end{aligned}$
$Follow集合$ :
$\begin{aligned}
    & Follow(S')            = \{\#\} \\
    & Follow(Expression)    = \{\#, +, -, )\} \\
    & Follow(Term)          = \{\#, +, -, *, /, )\} \\
    & Follow(Factor)        = \{\#, +, -, *, /, )\} \\
\end{aligned}$
将其简化一下文法：
$\begin{aligned}
    E & \to T | +T | -T \\
    E & \to E + T | E - T\\
    T & \to F \\
    T & \to T * F | T / F \\
    F & \to i | u | (E) \\
\end{aligned}$
对应的终结符和非终结符集合如下：
$\begin{aligned}
    & V_T = \{+, -, *, /, (, ), i, u\} \\
    & V_N = \{S', E, T, F\}
\end{aligned}$
拓广文法
文法的拓广，将文法 $G(S)$ 拓广为 $G'(S')$ ，并规定每一个产生式的编号，以便后续的方便使用：
$\begin{aligned}
    & 0: & S &' \to E \\
    & 1: & E & \to T \\
    & 2: & E & \to +T \\
    & 3: & E & \to -T \\
    & 4: & E & \to E + T \\
    & 5: & E & \to E - T \\
    & 6: & T & \to F \\
    & 7: & T & \to T * F \\
    & 8: & T & \to T / F \\
    & 9: & F & \to i \\
    & 10: & F & \to u \\
    & 11: & F & \to (E) \\
\end{aligned}$
构造识别活前缀的DFA

由此DFA可以看出，某些状态存在“规约-移进”冲突，所以可以通过SLR分析法的方式来尝试构造分析表，构造出此时构造出的分析表显然没有冲突：
SLR分析表
$\begin{array}{c|c}
    \hline
        & + & - & * & / & ( & ) & i & u & \# & E & T & F \\ \hline
    0 & s5 & s4 &  &  & s8 &  & s6 & s7 &  & 1 & 2 & 3 \\ \hline
    1 & s9 & s10 &  &  &  &  &  &  & acc &  &  &  \\ \hline
    2 & r1 & r1 & s11 & s12 &  & r1 &  &  & r1 &  &  &  \\ \hline
    3 & r6 & r6 & r6 & r6 &  & r6 &  &  & r6 &  &  &  \\ \hline
    4 &  &  &  &  &  &  &  &  &  &  & 13 &  \\ \hline
    5 &  &  &  &  &  &  &  &  &  &  & 14 &  \\ \hline
    6 & r9 & r9 & r9 & r9 &  & r9 &  &  & r9 &  &  &  \\ \hline
    7 & r10 & r10 & r10 & r10 &  & r10 &  &  & r10 &  &  &  \\ \hline
    8 & s5 & s4 &  &  & s8 &  & s6 & s7 &  & 15 & 2 & 3 \\ \hline
    9 &  &  &  &  & s8 &  & s6 & s7 &  &  & 16 & 3 \\ \hline
    10 &  &  &  &  & s8 &  & s6 & s7 &  &  & 17 & 3 \\ \hline
    11 &  &  &  &  & s8 &  & s6 & s7 &  &  &  & 18 \\ \hline
    12 &  &  &  &  & s8 &  & s6 & s7 &  &  &  & 19 \\ \hline
    13 & r3 & r3 &  &  &  & r3 &  &  & r3 &  &  &  \\ \hline
    14 & r2 & r2 &  &  &  & r2 &  &  & r2 &  &  &  \\ \hline
    15 & s9 & s10 &  &  &  & s20 &  &  &  &  &  &  \\ \hline
    16 & r4 & r4 & s11 & s12 &  & r4 &  &  & r4 &  &  &  \\ \hline
    17 & r5 & r5 & s11 & s12 &  & r5 &  &  & r5 &  &  &  \\ \hline
    18 & r7 & r7 & r7 & r7 &  & r7 &  &  & r7 &  &  &  \\ \hline
    19 & r8 & r8 & r8 & r8 &  & r8 &  &  & r8 &  &  &  \\ \hline
    20 & r11 & r11 & r11 & r11 &  & r11 &  &  & r11 &  &  &  \\ \hline
\end{array}$
得到分析表后，就可以根据LR分析的程序框架完成总控程序等的编写，由上一次的 自上而下的SLR分析表法 的代码可以简单的修改一些代码，便可实现整个分析程序的编写。
算法流程

源程序
整个SLR分析程序是由上一实验的预测分析程序修改而来，根据SLR分析的所需，简单的修改了分析表的构成，即由ACTION和GOTO表组成，将原来的分析总控程序中的具体的执行流程根据LR分析法来修改，其他内容保持不变即可：
整个LR分析程序所设计到的类以及相互的关系如下：

项目地址
基础符号类
基础符号类作为一个符号类的基类，主要用途为使用基类指针来指引子类的终结符或非终结符，简化后续的操作。
// symbols.h
#ifndef symbols_h
#define symbols_h
#include<iostream>
/*
终结符和非终结符的一个共同的基类
这样可以通过基类来引用终结符和非终结符

*/
class symbols
{
private:
    /* data */
public:
    symbols(){};
    virtual ~symbols(){};
    virtual std::string getClassName(){
        return "symbols";
    }
    virtual void print(){};
};

#endif /*symbols_h*/

终结符类
终结符类继承至基础符号类，终结符由终结符的值和编码构成。
// symbolsVT.h
#ifndef symbolsVT_h
#define symbolsVT_h
#include<iostream>
#include"symbols.h"
/*
一个终结符
终结符由终结符的值和编码构成

*/
class symbolsVT : public symbols{
private:
    std::string word;   //终结符的值
    std::string code;   //词法分析后终结符的标识（编码）
public:
    symbolsVT(){}
    symbolsVT(std::string W, std::string C):word(W), code(C) {
        std::cerr<< "V_T: " << word << " " << code << " created..." << std::endl;
    }
    ~symbolsVT() {}
    std::string getClassName();
    std::string getWord();
    std::string getCode();
    void print();
};

#endif /*symbolsVT_h*/

// symbolsVT.cpp
#include<iostream>
#include"symbolsVT.h"

std::string symbolsVT::getClassName(){
    return "VT";
}
std::string symbolsVT::getWord(){
    return word;
}
std::string symbolsVT::getCode(){
    return code;
}
void symbolsVT::print(){
    std::cerr << "VT: " << word << " " << code << std::endl;
}

非终结符类
非终结符类与终结符类一样继承至基础符号类，非终结符由其左部的非终结符和有部一个一些产生式构成，产生式即为一些符号的排列，此处存储的是一些产生式的指针。
// symbolsVN.h
#ifndef symbolsVN_h
#define symbolsVN_h
#include<iostream>
#include"symbols.h"
#include"production.h"
const int maxnNum = 5;     // 一个终结符所有的产生式的数量
class production;
/*
非终结符
非终结符由其左部的非终结符和有部一个一些产生式构成
产生式即为一些符号的排列，此处存储的是一些产生式的指针
*/

class symbolsVN: public symbols{
private:
    std::string name;							// 非终结符左部名称X
    production *p[maxnNum];						// 产生式集合
    int num;
public:
    symbolsVN();
    symbolsVN(std::string);
    ~symbolsVN() {}
    std::string getClassName();
    std::string getName();
    void insertProduction(production *newp);	// 加入一个产生式
    production* getProductionIndexOf(int i);	// 获得第i个产生式
    production** getAllProduction();			// 获得所有的产生式
    void print();
};

#endif /*symbolsVN_h*/

// symbolsVN.cpp
#include<iostream>
#include"symbolsVN.h"

symbolsVN::symbolsVN(){
    num = 0;
}
symbolsVN::symbolsVN(std::string n):name(n){
    symbolsVN();
    std::cerr << "V_N: " << name << " created..." << std::endl;
}

std::string symbolsVN::getClassName(){
    return "VN";
}
std::string symbolsVN::getName(){
    return name;
}
void symbolsVN::insertProduction(production *newp){
    p[num++] = newp;
    return;
}
production* symbolsVN::getProductionIndexOf(int i){
    if(i >= num){
        std::cerr << "index overflow..." << std::endl;
        return NULL;
    }
    return p[i];
}
production** symbolsVN::getAllProduction(){
    return p;
}
void symbolsVN::print(){
    std::cerr << "VN: " << name << std::endl;
    std::cerr << "ALL production: " << std::endl;
    for(int i = 0; i < num; ++i){
        std::cerr << name << " \\to ";
        p[i]->print();
    }
    std::cerr << std::endl;
}

产生式类
一个产生式由一个左部的非终结符和一些右部的符号集合构成。
// production.h
#ifndef production_h
#define production_h
#include<iostream>
#include"symbols.h"
#include"symbolsVT.h"
#include"symbolsVN.h"
/*
产生式
一个产生式由一个左部的非终结符和一些右部的符号集合构成
*/

const int maxnLen = 10;        // 一个产生式的右部符号的数量
class symbolsVN;
class production
{
private:
    symbolsVN *vn;					// 产生式左部的非终结符
    symbols *pro[maxnLen];			// 产生式，由一些非终结符和终结符构成，故使用符号指针来指引
    int len;
public:
    production();
    production(symbolsVN *v);
    ~production(){}
    void push_back(symbols *a);		// 为产生式后部插入一个符号
    symbolsVN* getVN();				// 获得左部非终结符符号
    symbols** getProduction();		// 获得产生式指针数组
    int getLen();					// 获得产生式长度
    symbols* getProductionIndexOf(int i); // 获得产生式中第i个位置的符号
    void print();
};

#endif /*production_h*/

// production.cpp
#include<iostream>
#include"production.h"
#include"symbolsVT.h"
#include"symbolsVN.h"

production::production(){
    len = 0;
}
production::production(symbolsVN *v){
    vn = v;
    production();
    std::cerr << "A production of " << vn->getName() << " has created..." << std::endl;
}
void production::push_back(symbols *a){
    pro[len++] = a;
}
symbolsVN* production::getVN(){
    return vn;
}
symbols** production::getProduction(){
    return pro;
}
symbols* production::getProductionIndexOf(int i){
    if(i >= len){
        std::cerr << "index Overflow..." << std::endl;
        return NULL;
    }
    return pro[i];
}
int production::getLen(){
    return len;
}
void production::print(){
    std::cerr << vn->getName() << "->";
    for(int i = 0; i < len; ++i){
        if(pro[i]->getClassName() == "VT"){
            std::cerr << ((symbolsVT*)pro[i])->getWord();
        }
        else{
            std::cerr << ((symbolsVN*)pro[i])->getName();
        }
    }
    // std::cerr << std::endl;
}

分析表
分析表，由ACTION表和GOTO表构成，具体的状态内容由前期的DFA分析等得到：
// analysisTable.h
#ifndef analysisTable_h
#define analysisTable_h
#include<map>
#include"symbols.h"
#include"symbolsVN.h"
#include"symbolsVT.h"
#include"production.h"
const int NUMOFVT = 20;
const int NUMOFVN = 20;
const int NUMOFSTATE = 30;
const int NUMOFPRODUCTIONS = 30;
/*
分析表子程序
由前期的分析得到该文法的分析表，由ACTION表和GOTO表构成
*/
class ACTIONTable{
private:
    std::pair<char, int> ACTION[NUMOFSTATE][NUMOFVT];
    int numofstate;						// ACTION表状态的数量
    int numofsymbolsvt;					// ACTION表终结符的数量
    std::map<symbolsVT*, int> vtmap;    // 终结符对应在分析表中的位置
    int getVTMap(symbolsVT*);			// 获得终结符对应的编号
public:
    ACTIONTable();
    ACTIONTable(int);
    ~ACTIONTable(){}
    void setNumOfState(int);			// GOTO状态数量
    void insertVT(symbolsVT*);			// 插入一个终结符以及给一个对应的编号
    void insertSHIFT(int state, symbolsVT* vt, int numOfPro);       // 插入一个移进状态
    void insertREDUCE(int state, symbolsVT* vt, int numOfPro);      // 插入一个规约状态
    void insertACC(int state, symbolsVT* vt);                       // 插入一个acc状态
    std::pair<char, int> getACTION(int state, symbolsVT* vt);       // 获得一个ACTION信息
    void print();
};
class GOTOTable{
private:
    int GOTO[NUMOFSTATE][NUMOFVN];
    int numofstate;						// GOTO状态数量
    int numofsymbolsvn;
    std::map<symbolsVN*, int> vnmap;    // 非终结符对应在分析表中的位置
    int getVNMap(symbolsVN*);			// 获得非终结符对应的编号
public:
    GOTOTable();
    GOTOTable(int);
    ~GOTOTable(){}
    void setNumOfState(int);			// 设置GOTO表的状态数
    void insertVN(symbolsVN*);          // 插入一个非终结符
    void insert(int state, symbolsVN* vn, int numOfPro);    // 插入一个GOTO状态
    int get(int state, symbolsVN* vn);                      // 获得一个GOTO状态
    void print();
};
class analysisTable
{
private:
    ACTIONTable ACTION;                 // ACTION表
    GOTOTable GOTO;                     // GOTO表
    int numofstate;                     // 状态个数I_n
    int numofpro;                       // 产生式数量
    production* productions[NUMOFPRODUCTIONS];  // 产生式数组，下标即为编号
public:
    analysisTable(int ns);
    // analysisTable(int, int, int);
    ~analysisTable() {}
    void insertSymbols(symbols*);		// 插入一个符号
    void insertProduction(production* p);	// 插入一条产生式，自动编号
    production* getProduction(int i);	// 获得第i条产生式
    void insert(int state, symbols* s, char ch, int numOfPro);	// 插入一个状态
    std::pair<char, int> get(int state, symbols* s);	// 获得一个状态
    void print();
};

#endif /*analysisTable_h*/

// analysisTable.cpp
#include<iostream>
#include<algorithm>
#include<string.h>
#include"analysisTable.h"

ACTIONTable::ACTIONTable(){
    numofsymbolsvt = 0;
    vtmap.clear();
    std::pair<char, int> init = std::make_pair('e', -1);
    // fill(begin(ACTION), end(ACTION), std::make_pair('e', -1));
    for(int i = 0; i < NUMOFSTATE; ++i)
        for(int j = 0; j < NUMOFVT; ++j)
            ACTION[i][j] = init;
    std::cerr << "ACTIONTable has created..." << std::endl;
}
void ACTIONTable::setNumOfState(int ns){
    numofstate = ns;
}
int ACTIONTable::getVTMap(symbolsVT* vt){
    if(vtmap.find(vt) != vtmap.end())return vtmap[vt];
    return -1;
}
void ACTIONTable::insertVT(symbolsVT* vt){
    vtmap[vt] = numofsymbolsvt++;
}
void ACTIONTable::insertSHIFT(int state, symbolsVT* vt, int numOfPro){
    int nvt = getVTMap(vt);
    if(state < numofstate && ~nvt){
        ACTION[state][nvt] = std::make_pair('s', numOfPro);
    }
}
void ACTIONTable::insertREDUCE(int state, symbolsVT* vt, int numOfPro){
    int nvt = getVTMap(vt);
    if(state < numofstate && ~nvt){
        ACTION[state][nvt] = std::make_pair('r', numOfPro);
    }
}
void ACTIONTable::insertACC(int state, symbolsVT* vt){
    int nvt = getVTMap(vt);
    if(state < numofstate && ~nvt){
        ACTION[state][nvt] = std::make_pair('a', 0x3f3f3f3f);
    }
}
std::pair<char, int> ACTIONTable::getACTION(int state, symbolsVT* vt){
    int nvt = getVTMap(vt);
    if(state < numofstate && ~nvt){
        return ACTION[state][nvt];
    }
    return std::make_pair('e', -1);
}
void ACTIONTable::print(){
    std::cerr << "ACTION:" << std::endl;
    std::cerr << numofsymbolsvt << std::endl;
    std::cerr << "\t";
    // for(auto i: vtmap)std::cerr << i.first->getWord() << "\t";
    for(std::map<symbolsVT*, int>::iterator i = vtmap.begin(); i != vtmap.end(); ++i)std::cerr << i->first->getWord() << "\t";
    std::cerr << std::endl;
    for(int i = 0; i < numofstate; ++i){
        std::cerr << i << ": \t";
        for(int j = 0; j < numofsymbolsvt; ++j){
            if(~ACTION[i][j].second)
                std::cerr << ACTION[i][j].first << ACTION[i][j].second << " \t";
            else
                std::cerr << "   \t";
        }
        std::cerr << std::endl;
    }
    std::cerr << std::endl;
}


GOTOTable::GOTOTable(){
    numofsymbolsvn = 0;
    vnmap.clear();
    memset(GOTO, -1, sizeof GOTO);
    std::cerr << "GOTOTable has created..." << std::endl;
}
void GOTOTable::setNumOfState(int ns){
    numofstate = ns;
}
void GOTOTable::insertVN(symbolsVN* vn){
    vnmap[vn] = numofsymbolsvn++;
}
int GOTOTable::getVNMap(symbolsVN* vn){
    if(vnmap.find(vn) != vnmap.end())return vnmap[vn];
    return -1;
}
void GOTOTable::insert(int state, symbolsVN* vn, int numOfPro){
    int nvn = getVNMap(vn);
    if(state < numofstate && ~nvn){
        GOTO[state][nvn] = numOfPro;
    }
}
int GOTOTable::get(int state, symbolsVN* vn){
    int nvn = getVNMap(vn);
    if(state < numofstate && ~nvn){
        return GOTO[state][nvn];
    }
    return -1;
}
void GOTOTable::print(){
    std::cerr << "GOTO:" << std::endl;
    std::cerr << numofsymbolsvn << std::endl;
    std::cerr << "\t";
    // for(auto i: vnmap)std::cerr << i.first->getName() << "\t";
    for(std::map<symbolsVN*, int>::iterator i = vnmap.begin(); i != vnmap.end(); ++i)std::cerr << i->first->getName() << "\t";
    std::cerr << std::endl;
    for(int i = 0; i < numofstate; ++i){
        std::cerr << i << ": \t";
        for(int j = 0; j < numofsymbolsvn; ++j){
            if(~GOTO[i][j])
                std::cerr << GOTO[i][j] << "\t";
            else
                std::cerr << "   \t";
        }
        std::cerr << std::endl;
    }
    std::cerr << std::endl;
}


analysisTable::analysisTable(int ns):numofstate(ns){
    ACTION.setNumOfState(numofstate);
    GOTO.setNumOfState(numofstate);
    numofpro = 0;
    std::cerr << "An AnalysisTable has created..." << std::endl;
}
void analysisTable::insertSymbols(symbols* s){
    if(s->getClassName() == "VT"){
        ACTION.insertVT((symbolsVT*)(s));
    }
    else if(s->getClassName() == "VN"){
        GOTO.insertVN((symbolsVN*)(s));
    }
}
void analysisTable::insertProduction(production* p){
    productions[numofpro++] = p;
}
production* analysisTable::getProduction(int i){
    if(i < numofpro)return productions[i];
    // return nullptr;
    return NULL;
}
void analysisTable::insert(int state, symbols* s, char ch, int numOfPro){
    if(s->getClassName() == "VT"){
        if(ch == 'a'){
            ACTION.insertACC(state, (symbolsVT*)(s));
        }
        else if(ch == 's'){
            ACTION.insertSHIFT(state, (symbolsVT*)(s), numOfPro);
        }
        else if(ch == 'r'){
            ACTION.insertREDUCE(state, (symbolsVT*)(s), numOfPro);
        }
    }
    else if(s->getClassName() == "VN"){
        GOTO.insert(state, (symbolsVN*)(s), numOfPro);
    }
}
std::pair<char, int> analysisTable::get(int state, symbols* s){
    if(s->getClassName() == "VT"){
        return ACTION.getACTION(state, (symbolsVT*)(s));
    }
    else if(s->getClassName() == "VN"){
        return std::make_pair('g', GOTO.get(state, (symbolsVN*)(s)));
    }
    return std::make_pair('e', -1);
}
void analysisTable::print(){
    std::cerr << "analysisTable: " << std::endl;
    ACTION.print();
    GOTO.print();
    std::cerr << std::endl;
}

LR分析总控程序
根据LR分析程序编写的总控程序，包括初始化、读入、分析以及释放资源等：
// SLRAnalysis.cpp
#include<iostream>
#include<cstdio>
#include<string.h>
#include"symbols.h"
#include"symbolsVN.cpp"
#include"symbolsVT.cpp"
#include"production.cpp"
#include"analysisTable.cpp"
const int maxnAnalysisStack = 1e2 + 5;

// 定义出文法的所有终结符
symbolsVT* PLUS = new symbolsVT("+", "plus");
symbolsVT* MINUS = new symbolsVT("-", "minus");
symbolsVT* times = new symbolsVT("*", "times");
symbolsVT* slash = new symbolsVT("/", "slash");
symbolsVT* lparen = new symbolsVT("(", "lapren");
symbolsVT* rparen = new symbolsVT(")", "rparen");
symbolsVT* ident = new symbolsVT("i", "ident");
symbolsVT* unsignint = new symbolsVT("u", "unsignint");
symbolsVT* END = new symbolsVT("#", "end");
symbolsVT* epslion = new symbolsVT("e", "epslion");
// 定义出文法的所有非终结符
symbolsVN* Sdot = new symbolsVN("S'");
symbolsVN* E = new symbolsVN("E");
symbolsVN* T = new symbolsVN("T");
symbolsVN* F = new symbolsVN("F");

// 构造所有的产生式
production* Sdotproduction[1];
production* Eporduction[5];
production* Tproduction[3];
production* Fproduction[3];

// 定义出预测分析表
analysisTable AnalysisTable(21);

// 分析栈
std::pair<int, symbols*> analysisStack[maxnAnalysisStack];
int top;
void init(){
    // 初始化所有变量
	// 根据文法的不同，得到的分析表的结构也不同，此时初始化部分也不同

    // 定义出预测分析表
	// 为预测分析表插入终结符、非终结符
    AnalysisTable.insertSymbols(PLUS);
    AnalysisTable.insertSymbols(MINUS);
    AnalysisTable.insertSymbols(times);
    AnalysisTable.insertSymbols(slash);
    AnalysisTable.insertSymbols(lparen);
    AnalysisTable.insertSymbols(rparen);
    AnalysisTable.insertSymbols(ident);
    AnalysisTable.insertSymbols(unsignint);
    AnalysisTable.insertSymbols(END);

    AnalysisTable.insertSymbols(Sdot);
    AnalysisTable.insertSymbols(E);
    AnalysisTable.insertSymbols(T);
    AnalysisTable.insertSymbols(F);

    // 根据文法定义E的三条产生式，同理处理其他的产生式
    for(int i = 0; i < 1; ++i)Sdotproduction[i] = new production(Sdot);
    Sdotproduction[0]->push_back(E);
    Sdotproduction[0]->print();


    for(int i = 0; i < 5; ++i)Eporduction[i] = new production(E);

    Eporduction[0]->push_back(T);
    Eporduction[1]->push_back(PLUS); Eporduction[1]->push_back(T);
    Eporduction[2]->push_back(MINUS); Eporduction[2]->push_back(T);
    Eporduction[3]->push_back(E); Eporduction[3]->push_back(PLUS); Eporduction[3]->push_back(T);
    Eporduction[4]->push_back(E); Eporduction[4]->push_back(MINUS); Eporduction[4]->push_back(T);
    for(int i = 0; i < 5; ++i)E->insertProduction(Eporduction[i]);
    for(int i = 0; i < 5; ++i)Eporduction[i]->print();
    
    for(int i = 0; i < 3; ++i)Tproduction[i] = new production(T);
    Tproduction[0]->push_back(F);
    Tproduction[1]->push_back(T); Tproduction[1]->push_back(times); Tproduction[1]->push_back(F);
    Tproduction[2]->push_back(T); Tproduction[2]->push_back(slash); Tproduction[2]->push_back(F);
    for(int i = 0; i < 3; ++i)T->insertProduction(Tproduction[i]);
    for(int i = 0; i < 3; ++i)Tproduction[i]->print();

    
    for(int i = 0; i < 3; ++i)Fproduction[i] = new production(F);
    Fproduction[0]->push_back(ident);
    Fproduction[1]->push_back(unsignint);
    Fproduction[2]->push_back(lparen); Fproduction[2]->push_back(E); Fproduction[2]->push_back(rparen);
    for(int i = 0; i < 3; ++i)F->insertProduction(Fproduction[i]);
    for(int i = 0; i < 3; ++i)Fproduction[i]->print();   

    for(int i = 0; i < 1; ++i)AnalysisTable.insertProduction(Sdotproduction[i]);
    for(int i = 0; i < 5; ++i)AnalysisTable.insertProduction(Eporduction[i]);
    for(int i = 0; i < 3; ++i)AnalysisTable.insertProduction(Tproduction[i]);
    for(int i = 0; i < 3; ++i)AnalysisTable.insertProduction(Fproduction[i]);

    // 给出LR分析表
    AnalysisTable.insert(0, PLUS, 's', 5); AnalysisTable.insert(0, MINUS, 's', 4); AnalysisTable.insert(0, lparen, 's', 8); AnalysisTable.insert(0, ident, 's', 6); AnalysisTable.insert(0, unsignint, 's', 7); AnalysisTable.insert(0, E, ' ', 1); AnalysisTable.insert(0, T, ' ', 2); AnalysisTable.insert(0, F, ' ', 3);
    AnalysisTable.insert(1, PLUS, 's', 9); AnalysisTable.insert(1, MINUS, 's', 10); AnalysisTable.insert(1, END, 'a', -1);
    AnalysisTable.insert(2, PLUS, 'r', 1); AnalysisTable.insert(2, MINUS, 'r', 1); AnalysisTable.insert(2, times, 's', 11); AnalysisTable.insert(2, slash, 's', 12); AnalysisTable.insert(2, rparen, 'r', 1); AnalysisTable.insert(2, END, 'r', 1);
    AnalysisTable.insert(3, PLUS, 'r', 6); AnalysisTable.insert(3, MINUS, 'r', 6); AnalysisTable.insert(3, times, 'r', 6); AnalysisTable.insert(3, slash, 'r', 6); AnalysisTable.insert(3, rparen, 'r', 6); AnalysisTable.insert(3, END, 'r', 6);
    AnalysisTable.insert(4, T, ' ', 13);
    AnalysisTable.insert(5, T, ' ', 14);
    AnalysisTable.insert(6, PLUS, 'r', 9); AnalysisTable.insert(6, MINUS, 'r', 9); AnalysisTable.insert(6, times, 'r', 9); AnalysisTable.insert(6, slash, 'r', 9); AnalysisTable.insert(6, rparen, 'r', 9); AnalysisTable.insert(6, END, 'r', 9);
    AnalysisTable.insert(7, PLUS, 'r', 10); AnalysisTable.insert(7, MINUS, 'r', 10); AnalysisTable.insert(7, times, 'r', 10); AnalysisTable.insert(7, slash, 'r', 10); AnalysisTable.insert(7, rparen, 'r', 10); AnalysisTable.insert(7, END, 'r', 10);
    AnalysisTable.insert(8, PLUS, 's', 5); AnalysisTable.insert(8, MINUS, 's', 4); AnalysisTable.insert(8, lparen, 's', 8); AnalysisTable.insert(8, ident, 's', 6); AnalysisTable.insert(8, unsignint, 's', 7); AnalysisTable.insert(8, E, ' ', 15); AnalysisTable.insert(8, T, ' ', 2); AnalysisTable.insert(8, F, ' ', 3);
    AnalysisTable.insert(9, lparen, 's', 8); AnalysisTable.insert(9, ident, 's', 6); AnalysisTable.insert(9, unsignint, 's', 7); AnalysisTable.insert(9, T, ' ', 16); AnalysisTable.insert(9, F, ' ', 3);
    AnalysisTable.insert(10, lparen, 's', 8); AnalysisTable.insert(10, ident, 's', 6); AnalysisTable.insert(10, unsignint, 's', 7); AnalysisTable.insert(10, T, ' ', 17); AnalysisTable.insert(10, F, ' ', 3);
    AnalysisTable.insert(11, lparen, 's', 8); AnalysisTable.insert(11, ident, 's', 6); AnalysisTable.insert(11, unsignint, 's', 7); AnalysisTable.insert(11, F, ' ', 18);
    AnalysisTable.insert(12, lparen, 's', 8); AnalysisTable.insert(12, ident, 's', 6); AnalysisTable.insert(12, unsignint, 's', 7); AnalysisTable.insert(12, F, ' ', 19);
    AnalysisTable.insert(13, PLUS, 'r', 3); AnalysisTable.insert(13, MINUS, 'r', 3); AnalysisTable.insert(13, rparen, 'r', 3); AnalysisTable.insert(13, END, 'r', 3);
    AnalysisTable.insert(14, PLUS, 'r', 2); AnalysisTable.insert(14, MINUS, 'r', 2); AnalysisTable.insert(14, rparen, 'r', 2); AnalysisTable.insert(14, END, 'r', 2);
    AnalysisTable.insert(15, PLUS, 's', 9); AnalysisTable.insert(15, MINUS, 's', 10); AnalysisTable.insert(15, rparen, 's', 20);
    AnalysisTable.insert(16, PLUS, 'r', 4); AnalysisTable.insert(16, MINUS, 'r', 4); AnalysisTable.insert(16, times, 's', 11); AnalysisTable.insert(16, slash, 's', 12); AnalysisTable.insert(16, rparen, 'r', 4); AnalysisTable.insert(16, END, 'r', 4);
    AnalysisTable.insert(17, PLUS, 'r', 5); AnalysisTable.insert(17, MINUS, 'r', 5); AnalysisTable.insert(17, times, 's', 11); AnalysisTable.insert(17, slash, 's', 12); AnalysisTable.insert(17, rparen, 'r', 5); AnalysisTable.insert(17, END, 'r', 5);
    AnalysisTable.insert(18, PLUS, 'r', 7); AnalysisTable.insert(18, MINUS, 'r', 7); AnalysisTable.insert(18, times, 'r', 7); AnalysisTable.insert(18, slash, 'r', 7); AnalysisTable.insert(18, rparen, 'r', 7); AnalysisTable.insert(18, END, 'r', 7);
    AnalysisTable.insert(19, PLUS, 'r', 8); AnalysisTable.insert(19, MINUS, 'r', 8); AnalysisTable.insert(19, times, 'r', 8); AnalysisTable.insert(19, slash, 'r', 8); AnalysisTable.insert(19, rparen, 'r', 8); AnalysisTable.insert(19, END, 'r', 8);
    AnalysisTable.insert(20, PLUS, 'r', 11); AnalysisTable.insert(20, MINUS, 'r', 11); AnalysisTable.insert(20, times, 'r', 11); AnalysisTable.insert(20, slash, 'r', 11); AnalysisTable.insert(20, rparen, 'r', 11); AnalysisTable.insert(20, END, 'r', 11);
    AnalysisTable.print();
	
	// 初始化分析栈
    top = -1;
}
void release(){
	// 释放所有的动态申请的资源
    delete PLUS;
	delete MINUS;
	delete times;
	delete slash;
	delete lparen;
	delete rparen;
	delete ident;
	delete unsignint;
	delete END;
	delete epslion;
    delete E;
	delete T;
	delete F;
    for(int i = 0; i < 1; ++i)delete Sdotproduction[i];
    for(int i = 0; i < 5; ++i)delete Eporduction[i];
    for(int i = 0; i < 3; ++i)delete Tproduction[i];
    for(int i = 0; i < 3; ++i)delete Fproduction[i];
}
std::string word, code; 
// char word[10], code[10];
char ch;
symbolsVT* a;
void ADVANCE(){
	// 读入一个词法分析的结果项，同时给出对应的终结符a
    // if(scanf("(%s,%s)", code, word) != -1){
    std::cin >> ch;
    if(!std::cin.eof()){
    // if(scanf("%c", &ch) != -1){
        std::getline(std::cin, code, ',');
        std::getline(std::cin, word);
        word.resize(word.size() - 1);
        // std::cin >> ch;
        std::cerr << word << " " << code << std::endl;
        if(code == "plus")a = PLUS;
        else if(code == "minus") a = MINUS;
        else if(code == "times") a = times;
        else if(code == "slash") a = slash;
        else if(code == "lparen") a = lparen;
        else if(code == "rparen") a = rparen;
        else if(code == "ident") a = ident;
        else if(code == "number") a = unsignint;
    }
    else{ 
        a = END;
    // if(std::cin.eof() == EOF){
        std::cerr << "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh" << std::endl;
    }
    std::cerr << word << "_____________" << code << std::endl;
}
bool SLRAnalysis(){
	// 预测分析程序的总控程序
    init();
    bool grammer = true;		// 表示句子是否符合一定的文法
    bool flag = true;			// 总控程序的运行标志
    analysisStack[++top] = std::make_pair(0, (symbols*)END);  // 初始化栈，将状态0和符号#压入
    std::pair<int, symbols*> X;					// 定义一个公共变量：状态和符号的指针
    production *p;				// 定义一个产生式的指针
    std::pair<char, int> state; // 从分析表中获得的状态信息
    ADVANCE();					// 读入一个词法分析的结果项
    while(flag){
		//************************************************************//
		// 调试信息：状态栈和符号栈的中内容
        std::cerr << std::endl << std::endl;
        std::cerr << "================" << std::endl;
        a->print();
        std::cerr << "stack: " << std::endl;;
        for(int i = 0; i <= top; ++i){
            std::cerr << analysisStack[i].first << " ";            
        }
        std::cerr << std::endl;
        for(int i = 0; i <= top; ++i){
            if(analysisStack[i].second->getClassName() == "VT")std::cerr << ((symbolsVT*)(analysisStack[i].second))->getWord() << " ";
            else std::cerr << ((symbolsVN*)analysisStack[i].second)->getName() << " ";
        }
        std::cerr << std::endl << "================" << std::endl;
        std::cerr << std::endl;
		//************************************************************//
		
        X = analysisStack[top];	// 得到分析栈的栈顶元素，pop操作
        state = AnalysisTable.get(X.first, a);	// 根据栈顶的状态以及分析表中的变化情况来获得下一转换的状态s_i, r_i, acc, i等等
        std::cerr << state.first << "  " << state.second << std::endl;
        if(state.first == 's'){		// 如果是移进状态
            analysisStack[++top] = std::make_pair(state.second, a);
            ADVANCE();
            std::cerr << "One SHIFT..." << std::endl << std::endl;;
        }
        else if(state.first == 'r'){	// 如果是规约状态
            p = AnalysisTable.getProduction(state.second);	// 获得第i个产生式
            p->print();
            int len = p->getLen();
            top -= len;					// 将栈顶的符号按照产生式来规约
            X = analysisStack[top];		// 获得此时的栈顶元素，据此来获得GOTO表的下一状态
            analysisStack[++top] = std::make_pair(AnalysisTable.get(X.first, p->getVN()).second, p->getVN());
            std::cerr << "One REDUCE..." << std::endl << std::endl;;
        }
        else if(state.first == 'a'){	// 如果是acc状态
            std::cerr << "ACC!!!" << std::endl << std::endl;
            flag = false;
        }
        else{							// 到达分析表的其他状态，错误
            grammer = false;
            flag = false;
        }
    }

    release();		// 释放资源
    return grammer;	// 返回结果，true表示句子符合一定的语法
}

程序入口
项目调用测试入口：
// main.cpp
#include<bits/stdc++.h>
#include"SLRAnalysis.cpp"
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1e2 + 5;
const int inf = 0x3f3f3f3f;


int main(int argc, char *argv[]){
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);

    if(SLRAnalysis()) cout << "Yes,it is correct." << endl;
    else cout << "No,it is wrong." << endl;

    return 0;
}

调试数据
给出两组测试数据：
// in.in
(lparen,()
(ident,a)
(plus,+)
(number,15)
(rparen,))
(times,*)


// out.out
No,it is wrong.

// in.in
(ident,akldjsfkl)
(plus,+)
(lparen,()
(ident,alk)
(times,*)
(ident,askd)
(minus,-)
(ident,jfdkj)
(times,*)
(ident,ksfj)
(slash,/)
(ident,jsadlk)
(plus,+)
(lparen,()
(ident,a)
(slash,/)
(ident,v)
(minus,-)
(ident,d)
(plus,+)
(ident,b)
(rparen,))
(rparen,))
(slash,/)
(ident,jfj)

// out.out
Yes,it is correct.

实验体会
本次实验是完成 LR分析法 的自下而上分析，相比较上一次实验的预测分析法，LR分析法主要的差别是分析表的构造上，通过活前缀DFA的构造，以及由此分析得到SLR分析表，将图的转换变为表内各状态的转换。实验中，自我认为最难的并不是程序的编写，而是构造活前缀DFA以及得到分析表的步骤，这一步中画图花费了很多的时间，同时也再一次的复习了相关的理论知识内容，当这一切准备工作完成后，只需根据此编写相关的代码即可，以为上个实验已经完成了最基础的诸如符号、产生式等类的编写，所以这次只需考虑分析表以及分析程序的编写，这次实验的简化也一定程度上达到了上一次实验中 代码重复使用 的目的。实验整体难度不大，是进一步的对理论知识的复习过程。
HTML

知识点
       自上而下分析法是从输入串开始，逐步进行规约，知道规约到文法的开始符号，即从语法书的末端开始，向上规约到根部。自上而下分析采用了移进-规约的方法进行语法分析，用一个寄存符号的栈，从输入串中将符号一个个移进栈中，使栈顶形成某一候选式的产生式，再将这部分产生式规约成该产生式左部的符号。 自上而下分析中有两种分析方法，算符优先方法和规范规约方法，分别使用最左素短语和句柄来描述可规约串。
        一 规范规约：
        如果在一个文法中 S=>* αAγ且A=>+ β 则称β是句型αβγ相对于非终结符A的短语，两个条件缺一不可。如果A可以直接推出β则称β是句型αβγ相对于规则A->β的直接短语。而一个举行的最左直接短语测成为该举行的句柄。
        规范规约的定义：
        定义：假定a是文法G的一个句子，我们称序列
                   an， an-1，... ，a0
           是a的一个规范归约，如果此序列满足：
          (1)  an= a
          (2)  a0为文法的开始符号，即a0=S
          (3)  对任何i，0 < i £ n， ai-1是从ai经把句柄替换成为相应产生式左部符号而得到的。
        规范规约是规范推导（最右推导）的逆过程。
        

        二 算符优先：
        算符优先定义了算符之间的优先关系，借助这种关系来寻找可规约串和进行规约。算符之间的关系有三种：
        a<.b a的优选性低于b；a=.b a的优选性等于b；a>.b a的优先性大于b。
        注：a<.b 并不意味着b>.a，a=.b也不意味着b=.a。
        使用算符优先文法构造优先表。若P->···aQb···或P->···ab···，则a=.b，若P->···aR···且R->···b···或R->···Qb···，则a<.b，若P->···Rb···且R->···a···或R->···aQ···，则a>.b，然后通过优先符之间的优先关系，生成firstvt(P)和lastvt(P)集合。
	
        为了完成算符优先算法的设计，引入素短语的概念。素短语就是指一个举行的短语，它至少包含有一个终结符号，且除去它本身，不再含有更小的素短语。处在句型最左边的素短语称为最左素短语。

        三 LR分析：
        LR分析器的核心是一张分析表，包括动作（action）和状态转换（goto）两个表。action[s,a]规定了当前的状态，goto[s,X]规定了状态s面对文法符号X（终结符或非终结符）是下一状态是什么（以文发符号为字母表的dfa）。
        action的四种动作：移进，规约，接受，报错。
        LR文法：对于一个文法，如果能构造一张分析表，是的它的每一个入口都是唯一确定的，则这个文法是LR文法。
        如果一个文法每一步顶多向前检查k个输入符号的LR分析器进行分析，这这个文法为LR（k）文法。
        LR（0）项目：在产生式中添加原点 · 。原点在符号左边表示该符号未处理，在符号右边表示该符号已经处理。
        添加项目概念的目的是为了识别文法中的活前缀（规范句型的一个前缀，这种前缀不含句柄之后的任何符号）。我们可以通过构造一个有限自动机来识别该文法的所有活前缀，并将自动机转变成LR分析表。而构造识别一个文法活前缀的DFA的项目集（状态）的全体称为这个文法的LR（0）项目集规范族。
        LR（0）项目集规范族的构造：引入closure（闭包）。
        
        

  衔接上一章的词法分析，这章就到了语法分析。语法分析大体上分了两种：自上而下和自下而上。这章的主要内容是前者，下一章会对后者进行介绍。其实学到了这里应该清楚语法分析和词法分析的关系了。在实际编译的过程中并不是先进行一遍词法分析，再来一遍语法分析。两者其实是并行的。从缓冲区中读入一定字符串，经过词法分析合格后进行语法的审核。符合语法规则通过，不符合就报错。这样周而复始直至结束。
  语法分析要联系到第二章的内容了，还记得什么是文法吗？就是那个使用四元式表示（不过四元式在本章中没什么地位），表示语法规则的文法啊。其实我觉得这章的一个核心内容就是告诉如何利用文法来进行语法分析的，更为通俗的一种说法是文法如何找到语法错误的呢？且听我慢慢道来！
  先列举一下本章的关键词：自上而下、FIRST集、FOLLOW集、LL（1）分析法，递归下降分析程序、预测分析程序、LL(1)文法的出错处理。
  希望通过这篇文章能说明这些关键词是什么，更希望说明为什么。下面正式开始吧！
语法分析——自上而下
  这章的题目就是这个，其实说白了语法分析就是个匹配字符串的环节嘛。看你输入的字符串在我已表示的语言中能否找到对应的。之前第二章介绍过对于任何语法都可以构建成一颗语法分析树。从开始符号开始，一个又一个的产生式衔接，匹配结束且刚好到达叶子节点。整个过程就是自上而下的语法分析。Hhh，说起来很轻松哈，那如何在那么多个分岔口找到最正确的一条呢？这就需要学一下正确的语法分析步骤喽~
  自上而下也是一个推导的过程，之前提过推导分为最左推导和最右推导。在自上而下中，统一规定使用最左推导。
  先来看一个简单的例子（这个例子没有说明语句是否符合语法规则，只是表示一下推导过程）：

  在本例中每步都要进行一个产生式的选择，选择的原则就是尽可能让终结符贴近要表达的。从字符逐个匹配的角度看，本例中的字符串一个个进行匹配并且恰好都是正确（为什么这么说呢？来看下面这个：）


  对于上图中，一眼就可以看见第二才是正确的，但是在计算机识别过程中由于**中的第一个和xy中达成了匹配，是不会立即检验下一个字符的。当检验下一个字符时原式中是y而自己拼的是*，计算机这才知道：哦，错了！其实错了也没关系嘛，可以采用回溯的思想退回到上一个成功匹配的字符处选择另一个产生式，就选到了x*y了。回溯当然OK啦！可我们都知道回溯是要多耗费一些资源（时间/空间）的，避免回溯是学计算机人的伟大使命。但似乎随着算力和空间的发展，当我们真的不在乎回溯的影响时，就可以肆意妄为了吗？答案是No!来看下面这个例子：

  按照前面的思想：不停的回溯重来，结果就会使Saaaaaa…aaaa，这样运行下去再大的空间也终有一日会满（积硅步，行千里）。这种情况就叫做左递归。左递归作为语法分析最大的敌人之一，自然需要被先解决。那左递归如何可以被消除呢？
消除直接左递归的方法


  再配上我独门的记忆口诀：引入新的非终结符，把所有原来没有左递归的项加上新的非终结符组成一个产生式，再为新非终结符构造一个产生式：把之前左递归的右边系数加上新非终结符构成一个右递归，最后再加上个空字即可大功告成。
  举个例子：


  注意上面的副标题我多加了“直接”两字，只有一眼直接看到S->Sx的才是左递归吗？当然没有这么简单~看下例：


  如果把三个产生式一层层消除，就按照SQR的顺序依次带入前者（即Q带入S，R带入Q）最后会得到这样的结果：


  当出现这样的情况时，就发现上面的解决办法只能解决直接左递归。对于这种间接的还是比较麻烦。下面介绍一下通用的消除左递归办法：


  其实这个说是办法，方法还是属于暴力迭代。尽可能消去无用的非终结符达到一眼看出直接左递归的情况为止，再按照上面的方法解决问题。
  这里有个事情需要强调下：第一步对于顺序的排列是无所谓的。选择不同的顺序可能会导致最后构造出的文法不完全相同（因为在选择添加新的非终结符时，非左递归项可能不同），但能完成同样消除左递归的功能即可。
  所以对于上面问题的解决办法就是：


  说到现在，左递归就基本说完了。其实回想整个过程，左递归是语法分析必须要避免的。具有消除左递归的方法，但同样也需要付出：引入新的非终结符。（正所谓：天上不会掉馅饼~）
  上文介绍到，我们要避免回溯。那想想为什么会出现回溯呢？不就是因为一个“虚假”的匹配嘛？如果我们能够避免这种虚假，不就可以消除回溯吗？什么意思呢？比如A->x1|x2|x3…，下个字符要匹配a，如果x1,x2,x3等所有项中只有一个第一个字符是a，那不就直接选这个，对了就继续走，不对就匹配失败呗。这就是提取公共左因子。
提取公共左因子

  其实这个方法有点像小时候学加法的时候提取公因式，当把公因式提取出来时对于当前字符只有了唯一项，就不会出现当前字符造成回溯的情况了。需要注意的是：一定要提取最长公共前缀。
FIRST集、FOLLOW集
  按照思路：先懂是什么，再懂为什么？先对如何计算两种集合做一个介绍。
FIRST集
  FIRST集的全名叫做终结首符集，每一个非终结符都有。就是由该非终结符能够推导出的第一个终结符或空字组成的集合。看一下标准的概念：


  那求某一非终结符FIRST集的步骤呢？看下面（先形式化的定义下，后面有配合的例题进行讲解）：

FOLLOW集
  FOLLOW集是推导过程中非终结符紧接着的终结符组成的集合。


  对于FOLLOW集有两个需要特别注意：
    1）对于起始符的FOLLOW集需要引入“#”符号
    2） 在FOLLOW集中不可能出现空字ε
  求FOLLOW集的步骤如下：


  从上面可知，FOLLOW集只关注于产生式的右边。对于某一非终结符，影响其FOLLOW集的只是右边包含该非终结符的产生式。
  如果你从上面文字性的就看懂了，求解FIRST集和FOLLOW集的步骤。那你真是个天才，像我这种稍微有点儿笨的只能看看例题理解理解哈：


  这类题顺序是先求解FIRST集再求解FOLLOW集。
  对于FIRST(E)，E的产生式第一项是T是非终结符，所以求E必须先求出T的FIRST集，FIRST（T）中的内容都属于FIRST(E)。转而求解FIRST(T)，T的产生式第一项是F，转而求解F。F的第一项有两个并且均为终结符——{(,i};所以可反推出FIRST(E/T/F)均为{（，i}；求解FIRST(E’)，E‘有两项组成第一个是终结符+，加入集合。第二个是空字，按照定义也加入集合。最终得到{+，ε}。同理可得FIRST(T’)为{*，i}；
   对于FOLLOW集，首先E作为开始符，先将#加入FOLLOW（E）中，接着寻找右侧产生式带E的，看后面是否为终结符。本例中E后只有），将其加入FOLLOW（E）中。对于E’，在前两个产生式中出现，但后面无任何符号（相当于空字ε），于是顺承左边非终结符的FOLLOW集，即FOLLOW（E）。并且FIRST（E）中无空字ε。FOLLOW（E’）= FOLLOW(E) = { ），#}。接着计算FOLLOW（T）,T后为E’，于是将FOLLOW（E’）及非字FIRST（E‘）加入T中，得出FOLLOW(T)={+，），#}。对于T’后无字符，顺承T，且FIRST(T)中无空字，FOLLOW(T‘)=FOLLOW（T’）。F后为T‘，FIRST(T’)含有空字，将FIRST集非空字符及FOLLOW(T‘)加入FOLLOW(F)中={*，+，），#}。
  弄懂以上的两个过程，证明已经会求解FIRST集和FOLLOW集了，也许可以参加考试了。但是为什么需要FIRST集和FOLLOW集呢？仔细想想FIRST集和FOLLOW集究竟干了什么呢？我将其理解为开始匹配和继续匹配。当我们面临一个新的非终结符时，可能由于产生式的多个或，选错了就要进行回溯。务必一击就中，就可以通过FIRST集，FIRST集中每一项都是可直接到达，且路线唯一。而FOLLOW集就是当前非终结符下一个终结符可以是哪个？如果当前的符号不在备选范围内，就说明不存在下一个到达提供字符的可能，即认定失败。成功继续，失败结束。两个集合起的作用就是让一切看起来尽量直观。
LL(1)文法
   LL（1）文法是一类特殊的文法，其需满足的条件如下：

  其实LL(1)文法就是进行语法分析的一整套流程，满足该文法字符串有效。不满足就无效。之前一直在纠结于：LL(1)文法的作用是什么呢？其实LL(1)也是一种文法，文法就是用来定义语言的。不过LL1(1)文法特殊在有很多特别的限制。
递归下降分析程序
  其实递归下降程序就是文法（该文法需要确保已无左递归以及公共因子的情况，即LL(1)文法）的分析过程。把每一个产生式写成了一个程序。所以对于任何一个非终结符都有一个属于子集的程序。我把这个理解成贴近于高级语言的语法分析检测过程。文字性的定义放一张图：


  举一个例子，再加上我总结的一点儿规律吧：


  程序开头：PROCEDURE xxx(非终结符名称)
  对于直接由非终结符组成，如E和T。BEGIN和END中间夹着产生式右端所有非终结符，以分号连接。对于第一项为终结符，如果是匹配的就调用ADVANCE。SYM代表当前获取到的单词（即输入字符）。如果是非终结符就调用相应的过程。空字需要特殊处理（虽然在上面的图里没有展示出来），什么时候可以使用空字去进行匹配呢？当需要空字说明目前的SYM与非终结符不匹配。SYM可能是当前非终结符的FOLLOW集，那么对当前非终结符使用空字匹配就可以保证对SYM的匹配。但这有一个要求：SYM必须在取空字非终结符的FOLLOW集中使才可以。否则就是一种错误。说的有点复杂：简单点就是要想成功的取到空字，当前的输入字符必须在非终结符的FOLLOW集中。
扩充的巴科斯范式
  扩充的巴科斯范式是对文法符号的扩展，具体扩展包括三种：


  对以上做个小结：
  递归下降程序就是自顶向下的语法分析，扩充的巴科斯范式是表示文法的一种方法，并且该方法能够比较容易的处理左递归问题。
预测分析程序
   到了预测分析程序就有点偏实用了，采用预测表和栈结合的方法。对一个字符串进行判断。
  预测分析表的作用就是能够直观看出当前非终结符在指定输入下选择哪个具体的产生式。表的列项是所有的非终结符，横项是所有的终结符。具体的坐标要么是产生式要么为空（说明不存在）。形式化的定义如下：

  还拿刚才的例子，说一下预测分析表怎么构造：


  想求预测分析表还是要先求出FIRST和FOLLOW集。按顺序说，写每一个的时候先看FIRST集，对非终结符求每一个候选式的FIRST集合。结果大体可分为两类：有空字和无空字。对于无空字像E和T，在FIRST集合对应的单元格填入该候选式。比如i输入E的FIRST集。在（E，i）中填入候选式E->TE’。如果FIRST集合含有空字，说明xxx->ε。则在该非终结符的FOLLOW集对应的单元格放入该产生式。比如E‘的FIRST集中包含空字，并且FOLLOW（E’）={}，#}。于是在<E’，）>、<E’,#>中加入产生式E’->ε
   需要注意两个事情：
    1.  空出来的地方就是不合法的情况
    2.  表内每个产生式右端只可能出现一种情况
  说完了表，再说说栈。都知道栈是一种数据结构——后进先出。还记得前面说要在起始符的FOLLOW集中加入#嘛？这就是为了在此匹配。在输入字符串的最后加入#，如果两个#匹配到，说明分析结束。结束不代表正确。下文关于错误处理会给出解释。对于栈，在此不在多说（其实是我也不会，不过上机的时候应该需要。如果过后搞懂了，再来补充）。附上形式化描述：

LL(1)文法中的出错处理：
  文法中的错误难免出现，但如果一出错就全部停止。未免有些影响效率。我们崇尚的是那种报错了保留错误位置并且程序能够继续执行的情况。如果在预测分析处理的过程中发现了错误，错误分两种：
  错误一：栈顶的终结符与当前的输入符号不匹配
  错误二：非终结符A处于栈顶，面临的输入符号为a，但预测分析表中M的M[A,a]为空。
  解决方法采用忽略的思想，不断跳过直至下一次匹配再此出现。（此处解释了分析结束并不代表语法正确）

  说到这里自上而下的语法分析主要内容就基本结束了，整个过程说起来比较简单。但如果真正实现起来想必是困难重重。收拾心态，准备迎接更大的挑战，继续加油叭~
感谢编译原理课程谢老师对本文的耐心修改，同时感谢各位博主的优秀文章作为参考。
因作者水平有限，如有错误之处，请在下方评论区指出，谢谢！

1. 重点内容
       上一章讲到了语法分析中自上而下的分析方法，其主要思想是从文法的起始符出发进行句子的推导，这一章主要讲的是与其主要思想相反的自下而上的分析方法，其主要思想是从句子本身出发，进行归约，看能否把句子归约到起始符，即终结符到非终结符的归约。自下而上的分析方法主要有算符优先分析法和LR分析法。
       首先要了解几个基本的概念：移进归约、短语、直接短语、句柄，这些事进行规范归约的基础，规范归约就是最右推导的逆过程。
1. 移进归约：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。 归约就是指根据文法的产生式规则，把产生式的右部替换成左部符号。
2. 短语：令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，其中α,β,δd∈(VN∪VT)*，A∈VN ，如果有
 
则β称是句型αβδ相对于非终结符A的短语。
3. 直接短语：特别是，如果有A=>β,则称β是句型αβδ相对于规则A—>β的直接短语。
4. 句柄：一个句型的最左直接短语称为该句型的句柄。
      通过修剪语法树，根据子树和最简子树的叶节点更直观的找出句型和短语。
     用符号栈进行的自下而上的语法分析相对简单，接下来介绍算符优先分析法。
  算符优先分析法思路是定义算符之间优先关系，借助这种关系来寻找“可归约串”和进行归约。算符之间的优先关系是该分析法的基础，确定好算符之间的优先级后，构造算符优先级表，可借助构造集合LASTVT(P)。
    定义终结符之间的优先关系：
1.   a =. b 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；
2.   a <. b 当且仅当G中含有形如P→…aR…的产生式， 而R  b…或R  Qb…；
3.   a>.b 当且仅当G中含有形如P→…Rb…的产生式，而 R  …a或R …aQ。
  第二种分析法是LR分析法。根据归约过程中向前看输入符号串中字符的个数，定义不同的LR(k)分析方法，通常，k=0，1。LR分析方法是一种适用于一大类上下文无关文法的分析方法，比较复杂，不适于用手工实现，可借助于YACC/bison实现。
     LR分析法可构造LR分析器栈，由action表和goto表构成：
1. 动作表 ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作，每一项ACTION[s，a]所规定的四种动作:移进、归约、接受、报错。两个状态间用终结符连接，对其进行归约或移进，从前一状态转为后状态。
2. 状态转换表 GOTO[s，X]：状态s面对文法符号X时，下一状态是什么。两个状态之间用非终结符链接。
 

 
      LR(0)分析法需要知道什么是活前缀、LR(0)项目、项目集规范族、项目集的闭包、LR(0)分析表的构造。需要注意，该文法移进时不能归约，归约时只归一个产生式。
  活前缀：文法G的活前缀是他的规范句型的前缀，该前缀不超过句柄的右端。
     LR分析表的构造需要构造识别活前缀的有限自动机，用有限自动机中的状态表示分析表中的状态,用状态图中的状态之间的转换关系对分析表中的action、 goto函数等进行定义。 
 
	
2. 习题总结
     只做了部分规范归约的题目，相对于LR分析法要简单些主要练习了短语、句柄的判断，规范归约的分析过程以及算符优先级 的比较。

 
3. 课程总结
      总的来说，算符优先分析法确实要比LR分析法简单很多，这一章我主要掌握了算符优先分析法，包括算符优先级判断、构造FIRSTVT和LASTVT的构造，以及使用符号栈表示规范归约的步骤。LR分析法并没有掌握熟练，只是对于action和goto表、活前缀了解的比较清楚。