编译原理——基于LR(1)的语法检查器(一)

发表于   |  

前言

　　该项目是我在学习编译原理的时候所完成的一个项目，不同于成熟的yacc语法分析器，我的语法检查器通过和一个词法分析器相互配合，启动之前读入由BNF范式和正则表达式所描述的文法与词法，之后根据给定的文法对给出的代码文件进行检查，并指出文件中的错误。整个文法的解析以LR(1)为基础，总共的代码量为800左右（不包括词法分析器），完整的代码请移步Configurable-syntactic-analyzer。

正文

理论介绍

　　一般说来，常用的语法分析技术有两种，一种是自顶向下的，另一种是自底向上的，对于LL(1)型的文法来说，我们一般使用自顶向下的分析方式例如递归下降或者构造预测分析器的方式进行文法的解析，而其中递归下降分析法经常在手写的语法分析器中用到，这种方式对于大部分比较简单的文法是十分实用的，递归下降写起来也十分的方便。虽然LL(1)的文法足以描述大部分程序设计的构造，但是却无法描述左递归的文法以及二义性的文法，而在程序设计中，左递归的文法是经常出现的，例如S->Sab这样的产生式便是左递归的，因此递归下降的方式在此时并不适用，因此我们需要将左递归的文法经过某些变换，使它变为非递归的文法，但这种变换常常使得文法面目全非，而且实现起来也比较困难，因此我们提出了基于LR(k)的语法分析的概念。
　　LR语法分析技术是通过自底向上的方式进行语法分析的，而我们引入这种方法的原因有以下几点(摘自龙书):

  • 对于几乎所有的程序设计语言，只要能够写出该构造的上下文无关文法，就能够构造出识别该构造的LR语法分析器。
  • LR语法分析方法是已知的最通用的无回溯的移入-规约分析技术。
  • 一个LR语法分析器可以在对输入进行从左到右扫描时尽可能早的检测到错误。
  • 可以使用LR方法进行语法分析的文法类是可以使用预测方法或LL方法进行语法分析的文法类的真超集。

　　由此可见，LR语法分析技术的能力是十分强大的，LR语法分析技术一般来说有三种，一种是SLR(简单LR技术)，LR(规范LR技术)，LALR(向前看LR技术)。相较之下，规范LR技术的分析能力最强，但是占用的系统资源也最多，鉴于规范LR的典型性，因此我的语法检查器使用的规范LR技术。无论哪一种LR技术，在使用时都要经过如下的几个步骤：

  1. 根据给定的文法构造出该文法的规范LR(k)项集族。
  2. 根据规范LR(k)项集族构造出语法分析表。
  3. 在运行时根据语法分析表进行相应的移入，规约操作。

　　而本文则会针对以上三个步骤提供一个具体可行的实现方案，从而构造出一个简单的语法检查器。

配置文件

　　对于描述文法的配置文件，我以龙书上的文法描述方式为基础，在实际使用的时候做了一些修改，方便我对文法进行解析，首先文法中出现的所有终结符必须在文法之前注明，并且在这些终结符之前写上统一的标识”%token”并在结尾写上分号，所有的产生式需要用’ { ‘以及’ } ‘包裹起来。对于文法来说，文法应该写成增广文法的形式，即第一个产生式写成S'->S的形式，其次产生式的箭头”->”被修改为冒号’ : ‘，符号和或连接符’ | ‘之间无空格，最后在产生式的结尾处应加上分号’ ; ‘。因此，如下的文法格式：

1
2
3
S->L = R | R
L->* R | id
R->L

会被改写为

1
2
3
4
5
6
7
%token = * id;
{
S':S;
S:L = R|R;
L:* R|id;
R:L;
}

　　%token标识符后边的所有符号均应该在词法分析器的配置文件中使用正则表达式进行描述，例如上述的文法在配置文件中就应该被描述为：

1
2
3
id:[_0-9a-zA-Z]+
*:\*
=:=

　　由于我的词法分析器具有优先匹配的功能，因此需要优先匹配的需要写在前边。关于词法分析器的相关理论以及具体实现详见正则引擎入门以及Configurable-lexical-analyzer。

配置文件的解析

