构造LR(1)项集族

　　在龙书的P167中为我们提供了为某一个文法G’构造LR(1)项集族的完整算法，照搬如下：

SetOfItems CLOSURE(I) {
	repeat
		for(I中的每个项[A->α·Bβ,a])
			for(G'中的每个产生式B->γ)
				for(FIRST(βa)每个终结符号b)
					将[B->·γ,b]加入到集合I中;
	until 不能向I中加入更多的项;
	return I;
}

SetOfItems GOTO(I,X) {
	将J初始化为空集;
	for(I中的每个项[A->α·Xβ,a])
		将项[A->αX·β,a]加入到集合J中;
	return CLOSURE(J);
}

void items(G') {
	将C初始化为{CLOSURE}({[S'->·S,$]});
	repeat
		for(C中的每个项集I)
			for(每个文法符号X)
				if(GOTO(I,X)非空且不在C中)
					将GOTO(I,X)加入C中;
	until 不再有新的项集加入到C中;
}

　　上述的代码只是从理论角度提供的可行的算法，而具体怎么写还要根据我们的实现来进行修改。上边的item便是计算LR(1)项集族的主要函数，它会分别调用CLOSURE函数计算一个内核项所产生的项集，之后调用GOTO函数计算一个项集在遇到一个终结符或者非终结符时所产生的内核项。(内核项的概念十分重要，内核项是指包括初始项S'->·S以及点不在最左端的所有项，一个项集其实只用内核项表示就足够了，两个项集如果内核项一样，那这两个项集一定是相同的。)

计算FIRST(βa)

　　注意到函数CLOSURE在使用时调用了一个并未在算法中出现的函数FIRST，函数FIRST(α)被定义为可从α推导得到的串的首符号的集合，其中α是任意的文法符号串。虽然龙书中没有给出伪代码的算法，但是计算的规则已经表达得很清楚了:

如果X是一个终结符号，那么FIRST(X)=X。
如果X是一个非终结符号，且X->Y₁Y₂···Y_k是一个产生式，其中k≥1，那么如果对于某个i，a在FIRST(Y_i)中且ε在所有的FIRST(Y₁)、FIRST(Y₂)、···、FIRST(Y_i-1)中，就把a加入到FIRST(X)=X中。
如果X->ε是一个产生式，那么将ε加入到FIRST(X)中。

　　那么我们现在就按照上述的方式给出一个FIRST(α)的具体实现：

typedef struct _used
{
	int use[100];
	int num;
}used;


void count_first(element *e, element **first_elements, used *is_used)
{
	item *temp;
	if (!e)
		return;
	for (int i = 0; i < is_used->num; i++)
	{
		if (e->is_terminator&&e->type.t_index == is_used->use[i])
			return;
		else if (!e->is_terminator&&e->type.pro->p_index == is_used->use[i])
			return;
	}

	if (e->is_terminator)
	{
		is_used->use[is_used->num++] = e->type.t_index;
		add_e2e(e, first_elements);
	} else
	{
		is_used->use[is_used->num++] = e->type.pro->p_index;
		temp = e->type.pro->items;
		for (; temp; temp = temp->next)
		{
			if (temp->ele->is_terminator&&temp->ele->type.t_index == EMPTY)
				count_first(e->next, first_elements, is_used);
			else
				count_first(temp->ele, first_elements, is_used);
		}
	}
}

　　因为在构造LR(1)项集族的算法中，使用到的FIRST函数最多只有两个文法符号，因此我们的实现也就默认为最多两个文法符号，即参数element *e最多为两项。参数first_elements作为计算出的结果的存储链表，同时在这个函数中我们用到了一个is_used的结构体，它的目的是用来记录已经计算过的所有的文法符号，当我们重复计算某一文法符号时，函数会直接返回，这样一来便解决了所有的直接递归或者间接递归的情况。实际上在我的程序中并不会直接使用上边的函数进行计算，上边的实现只是作为计算FIRST集的一个核心函数，因此会有更顶层的函数对其进行调用，我们在实际使用的时候只会传入相应文法符号的序号，而返回的FIRST集也是以文法符号的序号进行表示的。
　　得益于我们在递归下降分析文法的时候建立了文法符号之间完整的关系图，因此在计算first集的时候使用递归的方式就是简单且可行的。

计算一个项集的闭包

　　下面我们来实现算法中的CLOSURE(I)函数，在实现之前我们来看一下产生式的另一个新的抽象描述形式，以及我们对单个项集的抽象：

typedef struct _n_pro
{
	int head;	//产生式头
	int *body;	//产生式体，使用一个数组存储，每个符号均用序号替换
	int body_len;	//产生式体的长度
	int look_ahead;	//向前看符号
	int dot_pos;	//产生式体中点的位置，如果是0表示点在最前边
	struct _n_pro *next;	//以链表形式存储的下一个产生式
}n_pro;
//new production

/*
	The struct that represent the set of items
*/
struct _set
{

	n_pro *pro_list;

	/*
	A table that records the transfer path when the set read a grammar symbol
	In this table,0 means matching error and 1 means match successfully.
	*/
	int *transfer_table;

	//The total number of kernel productions.
	int kernel_num;
};

　　我之所以引入新的抽象形式，是因为旧的形式在计算LR(1)项集族时十分不方便，而在计算LR(1)项集族时，仅需要文法的一些关键信息即可，因此使用了一个新的抽象形式。我们在之后的所以计算中均使用这一新的形式。下面我们来看看计算闭包的实现：

set* closure(set *se)
{
	n_pro *first_p = se->pro_list;
	n_pro *last_p = se->pro_list;
	n_pro *temp = NULL;

	int type, first_arr_len;
	int *first_arr = (int*)malloc(2 * transfer_index*sizeof(int));
	void *pvoid = NULL;
	item *t = NULL;
	for (; last_p->next; last_p = last_p->next);
	for (; first_p; first_p = first_p->next)
	{
		if (first_p->body_len == first_p->dot_pos)
			continue;
		pvoid = find_by_index(first_p->body[first_p->dot_pos], &type);
		if (type == TOKEN)
			continue;
		first_arr_len = first(first_p->body[first_p->dot_pos + 1], first_p->look_ahead, first_arr);
		for (t = ((production*)pvoid)->items; t; t = t->next)
		{
			for (int i = 0; i < first_arr_len; i++)
			{
				temp = (n_pro*)malloc(sizeof(n_pro));
				temp->head = first_p->body[first_p->dot_pos];
				temp->body = (int*)malloc(BODY_LENGTH*sizeof(int));
				memcpy(temp->body, t->body, BODY_LENGTH*sizeof(int));
				temp->body_len = t->body_len;
				temp->dot_pos = 0;
				temp->look_ahead = first_arr[i];
				temp->next = NULL;
				if (pro_is_contain(se->pro_list, temp))
				{
					free(temp->body);
					free(temp);
				} else
				{
					last_p->next = temp;
					last_p = last_p->next;
				}

			}
		}
	}
	free(first_arr);
	return se;
}

　　需要注意这个函数的传入的参数以及返回值的类型均是set的指针类型，笼统地说，全是关于一个项集的，这与龙书中的算法描述是一致的，函数中调用的find_by_index函数是通过一个文法符号的序号在token_list或者pro_list中进行查找，并返回指针。去掉算法中只有一句的那个for循环，算法中的三重循环中的每一层均与龙书中描述的相对应。最里层的循环便是使用新的抽象形式描述每一个产生式，同时如果构造出的这个产生式已经存在于这个项集中，那便调用free将其释放掉，最终我们得到了一个完整的项集，包含所有生成出的产生式。

GOTO函数的实现

　　GOTO函数计算当一个项集遇到某一个文法符号时，它会转移到哪个项集中，注意这个计算出来的新的项集只包含核心项。

/*
	The set that the program will go in when read a grammar symbol.
	More specifically, function _goto will figure out the kernel productions when read a symbol.
*/
set* _goto(set *s, int symbol_index)
{
	n_pro* temp = s->pro_list;
	n_pro *first = NULL, *last = NULL;
	set* se = NULL;
	int kernel_num = 0;
	for (; temp; temp = temp->next)
	{
		if (temp->body[temp->dot_pos] == symbol_index&&temp->dot_pos != temp->body_len)
		{
			if (!first)
			{
				first = (n_pro*)malloc(sizeof(n_pro));
				last = first;
				memcpy(first, temp, sizeof(n_pro));
				first->dot_pos++;
				first->next = NULL;

				kernel_num++;
			} else
			{
				last->next = (n_pro*)malloc(sizeof(n_pro));
				memcpy(last->next, temp, sizeof(n_pro));
				last->next->dot_pos++;
				last->next->next = NULL;
				last = last->next;

				kernel_num++;
			}
		}
	}
	if (kernel_num)
	{
		se = (set*)malloc(sizeof(set));
		se->kernel_num = kernel_num;
		se->pro_list = first;
		se->transfer_table = (int*)calloc(transfer_index, sizeof(int));

		temp = first;
		for (int i = 0; i < kernel_num; i++, temp = temp->next)
		{
			if (temp->body_len == temp->dot_pos&&temp->head != token_num)
				se->transfer_table[temp->look_ahead] = -(i + 1);
		}
	}
	return se;
}

　　注意到代码中的这一段：

if (kernel_num)
	{
		se = (set*)malloc(sizeof(set));
		se->kernel_num = kernel_num;
		se->pro_list = first;
		se->transfer_table = (int*)calloc(transfer_index, sizeof(int));

		temp = first;
		for (int i = 0; i < kernel_num; i++, temp = temp->next)
		{
			if (temp->body_len == temp->dot_pos&&temp->head != token_num)
				se->transfer_table[temp->look_ahead] = -(i + 1);
		}
	}

　　这一段的含义为：只有当计算出的核心项的数目不为0时，才会将这个项集构造出来，而下方的for循环是在计算该项集在遇到不同的文法符号时是否有规约的时候，如果满足规约的条件，那这个项集的transfer_table的相应的文法序号的那一个元素会被设置成为规约时所使用的产生式的序号，而加上一个1，并且取负的原因是避免和以下规则冲突：

transfer_table中1表示匹配成功；
transfer_table中大于0的项表示需要转移到的项集的序号；
transfer_table中小于0的项表示规约；
transfer_table中等于0的项表示错误；

SETS函数实现

　　这里的sets函数即为items函数，该函数通过调用closure和goto函数将项集族计算出来，而在程序中会有一个数组的全局变量sets_arr[ ]用以存储计算出来的项集。

void sets()
{
	int goto_index;
	set* closure_s = NULL;
	set* goto_s = NULL;
	/*
		Add [S'-->·S,$] into the sets_arr.
	*/
	set* begin = (set*)malloc(sizeof(set));
	begin->kernel_num = 1;
	begin->transfer_table = (int*)calloc(transfer_index, sizeof(int));
	begin->pro_list = (n_pro*)malloc(sizeof(n_pro));
	begin->pro_list->body = (int*)calloc(BODY_LENGTH, sizeof(int));
	begin->pro_list->body[0] = token_num + 1;
	begin->pro_list->body_len = 1;
	begin->pro_list->dot_pos = 0;
	begin->pro_list->head = token_num;
	begin->pro_list->look_ahead = STRING_END;
	begin->pro_list->next = NULL;
	add_set(begin);

	for (int i = 0; i < sets_num; i++)
	{
		closure_s = closure(sets_arr[i]);
		for (int j = 0; j < transfer_index; j++)
		{
			goto_s = _goto(closure_s, j);
			if (!goto_s)
				continue;
			goto_index = add_set(goto_s);
			if (i == 0 && j == token_num + 1)
				ending_set = goto_index;
			if (sets_arr[i]->transfer_table[j])
				exception("This grammar is not LR(1).", NULL);
			sets_arr[i]->transfer_table[j] = goto_index + 2;
			/*
				Because in the transfer table, 0 means error and 1 means match successfully.
			*/
		}
	}
	sets_arr[ending_set]->transfer_table[STRING_END] = 1;
}

　　该函数首先将[S’–>·S,$]放入到sets_arr中，函数add_set便是放入时需要调用的函数，它会判断传入的这个项集是否已经存在，如果存在就直接返回该项集所在的序号，如果不存在则将其加入到sets_arr中，并返回序号。该函数中需要注意的有这一句if (i == 0 && j == token_num + 1)，这里的token_num既表示终结符的数量，同时也是文法符号S'的序号，这一句是为了找到文法即将匹配成功的那个状态，当我们在这个状态中再读入一个STRING_END那就算解析成功了。因此代码sets_arr[ending_set]->transfer_table[STRING_END] = 1;便是在设置成功的状态。

语法检查器的运行

　　我们的程序运行至此，已经接近成功了，现在的sets_arr中，装的是各个状态，每一个元素的transfer_table记录了在读入不同的文法符号时的相应操作，接下来的操作便极为简单，这时需要一个词法分析器，将读取到的词素返回给我们的程序，我们的程序根据得到的词素的类型，对照现在所处的状态的转换表，进行相应的操作即可。在这里，语法检查器运行的代码就不贴了，实现起来比较简单。

结语

　　一个程序的实现和它的理论是完全不同的两种东西，理论往往是直观的，去掉了细枝末节的最基本的东西，而实现则是将这些细节全部都添加上的有血有肉的能运行的东西，他往往包含了许多关键性的trick以及想法。在动手实现之前，找到一个合适的数据结构对需要的东西进行描述是十分重要的，它往往决定了你的程序成功与否，因此这的确是一件想得多，写得少的工作。