////////////////////////////////////////////////////////////////
//版權(quán)所有：臺(tái)州學(xué)院信息與電子工程學(xué)院計(jì)算機(jī)系 應(yīng)老師
//制作日期：2003年10月25日
//《編譯原理》試驗(yàn)示例
//
//程序功能：
//根據(jù)算符優(yōu)先分析法，將表達(dá)式進(jìn)行語法分析，判斷一個(gè)表達(dá)式是否正確。
//文法：E→E+E|E-E|E*E|E/E|(E)|i
//		其中i為無符號(hào)整數(shù)
//
//例：
//輸入：10;
//輸出：正確
//輸入：1+2;
//輸出：正確
//輸入：(1+2)/3+4-(5+6/7);
//輸出：正確
//輸入：((1-2)/3+4;
//輸出：錯(cuò)誤
//
//輸入測試數(shù)據(jù)保存在同目錄的文本文件testin.txt中，保存格式：
//		表達(dá)式行;
//		表達(dá)式行;
//		.....
//預(yù)期的輸出保存在同目錄的文本文件testout.txt中，保存格式：
//		表達(dá)式行;
//      正確/錯(cuò)誤
//		表達(dá)式行;
//      正確/錯(cuò)誤
//		.....
/////////////////////////////////////////////////////////////////

#include "stdio.h"
#include "stdlib.h"
#define TRUE 1
#define FALSE 0

//文件信息：
#define TESTIN_FILENAME "testin.txt"
#define TESTOUT_FILENAME "testout.txt"
FILE * fTestIn;
FILE * fTestOut;	//打開文件后的柄

//運(yùn)算符定義：
#define O_NUMBER 8		//運(yùn)算符個(gè)數(shù)，+-*/()i#
#define O_PLUS 0	// 加+
#define O_MINUS 1	// 減-
#define O_TIMES 2	// 乘*
#define O_SLASH 3	// 除/
#define O_L_PAREN 4	//左括號(hào)(parenthesis)
#define O_R_PAREN 5	//右括號(hào)
#define O_IDENT 6	//標(biāo)識(shí)符
#define O_NUL 7		//語法界符#

//表達(dá)式緩沖區(qū)：由專門函數(shù)操作（ReadFormula(),GetChar()）
#define BUFFER_SIZE 1000	//表達(dá)式緩沖區(qū)大小
char Buffer[BUFFER_SIZE];	//表達(dá)式緩沖區(qū)，以'\0'表示結(jié)束
int ipBuffer = 0;		//表達(dá)式緩沖區(qū)當(dāng)前位置序號(hào)

//算符優(yōu)先關(guān)系表：
char O_Table[O_NUMBER][O_NUMBER] = {
	{'>','>','<','<','<','>','<','>'},
	{'>','>','<','<','<','>','<','>'},
	{'>','>','>','>','<','>','<','>'},
	{'>','>','>','>','<','>','<','>'},
	{'<','<','<','<','<','=','<','-'},
	{'>','>','>','>','-','>','-','>'},
	{'>','>','>','>','-','>','-','>'},
	{'<','<','<','<','<','-','<','='}
	};	//優(yōu)先關(guān)系表：八個(gè)字符分別是+-*/()i#,其中'-'表示出錯(cuò)

//文法：
#define OG_NUMBER 6	//文法個(gè)數(shù)
char OG[OG_NUMBER][4] = {"E+E","E-E","E*E","E/E","(E)","i"};	//文法右部

//單詞序列存放格式定義：
#define TOKEN_MAX_LENTH 100		//最大的單詞長度+1
typedef struct 
	{
		char ch;	//存放字符：+-*/()i#E
		int No;	//存放算符優(yōu)先關(guān)系表中的序號(hào)
		//double Value;	//當(dāng)ch==i時(shí)，且為數(shù)值時(shí)，存放值的大小
	} SToken;
#define MAX_TOKEN_NUMBER 1000	//在一個(gè)表達(dá)式中允許最大的單詞個(gè)數(shù)
SToken Token[MAX_TOKEN_NUMBER];	//單詞序列，最后一個(gè)以“#”結(jié)束
int TokenNumber = 0;	//單詞序列中包含的單詞個(gè)數(shù)
int ipToken = 0;	//進(jìn)行“移進(jìn)-規(guī)約”時(shí)的位置指示