　　虽然规范LR技术是本文章的重点，但是在解析配置文件的时候我依旧采用了递归下降的分析方法，这种方法写起来比较方便，也便于理解。我们解析配置文件的目的是要将文法读取进内存，使用某种数据结构将文法中各个符号之间的关系展现出来，便于我们下一步的分析，下面展示的三个结构体可以用来表示一个文法的各个结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct _production			//代表一个产生式
{
	char head[20];			//用于记录产生式的头
	int p_index;   			//记录产生式的序号
	struct _item *items;		//通过'|'进行分隔的产生式的不同产生体，以链表形式记录。
	struct _production *next;	//下一个产生式
};

struct _item
{
	struct _element *ele;	//以链表形式记录的产生式体中的不同符号
	struct _item *next;	//下一个产生式的体
	int *body;			//以序号形式记录的产生式的体
	int body_len;			//产生式体的长度
};

struct _element
{
	union
	{
		int t_index;			//终结符的序号
		struct _production *pro;//产生式
	}type;
	boolean is_terminator;	//是否为终结符
	char terminator_name[20];//终结符的字符串
	struct _element *next;	//下一个符号
};

typedef struct _element element;
typedef struct _item item;
typedef struct _production production;

　　在看主要的处理函数之前，我们先来看一下一些简单的辅助函数以及全局变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	//Recording the productions that are created.
production *pro_list = NULL;
	//Recording the elements that are created.
element *token_list = NULL;
	//The num of tokens and also the index of S'
int token_num = 0;
int transfer_index = 0;
char current_str[64];

int file_ptr = 0;
char *file_buff = NULL;

int advance();
void blank_skip();
void file_load(char *buff, FILE *fp);
void add_t(element *e);
void add_p(production *p);
int is_contain(char *key);
void* find_by_key(char *key);
int match(char *s);

　　pro_list记录了所有构造出来的产生式或者说所有的非终结符，token_list记录了所有的终结符，token_num记录终结符的数量，transfer_index记录终结符和非终结符的数量，current_str记录了扫描到的字符串，file_buff作为文件缓冲区，file_ptr记录当前读取的字符的数组下标。file_load函数将整个配置文件一次性地读入file_buff中，方便我们接下来的分析，blank_skip函数跳过数组当中所有的无意义的字符，例如空格，制表符等等，直到遇到一个有意义的字符。函数advance读入合法的标志符的字符，并将其放入数组current_str中，直到遇到一个非法字符。函数add_t(add_p)element和(production)加入到token_list(pro_list)中，is_contain查询token_list和pro_list这两个链表中是否有与字符串key相同名字的符号，find_by_key将返回具有相应字符串名字的符号的指针。match函数查看file_ptr所指向的或者接下来的几个字符是否与s相匹配。
　　了解了所有的辅助性的要素之后我们来看一下主要的分析函数，首先是一个顶层的驱动函数，没什么可说的就是载入文件之后按情况进行解析，逻辑比较简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
	Load all the grammar info into a buff,then create the
	structs group to describe the grammar.
*/
void grammar_load(FILE *fp)
{
	file_buff = (char*)calloc(FILE_LOAD_MAX, sizeof(char));
	file_load(file_buff, fp);
	blank_skip();
	if (match("%token"))
		token_analyze();
	blank_skip();
	if (match("{"))
		pro_analyze();
	else
		exception("Illegal grammar form error", "grammar_load");
}

　　接下来我们看一下处理终结符的函数，因为所有的终结符均需要在文件开始处声明一下。因此需要一个独立的函数对这些终结符进行处理。同时在文法中有两个比较特殊的终结符号，一个是空串的符号ε，它用在产生式体中，表示该产生式可能产生空字符串，在我们的程序中，我们使用EMPTY来表示它。另一个符号是字符串结束符号\$，它并不会显式地出现在文法中，只会出现在输入串的结尾处，它表示输入已经到达了终点，没有更多的输入了，在程序中我们使用STRING_END表示。ε和\$的序号分别被定义为0和1，因此在处理其他的终结符之前要先将两者加入到记录终结符的链表中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void token_analyze()
{
	blank_skip();
	element *e = NULL;
	/*
		Add STRING_END and EMPTY token first
	*/
	e = (element*)calloc(1, sizeof(element));
	e->is_terminator = TRUE;
	e->type.t_index = transfer_index;
	strcpy(e->terminator_name, "EMPTY");
	add_t(e);

	e = (element*)calloc(1, sizeof(element));
	e->is_terminator = TRUE;
	e->type.t_index = transfer_index;
	strcpy(e->terminator_name, "STRING_END");
	add_t(e);

	while (advance())
	{
		e = (element*)calloc(1, sizeof(element));
		e->is_terminator = TRUE;
		//temp->next = NULL;
		e->type.t_index = transfer_index;
		strcpy(e->terminator_name, current_str);
		add_t(e);
		blank_skip();
	}
	if (!match(";"))
		exception("Illegal grammar form error", "token_analyze");
}

