【编译原理】C++实现算符优先分析(超详细系列+有源码+有注释+可运行)_小树ぅ的博客-程序员宅基地_算符优先分析代码

技术标签: 算法  c++  java  字符串  编译原理  数据结构  

目录

算符优先分析

1.实验目的

2.实验过程

2.1算符优先关系表的构造方法

2.2思路

3.实验代码:

4.实验结果


算符优先分析

1.实验目的

了解用算符优先法对表达进行语法分析的方法,掌握自顶向下的预测语法分析程序的手工构造方法。

实验要求:一个交互式面向对象的算符优先分析程序基本功能是:

(1)  输入文法规则

(2)  对文法进行转换

(3)  生成每个非终结符的FirstVT和LastVT

(4)  生成算符优先分析表

(5)  再输入文法符号串

(6)  生成移进规约步骤

2.实验过程

2.1算符优先关系表的构造方法

利用文法G中的每个非终结符PFIRSTVT集和LASTVT集,我们就能方便地构造文法G的算符优先关系表,其构造方法如下:

规则一:对形如P→…ab…P→…aQb…的产生式,有a=b
规则二:对形如P→…aR…的产生式,若有bFIRSTVT,则a<b
规则三:对形如P→…Rb…的产生式,若有aLASTVT,则a>b
规则四:对于语句括号#,有#=#,且若aFIRSTVT(S)bLASTVT(S),则有#<ab>#

2.2思路

首先定义一个char类型的二维数组来存发优先关系(<,>,=)使用之前进行初始化一下,然后遍历产生式,根据上面四个规则进行判断,对表赋值。

  1. 移进:将输入串的一个符号移进分析栈。
  2. 归约:发现栈顶呈可归约串,并用适当的相应符号去替换这个串。
  3. 接受:宣布最终分析成功,可看作是归约的一种特殊形式。
  4. 报错:发现栈顶内容与输入串相悖,调用出错处理程序进行诊察和校正,并对栈顶内容和输入符号进行调整

3.实验代码:

Base.h:

#pragma once
#ifndef BASE_H_
#define BASE_H_
#include<iostream>
#include<fstream>
using namespace std;
struct Proce { //用结构体数组来存放产生式
	char Left;//存放产生式的左部
	char Right[100];//存放产生式的右部
};
struct Myset {
	char VN;//用于存放FIRSTVT(P)和LASTVT(P)的非终结符
	char VT[100]; //用于存放FIRSTVT(P)和LASTVT(P)的终结符
};
class Base
{
public:
	int flag;
	struct Proce pro[100];      //产生式
	struct Myset firstvt[100];  //firstvt集合
	struct Myset lastvt[100];   //lastvt集合
public:
	Base() :flag(0) {
		memset(firstvt, 0, sizeof(firstvt)); //置空字符串
		memset(lastvt, 0, sizeof(lastvt));
		memset(pro, 0, sizeof(pro));
	}
	int is_VN(char ch); //判断是否是非终结符,默认大写字母为非终结符,其他为终结符
	void is_gram(Proce pro[], int length); //判断文法是否为算符文法
	void NoAdd(Myset VNT[], int length1); //去掉集合中重复部分
	void FIRSTVT(Proce pro[], Myset firstvt[], int length);//求各非终结符的FIRSTVT集合
	void LASTVT(Proce pro[], Myset lastvt[], int length);//求各非终结符的FIRSTVT集合
};
#endif

 Base.cpp:

#include "Base.h"
int Base::is_VN(char ch) //判断是否是非终结符,默认大写字母为非终结符,其他为终结符
{
	if (ch >= 'A' && ch <= 'Z')
		return 1;
	else
		return 0;
}
void Base::is_gram(Proce pro[], int length) //判断文法是否为算符文法
{
	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < strlen(pro[i].Right) - 1; j++)
			if (is_VN(pro[i].Right[j]) == 1 && is_VN(pro[i].Right[j + 1]) == 1)//两个非终结符在一起了;
			{
				flag = 1;
				break;
			}
	}
	if (flag == 1)
	{
		cout << "该文法不是算符文法!" << endl;
		return;
	}
	else
		cout << "该文法是算符文法!" << endl;
}
void Base::NoAdd(Myset VNT[], int length1) //去掉集合中重复部分
{
	char str1[20];//非终结符
	char str2[20][100];//终结符
	int length;
	for (int i = 0; i < length1; i++)
	{
		str1[i] = VNT[i].VN;
		strcpy(str2[i], VNT[i].VT);//把终结符复制给str2
	}
	for (int i = 0; i < length1; i++)
		memset(VNT[i].VT, 0, sizeof(VNT[i].VT));//清空
	for (int i = 0; i < length1; i++)
	{
		int t = 0;
		for (int j = 0; j < strlen(str2[i]); j++)
		{
			flag = 1;
			for (int k = 0; k < t; k++)
				if (VNT[i].VT[k] == str2[i][j])//重复了
					flag = 0;
			if (flag == 1)
				VNT[i].VT[t++] = str2[i][j];
		}
		length = strlen(VNT[i].VT);
	}
}
//求各非终结符的FIRSTVT集合
void Base::FIRSTVT(Proce pro[], Myset firstvt[], int length)
{
	int  m = 0;//非终结符个数,flag记录产生式个数
	int  j, k;
	while (flag < length)//length=9产生式总个数
	{
		j = 0;
		firstvt[m].VN = pro[flag].Left;
		while (firstvt[m].VN == pro[flag].Left)
		{
			if (is_VN(pro[flag].Right[0]) == 0) //P->a...则将a加入firstvt(P)中
				firstvt[m].VT[j++] = pro[flag].Right[0];
			else if (is_VN(pro[flag].Right[0]) == 1 && is_VN(pro[flag].Right[1]) == 0) //P->Qa...则将a加入firstvt(P)中
				firstvt[m].VT[j++] = pro[flag].Right[1];
			flag++;
		}
		m++;
	}
	for (int i = length - 1; i >= 0; i--) //P->Q...,则将Q中的终结符加入P中
		if (is_VN(pro[i].Right[0]) == 1 && pro[i].Left != pro[i].Right[0])
		{
			for (j = 0; j < m; j++)   //E->E跳出
				if (firstvt[j].VN == pro[i].Right[0])
					break;
			for (k = 0; k < m; k++)
				if (firstvt[k].VN == pro[i].Left)
					break;
			strcat(firstvt[k].VT, firstvt[j].VT);//firstvt[j].VT添加到firstvt[k].VT后面(strcat字符串连接函数)
		}
	NoAdd(firstvt, m);//去重
	for (int i = 1; i < m; i++) //集合输出
	{
		cout << "FIRSTVT(";
		cout << firstvt[i].VN << ")" << "=" << "{";
		cout << firstvt[i].VT[0];
		for (int j = 1; j < strlen(firstvt[i].VT); j++)
			cout << "," << firstvt[i].VT[j];
		cout << "}" << endl;
	}
}
void Base::LASTVT(Proce pro[], Myset lastvt[], int length)//求各非终结符的FIRSTVT集合
{
	int m = 0;//非终结符个数,flag记录产生式个数
	int  j, k, t;
	while (flag < length)
	{
		j = 0;
		lastvt[m].VN = pro[flag].Left;//把非终结符赋给VN
		while (lastvt[m].VN == pro[flag].Left)
		{
			t = strlen(pro[flag].Right) - 1;
			if (is_VN(pro[flag].Right[t]) == 0) //P->...a则将a加入lastvt(P)中
				lastvt[m].VT[j++] = pro[flag].Right[t];
			else if (is_VN(pro[flag].Right[t]) == 1 && is_VN(pro[flag].Right[t - 1]) == 0) //P->...aQ则将a加入lastvt(P)中
				lastvt[m].VT[j++] = pro[flag].Right[t - 1];
			flag++;
		}
		m++;
	}
	for (int i = length - 1; i >= 0; i--) //P->...Q,则将Q中的终结符加入P中
	{
		t = strlen(pro[flag].Right) - 1;
		if (is_VN(pro[i].Right[t]) == 1 && pro[i].Left != pro[i].Right[t])
		{
			for (j = 0; j < m; j++)
				if (lastvt[j].VN == pro[i].Right[t])
					break;
			for (k = 0; k < m; k++)
				if (lastvt[k].VN == pro[i].Left)
					break;
			strcat(lastvt[k].VT, lastvt[j].VT);
		}
	}
	NoAdd(lastvt, m);
	for (int i = 0; i < m; i++) //集合输出
	{
		cout << "LASTVT(";
		cout << lastvt[i].VN << ")" << "=" << "{";
		cout << lastvt[i].VT[0];
		for (j = 1; j < strlen(lastvt[i].VT); j++)
			cout << "," << lastvt[i].VT[j];
		cout << "}" << endl;
	}
}

