/*
*功能：LR（0）分析方法
*作者：王文堃
*創建時間：2016/6/14
*/

/*
----------------任務分解--------------------
任務一：確定文法G的LR0項目，對文法加‘.‘
任務二：構造NFA
任務三：構造DFA
任務四：構造LR（0）分析表
任務五：規約
*/

#include?
#include?
#include?
using?namespace?std;
#pragma?warning（disable::4996）
#define?LR_MAXSIZE?20
#define?MAXSIZE?10
#define?NUM?20
#define?NUM_VN?4
#define?NUM_VT?5

/*---------------------------------數據結構----------------------------------*/
//NFA結點數據結構
typedef?struct?wenfanode
{
	int?num;?//文法的NFA編號
	char?data[MAXSIZE];?//文法內容
	bool?state;?//判斷文法是否已經被加入DFA
};

//棧操作
typedef?struct?Stack
{
	int?data[MAXSIZE];
	int?top;
};

/*---------------------------------全局變量----------------------------------*/
//文法加點
enum?{?S?E?A?B?};
char?WenFa[MAXSIZE][MAXSIZE];?//存放從文件中讀取的文法
int?g_num_wenfa?=?0;?//存放文法的個數，初值為0
wenfanode*?LRWenFa[LR_MAXSIZE];?//將加點后的文法存放于此
int?g_wenfa_dot?=?1;?//記錄加點后文法的下標
char?str_after[MAXSIZE];?//保存加點過后的文法
						?//NFA
char?NFA[NUM][NUM];?//構造的NFA表
char?VN[NUM_VN]?=?{?‘S‘‘E‘‘A‘‘B‘?};
char?VT[NUM_VT]?=?{?‘a‘?‘b‘?‘c‘?‘d‘?‘#‘?};
//DFA
static?unsigned?int?g_DFA_num?=?0;?//用來表示DFA的結點下標
char?DFA[NUM][NUM];?//構造的DFA表
wenfanode*?DFA_node[LR_MAXSIZE][MAXSIZE];?//用來存放DFA結點中的NFA結點
										??//LR表
string?ACTION[LR_MAXSIZE][NUM_VT];
int?GOTO[LR_MAXSIZE][NUM_VN];
//分析
int?g_num?=?0;?//用來記錄步驟
int?g_input?=?0;?//用來檢索輸入串
Stack?*State_Stack;?//狀態棧
Stack?*Symbol_Stack;?//符號棧
char?inputstring[10];?//輸入串


					??/*---------------------------------函數聲明----------------------------------*/
					??//文法加點
bool?readfromfile（char*?str）;?//讀取文法
void?AddChar2Str（const?char?str[]?char?str_after[]?int?i?int?k）;?//在字符串的某位置加一個字符‘.‘
void?AddDot（）;?//給文法加點???
void?Print_Dot（）;?//輸出加點的結果
				??//NFA
void?init_NFA（）;?//初始化NFA
int?find_pos_point（char*?str）;??//找到點的位置????????????????
bool?isVN（char?ch）;?//判斷一個字符是不是非終結符
bool?isVT（char?ch）;?//判斷一個字符是不是終結符??????????????????
int?find_node（char?ch?int?a[]）;?//查找以ch開頭，右部首為點的文法，將文法的編號存入數組a中，返回個數????????????????????????????
void?make_NFA（）;?//構造NFA，使用鄰接矩陣存儲????????????????
void?print_NFA（）;?//輸出NFA
				??//DFA
void?init_DFA（）;?//初始化DFA
void?add_state（int?to?int?from）;?//經from連接的結點添加到to可以連接的節點中去??????????
void?make_DFA（）;?//構造DFA
void?print_DFA（）;?//輸出DFA
				??//LR分析表
void?count_DFA_State（）;?//計算DFA結點的個數
void?init_LR_Table（）;?//初始化LR分析表??
int?VN2int（char?ch）;?//非終結符轉為對應表格下標??????
int?VT2int（char?ch）;?//終結符轉為對應表格下標
char*?need_protocol（int?point）;?//判斷結點中的點有沒有規約項
int?find_wenfa（char*?str）;?//根據文法內容找到文法編號
void?fill_LRtable（）;?//填充LR分析表
void?print_LR_Table（）;?//輸出LR分析表
					???//規約
void?init_Stack（Stack?**s）;?//初始化棧
bool?empty_Stack（Stack?*s）;?//判斷棧空
void?Push（Stack?*s?char?x）;?//入棧????
char?Pop（Stack?*s）;?//出棧
char?Top（Stack?*s）;?//取棧頂元素
void?print_Stack_ch（Stack?*s）;?//輸出符號棧
void?print_Stack_int（Stack?*s）;?//輸出狀態棧
bool?inputformfile（char*?str）;?//從文件中讀取輸入??????
bool?is_End（）;?//判斷規約是否完成?
int?count_right_num（string?str）;?//

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????7410??2017-10-28?14:45??LR（0）語法分析\LR（0）語法分析.vcxproj

?????文件????????946??2017-10-28?14:39??LR（0）語法分析\LR（0）語法分析.vcxproj.filters

?????文件???????1307??2017-10-30?16:07??LR（0）語法分析\Debug\LR（0）語法分析.log

?????文件????????213??2017-10-30?16:07??LR（0）語法分析\Debug\LR（0）語法分析.tlog\LR（0）語法分析.lastbuildstate

?????文件??????15866??2017-10-30?16:06??LR（0）語法分析\Debug\LR（0）語法分析.tlog\CL.read.1.tlog

?????文件????????456??2017-10-30?16:06??LR（0）語法分析\Debug\LR（0）語法分析.tlog\CL.write.1.tlog

?????文件????????700??2017-10-30?16:06??LR（0）語法分析\Debug\LR（0）語法分析.tlog\CL.command.1.tlog

?????文件???????2858??2017-10-30?16:07??LR（0）語法分析\Debug\LR（0）語法分析.tlog\link.read.1.tlog

?????文件????????432??2017-10-30?16:07??LR（0）語法分析\Debug\LR（0）語法分析.tlog\link.write.1.tlog

?????文件???????1130??2017-10-30?16:07??LR（0）語法分析\Debug\LR（0）語法分析.tlog\link.command.1.tlog

?????文件???????1148??2017-10-30?15:23??LR（0）語法分析\Debug\LR（0）語法分析.Build.CppClean.log

?????文件?????347136??2017-10-30?16:06??LR（0）語法分析\Debug\vc140.idb

?????文件?????413696??2017-10-30?16:06??LR（0）語法分析\Debug\vc140.pdb

?????文件?????230594??2017-10-30?16:06??LR（0）語法分析\Debug\LR（0）.obj

?????文件?????????44??2017-10-28?14:40??LR（0）語法分析\wenfa.txt

?????文件??????????6??2017-10-29?11:08??LR（0）語法分析\input.txt

?????文件??????17098??2017-10-30?15:35??LR（0）語法分析\LR（0）.cpp

?????目錄??????????0??2017-10-28?14:39??LR（0）語法分析\Debug\LR（0）語法分析.tlog

?????目錄??????????0??2017-10-28?14:39??LR（0）語法分析\Debug

?????目錄??????????0??2017-10-28?14:37??LR（0）語法分析

-----------?---------??----------?-----??----

??????????????1041040????????????????????20