编译原理 SLR(1)分析技术识别字符串

• 实验名称

SLR(1)分析技术识别字符串

• 实验目的

1. 掌握自底向上语法分析方法的原理
2. 编程完成LR分析法

• 实验内容和要求

本实验要求通过已给的SLR(1)分析表，利用LR分析技术实现对输入串的句型分析，具体包括六个部分：

1. 设计思路；
2. 主函数main；
3. SLR(1)分析表的录入；
4. 分析栈的设计与实现；
5. 用LR分析技术对输入串进行句型分析；
6. 输出LR分析过程。

• 实验环境

VS 2022

• 算法设计思想

1. 分析栈设计：建立两个栈，一个状态栈，一个符号栈。
2. LR分析表设计：分为ACTION表和GOTO表处理。ACTION表由于表内存放的为多个不同类型字符，用结构体实现二维数组，结构体内存放两个成员，即两个int型变量，第一个变量option表示移进操作还是归约操作（值为1为s操作，2为r为归约操作，默认为0）。第二个变量state，若为移进则表下一个要到达的状态，若为归约，则表要用到的第几条文法，若为0且option为1，则表accept。GOTO表由于表内只存数值，因此用一个int类型二维数组表示即可。
3. 主函数由两个函数和一个用户交互构成，slr_creat函数负责读取终结符集和非终结符集以及SLR表，并将其输出；Analysis函数负责主要分析。主分析过程为使用两个分析栈，在while循环里通过两个分析栈对待分析字符串的交叉同时分析，输出分析过程。
4. 详解均在代码里，请自看注释。

• 主要问题与解决方法

问题：分析过程需要输出相关信息，当涉及输出两个分析栈里的信息时，由于无可用函数可以直接从栈底到栈顶将栈元素依次输出，因此需要自行构造一子函数，得以将栈元素按需输出。

解决：构建了两个函数，一个是输出int类栈的state_Printf函数，另一个是输出char类栈的alphebet_Printf函数。 ????????????????????????????????????????????

• 实验结果

匹配成功与失败：

• 体会、质疑、建议

代码中的奥妙，其乐无穷！！！

• 源代码

