开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 简单优先分析法演示系统——C/C++/Qt实现 -> 正文阅读

[C++知识库]简单优先分析法演示系统——C/C++/Qt实现

🔋 第二个 Qt、C/C++ 程序设计项目

一、简单的效果演示

在这里插入图片描述

??● 说明：简单演示了一下整个系统。

二、系统要求

● 简单优先分析法，它是编译原理课程中所涉及的一种重要的语法分析方法：

（1）系统能够分步演示说明简单优先关系矩阵的计算过程（例如 L 关系、 R 关系、L+关系、R+关系、小于、大于、等于关系的求解过程）。

（2）系统能够演示利用简单优先关系矩阵分析符号串的过程。

（3）界面美观。

（4）对所采用的算法、程序结构和主要函数过程以及关键变量进行详细的说明。

（5）提供关键程序的清单、源程序及可执行文件和相关的软件说明。

三、系统设计

在这里插入图片描述
● 简单优先分析法演示系统的功能有如下 9 项：

（1）支持系统运行时的状态参数配置，如文法表达式符号串的输入、分析符号串的输入、所有计算内容和输入框的清空。

（2）能根据简单优先分析法的定义计算 L 关系、R 关系和等于关系，并利用 Warshall 算法实现 L+ 关系、R+ 关系的计算，最终计算出小于关系、大于关系和简单优先关系矩阵。

（3）支持通过友好的界面展示文法表。

（4）支持通过友好的界面展示 L 关系、R 关系、L+ 关系、R+ 关系、等于关系、小于关系、大于关系和简单优先关系矩阵。

（5）利用堆栈算法思想来分析输入的符号串，判断通过该文法能否生成该符号串。

（6）支持通过友好的界面展示分析过程。

（7）若不能构造简单优先关系矩阵，系统会分析出具体是哪里的构造出了问题，并给予提示。

（8）若不能通过该文法能否生成输入符号串，系统会分析出具体是哪一步出了问题，并给予提示。

（9）系统另外还支持展示“带关系符号”的分析过程。

四、框架搭建

● 项目管理如下：

在这里插入图片描述

● 说明：
??① main.cpp 是启动程序的入口。
??② mainwindow.cpp 是 “开始” 界面的源代码。
??③ analysis.cpp 是简单优先分析系统的源代码。

● 头文件analysis.h 如下：
在这里插入图片描述

● 说明：该系统所有功能的触发，都是点击含有 pushButton 的函数而实现的。

五、算法设计

5.1 主要数据结构

● 该系统中未使用自己构造的结构体。主要使用了二维数组来存储关系和 Qt5.14.2 里面的 QVector、QMap、QSet、QString。
??① QVector 用于存储文法表达式的相关信息。
??② QMap 用于存储每一个字符对应的数字，便于构造矩阵表。
??③ QSet 用于实现对右部产生式进行判重的功能。
??④ QString 用于输入输出、充当分析过程的“堆栈”。

5.2 主要算法流程

● Warshall算法：为了有效地由布尔矩阵 B 来计算 B+，1962 年 Warshall 提出了一种算法(简称 Warshall 算法)，该算法的文字描述过程如下，算法流程图如下图所示：
??① 首先置矩阵 $A = B$ ；
??② 置 $i = 1$ ；
??③ 对 $1 \leq j \leq n$ ，若 $A [j, i] = 1$ ，对所有 $k = 1, 2 ， \dots$ ， $n$ 置 $A [j, k] = A [j, k] + A [I, k]$ ( $+$ 为布尔和) ；
??④ 置 $i = i + 1$ ;
??⑤ 如果 $i \leq n$ ，则转步骤③，否则停止，这样得到矩阵 $A_{n×n}$ ，即 $A_{n×n}=B+$ 。

在这里插入图片描述

● 简单优先分析算法：首先是在文法各种符号之间(终结符号和非终结符号)建立优先关系，在分析一个句型(指规范句型)时，从左到右依次扫视其中符号，利用符号之间优先关系找到句柄，再归约成某个非终结符。流程图如下图所示。

