第三次实验因为逆波兰式比较简单所以略过 x

源代码仓库：CompilePrincipleLearning/experiment_4 · yusixian/CompilePrincipleLearning (github.com)

在 demo 文件夹中～

# 一。实验目的

掌握 LR (1) 分析法的基本原理
掌握 LR (1) 分析表的构造方法
掌握 LR (1) 驱动程序的构造方法

# 二。实验内容及要求

构造 LR (1) 分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解 LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

根据某一文法编制调试 LR（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对 LR（1）分析法的理解。

对下列文法，用 LR（1）分析法对任意输入的符号串进行分析：

	（0）S’->E

	（1）E->E+T

	（2）E->T

	（3）T->T*F

	（4）T->F

	（5）F->(E)

	（6）F->i

输出的格式如下：

(1) LR（1）分析程序，编制人：姓名，学号，班级

(2) 输入一以 #结束的符号串 (包括 +-*/（）i#)：在此位置输入符号串

(3) 输出过程如下：

步骤	状态栈	符号栈 ****	剩余输入串	动作
1	0	#	i+i*i#	移进

(4) 输入符号串为非法符号串或合法符号串

注意：

1. 表达式中允许使用运算符（+|*）、分割符（括号）、字符 i，结束符 #；

2. 如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；

3. 对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；

4．可采用的其它的文法，但是必须是 LR1 分析方法。

# 三。实验过程

# 1、构造识别 LR（1）文法活前缀的 DFA

如图：新标签页打开，不糊的。

LR1_DFA.drawio.png

action 表和 goto 表如下：

# 2、采用的数据结构

	// ACTION 表
	// + * ( ) i #
	string action[12][6];
	//goto 表
	// a b #
	int _goto[12][3];
	string vt = "+*()i#"; // 终结符表
	string vn = "ETF"; // 非终结符表
	string LR[6] = { "E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i" }; // 存放产生式
	stack<char> chars; // 符号栈
	stack<int> state; // 状态栈

# 3、头文件声明和全局变量定义

如下。

	#include <iostream>
	#include <string>
	#include <fstream>
	#include <stack>
	#include <vector>
	using namespace std;
	const string ExpFileName = "./exp.txt";
	const string GotoFileName = "./goto.txt";
	const string ActionFileName = "./action.txt";
	const int Null = -1;
	// ACTION 表
	// + * ( ) i #
	string action[12][6];
	//goto 表
	// a b #
	int _goto[12][3];
	string vt = "+*()i#"; // 终结符表
	string vn = "ETF"; // 非终结符表
	string LR[6] = { "E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i" }; // 存放产生式

# 4、函数汇总

# （1）函数汇总表

函数名称	功能简述
`readFile`	读取文件函数，返回一个 string 动态数组，以行数分割
`init`	初始化函数，在该函数中进行 goto 表和 action 表的初始化
`printActions / printGotos`	输出 goto 表与 action 表
`isTerminator`	判断当前字符 c 是否是终结符
`findTerminator`	返回终结符所处下标
`findNonTerminator`	返回非终结符所处下标
`s2string`	将栈转换为字符串返回，方便输出步骤
`analyzeLR1`	利用 LR1 分析法分析字符串 exp，输出其分析步骤
`main`	主程序入口，调用读取文件函数开始分析

# （2）函数的调用关系

function4.drawio.png

# （3）流程图

main.drawio.png

# 5、实验结果

# 输入

action.txt 文件

	N N s4 N s5 N
	s6 N N N N acc
	r2 s7 N r2 N r2
	r4 r4 N r4 N r4
	N N s4 N s5 N
	r6 r6 N r6 N r6
	N N s4 N s5 N
	N N s4 N s5 N
	s6 N N s11 N N
	r1 s7 N r1 N r1
	r3 r3 N r3 N r3
	r5 r5 N r5 N r5