TableStack.h:

#pragma once
#ifndef TABLESTACK_H_
#define TABLESTACK_H_
#include"Base.h"
class TableStack :public Base
{
	char table[50][50]; //存放优先表
	int step;           //序号
	char S[100];          //符号栈
public:
	TableStack() :step(1)
	{
		memset(table, 0, sizeof(table));//置空字符串
		memset(S, 0, sizeof(S));
	}
	void Table(Proce pro[], Myset firstvt[], Myset lastvt[], int length); //优先关系表 //返回非终结符个数
	char GetIndex(char a, char b); //找到a,b对应的关系
	void control(char* str);
	void out();
};
#endif

 TableStack.cpp:

#include "TableStack.h"
#include<string>
void TableStack::Table(Proce pro[], Myset firstvt[], Myset lastvt[], int length) //优先关系表 
{
	char str[50]; //存放终结符
	int i, k, i1, i2;
	int t = 0;
	memset(str, 0, sizeof(str));//初始化
	for (i = 0; i < length; i++) //遍历所有的产生式
	{
		flag = 1;
		for (k = 0; k < strlen(pro[i].Right); k++)//找终结符
			if (is_VN(pro[i].Right[k]) == 0)
			{
				for (i1 = 0; i1 < t; i1++)
					if (pro[i].Right[k] == str[i1])//已经存在了flag = 0;
						flag = 0;
				if (flag == 1)
					str[t++] = pro[i].Right[k];
			}
	}
	for (i = 0; i < strlen(str); i++)//与习惯保持一致,将#置于最后一个
	{
		if (str[i] == '#')
			swap(str[i], str[strlen(str) - 1]);//#和最后一个交换,把#放最后一个
	}
	for (i = 1; i <= strlen(str); i++)
	{
		table[0][i] = str[i - 1]; //第一列的终结符
		table[i][0] = str[i - 1]; //第一行的终结符 
	}
	for (int i = 0; i < length; i++)//遍历所有的产生式
	{
		int length1 = strlen(pro[i].Right);
		for (int j = 0; j < length1 - 1; j++)//遍历产生式的右部
		{
			if (is_VN(pro[i].Right[j]) == 0 && is_VN(pro[i].Right[j + 1]) == 0)//P->...ab...  
			{
				for (i1 = 0; i1 <= strlen(str); i1++)//遍历终结符
					for (i2 = 0; i2 <= strlen(str); i2++)
						if (table[0][i1] == pro[i].Right[j] && table[i2][0] == pro[i].Right[j + 1])//a=b
						{
							if (table[i1][i2] != 0) //刚开始表里面的值都为0
							{
								cout << "该文法不是算符优先文法!" << endl;
								return;
							}
							else//赋值=
								table[i1][i2] = '=';
						}
			}
			if (j < length1 - 2 && is_VN(pro[i].Right[j]) == 0 && is_VN(pro[i].Right[j + 2]) == 0 && is_VN(pro[i].Right[j + 1]) == 1)//P->...aQb... #E#,(E)
			{
				for (i1 = 0; i1 <= strlen(str); i1++)//遍历终结符
					for (i2 = 0; i2 <= strlen(str); i2++)
						if (table[0][i1] == pro[i].Right[j] && table[i2][0] == pro[i].Right[j + 2])//a=b
						{
							if (table[i1][i2] != 0)
							{
								cout << "该文法不是算符优先文法!" << endl;
								return;
							}
							else
							{
								table[i1][i2] = '=';
							}

						}
			}
			if (is_VN(pro[i].Right[j]) == 0 && is_VN(pro[i].Right[j + 1]) == 1)//P->...aQ...且Q=>b...或Q=>Rb...
			{                                                                  //P->X1 X2...Xi Xi+1.....Xn
				for (i1 = 0; table[0][i1] != pro[i].Right[j]; i1++);//a不等于b
				for (k = 0; firstvt[k].VN != pro[i].Right[j + 1]; k++);//非终结符P,Q不相等
				for (i2 = 0; i2 <= strlen(str); i2++)//遍历终结符
					for (t = 0; t < strlen(firstvt[k].VT); t++)//遍历firstvt集合
						if (table[i2][0] == firstvt[k].VT[t])       //firstvt(Xi+1)中的每个a  Xi<a
						{
							if (table[i1][i2] != 0)
							{
								cout << "该文法不是算符优先文法!" << endl;
								return;
							}
							else
								table[i1][i2] = '<';
						}
			}
			if (is_VN(pro[i].Right[j]) == 1 && is_VN(pro[i].Right[j + 1]) == 0)//P->...Qb...且Q=>..a或Q=>..aR
			{                                                                  //P->X1 X2...Xi Xi+1.....Xn
				for (t = 0; lastvt[t].VN != pro[i].Right[j]; t++);//非终结符P,Q不相等
				for (int k = 0; k < strlen(lastvt[t].VT); k++)//遍历lastvt集合
					for (i1 = 0; i1 <= strlen(str); i1++)//遍历终结符
						for (i2 = 0; i2 <= strlen(str); i2++)
							if (table[0][i1] == lastvt[t].VT[k] && table[i2][0] == pro[i].Right[j + 1])
							{                                                                  //lastvt(Xi)中的每个a >b
								if (table[i1][i2] != 0)
								{
									cout << "该文法不是算符优先文法!" << endl;
									return;
								}
								else
									table[i1][i2] = '>';
							}
			}
		}
	}
	for (int i = 0; i <= strlen(str); i++)
	{
		for (int j = 0; j <= strlen(str); j++)
			cout << table[i][j] << "    ";
		cout << endl;
	}
	cout << "---------------------------------------" << endl;
}
char TableStack::GetIndex(char a, char b) //找到a,b对应的关系
{
	int i, j;
	for (i = 0; table[0][i] != a; i++);
	for (j = 0; table[j][0] != b; j++);
	return table[i][j];
}
void TableStack::control(char* str)
{
	char a;   //输入串里面的每个字符
	int flag = 0;
	char Q;
	int j, k;
	cout << "步骤" << "\t\t符号栈" << "\t\t输入串" << "\t\t动作" << endl;
	a = str[0];//输入串的第一个字符赋给a
	k = 1;     //栈顶指针   栈S的深度
	S[k] = '#'; //栈里面压#
	while (a != '#')
	{
		a = str[flag++]; //把下一个输入字符读入a中                     //N1a1N2a2...aj-1Nj
		if (is_VN(S[k]) == 0)//j指向栈顶的终结符
			j = k;
		else                //栈顶是非终结符 j指向它下面的终结符
			j = k - 1;                            //j指向栈的最上面的终结符
		while (GetIndex(S[j], a) == '>')//外面a的优先级低于栈顶的 就规约
		{
			do { //自栈顶向栈底方向找出最左子串S[i]<S[i+1]…S[j]>a
				Q = S[j];
				if (is_VN(S[j - 1]) == 0) //j从最左素短语末逐步移向首
					j = j - 1;
				else
					j = j - 2;
			} while (S[j] == Q); //S[j]<Q时表明找到了最左素短语的首部
			cout << step++ << "\t\t" << S + 1 << "\t\t" << str + flag - 1 << "\t\t归约" << endl;
			for (int i = j + 2; i <= k; i++)
				S[i] = 0;
			k = j + 1;
			S[k] = 'N';   //栈顶的这些符号与某一个候选对应相等,就规约到N上
		}
		if (GetIndex(S[j], a) == '<' || GetIndex(S[j], a) == '=')//外面a的优先级高于或者等于栈顶的 就移进
		{
			cout << step++ << "\t\t" << S + 1 << "\t\t" << str + flag - 1;
			if (a != '#')
			{
				cout << "\t\t移进" << endl;
			}
			k = k + 1; //移进来的a就变成了栈顶终结符
			S[k] = a;
		}
		else
		{
			cout << "抱歉,输入的句子有误" << endl;
			return;
		}
	}
	cout << "\t\t接受" << endl << "恭喜您,分析成功" << endl;
	cout << "---------------------------------------------------" << endl;
}
void TableStack::out()
{
	char str3[100] = { 0 };//用于存放一个产生式子
	char str2[100];//用于存放待检测的字符串
	char filename[10];//文件名
	int length = 0; //记录产生式个数
	cout << "请输入文件名:";
	cin >> filename;
	ifstream fin(filename);
	if (!fin)
	{
		cout << "Cannot open the file.\n"; //未找到对应的文件名的文件
		exit(1);
	}
	while (fin)
	{
		fin.getline(str3, 100); //读出一个产生式
		cout << str3 << endl;
		pro[length].Left = str3[0];//产生式的左部
		strcpy(pro[length].Right, str3 + 3);
		length++;
	}
	length -= 1;
	is_gram(pro, length);
	cout << "各非终结符的FIRSTVT集合如下:" << endl;
	FIRSTVT(pro, firstvt, length);
	cout << "各非终结符的LASTVT集合如下:" << endl;
	LASTVT(pro, lastvt, length);
	cout << "-------------构造分析表如下------------" << endl;
	Table(pro, firstvt, lastvt, length);
	cout << "---------------------分析表过程---------------------" << endl;
	cout << "请任意输入一个输入串(以#号键结束):" << endl;
	cin >> str2;
	control(str2);
}