//堆棧：由專門的函數(shù)操作（PopUp(),Push(),…）
#define STACK_MAX_SIZE 1000	//堆棧最大存儲(chǔ)量
SToken Stack[STACK_MAX_SIZE];	//堆棧
int ipStack = 0;		//堆棧指針，指向棧頂（下一個(gè)空位置）

//詞法分析專用全局變量：
char ch;	//存放取得的一個(gè)字符
//char AToken[TOKEN_MAX_LENTH];	//存放組成的單詞，存放時(shí)以\0為結(jié)束
//int ipAToken;	//用于讀字符時(shí)，指向下一個(gè)AToken[]的位置，便于組成單詞

//錯(cuò)誤信息：
char * ErrMsg;	//出錯(cuò)信息

//函數(shù)聲明：
bool Judge(); //利用算符優(yōu)先關(guān)系表判斷單詞序列是否正確
int GuiYue(); //規(guī)約，并判斷是否完成
bool IsOK(); //判斷規(guī)約是否全部完成
bool GuiYueN(int n); //將堆棧中0~n單詞規(guī)約
int FindPriorOp(int Begin); //在堆棧中，從Begin開始，查找前一個(gè)終結(jié)符位置
int MoveIn(); //移進(jìn)，并判斷是否需要規(guī)約
void JudgeInit(); //（利用算符優(yōu)先關(guān)系表判斷單詞序列是否正確）判斷前的初始化
SToken Peek(int n); //窺視堆棧
bool PopUp(int n); //彈出堆棧
void PushToken(char ch, int O_No); //壓棧（以字符形式）
void Push(SToken Token); //壓棧
bool Init(); //全局初始化
void End(); //程序退出前作善后處理
void OutPut(char * Formula, char * Result); //將結(jié)果輸出到文件
bool ReadFormula(); //從文件中讀出一個(gè)表達(dá)式存于表達(dá)式緩沖區(qū)Buffer[]中，以'\0'結(jié)束，并置ipBuffer=0；
bool ChangeToTokens(); //將表達(dá)式分割成單詞序列
char GetFirstChar(); //從表達(dá)式緩沖區(qū)中取到下面第一個(gè)非空字符
char GetChar(); //從表達(dá)式緩沖區(qū)取一個(gè)字符，返回該字符的同時(shí)將它存于全局變量ch中
bool MakeErr(char * ErrMassage); //生成錯(cuò)誤信息，錯(cuò)誤信息存于全局變量ErrMsg中
///////////////////////////////////////

void main()
{
	if(! Init()) //初始化
	{
		printf("初始化失敗！程序不能繼續(xù)。錯(cuò)誤信息如下：\n%s\n",ErrMsg);
	//	exit(0);
	}

	while(ReadFormula())	//從文件中讀表達(dá)式成功
	{
		if(ChangeToTokens())	//將表達(dá)式分割成單詞序列
		{
        	if(Judge())	//利用算符優(yōu)先關(guān)系表判斷表達(dá)式（單詞序列）是否正確
				OutPut(Buffer,"正確！");
			else
				OutPut(Buffer,ErrMsg); //輸出錯(cuò)誤信息
		}
		else //出錯(cuò)
		{
			OutPut(Buffer,ErrMsg); //輸出錯(cuò)誤信息
		}
	}
	End(); //程序退出前作善后處理
}

//利用算符優(yōu)先關(guān)系表判斷單詞序列是否正確
//返回：TRUE正確；FALSE錯(cuò)誤，且錯(cuò)誤信息存于ErrMsg
//本函數(shù)的實(shí)現(xiàn)思路：
//    將單詞序列進(jìn)行“移進(jìn)-規(guī)約”操作，最后判斷是否能全部完成
//    使用到：堆棧（SToken Stack[]）、文法（char OG[][]）、算符優(yōu)先關(guān)系表（char O_Table[][]）等
bool Judge()
{
	JudgeInit();
	PushToken('#',O_NUL);	//將“#”號(hào)置棧底
	while(TRUE)	//進(jìn)行“移進(jìn)-規(guī)約”操作
	{
		switch(MoveIn())
		{
		case 1: //需要規(guī)約
			switch(GuiYue())//規(guī)約
			{
			case 1: //這一步規(guī)約成功
				break;
			case 2: //規(guī)約全部完成
				return TRUE;
			default: //出錯(cuò)
				ErrMsg = "規(guī)約錯(cuò)誤。";
				return FALSE;
			}
			break;
		case 2: //需要繼續(xù)移進(jìn)
			break;
		default: //出錯(cuò)
			return FALSE;
		}
	}
}

