//0806580227?劉馳
//給定文法產生式構造LR（1）項目集和DFA并對輸入的句子進行語法分析
//產生式存放在d:\syntax.txt
//句子存放在d:\test.txt
//項目集存放在d:\items_set
//DFA存放在d:\dfa.txt

#include“iostream“
#include“fstream“
#include“stack“
#include“utility“
using?namespace?std;

char?G[20][20];?????//存放文法，不超過20條產生式，每條產生式長度不超過20，用@表示空，以$結束
int??length[20];????//每條產生式的長度
int??number?=?0;	//產生式條數
bool?tempofinput[150];??//記錄文法中有哪些Vt和Vn，用ASCII碼對應位標記true表示
char?str_vn[20];????????//存放所有Vn
int??size_vn?=?0;		//Vn個數
char?str_vt[150];???????//存放所有Vt
int??size_vt?=?0;		//Vt個數
bool?first_vn[30][150];	//記錄每個非終結符的FIRST集，用位示圖法
char?buffer[50];????????//用來存放生成CLOSURE（I）時需要的FIRST集也用來讀入用戶的輸入串^_^
int??bsize?=?0;

struct?thri{
????int?beg;	//起始狀態號
????int?nex;	//下一狀態號
????char?ch;	//接收的字符
}trans[200];	//用來在go（）函數中記錄狀態間轉換
int??size_trans?=?0;
?
//定義項目集的形式
struct?proj{
????int?formula_numb;	//產生式序號
????int?part;			//產生式中.的位置
????char?expc;			//希望接受的字符
}items[100][100];
int?????Ccount?=?0;		//項目集個數
int?????size_item[100];	//每個項目集中產生式的條數
?
//狀態轉換表
struct?action{
????char????ch;			//接受字符
????int?????nxt_sta;	//下一狀態號
}action_table[100][100];//不超過100個狀態集；從每個狀態出發的狀態轉換不超過100條
int?size_act_table[100];//每個項目集狀態轉換邊數
?
ifstream??G_ifile;		//文法輸入文件流
ifstream??input_ifile;	//表達式輸入文件流
ofstream??items_ofile;	//項目集輸出文件流
ofstream??act_ofile;	//狀態轉換表輸出文件流
?
//讀取產生式
void?Read_G（）
{
????G_ifile?>>?number;???//讀取產生式條數
????for（int?i?=?1;?i?<=?number;?i++）{
????????char?temp;
????????int?j?=?0;
????????G_ifile?>>?temp;
????????while（temp?!=?‘$‘）{				//循環讀到每條產生式末尾$
????????????tempofinput[temp]?=?true;	//tempofinput[150]中讀入字符ASCII碼對應值的位置記為true
????????????G[i][j++]?=?temp;
????????????G_ifile?>>?temp;
????????}
????????length[i]?=?j;	//length[i]記錄每條產生式長度
????}
???
????G[0][0]?=?‘S‘;
????G[0][1]?=?G[1][0];
????length[0]?=?2;		//G[0]定義拓展文法S->E
???
????for（int?i?=?0;?i?????????if（tempofinput[i]）
???????????str_vt[size_vt++]?=?i;	//標記Vt
????for（int?i?=?91;?i?????????if（tempofinput[i]）
???????????str_vt[size_vt++]?=?i;	//標記Vt
????for（int?i?=?65;?i?????????if（tempofinput[i]）
???????????str_vn[size_vn++]?=?i;	//標記Vn
}


//計算每一個Vn的FIRST：
//先設置?flag1表示本輪掃描?first_vn?中有沒有新增加的內容。要是有，還要進行下一次掃描。
//每一輪掃描所有的產生式，在掃描每一個產生式的時候，設置一個下標指針?t?用來保證不會掃過本產生式.
//還設置?flag2?表示?t?的位置是否是一個可以推導出ε的非終結符。是的話，還要進行下一個?t?位置的檢查。
//如果?t走到產生式的最后位置的下一個位置，則表明ε屬于此產生式左邊非終結符的FIRST?集合
void?get_first（）{
????bool?flag1;
????do{
????????flag1?=?false;
????????for（int?i?=?1;?i?<=?number;?i++）{
???????????int?t?=?1;	//每條產生式中的指針
???????????bool?flag2;
???????????do{
???????????????flag2?=?false;
???????????????if?（G[i][t]?>=?‘A‘?&&?G[i][t]?<=?‘Z‘）{			//t當前位置是一個非終結符
??????????????????????for（int?k?=?0;?k?						??if（first_vn[G[i][t]-‘A‘][k]==true&&?!first_vn[G[i][0]-‘A‘][k]）{
								?first_vn[G[i][0]-‘A‘][k]?=?true;
								?flag1?=?true;
							??}
??????????????????????for（int?k?=?91;?k?						??if（first_vn[G[i][t]-‘A‘][k]==true&&?!