main:

#include"TableStack.h"
int main()
{
	TableStack s;
	s.out();
	system("pause");
	return 0;
}

4.实验结果

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44624536/article/details/116673483

智能推荐

html+css简单复习_呆瓜O_o的博客-程序员宅基地

文章目录前言一、HTML二、CSS前言学习地址:https://www.bilibili.com/video/BV1ZE411c7yM?p=30一、HTMLHTML:标签语言。常用的标签:标题标签h1-h6/段落标签p/div/ul&gt;li/ol&gt;li/a/表单标签(form input) , 自定义标签二、CSSCss:决定样式,重叠样式表标签的大小 (外边距 margin/ 内边距 padding/ 边框 border /内容的宽 width 高 height)盒子模

自定义控件 — ViewPagerIndicator(二)_天璇112的博客-程序员宅基地

自定义控件 — ViewPagerIndicator (二) 本文的学习文章出自 http://blog.csdn.net/lmj623565791/article/details/42160391 有兴趣的朋友可以去仔细的阅读下本片文章是在 自定义控件-ViewPagerIndicator(一)基础上逐步完善的,文章参考出自 鸿洋 大神的博客 仅练习 、积累 、学习。

为什么excel文件中的表不能删除?_daban1的博客-程序员宅基地_excel无法删除工作表

   如果excel表格里的内容无法删除的话,这个是excel表格设置了“保护工作表或者“保护”工作簿”了,只有取消“保护工作表或者“保护”工作簿”才可以删除工作里的内容了。...