//規(guī)約，并判斷是否完成
//返回：-1出錯(cuò)，1這一步規(guī)約成功，2規(guī)約全部完成
int GuiYue()
{
	int n0,n;
	char r; //存優(yōu)先關(guān)系

	n = FindPriorOp(-1); //取得堆棧中第一個(gè)終結(jié)符
	if(Peek(n).ch == '#') //出錯(cuò)或全部結(jié)束
	{
		if(IsOK())
			return 2;
		else
			return -1;
	}
	while(TRUE)
	{
		n0 = n;
		n = FindPriorOp(n0); //前一個(gè)終結(jié)符的堆棧位置
		if(n - n0 > 2) //出錯(cuò)（多個(gè)非終結(jié)符相鄰）
			return -1;
		r = O_Table[Peek(n).No][Peek(n0).No];
		if(r == '<') //尋找結(jié)束
		{
			if(! GuiYueN(n - 1)) //規(guī)約（從前一個(gè)后的字符開始）規(guī)約失敗
				return -1;
			else //規(guī)約成功，還要判斷是否全部完成
			{
				if(IsOK())
					return 2; //規(guī)約全部完成
				else
					return 1; //這一步規(guī)約成功
			}
		}
		else if(r == '=') //繼續(xù)向前找
		{
			continue;
		}
		else //出錯(cuò)（r為>或沒有關(guān)系）
			return -1;
	}
}

//判斷規(guī)約是否全部完成
//返回：TRUE全部完成；FALSE沒有完成
bool IsOK()
{
	//if(Peek(1) == NULL) return FALSE;
	if(Peek(0).ch == 'E'&& Peek(1).ch == '#' && Token[ipToken].ch == '#')
		return TRUE;
	else
		return FALSE;
}

//返回：TRUE成功，F(xiàn)ALSE失敗
bool GuiYueN(int n) //將堆棧中0~n單詞規(guī)約
{
	int i,j;
	bool k;
	for(i=0;i<OG_NUMBER;i++) //將規(guī)約串和文法右部OG[][]每一個(gè)進(jìn)行比較
	{
		for(j=n,k=FALSE;j>=0;j--)
		{
			if(OG[i][n-j] != Peek(j).ch)
			{
				k = TRUE; //TRUE表示規(guī)約串和文法右部不符，
				break;
			}
		}
		if(k) continue; 
		//k==FALSE表示規(guī)約串判斷完成
		if(OG[i][n+1]=='\0') //文法也判斷完成，匹配成功
		{
			PopUp(n + 1); //彈出規(guī)約串
			PushToken('E',O_IDENT); //壓入左部“E”
			return TRUE;
		}
	}
	return FALSE;
}

//在堆棧中，從Begin開始，查找前一個(gè)終結(jié)符位置
//如果從開始找，讓 Begin = -1
int FindPriorOp(int Begin)
{
	int n;
	n = Begin + 1;
	while(Peek(n).ch == 'E')
	{
		n ++;
	}
	return n;
}

//移進(jìn)，并判斷是否需要規(guī)約
//返回：-1出錯(cuò)，1需要規(guī)約，2可繼續(xù)移進(jìn)
//   1.單詞結(jié)束（遇到“#”號(hào)），無法移進(jìn)，需要規(guī)約，返回：1
//   2.單詞沒有結(jié)束，需判斷是否可以移進(jìn)
//     2-1.堆棧單詞<=單詞：移進(jìn)后返回：2
//     2-2.堆棧單詞>單詞：不能移進(jìn)，需要規(guī)約，返回：1
//     2-3.兩單詞沒有優(yōu)先關(guān)系：出錯(cuò)，返回：-1
int MoveIn()
{
	SToken s,t; //分別存堆棧頂單詞和單詞序列的第一個(gè)單詞
	char r; //存放優(yōu)先關(guān)系
	s = Peek(FindPriorOp(-1)); //取得堆棧中第一個(gè)終結(jié)符位置
	t = Token[ipToken];
	r = O_Table[s.No][t.No];
	if(t.ch == '#') //單詞結(jié)束，無法移進(jìn)，需要規(guī)約
		return 1;
	else //單詞沒有結(jié)束，需判斷是否可以移進(jìn)
	{
		if(r == '<' || r == '=') //需要移進(jìn)
		{
			Push(t);
			ipToken ++;
			return 2;
		}
		else if(r == '>') //不能移進(jìn)，需要規(guī)約
			return 1;
		else //沒有優(yōu)先關(guān)系，出錯(cuò)
		{
			MakeErr("移進(jìn)時(shí)出現(xiàn)兩個(gè)沒有優(yōu)先關(guān)系的相鄰單詞。");
			return -1;
		}
	}
}

