ll1grammar.cpp

编译原理部分代码

				first[len++] = '~';
				first[len] = '\0';
			}
		}
	}
	return first;
}
// 获取串的后继符号集合
char* LL1Grammar::FOLLOW(char ch)
{
	int i, j, pos, len;
	char *follow = new char[128];
	char *temp = new char[128];
	strcpy(follow, "\0");
	strcpy(temp, "\0");
	// 若遇见文法的开始符号则首先将'$'加入该非终结符的后继集合中
	if (grammar->production[0].left == ch)
	{
		strcat(follow, "$");
	}
	// 依次扫描文法中所有产生式看有没有形如"A->αBβ"、"A->αB"的匹配项，其中B是该函数的形参
	for (i=0; i<grammar->grammarSize; i++)
	{
		// 若该非终结符在某个产生式的右部则按相应规则计算后继集合
		pos = IsInString(grammar->production[i].right, ch);
		if (pos != -1)
		{
			// 将产生式右部该非终结符以右的字符串复制到临时数组
			strcpy(temp, "\0");
			len = 0;
			for (j=pos+1; grammar->production[i].right[j]!='\0'; j++)
			{
				temp[len++] = grammar->production[i].right[j];
			}
			temp[len] = '\0';
			// 若该非终结符已经在最右端则设置临时数组仅包含空字符'~'
			if (strlen(temp) == 0)
			{
				temp[0] = '~';
				temp[1] = '\0';
			}
			// 若产生式形如"A->αBβ"，则把β的开始集合（空字符除外）加入B的后继集合
			strcat(follow, FIRST(temp));
			len = strlen(follow);
			for (j=0; j<len; j++)
			{
				if (follow[j] == '~')
				{
					follow[j] = follow[len-1];
					follow[len-1] = '\0';
					break;
				}
			}
			// 若产生式形如"A->αB"，或者形如"A->αBβ"且空字符在β的开始集合中，且A不等于B，则把A的后继集合加入B的后继集合
			if ((IsInString(FIRST(temp), '~') >= 0) && (grammar->production[i].left != ch) )
			{
				strcat(follow, FOLLOW(grammar->production[i].left));
			}
		}
	}
	// 删除follow中重复的字符
	len = strlen(follow);
	for (i=0; i<len-1; i++)
	{
		for (j=i+1; j<len; j++)
		{
			if (follow[i] == follow[j])
			{		
				follow[j] = follow[len-1];
	    		follow[len-1] = '\0';
		    	len--;
			}
		}
	}
	return follow;
}
// 分别输出所有非终结符的开始集合
void LL1Grammar::PutFirst()
{
	int i, j, len = strlen(grammar->nonTerminal);
	char temp[128];
	cout << "\n所有非终结符的开始集合如下" << endl;
	for (i=0; i<len; i++)
	{
		temp[0] = grammar->nonTerminal[i];
		temp[1] = '\0';
		strcpy(temp, FIRST(temp));
		cout << "FIRST(" << grammar->nonTerminal[i] << "): ";
		for (j=0; temp[j]!='\0'; j++)
		{
			cout << temp[j] << " ";
		}
		cout << endl;
	}
}
// 分别输出所有非终结符的后继集合
void LL1Grammar::PutFollow()
{
	int i, j, len = strlen(grammar->nonTerminal);
	char temp[128];
	cout << "\n所有非终结符的后继集合如下" << endl;
	for (i=0; i<len; i++)
	{
		strcpy(temp, FOLLOW(grammar->nonTerminal[i]));
		cout << "FOLLOW(" << grammar->nonTerminal[i] << "): ";
		for (j=0; temp[j]!='\0'; j++)
		{
			cout << temp[j] << " ";
		}
		cout << endl;
	}
}
// 构造LL(1)文法的预测分析表
void LL1Grammar::MakePredictiveParsingTable()
{
	int i, j, row = strlen(grammar->nonTerminal), col = strlen(grammar->terminal);
	char *temp = new char[128];
	strcpy(temp, "\0");
	// 初始化预测分析表对象并为每个元素赋初始值-1
	mTable = new PredictiveParsingTable(row, col);
	for (i=0; i<row; i++)
	{
		for (j=0; j<col; j++)
		{
			mTable->table[i][j] = -1;
		}
	}
	// 由于'符号$'不在终结符数组中且不对应预测分析表中的列属性，则用空字符所在的列存放'$'的相关产生式，若空字符不在终结符数组中则新增一列，完成预测分析表的构造后在改空字符为'$'
	int pos = IsInString(grammar->terminal, '~');
	if (pos == -1)
	{
		pos = strlen(grammar->terminal);
	}
	// 循环分析每个产生式A->α，看它能被加到预测分析表的哪一格
	for (i=0; i<grammar->grammarSize; i++)
	{
		row = IsInString(grammar->nonTerminal, grammar->production[i].left);
		strcpy(temp, FIRST(grammar->production[i].right));
		// 对FIRST(α)中的每个终结符a，将A->α加入到M[A,a]中
		for (j=0; temp[j]!='\0'; j++)
		{
			// 空字符没有必要包含在预测分析表的列属性中
			if (temp[j] != '~')
			{
		     	col = IsInString(grammar->terminal, temp[j]);
		    	// 如果表格中已有产生式存在，则证明出错，结束程序
		    	if (mTable->table[row][col] >= 0)
				{
					cout << "\n在分析表的M[" << grammar->nonTerminal[row] << "," << grammar->terminal[col] << "]项中已有产生式" << grammar->production[mTable->table[row][col]].left << "->" << grammar->production[mTable->table[row][col]].right
						 << "\n和现在要添进M[" << grammar->nonTerminal[row] << "," << grammar->terminal[col] << "]的产生式" << grammar->production[i].left << "->" << grammar->production[i].right << "发生冲突";
		    		cout << "\n输入的文法不是LL(1)文法!" << endl;
		    		getch();
		    		exit(1);
				}
		    	mTable->table[row][col] = i;
			}
		}
		// 若空字符在FIRST(α)中，则对FOLLOW(A)中的每个终结符b以及$（若FOLLOW(A)包括$），将A->α加入到M[A,b]和M[A,$]中;
		if (IsInString(temp, '~') >= 0)
		{
			strcpy(temp, FOLLOW(grammar->production[i].left));
			for (j=0; temp[j]!='\0'; j++)
			{
				col = IsInString(grammar->terminal, temp[j]);
				if (temp[j] == '$')
				{
					col = pos;
				}
				// 如果表格中已有产生式存在，则证明出错，结束程序
				if (mTable->table[row][col] >= 0)
				{
					cout << 
			    	cout << "\n输入的文法不是LL(1)文法!" << endl;
			    	getch();
			    	exit(1);
				}
				mTable->table[row][col] = i;
			}
		}
	}
	// 用'$'替换终结符集合中的'~'或在终结符集合末尾加入'$'
	pos = IsInString(grammar->terminal, '~');
	if (pos >= 0)
	{
		grammar->terminal[pos] = '$';
	}
	else
	{
		int len = strlen(grammar->terminal);
		grammar->terminal[len++] = '$';
		grammar->terminal[len] = '\0';
	}
}
// 输出LL(1)文法的预测分析表
void LL1Grammar::PutPredictiveParsingTable()
{
	int i, j, k;
	cout << "\nLL(1)文法的预测分析表如下" << endl;
	// 声明整型变量productionLen和maxProductionLen来控制表格的输出格式
	int productionLen, maxProductionLen = 1;
	for (i=0; i<grammar->grammarSize; i++)
	{
		if (strlen(grammar->production[i].right) > (unsigned)(maxProductionLen))
		{
			maxProductionLen = strlen(grammar->production[i].right);
		}
	}
	maxProductionLen += 3;
	if (maxProductionLen%2 == 1)
	{
		maxProductionLen++;
	}
	cout << "━━━┯";
	int len = strlen(grammar->terminal)*maxProductionLen/2+strlen(grammar->terminal)-1;
	for (i=0; i<len; i++)
	{
		cout << "━";
	}
	cout << "\n 非终 │";
	len = (len * 2 - 8) / 2;
	for (i=0; i<len; i++)
	{
		cout << " ";
	}
	cout << "输入符号\n      ├";
	len = strlen(grammar->terminal) - 1;
	for (i=0; i<len; i++)
	{
		for (j=0; j<maxProductionLen/2; j++)
		{
			cout << "─";
		}
		cout << "┬";
	}
	for (j=0; j<maxProductionLen/2; j++)
	{
		cout << "─";
	}
	cout << "\n 结符 ";
	len++;
	for (i=0; i<len; i++)
	{
		cout << "│";
		for (j=0; j<maxProductionLen/2-1; j++)
		{
			cout << " ";
		}
		cout << grammar->terminal[i];
		for (j=0; j<maxProductionLen/2; j++)
		{
			cout << " ";
		}
	}
	cout << "\n───";
	for (i=0; i<len; i++)
	{
		cout << "┼";
		for (j=0; j<maxProductionLen/2; j++)
		{
			cout << "─";
		}
	}
	cout << endl;
	for (i=0; i<mTable->nonTerminalNum; i++)
	{
		cout << "  " << grammar->production[i].left << "   ";
		for (j=0; j<(int)(strlen(grammar->terminal)); j++)
		{
			cout << "│";
			if (mTable->table[i][j] >= 0)
			{
				productionLen = strlen(grammar->production[mTable->table[i][j]].right) + 3;
				cout << grammar->production[mTable->table[i][j]].left << "->" << grammar->production[mTable->table[i][j]].right;
				for (k=0; k<maxProductionLen-productionLen; k++)
				{
					cout << " ";
				}
			}
			else
			{
				for (k=0; k<maxProductionLen; k++)
				{
					cout << " ";
				}
			}
		}
		cout << endl;
	}
	cout << "━━━";
	for (i=0; i<len; i++)
	{
		cout << "┷";
		for (j=0; j<maxProductionLen/2; j++)
		{	
			cout << "━";
		}
	}
	cout << endl;
}
// 对输入的表达式进行预测分析
void LL1Grammar::DoPredictiveParsing()
{
	int i;
	// 声明变量pos记录输入串中当前字符的位置
	int pos = 0;
	// 声明变量productionNum记录调用的产生式的序号
	int productionNum = -1;
	// 声明变量row和col用来标识预测分析表中的产生式
	int row = -1, col = -1;
	// 接收输入并在字符串末尾加入符号'$'
	cout << "\n请输入一个表达式进行验证" << endl;
	cin >> input;
	strcat(input, "$");
	// 声明三个整形变量用来控制预测分析过程的输出格式
	int stackLen = 1, inputLen = 1, outputLen = 1;
	stackLen = strlen(grammar->nonTerminal) + strlen(input)/2;
	if (stackLen%2 == 1)
	{
		stackLen++;
	}
	if (stackLen < 4)
	{
		stackLen = 4;
	}
	inputLen = strlen(input);
	if (inputLen < 4)
	{
		inputLen = 4;
	}
	if (inputLen%2 == 1)
	{
		inputLen++;
	}
	for (i=0; i<grammar->grammarSize; i++)
	{
		if (strlen(grammar->production[i].right) > (unsigned)(outputLen))
		{
			outputLen = strlen(grammar->production[i].right);
		}
	}
	outputLen += 4;
	if (outputLen%2 == 1)
	{
		outputLen++;
	}
	// 建立一个栈对象，并将符号'$'和文法的开始符号压入
	LStack *stack = new LStack();
	stack->Push('$');
	stack->Push(grammar->production[0].left);
	cout << "\n文法的预测分析过程如下" << endl;
	for (i=0; i<stackLen/2; i++)
	{
		cout << "━";
	}
	cout << "┯";
	for (i=0; i<inputLen/2; i++)
	{
		cout << "━";
	}
	cout << "┯";
	for (i=0; i<outputLen/2; i++)
	{
		cout << "━";
	}
	cout << "\n 栈 ";
	for (i=0; i<stackLen/2-2; i++)
	{
		cout << "  ";
	}
	cout << "│输入";
	for (i=0; i<inputLen/2-2; i++)
	{
		cout << "  ";
	}
	cout << "│输出";
	for (i=0; i<outputLen/2-2; i++)
	{
		cout << "  ";
	}
	cout << endl;
	for (i=0; i<stackLen/2; i++)
	{
		cout << "─";
	}
	cout << "┼";
	for (i=0; i<inputLen/2; i++)
	{
		cout << "─";
	}
	cout << "┼";
	for (i=0; i<outputLen/2; i++)
	{
		cout << "─";
	}
	cout << endl;
	// 作以下分析直到栈只剩下'$'一个元素
	while ((stack->GetTop() != '$') && (input[pos] != '\0'))
	{
		cout << " ";
		int len = stack->BottomUp();
		for (i=0; i<stackLen-len-1; i++)
		{
			cout << " ";
		}
		cout << "│";
		len = strlen(input);
		PutSuffix(input, pos);
		if (len < 4)
		{
			for (i=0; i<4-len; i++)
			{
				cout << " ";
			}
		}
		cout << "│";
		if (productionNum >= 0)
		{
			cout << grammar->production[productionNum].left << "->" << grammar->production[productionNum].right;
		}
		cout << endl;
		if ((stack->GetTop() >= 'A') && (stack->GetTop() <= 'Z'))
		{
			// 从预测分析表中找出相应的产生式
			row = IsInString(grammar->nonTerminal, stack->GetTop());
			col = IsInString(grammar->terminal, input[pos]);
			if ((row == -1) || (col == -1))
			{
				for (i=0; i<stackLen/2; i++)
				{
					cout << "━";
				}
				cout << "┷";
				for (i=0; i<inputLen/2; i++)
				{
					cout << "━";
				}
				cout << "┷";
				for (i=0; i<outputLen/2; i++)
				{
					cout << "━";
				}
				cout << "\n输入的表达式与文法不符!" << endl;
				getch();
				exit(1);
			}
			productionNum = mTable->table[row][col];
			// 当栈顶是非终结符且在预测分析表中存在对应的产生式，则弹出栈顶让产生式右部逆序进栈，否则出错
			if (productionNum >= 0)
			{
				stack->Pop();
				int len = strlen(grammar->production[productionNum].right);
				for (i=len-1; i>=0; i--)
				{
					if (grammar->production[productionNum].right[i] != '~')
					{
						stack->Push(grammar->production[productionNum].right[i]);
					}
				}
			}
			else
			{
				for (i=0; i<stackLen/2; i++)
				{
					cout << "━";
				}
				cout << "┷";
				for (i=0; i<inputLen/2; i++)
				{
					cout << "━";
				}
				cout << "┷";
				for (i=0; i<outputLen/2; i++)
				{
					cout << "━";
				}
				cout << "\n预测分析失败!请检查错误!" << endl;
				getch();
				exit(1);
			}
		}
		else
		{
			productionNum = -1;
			// 当栈顶是终结符且与输入串的当前字符相同，则弹出栈顶并将输入串的当前字符位置向后移动一位，否则出错
			if (stack->GetTop() == input[pos])
			{
				stack->Pop();
				pos++;
			}
			else
			{
				for (i=0; i<stackLen/2; i++)
				{
					cout << "━";
				}
				cout << "┷";
				for (i=0; i<inputLen/2; i++)
				{
					cout << "━";
				}
				cout << "┷";
				for (i=0; i<outputLen/2; i++)
				{
					cout << "━";
				}
				cout << "\n预测分析失败!请检查错误!" << endl;
				getch();
				exit(1);
			}
		}
	}
	if (input[pos] == '$')
	{
		cout << " $";
		for (i=0; i<stackLen-2; i++)
		{
			cout << " ";
		}
		cout << "│";
		int len = strlen(input);
		PutSuffix(input, pos);
		if (len < 4)
		{
			for (i=0; i<4-len; i++)
			{
				cout << " ";
			}
		}
		cout << "│";
		if (productionNum >= 0)
		{
			cout << grammar->production[productionNum].left << "->" << grammar->production[productionNum].right;
		}
		cout << endl;
	}
	for (i=0; i<stackLen/2; i++)
	{
		cout << "━";
	}
	cout << "┷";
	for (i=0; i<inputLen/2; i++)
	{
		cout << "━";
	}
	cout << "┷";
	for (i=0; i<outputLen/2; i++)
	{
		cout << "━";
	}
	// 若输入的字符串中只剩下'$'一个字符时宣告成功，否则失败
	if (input[pos] == '$')
	{
		cout << "\n预测分析成功完成!" << endl;
	}
	else
	{
		cout << "\n预测分析失败!请检查错误!" << endl;
		getch();
		exit(1);
	}
	// 清空栈
	stack->Clear();
}

/////////////////////////////////////////////////

// 主函数
void main()
{
	int size;
	cout << "文法包含的产生式个数: ";
	cin >> size;
	LL1Grammar LL1(size);
	LL1.GetGrammar();
	LL1.PutGrammar();
	LL1.PutFirst();
	LL1.PutFollow();
	LL1.MakePredictiveParsingTable();
	LL1.PutPredictiveParsingTable();
	LL1.DoPredictiveParsing();
}

/*
ETP
P+TP|~
TFQ
Q*FQ|~
F(E)|d

SiEtSR|a
ReS|~
Eb

*/