编译原理——SLR（1）语法分析器（C/C++代码实现）

0 实验目的

设计、编制、实现并调试SLR（1）语法分析器，加深对语法分析的理解。

1 实验要求

根据编译原理理论课中学习的算术表达式文法以及该文法的LR分析表，用C语言编写接受算术表达式为输入的语法分析器，以控制台（或文本文件，也可以结合词法分析器完成）为输入，控制台（或文件）输出产生式序列形式的分析结果。

2 实验内容

实现LR语法分析器,执行过程举例：分析id+id*id，根据PPT上的预测分析表，输入id+id*id#，分析出栈和输出的内容。
文法：
E'->E
E->E+T
E->T
T->T*F
T->F
F->(E)
F->id

3 实验思路

1.首先，我定义了7个函数，分别为：最重要的SLRScanner()函数（进行SLR文法分析）；statestack()函数（输出状态栈）；signstack()函数（输出符号栈）；print()函数（剩余字符串输出）；Action()函数（用于分析和输出动作说明）；xfind()函数（用于查找预测分析遍行变量）；yfind()函数（用于查找预测分析表列变量）。紧接着，定义了字符串二维数组，用于储存预测分析表，还定义了二维字符数组，用于存储拓广文法；定义了两个栈，符号栈以及状态栈。
2.本次实验程序中最重要的就是SLRScanner()函数，接下来，对此进行简要分析：开始，通过以字符串此时的分析位置与字符串整体为判断条件进行循环，令标志变量flag等于0（做最开始的移进操作），并不断更新行变量与列变量，方便接下来查表，然后将0，#分别压入状态栈和符号栈。接着通过xfind和yfind函数进行查找并给行变量与列变量赋值，将对应预测分析表内的数据进行判断：如果等于0.不符合文法，返回。如果不是，就将对应的符号和状态分别压入符号栈与状态栈，同时，输出剩余字符串和对应的动作说明。如果等于‘s’，给flag赋值0，否则等于1。如果flag等于1，就进行规约（对SR(1)与对应的拓广文法分别比较并同时，对符号栈、状态栈、剩余字符串以及动作说明进行操作，还有输出相应的产生式。）如果flag等于2做goto后的移进操作，再与预测分析表进行比对，SR等于0，证明查表结果错误；SR等于acc，程序结束，并输出该字符串符合文法。
3.其他函数也比较重要，在SLR文法分析函数中都进行了调用，通过对栈的操作，实现了符号和状态的输出，极大的化简了程序；Action函数帮助输出动作说明；而xfind和yfind帮助查找预测分析表，都有着不可或缺的作用。

4 实验代码

#include <bits/stdc++.h>
using namespace std;
string SLRGrammer[12][9]{
    "s5", "0", "0", "s4", "0", "0", "1", "2", "3",
    "0", "s6", "0", "0", "0", "acc", "0", "0", "0",
    "0", "r2", "s7", "0", "r2", "r2", "0", "0", "0",
    "0", "r4", "r4", "0", "r4", "r4", "0", "0", "0",
    "s5", "0", "0", "s4", "0", "0", "8", "2", "3",
    "0", "r6", "r6", "0", "r6", "r6", "0", "0", "0",
    "s5", "0", "0", "s4", "0", "0", "0", "9", "3",
    "s5", "0", "0", "s4", "0", "0", "0", "0", "a",
    "0", "s6", "0", "0", "s11", "0", "0", "0", "0",
    "0", "r1", "s7", "0", "r1", "r1", "0", "0", "0",
    "0", "r3", "r3", "0", "r3", "r3", "0", "0", "0",
    "0", "r5", "r5", "0", "r5", "r5", "0", "0", "0"};