在这里插入图片描述

六、测试数据及其结果分析

0. 开始界面如下：

在这里插入图片描述

1. 输入文法表达式并无误展示：

在这里插入图片描述

2. L关系展示：
在这里插入图片描述

3. R关系展示：

在这里插入图片描述

4. L+关系展示：
在这里插入图片描述

5. R+关系展示：

在这里插入图片描述

6. 等于关系展示：

在这里插入图片描述

7. 小于关系展示：

在这里插入图片描述

8. 大于关系展示：

在这里插入图片描述

9. 简单优先关系矩阵展示：

在这里插入图片描述

10. 不能构造简单优先关系矩阵的错误示例一展示(有相同右部)：

在这里插入图片描述

11. 不能构造简单优先关系矩阵的错误示例二展示(关系发生重合)：
在这里插入图片描述

12. 分析符号串时的错误示例一演示(没有产生式)：

在这里插入图片描述

13. 分析符号串时的错误示例一演示(没有产生式)：
在这里插入图片描述

14. 分析符号串时的错误示例二演示(没有关系)：

在这里插入图片描述

15. 带关系符号串的分析：

在这里插入图片描述

七、完整代码

● 项目文件源代码：https://download.csdn.net/download/Wang_Dou_Dou_/86506201.

● 部分核心代码：

void Analysis::on_pushButton_14_clicked()   // 按下“L关系”按钮要做的事
{
    // L={(U,S)|U::=S…}, S可以是终结符或非终结符
    for (int i = 0; i < v1.size(); i++)
    {
        for (int j = 0; j < v2[i].size(); j++)
        {
            int row = m[v1[i]];
            int col = m[v2[i][j][0].toLatin1()];
            L_table[row][col] = 1;   // 相应关系赋值为 1
            LP_table[row][col] = 1;  // 后续还要对该 L+ 关系做处理
        }
    }

    // 终端输出 L关系
    qDebug() << "L关系如下：";
    for (int i = 0; i < m.size() ;i++)
    {
        for (int j = 0; j < m.size() ;j++)
        {
            cout << L_table[i][j] << " ";
        }
        cout << endl;
    }
    cout << "---------------------" << endl;

    setTable_2(L_table, "L关系");
}
void Analysis::on_pushButton_15_clicked()   // 按下“R关系”按钮要做的事
{
    // L={(U,S)|U::=…S}, S可以是终结符或非终结符
    for (int i = 0; i < v1.size(); i++)
    {
        for (int j = 0; j < v2[i].size(); j++)
        {
            int len = v2[i][j].length();
            int row = m[v1[i]];
            int col = m[v2[i][j][len-1].toLatin1()];
            R_table[row][col] = 1;      // 相应关系赋值为 1
            RP_table[row][col] = 1;     // 后续还要对该 R+ 关系做处理
        }
    }

    // 终端输出 R关系
    qDebug() << "R关系如下：";
    for (int i = 0; i < m.size() ;i++)
    {
        for (int j = 0; j < m.size() ;j++)
        {
            cout << R_table[i][j] << " ";
        }
        cout << endl;
    }
    cout << "---------------------" << endl;
    setTable_2(R_table, "R关系");
}

void Analysis::on_pushButton_17_clicked()   // 按下“等于关系”按钮要做的事
{
    // = 关系构造, 若有 U → ...S_i S_j..., 则有 S_i = S_j
    for (int i = 0; i < v1.size(); i++)
    {
        for (int j = 0; j < v2[i].size(); j++)
        {
            // 窗口大小为 2
            int fp = 1;
            while (fp < v2[i][j].length())
            {
                char row_c = v2[i][j][fp - 1].toLatin1();	// 为什么 u_int fp = 1; 就体现在这里
                char col_c = v2[i][j][fp].toLatin1();
                int row = m[row_c];
                int col = m[col_c];
                Q_table[row][col] = 1;	// 将 等于关系 置为 1
                fp++;
            }
        }
    }

    // 终端输出 等于关系
    qDebug() << "等于关系如下：";
    for (int i = 0; i < m.size() ;i++)
    {
        for (int j = 0; j < m.size() ;j++)
        {
            cout << Q_table[i][j] << " ";
        }
        cout << endl;
    }
    cout << "---------------------" << endl;
    setTable_2(Q_table, "等于关系");
}

