首页 > 其他分享 >编译原理实验二----文法类型的判断

编译原理实验二----文法类型的判断

时间:2025-01-13 16:33:12浏览次数:3  
标签:文法 型文法 leftText ---- 编译 ui QString 终结符

编译原理实验二----文法类型的判断


本文仅为编译原理课程实验记录开发过程,设计的知识点,以及实现算法的设计过程
使用的是Qt开发的有关 文法类型判断词法分析器NFA的确定化LL(1)分析表的构建使用LL(1)分析表分析句子等的演示应用程序,包含算法设计思路与过程。
请还请大家理解理解作者的辛苦,觉得文章写的通俗易懂的还请点赞支持支持,不胜感谢
文法类型判断

文法类型

0型文法(短语文法)

  1. 产生式形如:α->β,α、β属于字符串的闭包区间内且α至少包含有一个非终结符
  2. 人话:左边有含有非终结符(Vn),右边含有终结符(Vt)
  3. 举例:Aba->ab, Aa->Cb, aA->ab
  4. 0型文法是限制最少,一般见到的文法都可看做0型文法。

1型文法(上下文有关文法)

  1. 人话:式子左边至少含有一个非终结符,式子右边含有有限个字符,终结符或非终结符,且左边长度必须小于右边。
  2. 举例:Aa->aab,A->Bba ,BA->Ab

2型文法(上下文无关文法)

  1. 人话:式子左边只含有一个非终结符,式子右边含有有限个字符,终结符或非终结符
  2. 举例:A->abc,B->ab

3型文法(正规文法)

右线性文法:

  1. 产生式形如: A ->αB 或 A ->α
  2. 人话:式子左边只能有一个非终结符;式子右边最多有二个字符。如果有二个字符必须是 (终结符+非终结符) 的格式,如果是一个字符,那么必须是终结符。
  3. 举例:A->aA

左线性文法:

  1. 产生式形如: A ->Bα 或 A ->α
  2. 人话:式子左边只能有一个非终结符;式子右边最多有二个字符。如果有二个字符必须是 (非终结符+终结符) 的格式,如果是一个字符,那么必须是终结符。
  3. 举例:B->Bb

算法设计

在这里插入图片描述
首先针对每一条产生式进行下列判断,如果所有产生式都满足(满足的条数==产生式数量)则为相应的文法类型。注意:四种类型文法范围:0型>1型>2型>3型文法,所以判断的优先级为0型<1型<2型<3型文法。

3型文法判断

  1. 参数说明:Vn:非终结符集;Vt:终结符集;leftText:产生式左侧;rightText:产生式右侧
  2. 算法设计思路:
  • 首先判断产生式左侧字符数量是否是1,并且产生式右侧字符数是否小于等于2;
  • 如果成功则判断左侧字符是否是非终结符,如果不是则不是3型文法,反之继续判断;
  • 如果产生式右侧只有一个字符,则该字符必须是终结符,如果是两个字符,则必须为 (非终结符+终结符) 的格式;
  • 如果全部满足则为3型文法。
  1. 代码:
bool WF3(QString Vn, QString Vt, QString leftText, QString rightText) {
    // 	注意:本文所有代码使用的是Qt的框架,可以自行转化为c/c++,例如QString变为string
    int isVn = 0, isVt = 0;`
    if (leftText.length() == 1 && rightText.length() <= 2) {
        // 左边只有一个字符,且必须为非终结符
        for (int i = 0; i < Vn.length(); i++) {
            if (leftText[0] == Vn[i]) isVn = 1;
        }
        if (isVn != 1) return false;
        // 右边只有一个字符,且必须为终结符,或右边只有两个字符,且1个为终结符1个为非终结符
        if (rightText.length() == 1) {
            for (int i = 0; i < Vt.length(); i++) {
                if (rightText[0] == Vt[i]) isVt = 1;
            }
            if (isVt != 1) return false;
        }
        else if (rightText.length() == 2) {
            for (int i = 0; i < Vt.length(); i++) {
                if (rightText[0] == Vt[i]) isVt++;
                if (rightText[1] == Vt[i]) isVt++;
            }
            if (isVt != 1) return false;
        }
        return true;
    }
    else return false;
}

2型文法判断

  1. 参数说明:Vn : 非终结符集;Vt : 终结符集;leftText : 产生式左侧;rightText : 产生式右侧
  2. 算法设计思路:
  • 首先判断产生式左侧字符数量是否是1;
  • 如果成功则判断左侧字符是否是非终结符,如果不是则不是2型文法
  • (注:此处可以加一个判断,右侧所有字符是否全部属于非终结符或者终结符)
  • 如果全部满足则为2型文法。
  1. 代码:
bool WF2(QString Vn, QString Vt, QString leftText, QString rightText) {
    // 	注意:本文所有代码使用的是Qt的框架,可以自行转化为c/c++,例如QString变为string
    if (leftText.length() == 1) {
        // 左边只有一个字符,且必须为非终结符
        for (int i = 0; i < Vn.length(); i++) {
            if (leftText[0] == Vn[i]) return true;
        }
        return false;
    }
    else return false;
}

1型文法判断

  1. 参数说明:Vn:非终结符集;Vt:终结符集;leftText:产生式左侧;rightText:产生式右侧
  2. 算法设计思路:
  • 只需要判断产生式左侧是否含有非终结符即可。
  1. 代码:
bool WF1(QString Vn, QString Vt, QString leftText, QString rightText) {
    // 	注意:本文所有代码使用的是Qt的框架,可以自行转化为c/c++,例如QString变为string
    if (leftText.length() <= rightText.length()) {
        for (int i = 0; i < leftText.length(); i++){
            for (int j = 0; j < Vn.length(); j++) {
                if (leftText[i] == Vn[j]) return true;
            }
        }
        return false;
    }
    else return false;
}

总流程代码

上述过程为针对每条产生式的文法类型判断,想要判断整个文法的类型,我们需要对每条产生式进行上述判断,如果所有产生式都满足(满足的条数==产生式数量)则为相应的文法类型。注意:四种类型文法范围:0型>1型>2型>3型文法,所以判断的优先级为0型<1型<2型<3型文法。

void CompilersTechnology::on_chargeCs_clicked() {
    // 	注意:本文所有代码使用的是Qt的框架,可以自行转化为c/c++,例如QString变为string
    ui->csOutput->setPlainText("开始解析文法");
    int SumNum = CsInputLayout->count();
    
    // 读取Vn输入框内容
    QLineEdit* VN = ui->VnInput;
    QString Vn = VN->text();
    // 读取Vt输入框内容
    QLineEdit* VT = ui->VtInput;
    QString Vt = VT->text();

    if(Vn.isEmpty()) {
        ui->csOutput->setPlainText("Vn不能为空");
        return;
    }
    else if(Vt.isEmpty()) {
        ui->csOutput->setPlainText("Vt不能为空");
        return;
    }

    QLineEdit* test1 = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(0, 1)->widget());
    QLineEdit* test2 = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(0, 3)->widget());
    if(test1->text().isEmpty() || test2->text().isEmpty()) {
        ui->csOutput->setPlainText("输入的文法不正确");
        return;
    }

    QTextEdit* output = ui->csOutput;
    QString four1 = "G("+ ui->S->text() + ") :\nVn = " + Vn + "\nVt = " + Vt + "\nP:";
    output->setPlainText(four1);
    for (int i = 0; i < SumNum / 4; i++) {
        // 读取左边输入框内容
        QLineEdit* left = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(i, 1)->widget()); // 2表示第三列,索引从0开始
        QLineEdit* right = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(i, 3)->widget()); // 2表示第三列,索引从0开始
        QString leftText = left->text(); // 获取内容
        QString rightText = right->text(); // 获取内容
        output->append(leftText + " -> " + rightText);
    }
    output->append("S:" + ui->S->text());

    int wf,wf1 = 0, wf2 = 0, wf3 = 0;
    bool isEmpty;
    for (int i = 0; i < SumNum / 4; i++) {
        // 读取左边输入框内容
        QLineEdit* left = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(i, 1)->widget()); // 2表示第三列,索引从0开始
        QLineEdit* right = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(i, 3)->widget()); // 2表示第三列,索引从0开始
        
        QString leftText = left->text(); // 获取内容
        QString rightText = right->text(); // 获取内容
        // 如果有含空输入的文法
        isEmpty = false;
        if (leftText.isEmpty() || rightText.isEmpty()) {
            isEmpty = true;
            output->append("第" + QString::number(i + 1) + "行:\t" + leftText + "->" + rightText + "含有空的输入");
            continue;
        }

        if (WF3(Vn, Vt, leftText, rightText)) {               // 判断3型文法
            wf3++;
        }
        if (WF2(Vn, Vt, leftText, rightText)) {         // 判断2型文法
            wf2++;
        }
        if (WF1(Vn, Vt, leftText, rightText)) {              // 判断1型文法
            wf1++;
        }
    }
    if(wf3 == SumNum / 4) wf = 3;
    else if(wf2 == SumNum / 4) wf = 2;
    else if(wf1 == SumNum / 4) wf = 1;
    else wf = 0;
    if(isEmpty) ui->csOutput->append("去除空输入后");
    ui->csOutput->append("文法类型为" + QString::number(wf) + "型文法");
}

源代码

头文件CompilersTechnology.h

// 	注意:本文所有代码使用的是Qt的框架,可以自行转化为c/c++,例如QString变为string等
#pragma once

#include <QtWidgets/QMainWindow>
#include "ui_CompilersTechnology.h"
#include "NFA.h"       // 非确定性有穷自动机
#include "LexicalAnalysis.h"   // 词法分析器
#include "LL1.h"            // LL(1)分析表
#include "Compiler.h"       // 编译器
//#include "LR1.h"            // LR(1)分析表
//#include "LR0.h"            // LR(0)分析表
class NFA;             // 非确定性有穷自动机
class LexicalAnalysis;   // 词法分析器
class LL1;
class Compiler;

class CompilersTechnology : public QMainWindow
{
    Q_OBJECT

public:
    CompilersTechnology(QWidget *parent = nullptr);
    ~CompilersTechnology(); 

private:
    Ui::CompilersTechnologyClass *ui;
    NFA* nfa;     // 非确定性有穷自动机
    LexicalAnalysis* lexicalAnalysis;   // 词法分析器
    LL1* ll1;     // LL(1)分析表
    Compiler* compiler;

    //切换页面
    QStackedWidget* pages;
    //菜单栏
    QAction* page1;
    QAction* page2;
    QAction* page3;
    QAction* page4;
    QAction* page5;
    // 
    QScrollArea* wfSa;
    // 文法输入(添加或者删除)
    QGridLayout* CsInputLayout;
    QPushButton* addCs;
    QPushButton* deleteCs;

    QLineEdit* L0;
    QLineEdit* R0;
    QScrollArea* WfSa;
    QWidget* WifaWidget;

    // 判断文法
    QPushButton* chargeCs;
    QTextEdit* csOutput;     // 输出框

public slots:
    void on_stackedWidget_currentChanged(int index);
    void on_addCs_clicked();
    void on_deleteCs_clicked();
    void on_chargeCs_clicked();
}; 

源文件CompilersTechnology.cpp

// 	注意:本文所有代码使用的是Qt的框架,可以自行转化为c/c++,例如QString变为string等
#include "CompilersTechnology.h"
#define LARGE_NUM 100000
CompilersTechnology::CompilersTechnology(QWidget *parent)
    : QMainWindow(parent)
    , ui(new Ui::CompilersTechnologyClass)      // 非确定性有穷自动机)
{  
    ui->setupUi(this);
    nfa = new NFA(ui);         // 非确定性有穷自动机
    lexicalAnalysis = new LexicalAnalysis(ui);
    ll1 = new LL1(ui);         // LL(1)分析表
    compiler = new Compiler(ui);
    // 切换页面
    pages = ui->stackedWidget;
    page1 = ui->page1;
    page2 = ui->page2;
    page3 = ui->page3;
    page4 = ui->page4;
    page5 = ui->Compiler;
    connect(page1, &QAction::triggered, this, [this]() { on_stackedWidget_currentChanged(0); });
    connect(page2, &QAction::triggered, this, [this]() { on_stackedWidget_currentChanged(1); });
    connect(page3, &QAction::triggered, this, [this]() { on_stackedWidget_currentChanged(2); });
    connect(page4, &QAction::triggered, this, [this]() { on_stackedWidget_currentChanged(3); });
    connect(page5, &QAction::triggered, this, [this]() { on_stackedWidget_currentChanged(4); });
    // 文法的输入(添加或者删除产生式)
    CsInputLayout = ui->CsInput;
    //connect(ui.addCs, &QPushButton::released, this, &CompilersTechnology::on_addCs_clicked);
    //connect(ui.deleteCs, &QPushButton::released, this, &CompilersTechnology::on_deleteCs_clicked);

    // 判断文法类型
    //connect(ui.chargeCs, &QPushButton::released, this, &CompilersTechnology::on_chargeCs_clicked);
}

CompilersTechnology::~CompilersTechnology()
{}

void CompilersTechnology::on_stackedWidget_currentChanged(int index) {
    if (pages != nullptr) {
        if (index < pages->count()) pages->setCurrentIndex(index);    //切换页面
        else qDebug() << "页面" << index + 1 << "不存在";
    }
    else qDebug() << "页面为空";
}
void CompilersTechnology::on_addCs_clicked() {
    int SumNum = CsInputLayout->count()/4;
    // 假设您想放在第一行的第0列、第1列和第2列
    QLabel* label1 = new QLabel(QString::number(SumNum + 1) + ".");
    label1->setObjectName("wfNum" + SumNum);    // 设置对象名称

    QLineEdit* lineEdit1 = new QLineEdit("");// 创建 QLineEdit
    lineEdit1->setObjectName("L"+ SumNum);    // 设置对象名称

    QLabel* label2 = new QLabel("::=");
    QFont font = label2->font(); // 获取当前字体
    font.setPointSize(15); // 设置字体大小为15
    label2->setFont(font); // 应用修改后的字体

    QLineEdit* lineEdit2 = new QLineEdit("");
    lineEdit2->setObjectName("R" + SumNum);    // 设置对象名称
    qDebug() << (SumNum + 1) * (ui->L0->height() + 3 + 10) << ui->WifaWidget->height();
    if ((SumNum + 2) * (ui->L0->height() + 3 + 10) > ui->WfSa->height()) ui->WifaWidget->setFixedHeight(ui->WifaWidget->height() + ui->L0->height() + 3 + 10) ;       // 添加时自适应滑块
    CsInputLayout->addWidget(label1, SumNum, 0);
    CsInputLayout->addWidget(lineEdit1, SumNum, 1); // 第一行第一列
    CsInputLayout->addWidget(label2, SumNum, 2);     // 第一行第二列
    CsInputLayout->addWidget(lineEdit2, SumNum, 3); // 第一行第三列
}
void CompilersTechnology::on_deleteCs_clicked() {
    int SumNum = CsInputLayout->count()/4;
    if ((SumNum) * (ui->L0->height() + 3 + 10) >= ui->WfSa->height() - 10) ui->WifaWidget->setFixedHeight(ui->WifaWidget->height() - ui->L0->height()  - 3 - 10);// 删除时自适应滑块
    for (int i = 0; i < 4; i++) {
        QWidget* widget = CsInputLayout->itemAtPosition((SumNum) - 1, i)->widget(); // 获取控件
        if(SumNum != 1) CsInputLayout->removeWidget(widget); // 第一行第一列
    }
    
}
bool WF3(QString Vn, QString Vt, QString leftText, QString rightText) {
    int isVn = 0, isVt = 0;
    if (leftText.length() == 1 && rightText.length() <= 2) {
        // 左边只有一个字符,且必须为非终结符
        for (int i = 0; i < Vn.length(); i++) {
            if (leftText[0] == Vn[i]) isVn = 1;
        }
        if (isVn != 1) return false;
        // 右边只有一个字符,且必须为终结符,或右边只有两个字符,且1个为终结符1个为非终结符
        if (rightText.length() == 1) {
            for (int i = 0; i < Vt.length(); i++) {
                if (rightText[0] == Vt[i]) isVt = 1;
            }
            if (isVt != 1) return false;
        }
        else if (rightText.length() == 2) {
            for (int i = 0; i < Vt.length(); i++) {
                if (rightText[0] == Vt[i]) isVt++;
                if (rightText[1] == Vt[i]) isVt++;
            }
            if (isVt != 1) return false;
        }
        return true;
    }
    else return false;
}
bool WF2(QString Vn, QString Vt, QString leftText, QString rightText) {
    if (leftText.length() == 1) {
        // 左边只有一个字符,且必须为非终结符
        for (int i = 0; i < Vn.length(); i++) {
            if (leftText[0] == Vn[i]) return true;
        }
        return false;
    }
    else return false;
}
bool WF1(QString Vn, QString Vt, QString leftText, QString rightText) {
    if (leftText.length() <= rightText.length()) {
        for (int i = 0; i < leftText.length(); i++){
            for (int j = 0; j < Vn.length(); j++) {
                if (leftText[i] == Vn[j]) return true;
            }
        }
        return false;
    }
    else return false;
}
void CompilersTechnology::on_chargeCs_clicked() {
    ui->csOutput->setPlainText("开始解析文法");
    int SumNum = CsInputLayout->count();
    
    // 读取Vn输入框内容
    QLineEdit* VN = ui->VnInput;
    QString Vn = VN->text();
    // 读取Vt输入框内容
    QLineEdit* VT = ui->VtInput;
    QString Vt = VT->text();

    if(Vn.isEmpty()) {
        ui->csOutput->setPlainText("Vn不能为空");
        return;
    }
    else if(Vt.isEmpty()) {
        ui->csOutput->setPlainText("Vt不能为空");
        return;
    }

    QLineEdit* test1 = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(0, 1)->widget());
    QLineEdit* test2 = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(0, 3)->widget());
    if(test1->text().isEmpty() || test2->text().isEmpty()) {
        ui->csOutput->setPlainText("输入的文法不正确");
        return;
    }

    QTextEdit* output = ui->csOutput;
    QString four1 = "G("+ ui->S->text() + ") :\nVn = " + Vn + "\nVt = " + Vt + "\nP:";
    output->setPlainText(four1);
    for (int i = 0; i < SumNum / 4; i++) {
        // 读取左边输入框内容
        QLineEdit* left = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(i, 1)->widget()); // 2表示第三列,索引从0开始
        QLineEdit* right = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(i, 3)->widget()); // 2表示第三列,索引从0开始
        QString leftText = left->text(); // 获取内容
        QString rightText = right->text(); // 获取内容
        output->append(leftText + " -> " + rightText);
    }
    output->append("S:" + ui->S->text());

    int wf,wf1 = 0, wf2 = 0, wf3 = 0;
    bool isEmpty;
    for (int i = 0; i < SumNum / 4; i++) {
        // 读取左边输入框内容
        QLineEdit* left = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(i, 1)->widget()); // 2表示第三列,索引从0开始
        QLineEdit* right = qobject_cast<QLineEdit*>(CsInputLayout->itemAtPosition(i, 3)->widget()); // 2表示第三列,索引从0开始
        
        QString leftText = left->text(); // 获取内容
        QString rightText = right->text(); // 获取内容
        // 如果有含空输入的文法
        isEmpty = false;
        if (leftText.isEmpty() || rightText.isEmpty()) {
            isEmpty = true;
            output->append("第" + QString::number(i + 1) + "行:\t" + leftText + "->" + rightText + "含有空的输入");
            continue;
        }

        if (WF3(Vn, Vt, leftText, rightText)) {               // 判断3型文法
            wf3++;
        }
        if (WF2(Vn, Vt, leftText, rightText)) {         // 判断2型文法
            wf2++;
        }
        if (WF1(Vn, Vt, leftText, rightText)) {              // 判断1型文法
            wf1++;
        }
    }
    if(wf3 == SumNum / 4) wf = 3;
    else if(wf2 == SumNum / 4) wf = 2;
    else if(wf1 == SumNum / 4) wf = 1;
    else wf = 0;
    if(isEmpty) ui->csOutput->append("去除空输入后");
    ui->csOutput->append("文法类型为" + QString::number(wf) + "型文法");
}
    

标签:文法,型文法,leftText,----,编译,ui,QString,终结符
From: https://blog.csdn.net/2301_79878653/article/details/144113414

相关文章

  • 【AI中数学-概率论】 概率质量函数:离散世界的概率指南
    第四章概率论第5节概率质量函数:离散世界的概率指南概率质量函数(ProbabilityMassFunction,简称PMF)是离散型随机变量的重要工具,用于描述随机变量在各个可能取值上的概率分布。PMF不仅在概率论中占据核心地位,更在人工智能、机器学习和数据科学等领域发挥着关键作用。通过深入......
  • LampSecurityCTF4---靶机练习
    LampSecurityCTF4靶机练习声明B站UP主泷羽sec笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负。✍......
  • 线程和进程的区别
    1、线程是什么线程是应用程序执行的最小单位,是CPU调度和执行的基本单元。然后每一个进程至少都会有一个线程(也就是main方法所在的线程,也称为主线程),也可以有多个线程。线程在进程运行中,也共享进程的资源(比如内存、文件扫描等等)。线程本身也拥有自己的执行路径、计数器、栈和局......
  • ABC 388 (DEG)
    赛时4题,打得很差的一场。尤其是E题,赛时一直被卡,直到结束看群友的结论后顿然醒悟,不到3分钟码出并AC,只能恨自己赛时为什么这么sb...D模拟+差分从左到右枚举\(i\),每一次枚举可以计算出第\(i\)个人有多少颗糖(\(a[i]\)+前面\(i-1\)个人给的糖数\(num\))。这样,第\(i\)个人会给出的......
  • springboot+vue的河南天气数据分析与可视化系统python-计算机毕业设计
    目录功能和技术介绍具体实现截图开发核心技术:开发环境开发步骤编译运行核心代码部分展示系统设计详细视频演示可行性论证软件测试源码获取功能和技术介绍该系统基于浏览器的方式进行访问,采用springboot集成快速开发框架,前端使用vue方式,基于es5的语法,开发工具Intelli......
  • 如何将CIFAR-10数据集转化为图片
    如何将CIFAR-10数据集转化为图片简单记录一下CIFAR-10数据集转图片的过程1.首先在官网下载CIFAR-10数据集官网下载得到文件如下2.想把他转化为jpg图片,从网上得到代码如下#-*-coding:utf-8-*-fromscipy.miscimportimsaveimportnumpyasnpimportpickle......
  • springboot+vue的二手交易平台评论情感分析系统python-计算机毕业设计
    目录功能和技术介绍具体实现截图开发核心技术:开发环境开发步骤编译运行核心代码部分展示系统设计详细视频演示可行性论证软件测试源码获取功能和技术介绍该系统基于浏览器的方式进行访问,采用springboot集成快速开发框架,前端使用vue方式,基于es5的语法,开发工具Intelli......
  • springboot+vue的网购平台用户购买力差异分析及研究python-计算机毕业设计
    目录功能和技术介绍具体实现截图![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/43904518e65045b98fdab97fa21adb87.png)开发核心技术:开发环境开发步骤编译运行核心代码部分展示系统设计详细视频演示可行性论证软件测试源码获取功能和技术介绍该系统基于......
  • springboot+vue的股票预测模型系统python-计算机毕业设计
    目录功能和技术介绍具体实现截图开发核心技术:开发环境开发步骤编译运行核心代码部分展示系统设计详细视频演示可行性论证软件测试源码获取功能和技术介绍该系统基于浏览器的方式进行访问,采用springboot集成快速开发框架,前端使用vue方式,基于es5的语法,开发工具Intelli......
  • qiankun微前端——接入子应用Vue3+vite实现
    qiankun:乾坤微前端框架什么是微前端Techniques,strategiesandrecipesforbuildingamodernwebappwithmultipleteamsthatcanshipfeaturesindependently.–MicroFrontends微前端是一种多个团队通过独立发布功能的方式来共同构建现代化web应用的技术......