　　接下来是处理产生式的函数，它会检查现在读取到的产生式的头是否已经出现过并记录在了链表中，如果没有就初始化一个，之后再调用产生式体的处理函数，反之则把已经初始化的取出，再调用处理函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void pro_analyze()
{
	int contain;
	production *p = (production*)calloc(1, sizeof(production));
	production *temp_p = NULL;
	blank_skip();
	while (advance())
	{
		contain = is_contain(current_str);
		if (!contain)
		{
			strcpy(p->head, current_str);
			p->p_index = transfer_index;
			if (!match(":"))
				exception("Illegal grammar form error", "pro_analyze");
			add_p(p);
			p->items = items_analyze();
			p = (production*)calloc(1, sizeof(production));
		} else
		{
			temp_p = (production*)find_by_key(current_str);
			if (!match(":"))
				exception("Illegal grammar form error", "pro_analyze");

			temp_p->items = items_analyze();
		}
		blank_skip();
	}
	match("}");
}

　　接下来是产生式体的处理函数，它初始化一个item，将具体的符号处理交给elements_analyze，只是简单地记录一下item->body的信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
item* items_analyze()
{
	item* first_item = (item*)calloc(1, sizeof(item));
	item* temp = first_item;
	while (TRUE)
	{
		temp->ele = elements_analyze();
		temp->body = (int*)calloc(BODY_LENGTH, sizeof(int));
		item_body_count(temp);
		if (match("|"))
		{
			temp->next = (item*)calloc(1, sizeof(item));
			temp = temp->next;
		} else if (match(";"))
			return first_item;
		else
			exception("Illegal grammar form error", "items_analyze");
	}
}

　　接下来是产生式体中符号的处理函数，函数的逻辑也比较简单，就是首先判断读取到的这个符号是否已经被记录，如果是，那对终结符或者非终结符分别进行处理，如果不是，那这个符号只能是非终结符（因为规定所有的终结符必须事先声明）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
element* elements_analyze()
{
	element* first_element = NULL;
	element* temp_e = NULL;
	production* temp_p = NULL;
	int contain;
	while (advance())
	{
		contain = is_contain(current_str);
		if (contain == TOKEN)
		{
			if (first_element == NULL)
			{
				first_element = (element*)find_by_key(current_str);
				temp_e = first_element;
			} else
			{
				temp_e->next = (element*)find_by_key(current_str);
				temp_e = temp_e->next;
			}

		} else if (contain == PRODUCTION)
		{
			if (first_element == NULL)
			{
				first_element = (element*)calloc(1, sizeof(element));
				//first_element->is_terminator = FALSE;
				first_element->type.pro = (production*)find_by_key(current_str);
				temp_e = first_element;
			} else
			{
				temp_e->next = (element*)calloc(1, sizeof(element));
				//temp_e->next->is_terminator = FALSE;
				temp_e->next->type.pro = (production*)find_by_key(current_str);
				temp_e = temp_e->next;
			}
		} else
		{
			temp_p = (production*)calloc(1, sizeof(production));
			temp_p->p_index = transfer_index;
			strcpy(temp_p->head, current_str);
			add_p(temp_p);
			if (first_element == NULL)
			{
				first_element = (element*)calloc(1, sizeof(element));
				first_element->type.pro = temp_p;
				temp_e = first_element;
			} else
			{
				temp_e->next = (element*)calloc(1, sizeof(element));
				temp_e->next->type.pro = temp_p;
				temp_e = temp_e->next;
			}
		}
		blank_skip();
	}
	return first_element;
}

　　至此，整个配置文件便已经被处理完毕了，解析完成之后，链表pro_list和token_list分别记录了所有的非终结符与终结符，并且它们之间的指针指向与文法的描述是相一致的，这样的处理是十分方便的，在接下来的文章中我们便会使用这些链表构建出LR(1)项集族以及语法分析表。