void Analysis::on_pushButton_18_clicked()   // 按下“L+关系”按钮要做的事
{
    on_pushButton_14_clicked();   // 构造 L关系 的同时构造 L+关系
    // 计算 L+ 关系矩阵(先看列, 再看行)
    for (int j = 0; j < m.size(); j++)
    {
        for (int i = 0; i < m.size(); i++)
        {
            if (LP_table[j][i] == 1)
            {
                for (int k = 1; k < m.size(); k++)
                {
                    LP_table[j][k] = LP_table[j][k] || LP_table[i][k];	// 布尔加
                }
            }
        }
    }

    // 终端输出 L+关系
    qDebug() << "L+关系如下：";
    for (int i = 0; i < m.size() ;i++)
    {
        for (int j = 0; j < m.size() ;j++)
        {
            cout << LP_table[i][j] << " ";
        }
        cout << endl;
    }
    cout << "---------------------" << endl;
    setTable_2(LP_table, "L+关系");
}

void Analysis::on_pushButton_19_clicked()   // 按下“R+关系”按钮要做的事
{
    on_pushButton_15_clicked();   // 构造 R关系 的同时构造 R+关系
    // 计算 R+ 关系矩阵(先看列, 再看行)
    for (int j = 0; j < m.size(); j++)
    {
        for (int i = 0; i < m.size(); i++)
        {
            if (RP_table[j][i] == 1)
            {
                for (int k = 1; k < m.size(); k++)
                {
                    RP_table[j][k] = RP_table[j][k] || RP_table[i][k];	// 布尔加
                }
            }
        }
    }

    // 终端输出 R+关系
    qDebug() << "R+关系如下：";
    for (int i = 0; i < m.size() ;i++)
    {
        for (int j = 0; j < m.size() ;j++)
        {
            cout << RP_table[i][j] << " ";
        }
        cout << endl;
    }
    cout << "---------------------" << endl;
    setTable_2(RP_table, "R+关系");
}

void Analysis::on_pushButton_16_clicked()   // 按下“小于关系”按钮要做的事
{
    // “小于” = “等于” × “L+” (注意这是矩阵相乘)
    on_pushButton_17_clicked();   // 构造“等于关系”
    on_pushButton_18_clicked();   // 构造“L+关系”


    matrixMultiplication(Q_table, LP_table, XY_table, m.size());

    // 终端输出 小于关系
    qDebug() << "小于关系如下：";
    for (int i = 0; i < m.size() ;i++)
    {
        for (int j = 0; j < m.size() ;j++)
        {
            cout << XY_table[i][j] << " ";
        }
        cout << endl;
    }
    cout << "---------------------" << endl;
    setTable_2(XY_table, "小于关系");
}

void Analysis::on_pushButton_20_clicked()   // 按下“大于关系”按钮要做的事
{
    // “大于” = “(R+)^T” × “等于” × “L*” (注意这是矩阵相乘)
    on_pushButton_18_clicked();   // 构造“L*关系”之前需要构造 L+ 关系
    for(int i = 0; i < m.size(); i++)
    {
        for (int j = 0; j < m.size(); j++)
        {
            LX_table[i][j] = LP_table[i][j];
            if (i == j)
            {
                LX_table[i][i] = 1;
            }
        }
    }
    int res_table_1[100][100] = {{0}};
    int res_table_2[100][100] = {{0}};
    on_pushButton_19_clicked();   // 构造“R+关系”
    on_pushButton_17_clicked();   // 构造“等于关系”
    T(RP_table, res_table_1, m.size());
    matrixMultiplication(res_table_1, Q_table, res_table_2, m.size());
    matrixMultiplication(res_table_2, LX_table, DY_table, m.size());

    QMap<char, int>::iterator iter;
    // 此时还要将有非终结符号的列置零！！！
    for (int i = 0; i < v1.size(); i++)
        for (int j = 0; j < m.size(); j++)
            DY_table[j][m[v1[i]]] = 0;

    // 终端输出 大于关系
    qDebug() << "大于关系如下：";
    for (int i = 0; i < m.size() ;i++)
    {
        for (int j = 0; j < m.size() ;j++)
        {
            cout << DY_table[i][j] << " ";
        }
        cout << endl;
    }
    cout << "---------------------" << endl;
    setTable_2(DY_table, "大于关系");
}

