自底向上语法分析-算符优先分析器C语言实现

1） 任意输入一个文法G； 2） 判断该文法是否为算符文法； 3） 对文法中的每个非终结符自动生成并打印输出： ① FIRSTVT集； ② LASTVT集； 4）判断该文法是否为算符优先文法， 如果是自动生成并打印输出其算符优先矩阵； 5） 模拟分析过程。 如输入一个句子，如果该句子合法则输出与句子 对应的语法树；能够输出分析过程中每一步符号 栈的变化情况以及根据当前最左素短语进行归约 的过程。如果该句子非法则进行相应的报错处理。

#ifndef HEAD
#define HEAD
#include “OurHead.h“
#endif
#define STACK_SIZE		64

node_t stack[STACK_SIZE];
int top = 0;

node_t* reduce（int start int end int size） //规约，并构造相应语法结构
{
	node_t *new_vn *childs[STACK_SIZE];
	char *tar *g t1 t2 left;
	int i j =0 gi ti cn = 0;
	BOOL same;
	tar = （char *）malloc（sizeof（char）*MAX_BUFFER）;
	if（!tar）
	{
		printf（“Allocation fails.\n“）;
		exit（-1）;
	}
	for（i = start; i <= end; ++i）//将此最左素短语的终结符存入tar字符串
		if（!IS_VN（stack[i].stuff））
			tar[j++] = stack[i].stuff;
	tar[j++] = ‘\0‘;
	for（i = 0; i < gra_num; ++i）
	{
		g = grammar[i][1];
		gi = 0;
		ti = 0;
		same = FALSE;
		t1 = g[gi];
		t2 = tar[ti];
		while （t1 != ‘\0‘）
		{
			if（t2 == ‘\0‘ && !IS_VN（t1））
			{
				same = FALSE;
				break;
			}
			if（!IS_VN（t1））
			{
				if（t1 != t2）{
					same = FALSE;
					break;
				}
				t2 = tar[++ti];
				same = TRUE;
			}
			t1= g[++gi];
		}
		if（same && t2 == ‘\0‘）
			break;
	}
	if（i == gra_num）
	{
		printf（“无法找到相应文法！\n“）;
		return NULL;
	}
	left = grammar[i][0][0];
	new_vn = （node_t *）malloc（sizeof（node_t））;
	if（!new_vn）
	{
		printf（“Allocation fails.\n“）;
		exit（-1）;
	}
	new_vn->stuff = vn_list[get_vn（left）].c;
	for（i = start; i <= end; ++i）
	{
		childs[cn] = （node_t *）malloc（sizeof（node_t））;
		if（!childs[cn]）
		{
			printf（“Allocation fails.\n“）;
			exit（-1）;
	}
		*childs[cn++] = stack[i];
	}
	for（i = 0; i < cn; ++i）
	{
		childs[i]->next_sib = childs[i+1];
	}
	childs[i - 1]->next_sib = NULL;
	for（i = 0; i < cn; ++i）
		if（!IS_VN（childs[i]->stuff））
			childs[i]->fir_child = NULL;
		new_vn->fir_child = childs[0];
		new_vn->next_sib = NULL;
	return new_vn;
}

