编译原理实验指导书

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

实验一　词法分析器**的设计**

【实验目的】

1． 掌握生成词法分析器的方法，加深对词法分析原理的理解。

2． 掌握设计、编制并调试词法分析程序的思想和方法。

3． 本实验是高级语言程序设计、数据结构和编译原理中词法分析原理等知识的综合。

【实验性质】

综合性实验（学时数：2H）

【实验内容及要求】

1． 设计并实现一个四则运算的计算器,通过命令行方式启动,可以通过键盘输入整个算式,然后直接显示结果。将换行作为分隔符，把输入分隔为一个个算式。

2． 使用C语言设计、编写、调试一个词法分析子程序。

3． 实验前请仔细阅读实验预习提示，已经附有完整的源代码,请在实验报告中画出该分析器所实现的状态转换图。

4． 提交的实验报告中要有实验名称、实验目的、实验内容、实验程序清单、调试过程和运行结果，程序的主要部分做出功能说明，并有实验收获体会或改进意见等内容。

5． 进阶实验:扩展原有计算器,使其可以支持括号和负数运算。

6． 本实验建议学时数为2学时

【实验预习提示】

1.词法分析器的功能和输出格式

词法分析器的功能是输入以字符串表示的源程序，输出单词符号或单词符号序列。词法分析器的单词符号常常表示成以下的二元组(单词的种别码，单词符号的属性值)。本实验是用于计算器的词法分析器，只需处理运算符和数值。

2.“超前搜索”方法

词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a>+”,当前字符为’>’，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’>’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。

3.词法分析程序主程序的算法思想

算法的基本思想是根据扫描到单词符号的第一个字符的种类，拼写出相应的单词符号，其实现的基本任务是从字符串表示的源程序中识别出相应的具有独立意义的单词符号。主程序示意图如图1.1所示。

​

​

图1.1 词法分析主程序示意图

4.补充知识:

(1)避免重复包含。在头文件token.h中，有这样的代码段：

#ifndef TOKEN_H_INCLUDED

#define TOKEN_H_INCLUDED

​ …

#endif

这是为了防止多次用#include包含引起多重定义错误而采用的技巧。头文件用#include包含自己所依赖的其他所有头文件，可以让代码中只需书写一次include,且当依赖关系发生改变时较容易修改。但如果多个头文件这样书写，会报类型或宏的重复定义错误，一次可以采用这个技巧，根据开头的#ifndef语句，避免产生多重定义的错误。

(2)在执行语句sscanf(token->str,”%lf”,&token->value);时，会出现null pointer assignment错误，这是因为没有给指针初始化。

5.参考源程序

token.h

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
#ifndef TOKEN_H_INCLUDED
#define TOKEN_H_INCLUDED

typedef enum{
	BAD_TOKEN,
	NUMBER_TOKEN,
	ADD_OPERATOR_TOKEN,
	SUB_OPERATOR_TOKEN,
	MUL_OPERATOR_TOKEN,
	DIV_OPERATOR_TOKEN,
	END_OF_LINE_TOKEN
}TokenKind;

#define MAX_TOKEN_SIZE 100

typedef struct {
	TokenKind kind;
	double value;
	char str[MAX_TOKEN_SIZE];
}Token;

void set_line(char *line);
void get_token(Token *token);

#endif

lexicanalyzer.c

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>

#include"token.h"

static char *st_line;
static int st_line_pos;

typedef enum{
	INITIAL_STATUS,
	IN_INT_PART_STATUS,
	DOT_STATUS,
	IN_FRAC_PART_STATUS
}LexerStatus;

void get_token(Token *token)
{
	int out_pos=0;
	LexerStatus status=INITIAL_STATUS;
	char current_char;
	char ste[MAX_TOKEN_SIZE];
    token->kind=BAD_TOKEN;
while(st_line[st_line_pos]!='\0'){
	current_char=st_line[st_line_pos];

	if((status==IN_INT_PART_STATUS || status==IN_FRAC_PART_STATUS) && !isdigit(current_char) && current_char !='.'){
		token->kind=NUMBER_TOKEN;
		sscanf(token->str,"%lf",&token->value);
			return;
	}
	if(isspace(current_char)){
		if(current_char=='\n'){
			token->kind=END_OF_LINE_TOKEN;
			return;
		}
		st_line_pos++;
		continue;
	}
	if(out_pos>=MAX_TOKEN_SIZE-1){
		fprintf(stderr,"token too long.\n");
		exit(1);
	}
	token->str[out_pos]=st_line[st_line_pos];
	st_line_pos++;
	out_pos++;
	token->str[out_pos]='\0';

	if(current_char=='+'){
		token->kind=ADD_OPERATOR_TOKEN;
		return;
	}else if(current_char=='-'){
		token->kind=SUB_OPERATOR_TOKEN;
		return;
	} else if(current_char=='*'){
		token->kind=MUL_OPERATOR_TOKEN;
		return;
	} else if(current_char=='/'){
		token->kind=DIV_OPERATOR_TOKEN;
		return;
	}else if(isdigit(current_char)){
		if(status==INITIAL_STATUS){
			status=IN_INT_PART_STATUS;
		}else if(status==DOT_STATUS){
			status=IN_INT_PART_STATUS;
		}
	}else if(current_char=="."){
		if(status=IN_INT_PART_STATUS){
			status=DOT_STATUS;
		}else {
			fprintf(stderr,"syntax error.\n");
			exit(1);
		}
	}else {
		fprintf(stderr,"bad character(%c)\n",current_char);
	}
}
    }