PTA动态规划——换零钱(详细注释)_我new一个对象的博客-程序员宅基地

题目描述韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有 10​4​​ 枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。输入格式输入第一行给出两个正整数:N(≤10^4)是硬币的总个数,M(≤100​​ )是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。输出格式输入样例8 95 9 8 7 2 3 4 14 87

鸿蒙系统的软件怎么下载,怎么下载鸿蒙系统?_张A裕的博客-程序员宅基地

电梯直达huafen257355088新学乍练发表于 2020-12-23 08:53:26来自:HUAWEI Mate 30 Pro 5G最新回复 2021-4-28 12:38:58Screenshot_20201223_085118_com.tencent.mm.jpg (596.86 KB, 下载次数: 1)2020-12-23 08:53 上传huafen684234989新学乍练发表于...

java multiset_Guava学习之Multisets_采璇的博客-程序员宅基地

今天谈谈在以前,如果我们需要统计一篇文章中各个单词出现的次数,我们可能用下面的方法来实现: public void wordCounts(List words) {Map counts = new HashMap();for (String word : words) {Integer count = counts.get(word);if (count == null) {counts.put(...

随便推点

java 写文件后占用文件_Java独占写文件的5种解决方法_夏威廉的博客-程序员宅基地

下面是编程之家 jb51.cc 通过网络收集整理的代码片段。编程之家小编现在分享给大家,也给大家做个参考。参考自StackOverflow上的某个问题以及csdn上的这篇博客:以独占方式访问某个文件包含自己的一些理解// 方案1:利用RandomAccessFile的文件操作选项s,s即表示同步锁方式写RandomAccessFile file = new RandomAccessFile(fil...

换主板 oracle 蓝屏,在win7系统中更换主板后蓝屏的解决方案_赵瑞洁的博客-程序员宅基地

关于计算机在日常生活中的重要性,我不会多说,但是一旦您在win7系统中更换主板后遇到蓝屏引导问题,那么很大一部分小伙伴就无从下手. 在win7系统中更换主板后的屏幕. 实际上,在win7系统中更换主板后,处理启动蓝屏并不难. 只需遵循1.我建议您重新安装它,因为毕竟您正在使用软件来卸载驱动程序. 卸载可能不完整,从而导致系统和驱动程序的稳定性. 当出现问题时,很难认为是问题的根源所在. 2.如果...

计算机IPv4升级到IPv6的技术,从ipv4 到ipv6 的演进技术.pdf_拉面加点盐的博客-程序员宅基地

从ipv4 到ipv6 的演进技术《计算机工程》2000 年增刊IPv4 到IPv6 的演进技术邵文简* 曹争(东南大学计算机系,210096 南京)【摘要】本文首先介绍了IPv6 演进中的基本问题,如地址结构、域名解析、路由。然后介绍了两类演进工具,双协议栈和隧道技术以及转换工具,并且详细说明了几种具体的实现方法。【关键词】IPv6 DNS Tunneling Dual St...

网工小白升级打怪篇(七)动态路由协议ospf单区域配置_网事如烟释然的博客-程序员宅基地

加群交流在后台回复“加群”,添加小编微信,小编拉你进去​释然IT杂谈推荐搜索 网络运维安全linux后台回复“724”获取入门资料ospf相关基础理论查看上篇:网工小白升级打怪篇(六)动态路由协议ospf基础实验演示:一、CiscoOSPF单区域案例配置实验拓扑:采用eve-ng模拟实验1.初始化设备,配置设置IP【PC】【R1】Router&gt;en Router#conf tRouter(co...

Excel函数-带错误值的数据求和_牧文山的博客-程序员宅基地

一、数据姓名部门销量杨春海销售一部89赵春雨销售一部92李美桥销售一部#N/A刘永江销售一部83许文武销售一部91刘景瑞销售中心#DIV/0!二、公式1)数组公式(Ctrl+Shift+Enter)=SUM(IFERROR(C2:C7,0))2)一般公式=SUMIF(C2:C7,"&lt;9e307")...

虚拟机安装_菜鸟升级中....的博客-程序员宅基地

虚拟机安装教程安装vmware-12.5.9解压安装包,启动VMware,创建虚拟机选择安装典型的安装配置安装操作系统,将下载好的文件导入**注意:**启动虚拟机后,可能出错(已经踩坑的我重新总结了哈,得到有效地办法和大家分享哦)此时我查了很多资源都是说进入BIOS修改设置,但是要从开机时进行操作(Fn+F1~12)试了多次,每一次成功,但是知道看到一篇博客让我重新有了头绪,接下来,一起看看首先进入设置界面——》更新与安全——》恢复选项——》高级选项——》UEFI固件

推荐文章

热门文章

相关标签