ll1grammar.cpp

编译原理部分代码

/***********************************************************
  Copyright (c) 2004, RM.RYT. All rights reserved.
  Developed in Microsoft Visual C++ 6.0 Enterprise Edition.
 ***********************************************************/

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

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

#define NULL 0
#define LStack LinkedStack

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

// 链式栈类的前视定义
class LinkedStack;

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

// 定义链式栈结点类
class StackNode
{
friend class LinkedStack;
private:
	char data;
    StackNode *next;
	StackNode(char item = '\0', StackNode *p = NULL)
	{
		data = item;
		next = p;
	}
};

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

// 定义链式栈类
class LinkedStack
{
private:
	StackNode *top;
public:
	LinkedStack();
	~LinkedStack();
	int IsEmpty() const;
	int Length() const;
	void Push(const char &item);
	char Pop();
	char GetTop();
	void Clear();
	int BottomUp(StackNode *node);
	int BottomUp();
};
// 构造函数
LinkedStack::LinkedStack()
{
	top = NULL;
}
// 析构函数
LinkedStack::~LinkedStack()
{
	Clear();
}
// 判断栈是否为空
int LinkedStack::IsEmpty(void) const
{
	if (! top)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
// 获取队列的长度
int LinkedStack::Length(void) const
{
	StackNode *temp = new StackNode();
	temp = top;
	int length = 0;
	while (temp)
	{
		temp = temp->next;
		length++;
	}
	return length;
}
// 压入数据(入栈)
void LinkedStack::Push(const char &item)
{
	top = new StackNode(item, top);
}
// 抽出数据(出栈)
char LinkedStack::Pop(void)
{
	if (! IsEmpty())
	{
	    StackNode *temp = top;
		top = top->next;
		char value = temp->data;
		delete temp;
		return value;
	}
	else
	{
		cout << "Stack Already Empty!" << endl;
		getch();
		exit(1);
	}
}
// 获取栈头数据
char LinkedStack::GetTop(void)
{
	if (! IsEmpty())
	{
		return top->data;
	}
	else
	{
		cout << "Stack Already Empty!" << endl;
		getch();
		exit(1);
	}
}
// 设置栈为空栈
void LinkedStack::Clear(void)
{
	StackNode *temp = new StackNode();
	while (top)
	{
		temp = top;
		top = top->next;
		delete temp;
	}
}
// 自底向上到某一指定的节点输出栈中的各个元素
int LinkedStack::BottomUp(StackNode *node)
{
	int len;
	if (node->next)
	{
		len = BottomUp(node->next);
	}
	else
	{
		len = 0;
	}
	cout << node->data;
	return len+1;
}
// 自底向上到栈顶输出栈中的各个元素
int LinkedStack::BottomUp()
{
	return BottomUp(top);
}

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

// 定义产生式类
class Production
{
public:
	char left;
	char *right;
	Production(int len = 128)
	{
		right = new char[len];
		strcpy(right, "\0");
	}
	~Production()
	{
		delete [] right;
	}
};

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

// 定义文法类
class Grammar
{
public:
	Production *production;
	char *nonTerminal;
	char *terminal;
	int grammarSize;
	Grammar(int size = 128)
	{
		production = new Production[128];
		nonTerminal = new char[128];
      	terminal = new char[128];
		grammarSize = size;
	}
	~Grammar()
	{
		delete [] production;
		delete [] nonTerminal;
     	delete [] terminal;
	}
	int IsInString(char *str, char ch);
	void SortSymbols();
	void EliminateLeftRecursion();
};
// 判断字符是否在给定的字符串中
int Grammar::IsInString(char *str, char ch)
{
	int i, len = strlen(str);
	for (i=0; i<len; i++)
	{
		if (ch == str[i])
		{
			return i;
		}
	}
	return -1;
}
// 找出产生式中的所有非终结符和终结符
void Grammar::SortSymbols()
{
	int i, j, nLen, tLen;
	strcpy(nonTerminal, "\0");
	strcpy(terminal, "\0");
	nLen = tLen = 0;
	for (i=0; i<grammarSize; i++)
	{
		if (IsInString(nonTerminal, production[i].left) == -1)
		{
			nonTerminal[nLen++] = production[i].left;
		}
	}
	for (i=0; i<grammarSize; i++)
	{
		for (j=0; production[i].right[j]!='\0'; j++)
		{
			if ((production[i].right[j] >= 'A') && (production[i].right[j] <= 'Z'))
			{
				if (IsInString(nonTerminal, production[i].right[j]) == -1)
				{
		        	nonTerminal[nLen++] = production[i].right[j];
				}
			}
			else
			{
				if (IsInString(terminal, production[i].right[j]) == -1)
				{
		        	terminal[tLen++] = production[i].right[j];
				}
			}
		}
	}
	nonTerminal[nLen] = '\0';
	terminal[tLen] = '\0';
}
// 消除左递归
void Grammar::EliminateLeftRecursion()
{
	int i, j, nLen = strlen(nonTerminal);
	for (i=0; i<nLen; i++)
	{
		for (j=0; j<i; j++)
		{
			// 以下替换产生式的代码
		}
		// 以下是消除左递归的代码
	}
}

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

// 定义预测分析表类
class PredictiveParsingTable
{
public:
	int **table;
	int nonTerminalNum, inputSymbolNum;
	PredictiveParsingTable(int row = 128, int col = 128)
	{
		nonTerminalNum = row;
		inputSymbolNum = col;
		table = (int**)(new int*[nonTerminalNum]);
		for (int i=0; i<nonTerminalNum; i++)
		{
	    	table[i] = new int[inputSymbolNum+1];
		}
	}
	~PredictiveParsingTable()
	{
    	for (int i=0; i<nonTerminalNum; i++)
		{
	    	delete [] table[i];
		}
		delete table;
	}
};

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

// 定义LL(1)文法类
class LL1Grammar
{
public:
	LL1Grammar(int size = 128);
	~LL1Grammar();
	void GetGrammar();
	void PutGrammar();
	char* FIRST(char *str);
	char* FOLLOW(char ch);
	void PutFirst();
	void PutFollow();
	void MakePredictiveParsingTable();
	void PutPredictiveParsingTable();
	void DoPredictiveParsing();
private:
	Grammar *grammar;
	char *input;
	PredictiveParsingTable *mTable;
	void SplitProduction();
	int IsInString(char *str, char ch);
	void PutSuffix(char *buf, int pos);
};
// 构造函数
LL1Grammar::LL1Grammar(int size)
{
	if (size <= 0)
	{
		cout << "\n产生式数目错误!" << endl;
		getch();
		exit(1);
	}
	grammar = new Grammar(size);
	input = new char[128];
}	   
// 析构函数
LL1Grammar::~LL1Grammar()
{
	delete grammar;
	delete [] input;
}
// 输入文法
void LL1Grammar::GetGrammar()
{
	int i;
	char ch;
	cout << "\n请在下面输入这些产生式" << endl;
	for (i=0; i<grammar->grammarSize; i++)
	{
		ch = (char)(getch());
		// 检查产生式左部是否用英文字母表示
		if (! (((ch >= 'A') && (ch <= 'Z')) || ((ch >= 'a') && (ch <= 'z'))))
		{
			cout << "\n字符" << ch << "不符合输入要求!" << endl;
			getch();
			exit(1);
		}
		// 对于小写字母一律替换成大写以表示非终结符
		if ((ch >= 'a') && (ch <= 'z'))
		{
			ch -= 32;
		}
		grammar->production[i].left = ch;
		cout << ch << " -> ";
		// 输入产生式右部的字符串
		cin >> grammar->production[i].right;
		if (IsInString(grammar->production[i].right, '$') >= 0)
		{
			cout << "\n产生式中禁止'$'符号!" << endl;
			getch();
			exit(1);
		}
	}
	cout << endl;
	// 调用SplitProduction函数拆分右部包含'|'字符的产生式
	SplitProduction();
	// 调用SortSymbols函数获取非终结符和终结符的集合
	grammar->SortSymbols();
}
// 输出文法
void LL1Grammar::PutGrammar()
{
	int i;
	cout << "文法包含" << grammar->grammarSize << "个产生式如下" << endl;
	for (i=0; i<grammar->grammarSize; i++)
	{
		cout << grammar->production[i].left << " -> " << grammar->production[i].right << endl;
	}
	cout << "\n非终结符: " << grammar->nonTerminal << "\n终结符: " << grammar->terminal << endl;
}
// 将文法中带有'|'的产生式拆开
void LL1Grammar::SplitProduction()
{
	int i, j, k, flag;
	char *temp = new char[128];
	strcpy(temp, "\0");
	// 第一步：把右部含有'|'的产生式拆分为不含'|'的多个产生式
	for (i=0; i<grammar->grammarSize; i++)
	{
		k = 0;
		// 设置flag为标志位判断产生式右部是否第一次遇见符号'|'
		flag = 0;
		for (j=0; ; j++)
		{
			// 当遇见一般非终结符或终结符时将字符缓存在字符数组中
			if ((grammar->production[i].right[j] != '|') && (grammar->production[i].right[j] != '\0'))
			{
				temp[k++] = grammar->production[i].right[j];
			}
			// 当遇见'|'号或字符串结束符时判断是否执行产生式右部字符串的拆分
			else
			{
				// 如果是第一次遇见则清空缓存字符数组并修改标志位
				if (flag == 0)
				{
					strcpy(temp, "\0");
					k = 0;
					flag = 1;
				}
				// 如果第二次遇见则将'|'后面的字符串移植到新的产生式中
				else
				{
					// 当产生式右部的最后一个字符是'|'所做的出错处理
					if (strlen(temp) == 0)
					{
						cout << "输入不符合要求!" << endl;
						getch();
						exit(1);
					}
					temp[k] = '\0';
					grammar->production[grammar->grammarSize].left = grammar->production[i].left;
					strcpy(grammar->production[grammar->grammarSize].right, temp);
					grammar->grammarSize++;
					strcpy(temp, "\0");
					k = 0;
				}
			}
			// 遇见字符串结束符时跳出循环
			if (grammar->production[i].right[j] == '\0')
			{
				// 跳出循环前把产生式右部的第一个'|'号右边的字符全部去掉
				for (k=0; grammar->production[i].right[k]!='\0'; k++)
				{
					if (grammar->production[i].right[k] == '|')
					{
						grammar->production[i].right[k] = '\0';
						break;
					}
				}
				break;
			}
		}
	}
	// 第二步：合并第一步处理后重复的产生式
	for (i=0; i<grammar->grammarSize-1; i++)
	{
		// 若检测到的重复的表达式，则将文法中最后一个表达式移动替换两个重复表达式的后者
		for (j=i+1; j<grammar->grammarSize; j++)
		{
			if ((grammar->production[i].left == grammar->production[j].left)
				&& (strcmp(grammar->production[i].right, grammar->production[j].right) == 0))
			{
				grammar->production[j].left = grammar->production[grammar->grammarSize-1].left;
				strcpy(grammar->production[j].right, grammar->production[grammar->grammarSize-1].right);
				grammar->production[grammar->grammarSize-1].left = '\0';
				strcpy(grammar->production[grammar->grammarSize-1].right, "\0");
				grammar->grammarSize--;
			}
		}	
	}
}
// 判断字符是否在给定的字符串中
int LL1Grammar::IsInString(char *str, char ch)
{
	int i, len = strlen(str);
	for (i=0; i<len; i++)
	{
		if (ch == str[i])
		{
			return i;
		}
	}
	return -1;
}
// 从指定的位置起输出字符串
void LL1Grammar::PutSuffix(char *buf, int pos)
{
	for (int i=0; buf[i]!='\0'; i++)
	{
		if (i < pos)
		{
			cout << " ";
			continue;
		}
		cout << buf[i];
	}
}
// 获取串的开始符号集合
char* LL1Grammar::FIRST(char *str)
{
	int i, j, k, len = 0;
	char *first = new char[128];
	char *temp = new char[128];
	strcpy(first, "\0");
	strcpy(temp, "\0");
	// 对于字符串只含一个符号的处理
	if (strlen(str) == 1)
	{
		// 当该符号是非终结符的处理
		if ((str[0] >= 'A') && (str[0] <= 'Z'))
		{
			// 逐项扫描文法表
			for (i=0; i<grammar->grammarSize; i++)
			{
				// 当检测到该非终结符在某个产生式左部时的处理
				if (grammar->production[i].left == str[0])
				{
					// 如果产生式右部恰好是空字符时将空字符加入开始符号集合
					if (strcmp(grammar->production[i].right, "~") == 0)
					{
						first[len++] = '~';
						first[len] = '\0';
						break;
					}
					// 如果产生式右部不是空字符串时检查逐个字符的开始符号集合
			    	else
					{
						j = 0;
				    	while (grammar->production[i].right[j] != '\0')
						{
							temp[0] = grammar->production[i].right[j];
							temp[1] = '\0';
							strcpy(temp, FIRST(temp));
							for (k=0; temp[k]!='\0'; k++)
							{
								if (IsInString(first, temp[k]) == -1)
								{
									first[len++] = temp[k];
									first[len] = '\0';
								}
							}
							if (IsInString(temp, '~') == -1)
							{
								break;
							}
							j++;
						}
						// 若产生式右部的每个字符的开始符号集合都包括空字符，则空字符也属于该产生式左部非终结符的开始符号集合
                		if (grammar->production[i].right[j] == '\0')
						{
							if (IsInString(first, '~') == -1)
							{
								first[len++] = '~';
								first[len] = '\0';
							}
						}
					}							
				}
			}
		}
		// 当该符号是终结符的处理
		else
		{
			first[0] = str[0];
			first[1] = '\0';
		}
	}
	// 对于字符串含多个符号的处理
	else
	{
		j = 0;
		while (str[j] != '\0')
		{
			temp[0] = str[j];
			temp[1] = '\0';
			strcpy(temp, FIRST(temp));
			for (k=0; temp[k]!='\0'; k++)
			{
				if (IsInString(first, temp[k]) == -1)
				{
					first[len++] = temp[k];
					first[len] = '\0';
				}
			}
			if (IsInString(temp, '~') == -1)
			{
				break;
			}
			j++;
		}
		// 若字符串中每个字符的开始符号集合都包括空字符，则空字符也属于该字符串的开始符号集合
		if (str[j] == '\0')
		{
			if (IsInString(first, '~') == -1)
			{