这是当时编译原理课的实验作业，其实现在有很多概念记忆已经比较模糊了，好在留下来一篇实验报告，供大家参考，也留给我自己回忆吧。另有一篇SLR语法分析器的设计

实验内容

编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下文法产生。

$ E -> E + T | E - T | T $

$ T -> T * F | T / F | F $

$ F -> (E) | num $

LL(1)分析程序需要用到一个输入缓冲区、一个分析栈、一张分析表，其核心是预测分析程序。
LL(1)要求文法中不含左递归，因此需要先消除左递归：

$ E -> TA $

$ A -> +TA | -TA | ε $

$ T -> FB $

$ B -> *FB | /FB | ε $

$ F -> (E) | num $

设计过程可大致分为两步：

• 构造预测分析表
• 构造预测分析程序

首先定义产生式和非终结符的数据结构

typedef struct{
    char left;   //左部单个非终结符
    string right;  //右部长度>=0的串
    set<char> firstSet;  //生成串的first集合
}formula;

typedef struct{
    char ch;
    set<char> firstSet;
    set<char> followSet;
}nonterm; //非终结符

1. 构造预测分析表

构造预测分析表，我们可以遵循以下算法流程：

for(文法G的每一个产生式A->α){
    for(每个终结符号a∈FIRST(α)) 把A->α放入表项M[A, a]中;
    if(ε∈FIRST(α))
        for(每个b∈FOLLOW(A)) 把A->α放入表项M[A, b]中;
    };
for(所有无定义的表项M[A, a]) 标上错误标志;

对应的c++代码如下：

void getAnalysisTable()
{
    int i = 0, j = 0; 
    //填写错误标记
    for(vector<nonterm>::iterator iter1 = nontList.begin(); iter1 != nontList.end(); iter1++){
        j = 0;
        for(vector<char>::iterator iter2 = termList.begin(); iter2 != termList.end(); iter2++){
            analysisTable[i][j] = -1;
            j++;
        }
        analysisTable[i][j] = -1;
        i++;
    }

    //填写对应项
    i = 0;
    for(vector<formula>::iterator iter1 = fList.begin(); iter1 != fList.end(); iter1++){
        for(vector<char>::iterator iter2 = termList.begin(); iter2 != termList.end(); iter2++){
            if( iter1->firstSet.find(*iter2) != iter1->firstSet.end() ){
                analysisTable[isVn(iter1->left)][isVt(*iter2)] = i;
            }
        }

        if(iter1->right == "#"){
            for(vector<char>::iterator iter2 = termList.begin(); iter2 != termList.end(); iter2++){
                int index = isVn(iter1->left);
                if( nontList[index].followSet.find(*iter2) != nontList[index].followSet.end() ){
                    analysisTable[isVn(iter1->left)][isVt(*iter2)] = i;
                }
            }
        }
        i++;
    }
}

输入文法，测试输出结果：

2. 构造预测分析程序

构造预测分析程序，可以遵循以下方法：

初始化：将$压入栈底，将文法开始符号E入栈;
讲ω$放入输入缓冲区中，并将向前指针ip指向ω$的第一个符号
do{
    令X是栈顶文法符号，a是ip所指向的输入符号;
    if(X是终结符号或$)
        if(X == a) {从栈顶弹出X; ip向前移一个位置;}
        else error();
    else
        if(M[X, a] = X->Y...Z){
            从栈顶弹出X;
            依次把Z...Y压入栈;
            输出产生式X->Y...Z;
        };
        else error();
}while(X != $)

预测分析的c++代码如下：

SS.push('$');
    SS.push('E');
    do{
        chS = SS.top();
        chIN = str[ip];
        if(chIN >= '0' && chIN <= '9') chIN = '@';

        if( (isVt(chS) != -1) ){
            //终结符
            if(chS == chIN){
                SS.pop();
                ip++;
            }
            else {
                cout << "error";
                break;
            }
        }
        else{
            //非终结符
            int fId = analysisTable[isVn(chS)][isVt(chIN)];

            if(fId != -1){
                //有产生式
                SS.pop();
                string tmp = fList[fId].right;
                //非空产生式反序入栈
                if(tmp != "#"){
                    reverse(tmp.begin(), tmp.end());
                    while(tmp.length()){
                        SS.push(tmp[0]);
                        tmp = tmp.substr(1);
                    }
                }
                cout << fList[fId].left << "->" << fList[fId].right << endl;
            }
            else{
                cout << "error";
                break;
            }
        }
    }while(chS != '$');

3. 测试

程序输入

程序运行前，需要在根目录放入文件grammar.txt，其中第一行为非终结符，第二行为终结符(数字记号用单个@符号代替、空产生式用#代替)，其后n行为文法产生式。

程序输出

对每个输入串，程序给出自顶向下的推导序列或错误信息。

总结

• 语法分析的输入是词法分析程序扫描字符串源程序的过程中识别并生成的记号序列，因此对于单词、数字等都可以按照单个字符的形式处理。
• 语法分析结合语法制导分析技术即可生成语法树从而进行后续的语义分析，LL(1)是一种自顶向下的分析方法，即语法分析程序按照从树根到树叶的顺序建立分析树。
• 对于语法分析程序的错误处理，可在原分析表的基础上增加同步记号synch，从而使其具有处理两种错误的能力。