goto.txt 文件

	1 2 3
	N N N
	N N N
	N N N
	8 2 3
	N N N
	N 9 3
	N N 10
	N N N
	N N N
	N N N
	N N N

exp.txt 文件

	i+(ii)(i+i)#
	ii+ii#
	i+ii+i(i+i*i)#
	i+(i)+i(i+ii)#
	i+i(i)#

# 输出

# 完整代码

	/*
	* @Author: cos
	* @Date: 2022-04-30 14:20:51
	* @LastEditTime: 2022-05-01 02:34:12
	* @LastEditors: cos
	* @Description: 实验 4 LR (1) 分析法
	* @FilePath: \CompileTheory\experiment_4\demo\main.cpp
	*/
	#include <iostream>
	#include <string>
	#include <fstream>
	#include <stack>
	#include <vector>
	using namespace std;
	const string ExpFileName = "./exp.txt";
	const string GotoFileName = "./goto.txt";
	const string ActionFileName = "./action.txt";
	const int Null = -1;
	// ACTION 表
	// + * ( ) i #
	string action[12][6];
	//goto 表
	// a b #
	int _goto[12][3];
	string vt = "+*()i#"; // 终结符表
	string vn = "ETF"; // 非终结符表
	string LR[6] = { "E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i" }; // 存放产生式
	// 读文件
	vector<string> readFile(string fileName) {
	vector<string> res;
	try {
	ifstream fin;
	fin.open(fileName);
	string temp;
	while (getline(fin, temp))
	res.push_back(temp);
	return res;
	}
	catch (const exception& e) {
	cerr << e.what() << '\n';
	return res;
	}
	}
	void printActions() {
	cout << "-----------------ACTION表------------------" << endl;
	cout << "+\t*\t(\t)\ti\t$" << endl;
	for (int i = 0; i < 12; ++i) {
	for (int j = 0; j < 6; ++j)
	cout << action[i][j] << "\t";
	cout << endl;
	}
	}
	void printGotos() {
	cout << "-----------------GOTO表------------------" << endl;
	cout << "E\tT\tF" << endl;
	for (int i = 0; i < 12; ++i) {
	for (int j = 0; j < 3; ++j)
	cout << _goto[i][j] << "\t";
	cout << endl;
	}
	}
	void init() {
	vector<string> actions = readFile(ActionFileName);
	for (int i = 0; i < 12; ++i) {
	int cnt = 0;
	string row = actions[i];
	int len = actions[i].length();
	for (int j = 0; j < len; ++j) {
	string temp = "";
	while (j < len && row[j] != ' ' && row[j] != '\t') {
	temp += row[j];
	++j;
	}
	while (j < len && (row[j] == ' ' \|\| row[j] == '\t'))
	++j;
	--j;
	action[i][cnt++] = temp;
	}

	}
	printActions();
	vector<string> gotos = readFile(GotoFileName);
	for (int i = 0; i < 12; ++i) {
	int cnt = 0;
	string row = gotos[i];
	int len = row.length();
	for (int j = 0; j < len; ++j) {
	string temp = "";
	while (j < len && row[j] != ' ' && row[j] != '\t') {
	temp += row[j];
	++j;
	}
	while (j < len && (row[j] == ' ' \|\| row[j] == '\t'))
	++j;
	--j;
	_goto[i][cnt++] = (temp == "N") ? Null : stoi(temp);
	}
	}
	printGotos();
	}
	bool isTerminator(char c) {
	return vt.find(c) != string::npos;
	}
	int findTerminator(char c) { // 返回终结符所处下标
	return vt.find(c);
	}
	int findNonTerminator(char c) { // 返回非终结符的下标
	return vn.find(c);
	}
	// 将栈转换为字符串返回
	string s2string(stack<int> s) {
	string str = "";
	while(!s.empty()) {
	str += to_string(s.top()) + " ";
	s.pop();
	}
	return str;
	}
	// 输出剩余输入串
	void printRestInput(string exp, int start, int len) {
	for(int i = start; i < len; ++i)
	cout << exp[i];
	cout << '\t';
	}
	void analyzeLR1(string exp) { // 分析一个表达式
	int len = exp.length();
	stack<char> chars; // 符号栈
	stack<int> state; // 状态栈
	state.push(0); // 初始状态为 0
	chars.push('#'); // 初始符号为#
	string charsStr = "#";
	stack<int> copyState;
	copyState.push(0);
	int cnt = 0; // 序号
	int idx = 0; // 当前输入指针
	cout << "序号\t\t状态栈\t\t符号栈\t\t输入串\t\t描述" << endl;
	cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t' << exp << '\t' << " 初始状态 " << endl;
	while(1) {
	int nowState = state.top();
	char nowChar = exp[idx]; // 当前输入字符
	int isT = findTerminator(nowChar);
	if(isT == Null) { // 非终结符
	cout << "Error!" << "出现非法字符，程序错误退出" <<endl;
	return;
	}
	string actionStr = action[nowState][isT];
	if(actionStr == "acc") {
	cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t' << exp << '\t' << " accept 接受！ " << endl;
	return;
	} else if(actionStr == "N") {
	cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t' << exp << '\t' << "Error! 程序异常退出" << endl;
	return;
	} else if(actionStr[0] == 'r') { // 归约
	int num = stoi(actionStr.substr(1)); // 选用第几个产生式归约
	int len = LR[num-1].length()-3;
	while(len--) {
	chars.pop(); // 出栈，归约
	state.pop();
	charsStr = charsStr.substr(0, charsStr.length()-1);
	copyState.pop(); // 便于输出
	}
	chars.push(LR[num-1][0]); // 产生式左部入符号栈
	charsStr += LR[num-1][0];

	int nowState = state.top();
	int gidx = findNonTerminator(LR[num-1][0]);
	int newState = _goto[nowState][gidx];
	state.push(newState);
	copyState.push(newState);

	cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t';
	printRestInput(exp, idx, len);
	cout << '\t' << " 归约 " << LR[num-1] << endl;
	} else if(actionStr[0] == 's') { // 移进
	int newState = stoi(actionStr.substr(1));
	state.push(newState);
	copyState.push(newState);

	chars.push(nowChar);
	charsStr += nowChar;
	++idx; // 输入指针后移

	cout << cnt++ << '\t' << s2string(copyState) << '\t' << charsStr << '\t';
	printRestInput(exp, idx, len);
	cout << '\t' << actionStr << " 移进 " << endl;
	} else {
	cout << "Error!" << "程序异常退出" <<endl;
	return;
	}
	}
	}
	int main() {
	cout << "LR（1）分析程序，编制人：xxx xxxxxxxx xxxx班" << endl;
	cout << "提示:本程序只能对由'i','+','*','/','(',')'构成的以'#'结束的表达式进行分析，每行读入一个表达式" << endl;
	cout << "读取的文件名为：" << ExpFileName << endl;
	init();
	vector<string> exps = readFile(ExpFileName);
	int len = exps.size();
	for (int i = 0; i < len; i++) {
	string exp = exps[i];
	cout << "\n------------------待分析表达式" << i+1 << "："<< exp << "--------------------" << endl;
	bool flag = true;
	for (int j = 0; j < exp.length(); j++) {
	if (!isTerminator(exp[j])) {
	cout << "第 "<< i+1 << "行输入的字符串不合法，请重新输入" << endl;
	flag = false;
	break;
	}
	}
	if (flag) {
	cout << "表达式" << i+1 << "：" << exp << "分析开始" << endl;
	analyzeLR1(exp);
	}
	}
	return 0;
	}

编译原理

	i+(ii)(i+i)#
	ii+ii#
	i+ii+i(i+i*i)#
	i+(i)+i(i+ii)#
	i+i(i)#