//（利用算符優(yōu)先關(guān)系表判斷單詞序列是否正確）判斷前的初始化
//由于多個(gè)表達(dá)式需要依次判斷，因此對(duì)每個(gè)表達(dá)式判斷前都需要初始化
void JudgeInit()
{
	ipStack = 0; //堆棧初始化（如果有專門的StackClear()函數(shù)則更好）

	ipToken = 0; //指向首個(gè)單詞
}

//窺視堆棧
//參數(shù)：n相對(duì)棧頂?shù)奈恢茫?開始）
//成功返回：返回單詞
//不成功返回：NULL
SToken Peek(int n)
{
	SToken Token;
	if(n > 0 || n < ipStack) 
		Token = Stack[ipStack - n - 1];
	else if(n < 0)
		Token = Stack[ipStack - 1];
	else
		Token = Stack[0];
	return Token;
}

//彈出堆棧
//參數(shù)：n彈出單詞個(gè)數(shù)（不能全部彈空，即保留#號(hào)）
//不成功返回：FALSE
//成功返回：TRUE
bool PopUp(int n)
{
	if(ipStack < 2) return FALSE; //只剩0個(gè)或1個(gè)
	if(n > ipStack - 1) n = ipStack - 1;
	ipStack -= n;
	return TRUE;
}

//壓棧（以字符形式）
//參數(shù)：ch是要壓棧的字符（+-*/()i#E 之一），O_No運(yùn)算符序號(hào)
//調(diào)用：Push()
void PushToken(char ch, int O_No)
{
	SToken Token;
	Token.ch = ch;
	Token.No = O_No;
	Push(Token);
}

//壓棧
//參數(shù)：Token是要壓棧的SToken結(jié)構(gòu)體類型的單詞
//缺點(diǎn)：沒有判斷堆棧是否滿
void Push(SToken Token)
{
	Stack[ipStack ++] = Token;
}

//全局初始化
//成功：返回TRUE；失敗：返回FALSE
bool Init()
{
	//if((fTestIn = fopen(TESTIN_FILENAME, "r")) = NULL) return ! MakeErr("不能打開測試文件！");
	//if((fTestOut = fopen(TESTOUT_FILENAME, "w")) = NULL) return ! MakeErr("不能打開結(jié)果輸出文件！");
fTestIn = fopen(TESTIN_FILENAME, "r");
fTestOut = fopen(TESTOUT_FILENAME, "w");
	return TRUE;
}

//程序退出前作善后處理
//主要是關(guān)閉文件等
void End()
{
	fclose(fTestIn);
	fclose(fTestOut);
}

//將結(jié)果輸出到文件
//要求文件事先以追加方式打開，文件指針為fTestOut
//參數(shù)：Formula表達(dá)式內(nèi)容，Result判斷結(jié)果
void OutPut(char * Formula, char * Result)
{
	fprintf(fTestOut,"%s\n%s\n",Formula,Result);
}

