LR实现语法分析

（1）构造LR 分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子； （2）了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

/*
*功能：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