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

实验内容

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

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

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

$ F -> (E) | num $

LR分析为自底向上的分析，基本思想是在规范规约的过程中，一方面要记住历史信息，即已经移进和规约的整个符号串；另一方面要预测未来，即根据所用的产生式推测未来可能遇到的输入符号；根据历史信息和预测信息来确定下一步分析动作。

LR分析程序的设计可分为三步：

  • 构造识别该文法所有活前缀的DFA
  • 构造该文法的LR分析表
  • 构造LR分析程序

自底向上的分析不需要消除文法的左递归，所以直接写出原文法的拓广文法：

$ S -> E $

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

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

$ F -> (E) | num $

1. 构造DFA

根据拓广文法作出SLR项目规范族及识别所有活前缀的DFA：

SLRDFA

2. 构造LR分析表

根据以上DFA，可以直接写出该文法的LR分析表：

—+-*/()num$ETF
0----S10-S4-123
1S5S6-----ACC---
2R4R4S7S8-R4-R4---
3R7R7R7R7-R7-R7---
4R9R9R9R9-R9-R9---
5----S10-S4--93
6----S10-S4--113
7----S10-S4---12
8----S10-S4---13
9R2R2S7S8-R2-R2---
10----S10-S4-14153
11R3R3S7S8-R3-R3---
12R5R5R5R5-R5-R5---
13R6R6R6R6-R6-R6---
14S5S6---S16-----
15R4R4S7S8-R4-R4---
16R8R8R8R8-R8-R8---

3. 构造LR分析程序

构造分析表可以按照以下算法进行：

初始化：将状态0入栈，将ω$存入输入缓冲区;
置ip置指向ω$的第一个符号；
do{
    令S是栈顶状态，a是ip所指向的符号;
    if(action[S, a] = shift S'){
        把a和S'分别压入符号栈和状态栈的栈顶;
        推进ip使其指向下一符号;
    };
    else if(action[S, a] = reduce by A->β) {
        从栈顶弹出|β|个符号;
        令S'是当前栈顶状态,把A和goto[S', A]分别压入符号栈和状态栈的栈顶;
        输出产生式A->β;
    };
    else if(action[S, a] = accept) return;
    else error();
}while(1);

依此写出的c++实现代码：

s.val = 0;
s.symble = '$';
SS.push(s);
do{
    s = SS.top();
    ch = str[ip];
    int opt = SLRTable[s.val][checkN(ch)];

    if(opt >= 100 && opt < 200)
    {//Shift
        s.val = opt - 100;
        s.symble = ch;
        SS.push(s);
        ip++;
        cout << "shift" << s.val << endl;
    }
    else if(opt >= 200 && opt < 300)
    {//Reduce
        id = opt - 200;
        //弹出右部
        if(id == 4 || id == 7 || id == 9)
            SS.pop();
        else
        {
            SS.pop();
            SS.pop();
            SS.pop();
        }

        s = SS.top();
        state tmp;

        tmp.symble = formulaList[id-1].at(0);
        int c;
        if(tmp.symble == 'E')   c =  8;
        else if(tmp.symble == 'T')  c = 9;
        else if(tmp.symble == 'F')  c = 10;
        tmp.val = SLRTable[s.val][c];

        SS.push(tmp);
        cout << "reduce by " << formulaList[id-1] <<  endl;
    }
    else if(opt == 0)
    {//ACC
        cout << "success!" << endl;
        break;
    }
    else
    {//ERR
        cout << "error" << endl;
        break;
    }
}while(1);

4. 测试

对于每个输入串，程序给出移进-归约的动作序列或错误信息。

SLROut

总结

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