void set_line(char *line)
{
	st_line=line;
	st_line_pos=0;
}

void parse_line(char *buf)
{
	Token token;
	char str[MAX_TOKEN_SIZE];
	set_line(buf);
	for(;;){
	get_token(&token);
	if(token.kind==END_OF_LINE_TOKEN){
		break;
	}else {
		printf("kind..%d,str..%s\n",token.kind,token.str);
		if(token.kind=NUMBER_TOKEN)
			sscanf(token.str,"%lf",&token.value);
	  }
	}
}

int main()
{
	char buf[1024];
	while(fgets(buf,1024,stdin)!=NULL){
		parse_line(buf);
	}
	return 0;
}

实验二　用递归下降法实现语法分析

【实验目的】

1.掌握用递归下降分析法进行语法分析的方法。加深对自顶向下语法分析原理的理解。

2.掌握设计、编制并调试自顶向下语法分析程序的思想和方法。

3.本实验是高级语言程序设计、数据结构和编译原理中词法分析、自顶向下语法分析原理等知

识的综合。由于语法分析是在词法分析的基础上进行的，且词法分析器输出的结果即单词符号

或单词符号序列是语法分析的输入。

【实验性质】

综合性实验（学时数：2H）

【实验要求】

\1. 调用实验一的get_token函数进行词法分析，使用递归下降法作语法分析器，实现计算器的功能。

\2. 实验前请仔细阅读实验预习提示，参考所附完整的源代码,请在实验报告中写出该分析器所使用的语法规则。

\3. 本实验建议学时2学时。

【实验预习提示】

1、 语法分析程序的算法思想

（1） 主程序示意图如图4.1所示。
img

图4.1 递归下降法语法分析主程序示意图

（2） 递归下降分析程序示意图如图4.2所示。
img

​ 图4.2 递归下降分析程序示意图

2.参考源程序parser.c：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<stdio.h>
#include<stdlib.h>

#include"token.h"
#include"lexicanalyzer.c"

#define LINE_BUF_SIZE 1024

static Token st_look_abead_token;
static int st_look_abead_token_exists;

static void my_get_token(Token *token){
	if (st_look_abead_token_exists){
		*token = st_look_abead_token;
		st_look_abead_token_exists = 0;
	}
	else
	{
		get_token(token);
	}
}

static void unget_token(Token *token)
{
	st_look_abead_token = *token;
	st_look_abead_token_exists = 1;
}

//double parse_expression();

static double parse_primary_expression()
{
	Token token;
	my_get_token(&token);
	if (token.kind==NUMBER_TOKEN)
	{
		return token.value;
	}
	fprintf(stderr, "syntax error.\n");
	exit(1);
	return 0.0;
}

static double parse_term()
{
	double v1;
	double v2;
	Token token;
	v1 = parse_primary_expression();
	while (1){
		my_get_token(&token);
		if (token.kind != MUL_OPERATOR_TOKEN && token.kind != DIV_OPERATOR_TOKEN){
			unget_token(&token);
			break;
		}
		v2 = parse_primary_expression();
		if (token.kind == MUL_OPERATOR_TOKEN)
			v1 *= v2;
		else if (token.kind == DIV_OPERATOR_TOKEN)
			v1 /= v2;
	}
	return v1;
}

double parse_expression()
{
	double v1;
	double v2; 
	Token token;
v1 = parse_term();
while (1){
	my_get_token(&token);
	if (token.kind != ADD_OPERATOR_TOKEN && token.kind != SUB_OPERATOR_TOKEN){
		unget_token(&token);
		break;
	}
	v2 = parse_term();
	if (token.kind == ADD_OPERATOR_TOKEN)
		v1 += v2;
	else if (token.kind == SUB_OPERATOR_TOKEN)
		v1 -= v2;
	else 
		unget_token(&token);
}
return v1;
    }

double parse_line()
{
	double value;
	st_look_abead_token_exists = 0;
	value = parse_expression();
	return value;
}
int main(){
	char line[LINE_BUF_SIZE];
	double value;
    while (fgets(line, LINE_BUF_SIZE, stdin) != NULL){
	set_line(line);
	value = parse_line();
	printf(">>%f\n", value);
}
return 0;
    }
Boss 扫一下呗