BOOL analyze（char *sentence）
{
	char r c;
	int i = 0 k = 0 j pi printi = 1 cou = 1;		//i是sentence[]和stack[]的索引
	int r_index s_index pre_index;
	node_t *new_vn;
	printf（“\n\n规约过程如下表所示：\n“）;
	printf（“--------------------------------------\n“）;
	stack[top++].stuff = ‘#‘;
	printf（“序号\t符号栈\t最左素短语\t规约\t\n“）;
	do
	{
		r = sentence[i++];
		if（（r_index = get_oper（r）） == -1）
		{
			printf（“Error : 您输入的字符不在文法定义中！\n“）;
			flushall（）;c = getchar（）;flushall（）;
			return FALSE;
		}
		if（!IS_VN（stack[k].stuff））
		{
			j = k;
			s_index = get_oper（stack[j].stuff）;
		}
		else
		{
			j = k - 1;
			s_index = get_oper（stack[j].stuff）;
		}
		while（prior_table[s_index][r_index] == HIGHER）
		{
			do
			{
				pre_index = s_index;
				if（!IS_VN（stack[j-1].stuff））
				{
					j--;
					s_index = get_oper（stack[j].stuff）;
				}
				else
				{
					j -= 2;
					s_index = get_oper（stack[j].stuff）;
				}
			}while（prior_table[s_index][pre_index] != LOWER）;
			printf（“  %d\t“ cou++）;
			for（pi = 0; pi < top; ++pi）
			{
				printf（“%c“stack[pi].stuff）;
			}
			printf（“ \t“）;
			for（pi = j + 1; pi <= k; ++pi）
			{
				if （pi == j+1）
					printf（“   %c“stack[pi].stuff）;
				else
					printf（“%c“stack[pi].stuff）;
			}
			if（（new_vn = reduce（

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3718  2011-06-09 00:04  算符优先分析器\analyze.c

     文件       2200  2011-06-08 23:57  算符优先分析器\buff_deal.c

     文件       2352  2011-05-27 09:00  算符优先分析器\create_table.c

     文件      10217  2011-06-09 00:04  算符优先分析器\Debug\analyze.obj

     文件       5956  2011-06-08 23:59  算符优先分析器\Debug\buff_deal.obj

     文件       4965  2011-05-31 09:35  算符优先分析器\Debug\create_table.obj

     文件       4319  2011-06-09 00:04  算符优先分析器\Debug\display_fir_lastvt.obj

     文件       4200  2011-06-09 00:04  算符优先分析器\Debug\display_table.obj

     文件       3486  2011-05-31 09:35  算符优先分析器\Debug\display_tree.obj

     文件       5752  2011-06-09 00:01  算符优先分析器\Debug\get_FIRVT_LASTVT.obj

     文件       2828  2011-05-31 09:35  算符优先分析器\Debug\get_input.obj

     文件       2128  2011-05-31 09:35  算符优先分析器\Debug\init_table.obj

     文件       1350  2011-06-09 19:51  算符优先分析器\Debug\init_tree.obj

     文件      15809  2011-06-09 19:47  算符优先分析器\Debug\main.obj

     文件      66560  2011-06-09 19:51  算符优先分析器\Debug\vc60.idb

     文件      53248  2011-06-09 19:51  算符优先分析器\Debug\vc60.pdb

     文件     200784  2011-06-09 19:51  算符优先分析器\Debug\算符优先分析器.exe

     文件     217080  2011-06-09 19:51  算符优先分析器\Debug\算符优先分析器.ilk

     文件     157340  2011-06-09 19:51  算符优先分析器\Debug\算符优先分析器.pch

     文件     533504  2011-06-09 19:51  算符优先分析器\Debug\算符优先分析器.pdb

     文件       1125  2011-06-09 00:04  算符优先分析器\display_fir_lastvt.c

     文件       1081  2011-06-09 00:04  算符优先分析器\display_table.c

     文件        345  2011-05-31 09:34  算符优先分析器\display_tree.c

     文件       1919  2011-05-27 13:08  算符优先分析器\get_FIRVT_LASTVT.c

     文件        440  2011-05-25 00:08  算符优先分析器\get_input.c

     文件        206  2011-05-22 23:52  算符优先分析器\init_table.c

     文件          0  2011-06-09 19:50  算符优先分析器\init_tree.c

     文件       4431  2011-06-09 19:47  算符优先分析器\main.c

     文件       3427  2011-05-31 09:23  算符优先分析器\OurHead.h

     文件       5095  2011-05-22 23:52  算符优先分析器\算符优先分析器.dsp

............此处省略10个文件信息