char Grammer[7][10] = {"E→E'", "Ｅ→Ｅ+Ｔ", "Ｅ→Ｔ", "Ｔ→Ｔ*Ｆ", "Ｔ→Ｆ", "Ｆ→(Ｅ)", "Ｆ→id"};
char x[12] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b'};
char y[9] = {'i', '+', '*', '(', ')', '#', 'E', 'T', 'F'};
int xfind(char a);
int yfind(char a);
int stri = 0;
int flag = 0;
int strlength;
string SR;
string strs;
string str;
stack<char> state;
stack<char> sign;
void SLRScanner(string str);
void statestack();
void signstack();
void print(string s, int n);
void VerbScanner(string str, int i);
void Action(int i, int flag2, int x, int y);
string Convert(char a, string b);
void SLRScanner(string str)
{
    for (; stri < str.length();)
    {
        if (flag == 0)
        {
            stri++;
            int x, y;
            state.push(SR[1]);
            sign.push(str[stri - 1]);
            x = xfind(SR[1]);
            y = yfind(str[stri]);
            SR = SLRGrammer[x][y];
            if (SR == "0")
            {
                cout << "\t输入的字符串不符合SLR文法" << endl;
                break;
            }
            print(str, stri);
            signstack();
            cout << "\t\t";
            statestack();
            cout << "\t\t\t";
            Action(stri, 0, x, y);
            printf("\n");
            if (SR[0] == 's')
                flag = 0;
            else
                flag = 1;
        }
        if (flag == 1)
        {
            int x, y;
            char r, c;
            if (SR[1] == '1')
            {
                for (int i = 0; i < 3; i++)
                {
                    state.pop();
                    sign.pop();
                }
                sign.push('E');
                r = state.top();
                c = sign.top();
                x = xfind(r);
                y = yfind(c);
                print(str, stri);
                signstack();
                cout << "\t\t";
                statestack();
                cout << "\t\t" << Grammer[1];
                Action(stri, 1, x, y);
                printf("\n");
                SR = SLRGrammer[x][y];
            }
            else if (SR[1] == '2')
            {
                for (int i = 0; i < 1; i++)
                {
                    state.pop();
                    sign.pop();
                }
                sign.push('E');
                r = state.top();
                c = sign.top();
                x = xfind(r);
                y = yfind(c);
                print(str, stri);
                signstack();
                cout << "\t\t";
                statestack();
                cout << "\t\t" << Grammer[2] << "\t";
                ;
                Action(stri, 1, x, y);
                printf("\n");
                SR = SLRGrammer[x][y];
            }
            else if (SR[1] == '3')
            {
                for (int i = 0; i < 3; i++)
                {
                    state.pop();
                    sign.pop();
                }
                sign.push('T');
                r = state.top();
                c = sign.top();
                x = xfind(r);
                y = yfind(c);
                print(str, stri);
                signstack();
                cout << "\t\t";
                statestack();
                cout << "\t\t" << Grammer[3];
                Action(stri, 1, x, y);
                printf("\n");
                SR = SLRGrammer[x][y];
            }
            else if (SR[1] == '4')
            {
                for (int i = 0; i < 1; i++)
                {
                    state.pop();
                    sign.pop();
                }
                sign.push('T');
                r = state.top();
                c = sign.top();
                x = xfind(r);
                y = yfind(c);
                print(str, stri);
                signstack();
                cout << "\t\t";
                statestack();
                cout << "\t\t" << Grammer[4] << "\t";
                ;
                Action(stri, 1, x, y);
                printf("\n");
                SR = SLRGrammer[x][y];
            }
            else if (SR[1] == '5')
            {
                for (int i = 0; i < 3; i++)
                {
                    state.pop();
                    sign.pop();
                }
                sign.push('F');
                r = state.top();
                c = sign.top();
                x = xfind(r);
                y = yfind(c);
                print(str, stri);
                signstack();
                cout << "\t\t";
                statestack();
                cout << "\t\t" << Grammer[5] << "\t";
                ;
                Action(stri, 1, x, y);
                printf("\n");
                SR = SLRGrammer[x][y];
            }
            else if (SR[1] == '6')
            {
                for (int i = 0; i < 1; i++)
                {
                    state.pop();
                    sign.pop();
                }
                sign.push('F');
                r = state.top();
                c = sign.top();
                x = xfind(r);
                y = yfind(c);
                print(str, stri);
                signstack();
                cout << "\t\t";
                statestack();
                cout << "\t\t" << Grammer[6] << "\t";
                ;
                Action(stri, 1, x, y);
                printf("\n");
                SR = SLRGrammer[x][y];
            }
            flag = 2;
        }
        if (flag == 2)
        {
            int prow, pcol;
            state.push(SR[0]);
            prow = xfind(SR[0]);
            pcol = yfind(str[stri]);
            SR = SLRGrammer[prow][pcol];
            if (SR == "0")
            {
                cout << "\t 输入的字符串不符合SLR文法" << endl;
                break;
            }
            print(str, stri);
            signstack();
            cout << "\t\t";
            statestack();
            cout << "\t\t\t";
            Action(stri, 0, prow, pcol);
            cout << endl;
            if (SR[0] == 's')
                flag = 0;
            else
                flag = 1;
        }
        if (SR == "acc")
        {
            cout << "\n\t该字符串符合SLR文法。" << endl;
            break;
        }
    }
}
void statestack()
{
    stack<char> temp;
    string b;
    int l = state.size();
    for (int i = 0; i < l; i++)
    {
        char a = state.top();

        state.pop();
        temp.push(a);
    }
    for (int i = 0; i < l; i++)
    {
        char a = temp.top();
        b = Convert(a, b);
        temp.pop();
        state.push(a);
    }
    cout << std::left << setw(7) << b;
}
void VerbScanner(string str, int i)
{

    if (isalpha(str[i]))
    {
        string lett;
        while (isdigit(str[i]) || isalpha(str[i]) || str[i] == '_' || str[i] == '.')
        {
            lett += str[i];
            i++;
        }
        i--;
        if (lett == "id")
            strs = strs + 'i';
    }
    else if (str[i] == '+')
        strs = strs + '+';
    else if (str[i] == '*')
        strs = strs + '*';
    else
        strs = strs + '#';
}
int xfind(char a)
{
    int n;
    for (int i = 0; i < 12; i++)
    {
        if (a == x[i])
        {
            n = i;
            return n;
        }
    }
    return 0;
}
int yfind(char a)
{
    int n;
    for (int i = 0; i < 9; i++)
    {
        if (a == y[i])
        {
            n = i;
            return n;
        }
    }
    return 0;
}
string Convert(char a, string b)
{
    if (a == 'i')
        b = b + "id";
    else
        b = b + a;
    return b;
}
void Action(int i, int flag2, int x, int y)
{
    char G = sign.top();
    if (flag2 == 0)
        cout << "\t"
             << " Action(" << x << "," << str[i] << ")";
    else
        cout << "\t"
             << " Goto(" << x << "," << G << ")";
}
void signstack()
{
    stack<char> temp;
    string b;
    int l = sign.size();
    for (int i = 0; i < l; i++)
    {
        char a = sign.top();

        sign.pop();
        temp.push(a);
    }
    for (int i = 0; i < l; i++)
    {
        char a = temp.top();
        b = Convert(a, b);
        temp.pop();
        sign.push(a);
    }
    cout << "\t" << std::left << setw(7) << b;
}
void print(string s, int n)
{
    string a;
    for (; n < s.length(); n++)
        if (s[n] == 'i')
            a = a + "i";
        else
            a = a + s[n];
    cout << std::right << setw(10) << a;
}
int main()
{
    cout << "请输入需要分析的符号串：";
    cin >> str;
    strlength = str.length();
    for (int i = 0; i < strlength; i++)
    {
        if (str[i] == ' ' || str[i] == '\n')
            continue;
        else
            VerbScanner(str, i);
    }
    cout << "   输入串"
         << "\t状态栈"
         << "\t\t符号栈"
         << "\t\t所用产生式"
         << "\t 所做动作" << endl;
    cout << " " << str;
    str = strs;
    cout << "  ";
    sign.push('#');
    state.push('0');
    SR = "s5";
    signstack();
    cout << "\t\t";
    statestack();
    cout << "\t\t\t";
    Action(0, 0, 0, 0);
    printf("\n");
    SLRScanner(str);
    return 0;
}

5 实验结果

6 实验总结

这个实验要求不尽相同，需要改一下，可以与我私信讨论。

7 实验程序以及实验报告下载链接

编译原理实验：包括实验一词法分析器，实验二进制分析，实验三语法分析器，实验四SLR语法分析器等其中含有实验报告，实验代码等等-C++文档类资源-CSDN文库