//從文件中讀出一個(gè)表達(dá)式存于表達(dá)式緩沖區(qū)Buffer[]中，以'\0'結(jié)束，并置ipBuffer=0；
//需要先打開文件，文件指針存于fTestIn
//讀出非空表達(dá)式：返回 TRUE；文件結(jié)束：返回 FALSE
bool ReadFormula() 
{
	int n = 0;
	bool k = FALSE;	//當(dāng) k==TRUE 時(shí)表示文件結(jié)束，否則文件沒有結(jié)束
	while(TRUE)
	{
		if((Buffer[n] = fgetc(fTestIn)) != EOF) //讀出一個(gè)字符成功
		{
			if(Buffer[n] == ';') break;
			n ++;
		}
		else //文件結(jié)束
		{
			k = TRUE;
			break;
		}
	}
	Buffer[n] = '\0';	//最后一個(gè)字符用結(jié)束標(biāo)記'\0'代替
	ipBuffer = 0;	//初始化緩沖區(qū)指針
	if(n > 0) //讀出的數(shù)據(jù)非空，返回成功
		return TRUE;
	else //讀出的數(shù)據(jù)為空，需要判斷文件結(jié)束，還是只有';'的空表達(dá)式
	{
		if(k) //文件結(jié)束
			return FALSE;
		else //空表達(dá)式，文件沒有結(jié)束，讓它繼續(xù)讀下一個(gè)表達(dá)式
			return ReadFormula();
	}
}

//將表達(dá)式分割成單詞序列
//結(jié)果：單詞序列存于SToken Token[]中，單詞個(gè)數(shù)存于TokenNumber中
//這是一個(gè)大模塊，其中要調(diào)用一些子函數(shù)
//本函數(shù)只識(shí)別：運(yùn)算符+-*/、括號(hào)()、無符號(hào)整數(shù)i，并在末尾添加#號(hào)
//				遇到其它任何字符都返回錯(cuò)誤信息
//返回：TRUE表示成功；FALSE表示失敗，同時(shí)將錯(cuò)誤信息存于全局變量ErrMsg中
//使用到的其他全局變量：ch（取一個(gè)字符）、AToken[]（取到的單詞）
bool ChangeToTokens()
{
	TokenNumber = 0;
	if(GetFirstChar() == '\0') return ! MakeErr("表達(dá)式為空。");
	while(TRUE) //對(duì)緩沖區(qū)進(jìn)行循環(huán)讀
	{
		if(ch <= 32 && ch > 0) GetFirstChar(); //濾去空格
		switch(ch) //對(duì)單詞的第一個(gè)進(jìn)行判斷，在下面一次處理整個(gè)單詞
		{
		case '\0':
			Token[TokenNumber].ch = '#';
			Token[TokenNumber].No = O_NUL;
			return TRUE; //處理結(jié)束
		case '+':
			Token[TokenNumber].ch = '+';
			Token[TokenNumber].No = O_PLUS;
			GetChar();
			break;
		case '-':
			Token[TokenNumber].ch = '-';
			Token[TokenNumber].No = O_MINUS;
			GetChar();
			break;
		case '*':
			Token[TokenNumber].ch = '*';
			Token[TokenNumber].No = O_TIMES;
			GetChar();
			break;
		case '/':
			Token[TokenNumber].ch = '/';
			Token[TokenNumber].No = O_SLASH;
			GetChar();
			break;
		case '(':
			Token[TokenNumber].ch = '(';
			Token[TokenNumber].No = O_L_PAREN;
			GetChar();
			break;
		case ')':
			Token[TokenNumber].ch = ')';
			Token[TokenNumber].No = O_R_PAREN;
			GetChar();
			break;
		default:
			if(ch >= '0' && ch <= '9') //整數(shù)
			{
				while(GetChar()>0)
				{
					if(ch < '0' || ch > '9') break;
				}
				Token[TokenNumber].ch = 'i';
				Token[TokenNumber].No = O_IDENT;
			}
			else
			{
				return ! MakeErr("表達(dá)式中含有非法字符。");
			}
			break;
		}
		TokenNumber ++;
	}
}

//從表達(dá)式緩沖區(qū)中取到下面第一個(gè)非空字符
//成功：返回字符；不成功：返回'\0'
char GetFirstChar()
{
	while(GetChar() != '\0')
	{
		if(ch>32) return ch;
	}
	return '\0';
}

//從表達(dá)式緩沖區(qū)取一個(gè)字符，返回該字符的同時(shí)將它存于全局變量ch中
//成功：返回字符；不成功：返回'\0'
char GetChar() 
{
	if((ch = Buffer[ipBuffer]) != '\0')
		ipBuffer ++;
	return ch;
}

//生成錯(cuò)誤信息
//錯(cuò)誤信息存于全局變量ErrMsg中
//返回：TRUE
bool MakeErr(char * ErrMassage)
{
	ErrMsg = ErrMassage;
	return TRUE;
}