编译原理实验二----文法类型的判断
本文仅为编译原理课程实验记录开发过程,设计的知识点,以及实现算法的设计过程
使用的是Qt开发的有关 文法类型判断、 词法分析器、 NFA的确定化、 LL(1)分析表的构建、 使用LL(1)分析表分析句子等的演示应用程序,包含算法设计思路与过程。
请还请大家理解理解作者的辛苦,觉得文章写的通俗易懂的还请点赞支持支持,不胜感谢
文法类型
0型文法(短语文法)
- 产生式形如:α->β,α、β属于字符串的闭包区间内且α至少包含有一个非终结符
- 人话:左边有含有非终结符(Vn),右边含有终结符(Vt)
- 举例:Aba->ab, Aa->Cb, aA->ab
- 0型文法是限制最少,一般见到的文法都可看做0型文法。
1型文法(上下文有关文法)
- 人话:式子左边至少含有一个非终结符,式子右边含有有限个字符,终结符或非终结符,且左边长度必须小于右边。
- 举例:Aa->aab,A->Bba ,BA->Ab
2型文法(上下文无关文法)
- 人话:式子左边只含有一个非终结符,式子右边含有有限个字符,终结符或非终结符
- 举例:A->abc,B->ab
3型文法(正规文法)
右线性文法:
- 产生式形如: A ->αB 或 A ->α
- 人话:式子左边只能有一个非终结符;式子右边最多有二个字符。如果有二个字符必须是 (终结符+非终结符) 的格式,如果是一个字符,那么必须是终结符。
- 举例:A->aA
左线性文法:
- 产生式形如: A ->Bα 或 A ->α
- 人话:式子左边只能有一个非终结符;式子右边最多有二个字符。如果有二个字符必须是 (非终结符+终结符) 的格式,如果是一个字符,那么必须是终结符。
- 举例:B->Bb
算法设计
首先针对每一条产生式进行下列判断,如果所有产生式都满足(满足的条数==产生式数量)则为相应的文法类型。注意:四种类型文法范围:0型>1型>2型>3型文法,所以判断的优先级为0型<1型<2型<3型文法。
3型文法判断
- 参数说明:Vn:非终结符集;Vt:终结符集;leftText:产生式左侧;rightText:产生式右侧
- 算法设计思路:
- 首先判断产生式左侧字符数量是否是1,并且产生式右侧字符数是否小于等于2;
- 如果成功则判断左侧字符是否是非终结符,如果不是则不是3型文法,反之继续判断;
- 如果产生式右侧只有一个字符,则该字符必须是终结符,如果是两个字符,则必须为 (非终结符+终结符) 的格式;
- 如果全部满足则为3型文法。
- 代码:
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型文法判断
- 参数说明:Vn : 非终结符集;Vt : 终结符集;leftText : 产生式左侧;rightText : 产生式右侧
- 算法设计思路:
- 首先判断产生式左侧字符数量是否是1;
- 如果成功则判断左侧字符是否是非终结符,如果不是则不是2型文法
- (注:此处可以加一个判断,右侧所有字符是否全部属于非终结符或者终结符)
- 如果全部满足则为2型文法。
- 代码:
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型文法判断
- 参数说明:Vn:非终结符集;Vt:终结符集;leftText:产生式左侧;rightText:产生式右侧
- 算法设计思路:
- 只需要判断产生式左侧是否含有非终结符即可。
- 代码:
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