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

2023-06-07

int cout endl

0🐣实验目的编写一个简单的LL（1）语法分析器。（注意：此实验是简化版的LL（1）文法，已给出预测分析表，不需要求FIRST和FOLLOW集，直接根据预测分析表编写程序即可）1🐣实验要求根据编译原理理论课中学习的算术表达式文法，以及该文法LL（1）分析表，用C语言编写接受算术表达式为输入的语法分

0 🐣实验目的

编写一个简单的LL（1）语法分析器。（注意：此实验是简化版的LL（1）文法，已给出预测分析表，不需要求FIRST和FOLLOW集，直接根据预测分析表编写程序即可）

1 🐣实验要求

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

2 🐣实验内容

实现LL（1）语法分析器。执行过程举例：分析id+id*id，根据PPT上的预测分析表，输入id+id*id#，分析出栈和输出的内容。
文法如下：

E→TE' E' →+TE' |ε T→FT'
T' →*FT' |ε F→(E)|id

3 🐣实验思路

首先明确LL（1）语法分析器的大致结构，然后设计各个模块结构。

定义常量（比如预测分析表的行变量个数，列变量个数），变量（主函数用到的循环变量等等），数据结构（比如存储符号的分析栈以及临时使用的临时栈）

定义两个一维数组，一个用于存储终结符号，一个用于存储语法变量，再定义一个二维数组用于存储预测分析表。

我将输出栈内字符和输出输入缓冲区内剩余字符分别定义为了两个函数，这样更方便我进行调用输出。

主函数是整个程序的重要部分，主要是LL(1)文法的算法实现：即根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作：大致过程是先将初始的符号压入分析栈内，紧接着进入循环，循环测试即为缓冲区内串长度，然后取出栈顶看是否输入缓冲区的符号匹配，不匹配判断栈弹出的符号是否与行变量匹配，匹配就记住行变量，不匹配就报错，接着判断输入缓冲区第一个字符是否与列变量匹配，如果匹配，记住此时列变量，然后与预测分析表进行比对，分析此时情况，直到循环结束，最后得出结论，输出最后的分析结果。

4 🐣实验代码


#include <bits/stdc++.h>
#define A 5 
#define B 6 
 
using namespace std;
 
stack<char> p;
char Vn[A] = {'E', 'e', 'T', 't', 'F'};
char Vt[B] = {'i', '+', '*', '(', ')', '#'};
string L[A][B] = {
    {"Te", "ERROR", "ERROR", "Te", "ERROR", "ERROR"},
    {"ERROR", "+Te", "ERROR", "ERROR", "NULL", "NULL"},
    {"Ft", "ERROR", "ERROR", "Ft", "ERROR", "ERROR"},
    {"ERROR", "NULL", "*Ft", "ERROR", "NULL", "NULL"},
    {"i", "ERROR", "ERROR", "(i)", "ERROR", "ERROR"}};
 
void printstack();
void printinput(string s, int n);
int main()
{
    cout << "输入一个对由'i','+','*','(',')'构成的以'#'结束的字符串：\n";
    string input;
    cin >> input;
    cout << "匹配过程如下:"<< endl;
    p.push('#');
    p.push(Vn[0]);
    cout << "步骤"<< "\t输入缓冲区"<< "\t栈"<< "\t\t输出" << endl;
    cout << '0' << "\t";
    cout << input;
    cout << "\t\t";
    printstack();
    printf("\n");
    int i = 0;
    for (int j = 1; i < input.length(); j++)
    {
        char v = p.top();
        p.pop();
        if (v == input[i])
        {
            cout << j << "\t";
            printinput(input, i);
            cout << "\t\t";
            printstack();
            cout << "\t\t" << input[i] << "匹配"<< "\t\t" << endl;
            i++;
            continue;
        }
        else
        {
            int m, n;
            m = -1;
            for (int k = 0; k < A; k++)
            {
                if (v == Vn[k])
                {
                    m = k;
                    break;
                }
            }
            if (m == -1)
            {
                cout << "错误"<<endl;
                cout << "第" << i << "个字符" ;
                printf("%c",input[i]);
                cout << "匹配错误" << endl;
                cout << input << "为非法符号串" << endl;
                break;
            }
            for (int k = 0; k < B; k++)
            {
                if (input[i] == Vt[k])
                {
                    n = k;
                    break;
                }
            }
            if (L[m][n] == "ERROR")
            {
                cout << "第" << i << "个字符" ;
                printf("%c",input[i]);
                cout << "匹配错误" << endl;
                cout << input << "为非法符号串" << endl;
                break;
            }
            if (L[m][n] == "NULL")
            {
                cout << j << "\t";
                printinput(input, i);
                cout << "\t\t";
                printstack();
                cout << "\t\t" << v << "->"<< "ε" << endl;
                continue;
            }
            else
            {
                string t = "";
                for (int k = L[m][n].length() - 1; k >= 0; k--)
                {
                    t += L[m][n][k];
                    p.push(L[m][n][k]);
                }
                cout << j << "\t";
                printinput(input, i);
                cout << "\t\t";
                printstack();
                cout << "\t\t" << v << "->" << L[m][n];
            }
        }
        cout << endl;
    }
    if (i == input.length())
        cout << input << "为合法符号串" << endl;
}
 
void printstack()
{
    stack<char> temp;
    int l = p.size();
    for (int i = 0; i < l; i++)
    {
        char a = p.top();
        p.pop();
        cout << a;
        temp.push(a);
    }
    l = temp.size();
    for (int i = 0; i < l; i++)
    {
        char a = temp.top();
        temp.pop();
        p.push(a);
    }
}
 
void printinput(string s, int n)
{
    for (; n < s.length(); n++)
        cout << s[n];
}