#include<iostream>
#include<fstream>
#include<stack>
#include<string>
#include<vector>
#include<iomanip>
#define N 100
using namespace std;
/**************************************全局变量定义**********************************************/
struct
{
	int option;        //1为s操作，2为r为归约操作，默认为0
	int state = -1;    //若为移进则表下一个要到达的状态，若为归约，则表要用到的第几条文法，若为0且option为1，则表accept。
}ACTION[N][N],action;
int GOTO[N][N];
string str, VT, VN, Rule[N];
/**************************************函数声明**************************************************/
void slr_creat();
void state_Printf(stack<int>state);
void alphebet_Printf(stack<char>alphebet);
void Analysis();
/**************************************函数区****************************************************/
int main()
{
	/********************************主函数实现部分************************************************/
	int choice = 0;          
	slr_creat();
	Analysis();
	/********************************简单的用户交互设计********************************************/
	while (1) {
		cout << "1.Try new string/2.Exit." << endl << "Press:";
		cin >> choice;
		if (choice == 1)Analysis();
		else exit(0);      //如果选择不是1，则退出系统
	}
	return 0;
}
void slr_creat()
{
	/********************************SLR表文件读入************************************************/
	int sum;								//读取个数需求
	ifstream f("SLR Table.txt");			//C++读取文件方式：ifstream
	getline(f, VN);							//整行读入非终结符字符到VN的string类字符串中
	getline(f, VT);							//整行读入终结符字符到VT的string类字符串中
	/********************************SLR表总共分三部分********************************************/
	/********************************Rule表：文法表输入，string类一维数组**************************/
	f >> sum;								//读入文法个数
	for (int i = 0;i <= sum;i++)
		getline(f, Rule[i]);
	/********************************GOTO表读入***************************************************/
	f >> sum;								//读入状态行数
	for (int i = 0;i < sum;i++)
		for (int j = 0;j < VN.size();j++)
			f >> GOTO[i][j];
	/********************************ACTION表读入************************************************/
	for(int i=0;i<sum;i++)
		for (int j = 0;j < VT.size();j++) {
			f >> ACTION[i][j].option;		//读入操作
			f >> ACTION[i][j].state;		//读入转入状态
		}
	f.close();
}
void Analysis()
{
	/********************************主分析过程**************************************************/
	int step=0;					//步骤
	char now_char;				//此即为当前输入符
	stack<int>state;			//定义一个int型状态栈
	stack<char>alphebet;		//定义一个char型符号栈
	/********************************初始化******************************************************/
	state.push(0);				//初始先对状态栈入0
	alphebet.push('#');			//初始先对符号栈入#号
	/********************************读取用户待分析字符串****************************************/
	cout << "Please input the string be ready to analyze:" << endl;
	cin >> str;
	str.push_back('#');			//对待分析字符串尾部入个#号，为后期分析做准备
	/********************************输出分析过程************************************************/
	cout << "The analysis process of SLR(1) is as follows：" << endl;
	cout << left << setw(9) << "步骤" << setw(16) << "状态栈" << setw(11) << "符号栈";  //分析表标题部分
	cout<< setw(15) << "当前输入符" << setw(15) << "剩余输入串" << setw(21) << "ACTION_Step" << setw(18) << "GOTO_Step" << "动作" << endl;//分析表标题部分
	now_char = str.front();		//首先取待分析字符串首字符
	str.erase(0, 1);			//删去首字符,str.erase(0,1)表示在“0”位置删除“1”个字符
	while (1) {
		cout << left << setw(9) << step++;							//输出步骤
		state_Printf(state);										//利用state_Printf函数将state栈输出
		alphebet_Printf(alphebet);									//利用alphebet_Printf函数将alphebet栈输出
		cout << setw(4) << "" << left << setw(6) << now_char;		//输出当前输入符
		cout << right << setw(15) << str<<setw(5)<<"";				//输出当前剩余待分析字符串
		if (VT.find(now_char) > VT.size()) {						//如果如果当前输入字符找不到，则报错，输出该字符无法识别，
			cout <<  now_char << "无法识别" << endl;				//VT.find()如果找不到当前字符，则会返回一个很大的数，这里便用大于size()来判断该字符是否存在
			break;													//break退出Analysis函数
		}
		action = ACTION[state.top()][VT.find(now_char)];			//为避免分析复杂，用单变量action取值得ACTION[state.top()][VT.find(now_char)]，然后方便做分析
		/********************************做移进操作********************************************************************************************************/
		if (action.option==1) {										//option表操作，1表示s操作，即移进操作
			if (!action.state) {									//这里我将Accept的option也置为1，且state置为0，因此这里做判断，看是否到达结束分析
				cout << "ACTION[" << state.top() << "," << now_char << "]=Accept" << setw(21) << ""<<"接受"<<endl;//如果是0，接受
				cout << "Congratulation!!!   Accept." << endl;
				break;
			}
			cout << "ACTION[" << state.top() << "," << now_char << "]=s" << action.state;	//输出ACTION步骤，ACTION占用6+10+5=21位（格式）
			if (state.top() > 9 && action.state > 9)cout << setw(5) << "";					//这几个判断是为了格式对齐
			else if (state.top() > 9 || action.state > 9)cout << setw(6) << "";				//
			else cout << setw(7) << "";														//
			state.push(action.state);														//移进操作，因此状态栈入新状态，即当前action.state
			alphebet.push(now_char);														//同样符号栈也入掉当前字符，然后取新字符
			now_char = str.front();															//从待分析字符串首位取新的当前字符
			str.erase(str.begin());															//取完之后，将首位字符删除
			cout << setw(18) << "";															//移进操作中，无GOTO步骤输出
			cout << "移进" << endl;															//输出“移进”，进入下一行分析
		}
		/********************************做归约操作********************************************************************************************************/
		else if(action.option==2){															//option表操作，2表示r操作，即归约操作
			int k = 7;																		//对齐格式需要，引进一个k值，并无其他用处
			cout << "ACTION[" << state.top() << "," << now_char << "]=r" << action.state;	//正常输出ACTION步骤，ACTION占用6+10+5=21位（格式）
			if (state.top() > 9 && action.state > 9)cout << setw(5) << "";					//同样，这几个判断是为了格式对齐
			else if (state.top() > 9 || action.state > 9)cout << setw(6) << "";				//
			else cout << setw(7) << "";														//
			for (int i = 1;i < Rule[action.state].size();i++) {								//归约，利用单条文法大小个数对状态栈，符号栈进行精确出栈
				alphebet.pop();																//符号栈出栈操作
				state.pop();																//状态栈出栈操作
			}																				//上下无关文法，文法左部必定是一个非终结符
			alphebet.push(Rule[action.state].front());										//将文法首字符，即归约的最终非终结符
			cout << "GOTO[" << state.top() << "," << alphebet.top() << "]=";				//state入新状态之前，输出GOTO表等号前半部分
			if (state.top() > 9)k--;														//对齐格式需求，因为大于10，输出就会多占一位，因此k--
			state.push(GOTO[state.top()][VN.find(alphebet.top())]);							//此时输出GOTO表前半部分之后，对state栈入新状态
			if (state.top() > 9)k--;														//同样对齐格式需求，因为大于10，输出就会多占一位，因此k--
			cout << state.top();															//输出GOTO表等号后半部分，等号前后state.top()不一样，得前后分开输出
			cout << setw(k) << "";															//格式对齐输出
			cout << "归约" << endl;															//输出“归约”，进入下一行分析
		}
		/********************************做报错操作********************************************************************************************************/
		else {
			cout << right<<setw(43)<<"拒绝" << endl;
			cout << "Sorry!!!   It can not be accepted." << endl;
			break;
		}
	}
}
void state_Printf(stack<int>state)												//由于栈无法直接输出，因此构造此函数
{
	/********************************状态栈输出函数************************************************/
	vector<int>state_lite;														//利用一个vector动态数组
	while (!state.empty()) {													//采用表头插入，在形参栈state空之前，依次插入数组state_lite
		state_lite.insert(state_lite.begin(), state.top());						//.insert(state_lite.begin(), state.top())表示在“state_lite.begin()”位置插入“state.top()”，state_lite.begin()是一个迭代器
		state.pop();															//插入一个，state出栈一个
	}
	int sum = (int   )state_lite.size();										//为了格式对齐需求，引进sum
	for (vector<int>::iterator i = state_lite.begin();i != state_lite.end();i++)//利用vector迭代器i，依次将state_lite数组遍历输出
		if (*i < 10)cout << *i;													//如果小于10，则正常输出
		else {																	//如果大于10，则需要括号，因此这里做特别处理
			cout << "(" << *i << ")";											//加括号输出
			sum += 3;															//格式需求，两个括号加2位，两位数比一位数多一位，因此加3位
		}																		//
	cout << setw(16 - sum) << "";												//做格式对齐输出
}
void alphebet_Printf(stack<char>alphebet)								//由于栈无法直接输出，因此构造此函数
{
	/********************************字符栈输出函数************************************************/
	string alphebet_lite;												//利用一个string类字符串alphebet_lite
	while (!alphebet.empty()) {											//利用表头插入法，将形参alphebet的栈顶元素依次入alphebet_lite字符串
		alphebet_lite.insert(alphebet_lite.begin(), alphebet.top());	//解释同上state_lite.insert
		alphebet.pop();													//插入一个，出栈一个
	}																	//
	cout << left << setw(11) << alphebet_lite;							//格式对齐直接输出string字符串alphebet_lite
}

样例识别字符串：（babbab）

样例SLR表：