void Analysis::matrixMultiplication(int m1[][100], int m2[][100], int result[][100], int n)   // 矩阵乘法
{
    // qDebug() << "矩阵运算过程：";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n ; k++)
            {
                result[i][j] |= m1[i][k] * m2[k][j];
            }
        }
    }
    return ;
}

void Analysis::T(int m[][100], int result[][100], int n)  // 矩阵的转置
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n ; j++)
        {
            result[j][i] = m[i][j];
        }
    }
}

void Analysis::on_pushButton_21_clicked()   // 按下“优先关系矩阵”按钮要做的事
{
    on_pushButton_17_clicked();    // “等于关系”
    on_pushButton_16_clicked();    // “小于关系”
    on_pushButton_20_clicked();    // “大于关系”
    int flag = 1;
    for (int i = 0 ; i < m.size(); i++)
    {
        for (int j = 0 ; j < m.size(); j++)
        {
            int tmp1 = 0, tmp2 = 0, tmp3 = 0;
            if (Q_table[i][j] == 1)     // =
            {
                Res_Matrix[i][j] = 2;
                tmp1++;
            }
            if (XY_table[i][j] == 1)    // <
            {
                Res_Matrix[i][j] = 3;
                tmp2++;
            }
            if (DY_table[i][j] == 1)    // >
            {
                Res_Matrix[i][j] = 4;
                tmp3++;
            }
            if (tmp1 + tmp2 + tmp3 == 0)
                Res_Matrix[i][j] = -1;      // 这两个符号之间没有关系
            if (tmp1 + tmp2 + tmp3 > 1)     // 这两个符号之间有多重关系
            {
                QChar X,Y;
                X = QChar(m.key(i));
                Y = QChar(m.key(j));
                if (tmp1 == 0)  // 如果成立则说明 tmp2 + tmp3 = 2
                {
                    QString str = "该文法中";
                    str = str + X + "和" + Y + "存在 > 和 < 的多重关系！不能构造简单优先关系矩阵！" ;
                    QMessageBox::information(this, "提示", str);
                }
                else if(tmp2 ==0)
                {
                    QString str = "该文法中 ";
                    str = str + X + " 和 " + Y + " 存在 = 和 > 的多重关系！不能构造简单优先关系矩阵！" ;
                    QMessageBox::information(this, "提示", str);
                }
                else if (tmp3 == 0)
                {
                    QString str = "该文法中 ";
                    str = str + X + " 和 " + Y + " 存在 = 和 < 的多重关系！不能构造简单优先关系矩阵！" ;
                    QMessageBox::information(this, "提示", str);
                }
                else
                {
                    QString str = "该文法中 ";
                    str = str + X + " 和 " + Y + " 存在 = 、> 和 < 的多重关系！不能构造简单优先关系矩阵！" ;
                    QMessageBox::information(this, "提示", str);
                }
                qDebug() << "对于任意两个语法符号 X 和 Y ，至多成立一种优先关系;";
                flag = 0;
                open = 0;   // 如果 优先关系矩阵 都不能构造, 则无法分析符号串
            }
        }
    }

    if (flag == 1)
    {
        // 终端输出 优先关系矩阵
        qDebug() << "优先关系矩阵如下：";
        for (int i = 0; i < m.size() ;i++)
        {
            for (int j = 0; j < m.size() ;j++)
            {
                cout << Res_Matrix[i][j] << " ";
            }
            cout << endl;
        }
        cout << "---------------------" << endl;

        setTable_2(Res_Matrix, "优先关系矩阵");
    }
}