选用哪条文法规则 - 照猫画虎 | Scarecrow = 2022

# 已知文法

E → T|E+T|E-T
T → F|T*F|T/F
F → (E)|i
给出下列表达式的最左最右推导
i*(i+i)
i+i*i

# 思想

1. 输入待推导的表达式
2. 对表达式字符串进行第一行文法判定

判断是否有 + or - 运算符括号内除外，是则输出 E→E+T or E→E-T ， + 之前的所有字符返回进行 2 ， + 之后的字符进行 3 ；否则进行下一步。
输出 E→T ，所有字符串进行 3 。

3. 对表达式字符串进行第二行文法判定

判断是否有 * or / 运算符括号内除外，是则输出 E→E*T or E→E/T ， + 之前的所有字符返回进行 2 ， + 之后的字符进行 3 ；否则进行下一步。
输出 T→F ，所有字符串进行 4 。

4. 对表达式字符串进行第三行文法判定
第一个字符是否为 ( ，是则输出 F→(E) ，然后将该字符串的 ( 、 ) 删除，返回 2 ；否则输出 F →i ，操作结束。

# 代码

	#include<iostream>
	#include<string.h>

	using namespace std;

	// 全局变量
	char str[10];// 存储
	int step;// 记录推导步长

	void DeduceE(int l, int r);// 文法第一行
	void DeduceT(int l, int r);// 文法第二行
	void DeduceF(int l, int r);// 文法第三行
	void DeDeduceE(int l, int r);// 文法第一行
	void DeDeduceT(int l, int r);// 文法第二行
	void DeDeduceF(int l, int r);// 文法第三行
	void menu();

	// 主函数
	int main() {
	string choose = "1";
	while (choose == "1") {
	system("cls");
	menu();
	int error = 1;
	while (error == 1) { // 输入句子，简单判错
	cout << "请输入该文法的句子：" << endl << ">>";
	cin >> str;
	for (int i = 0; i < strlen(str); i++) {
	if (str[i] != 'i' && str[i] != '+' && str[i] != '*' && str[i] != '/' && str[i] != '(' &&
	str[i] != ')') {
	cout << "输入有误请重新输入！表达式应只含有“i,+,*,/,(,)”等字符！" << endl;
	error = 1;
	break;
	} else
	error = 0;
	}
	}
	int choice;
	cout << "请选择" << endl << "1.最右" << endl << "2.最左" << endl << ">>";
	cin >> choice;
	switch (choice) {
	case 1:
	step = 1;
	DeduceE(0, strlen(str));// 进行文法的推导
	break;
	case 2:
	step = 1;
	DeDeduceE(0, strlen(str));// 反向进行文法的推导
	break;
	}
	cout << endl << "推导完毕！" << endl << endl;
	cout << "输入 1 继续推导其他句子，输入其他退出。" << endl;
	cin >> choose;
	}
	}

	void menu() {
	string P[3][4];
	P[0][0] = "E";
	P[0][1] = "T";
	P[0][2] = "E+T";
	P[0][3] = "E-T";
	P[1][0] = "T";
	P[1][1] = "F";
	P[1][2] = "T*F";
	P[1][3] = "T/F";
	P[2][0] = "F";
	P[2][1] = "(E)";
	P[2][2] = "i";
	cout << "文法如下：" << endl;// 输出文法
	for (int i = 0; i < 3; i++) {
	if (i < 2)
	cout << P[i][0] << " → " << P[i][1] << "\|" << P[i][2] << "\|" << P[i][3];
	else
	cout << P[i][0] << " → " << P[i][1] << "\|" << P[i][2];
	cout << endl;
	}
	}

	// 首字符 F，第三行文法
	void DeduceF(int l, int r) {
	char a[10];
	int i, j = 0;
	if (str[l] == '(') { // 判断是否含括号
	cout << "step " << step << ":" << "F->(E)" << endl;
	step++;
	for (i = 0; i < strlen(str); i++)
	if (str[i] != ')')
	a[j++] = str[i];
	memset(str, 0, sizeof(str));
	for (i = 0; i < strlen(a); i++)
	str[i] = a[i];
	DeduceE(l + 1, strlen(str));// 返回文法第一行
	} else { // 无括号，直接输出值 i
	cout << "step " << step << ":" << "F->i" << endl;
	step++;
	}
	}

	// 首字符 T，第二行文法
	void DeduceT(int l, int r) {
	int bracket = 0;// 记录括号
	int symbol = 0;// 记录符号
	for (int i = r - 1; i >= l; i--) { // 判断字符串是否含括号和运算符
	if (str[i] == ')')
	bracket++;
	if (str[i] == '(')
	bracket--;
	if (!bracket) { // 没有括号或不在括号内部，则进行运算符操作（不对括号内的内容进行运算符处理）
	if (str[i] == '*') {
	symbol = 1;
	cout << "step " << step << ":" << "T->T*F" << endl;
	step++;
	DeduceF(l, i);// 转去进行文法第三行判断
	DeduceT(i + 1, r);// 继续进行文法第一行判断
	break;
	} else if (str[i] == '/') {
	symbol = 1;
	cout << "step " << step << ":" << "T->T/F" << endl;
	step++;
	DeduceF(l, i);
	DeduceT(i + 1, r);
	break;
	}
	}
	}
	if (!symbol) { // 字符串既没括号，也没字符
	cout << "step " << step << ":" << "T->F" << endl;
	step++;
	DeduceF(l, r);// 转去进行文法第三行判断
	}
	}

	// 首字符 E，第一行文法
	void DeduceE(int l, int r) {
	int bracket = 0;// 记录括号
	int symbol = 0;// 记录符号
	for (int i = r - 1; i >= l; i--) { // 判断字符串是否含括号和运算符
	if (str[i] == ')')
	bracket++;
	if (str[i] == '(')
	bracket--;
	if (!bracket) { // 没有括号或不在括号内部，则进行运算符操作（不对括号内的内容进行运算符处理）
	if (str[i] == '+') {
	symbol = 1;
	cout << "step " << step << ":" << "E->E+T" << endl;
	step++;
	DeduceT(l, i);// 转去进行文法第二行判断
	DeduceE(i + 1, r);// 继续进行文法第一行判断
	break;
	} else if (str[i] == '-') {
	symbol = 1;
	cout << "step " << step << ":" << "E->E-T" << endl;
	step++;
	DeduceT(l, i);
	DeduceE(i + 1, r);
	break;
	}

	}
	}
	if (!symbol) { // 字符串既没括号，也没字符
	cout << "step " << step << ":" << "E->T" << endl;
	step++;
	DeduceT(l, r);// 转去进行文法第二行判断
	}
	}

	// 首字符 F，第三行文法
	void DeDeduceF(int l, int r) {
	char a[10];
	int i, j = 0;
	if (str[l] == '(') { // 判断是否含括号
	cout << "step " << step << ":" << "F->(E)" << endl;
	step++;
	for (i = 0; i < strlen(str); i++)
	if (str[i] != ')')
	a[j++] = str[i];
	memset(str, 0, sizeof(str));
	for (i = 0; i < strlen(a); i++)
	str[i] = a[i];
	DeDeduceE(l + 1, strlen(str));// 返回文法第一行
	} else { // 无括号，直接输出值 i
	cout << "step " << step << ":" << "F->i" << endl;
	step++;
	}
	}

	// 首字符 T，第二行文法
	void DeDeduceT(int l, int r) {
	int bracket = 0;// 记录括号
	int symbol = 0;// 记录符号
	for (int i = r - 1; i >= l; i--) { // 判断字符串是否含括号和运算符
	if (str[i] == ')')
	bracket++;
	if (str[i] == '(')
	bracket--;
	if (!bracket) { // 没有括号或不在括号内部，则进行运算符操作（不对括号内的内容进行运算符处理）
	if (str[i] == '*') {
	symbol = 1;
	cout << "step " << step << ":" << "T->T*F" << endl;
	step++;
	DeDeduceT(i + 1, r);// 继续进行文法第一行判断
	DeDeduceF(l, i);// 转去进行文法第三行判断
	break;
	} else if (str[i] == '/') {
	symbol = 1;
	cout << "step " << step << ":" << "T->T/F" << endl;
	step++;
	DeDeduceT(i + 1, r);
	DeDeduceF(l, i);
	break;
	}
	}
	}
	if (!symbol) { // 字符串既没括号，也没字符
	cout << "step " << step << ":" << "T->F" << endl;
	step++;
	DeDeduceF(l, r);// 转去进行文法第三行判断
	}
	}

	// 首字符 E，第一行文法
	void DeDeduceE(int l, int r) {
	int bracket = 0;// 记录括号
	int symbol = 0;// 记录符号
	for (int i = r - 1; i >= l; i--) { // 判断字符串是否含括号和运算符
	if (str[i] == ')')
	bracket++;
	if (str[i] == '(')
	bracket--;
	if (!bracket) { // 没有括号或不在括号内部，则进行运算符操作（不对括号内的内容进行运算符处理）
	if (str[i] == '+') {
	symbol = 1;
	cout << "step " << step << ":" << "E->E+T" << endl;
	step++;
	DeDeduceE(i + 1, r);// 继续进行文法第一行判断
	DeDeduceT(l, i);// 转去进行文法第二行判断
	break;
	} else if (str[i] == '-') {
	symbol = 1;
	cout << "step " << step << ":" << "E->E-T" << endl;
	step++;
	DeDeduceE(i + 1, r);
	DeDeduceT(l, i);
	break;
	}

	}
	}
	if (symbol == 0) { // 字符串既没括号，也没字符
	cout << "step " << step << ":" << "E->T" << endl;
	step++;
	DeDeduceT(l, r);// 转去进行文法第二行判断
	}
	}

思考 CPP 实验作业编译原理文法