source.txt

编译原理的三个子模块,包括词法分析,语法分析和语义分析,是绘图语言解释器

// ----------------------------- scanner.h ---------------------------------

#include <string.h>
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdarg.h>
#include <math.h>

//--------------------------------- 词法分析器类中的类型定义与常量声明
enum token_type								// 记号种类
{	ORIGIN, SCALE, ROT, IS,  TO,			// 保留字
	STEP,   DRAW,  FOR,	FROM,				// 保留字
	T,										// 参数
	SEMICO,L_BRACKET, R_BRACKET, COMMA,		// 分隔符号
	PLUS, MINUS, MUL, DIV, POWER,			// 运算符
	FUNC,									// 函数
	CONST_ID,								// 常数
	NONTOKEN,								// 空记号
	ERRTOKEN								// 出错记号
};
struct token_rec							// 记号与符号表结构
{	token_type  type;						// 记号的类别
	char		* lexeme;					// 构成记号的字符串
	double		value;						// 若为常数，则是常数的值
	double		(* func_ptr)(double);		// 若为函数，则是函数的指针
};
static token_rec token_table[] =			// 符号表内容
{	{CONST_ID,	"PI",		3.1415926,	NULL},
	{CONST_ID,	"E",		2.71828,	NULL},
	{T,			"T",		0.0,		NULL},
	{FUNC,		"SIN",		0.0,		sin},
	{FUNC,		"COS",		0.0,		cos},
	{FUNC,		"TAN",		0.0,		tan},
	{FUNC,		"LN",		0.0,		log},
	{FUNC,		"EXP",		0.0,		exp},
	{FUNC,		"SQRT",		0.0,		sqrt},
	{ORIGIN,	"ORIGIN",	0.0,		NULL},
	{SCALE,		"SCALE",	0.0,		NULL},
	{ROT,		"ROT",		0.0,		NULL},
	{IS,		"IS",		0.0,		NULL},
	{FOR,		"FOR",		0.0,		NULL},
	{FROM,		"FROM",		0.0,		NULL},
	{TO,		"TO",		0.0,		NULL},
	{STEP,		"STEP",		0.0,		NULL},
	{DRAW,		"DRAW",		0.0,		NULL}
};
const int  token_len = 100;			// 记号最大长度
const char str_end   = '\0';		// 字符串结束标志

//--------------------------------- 词法分析器类的声明
class scanner_class {							
protected:
	FILE *in_flie;								// 输入文件流
	char token_buf[token_len];					// 记号字符缓冲

public:
	unsigned int line_no;						// 跟踪记号所在源文件行号
	scanner_class()	{ line_no = 1; }
	~scanner_class() {}
	int init_scanner(const char *FileName);		// 初始化词法分析器
	void close_scanner(void);					// 关闭词法分析器
	token_rec get_token(void);					// 获取记号函数

private:
	char get_char(void);						// 从输入源程序中读入一个字符
	void back_char(char next_char);				// 把预读的字符退回到输入源程序中
	void add_in_token_str(char next_char);		// 加入字符到记号缓冲区
	void empty_token_str();						// 清空记号缓冲区
	token_rec check_token(const char *c_str);	// 判断所给的字符串是否在符号表中
};



// ----------------------------- scanner.cpp ---------------------------------
// 词法分析器类的定义

#include "scanner.h"

// ---------------初始化词法分析器
int scanner_class::init_scanner(const char *file_name)
{
	in_flie = fopen(file_name, "r");
	if (in_flie != NULL)  return 1;
	else                  return 0;
}

// ---------------关闭词法分析器
void scanner_class::close_scanner(void)
{
	if (in_flie != NULL) fclose (in_flie) ;
}

// ---------------从输入源程序中读入一个字符
char scanner_class::get_char(void)
{
	int next_char = getc(in_flie);   return toupper(next_char);
}

// ---------------把预读的字符退回到输入源程序中
void scanner_class::back_char(char next_char)
{
	if (next_char != EOF)   ungetc(next_char, in_flie);
}

// ---------------加入字符到记号缓冲区
void scanner_class::add_in_token_str(char next_char)
{
	int token_len = strlen (token_buf);
	if (token_len + 1 >= sizeof (token_buf)) return;
	token_buf[token_len]   = next_char;
	token_buf[token_len+1] = str_end;
}

// ----------------- 清空记号缓冲区
void scanner_class::empty_token_str ()
{	
	memset(token_buf, 0, token_len);
} 

// ----------------- 判断所给的字符串是否在符号表中
token_rec scanner_class::check_token(const char * c_str)
{	
	int count;
	token_rec err_token;
	
	for (count=0; count<sizeof(token_table)/sizeof(token_table[0]); count++)
	{ if (strcmp(token_table[count].lexeme, c_str)==0) return token_table[count];
	}
	memset(&err_token, 0, sizeof(token_rec));
	err_token.type = ERRTOKEN;
	return err_token;
}

// ---------------获取一个记号
token_rec scanner_class::get_token(void)
{	
	token_rec token;
	int next_char ;
	
	memset(&token, 0, sizeof(token_rec));
	empty_token_str();
	token.lexeme = token_buf;
	for (;;)	// 过滤源程序中的空格、TAB、回车等，遇到文件结束符返回空记号
	{	next_char = get_char() ;
		if (next_char == EOF)
		{	token.type = NONTOKEN;
			return token;
		}
		if (next_char == '\n')	line_no ++ ;
		if (!isspace(next_char))	break ;
	} // end of for 
	add_in_token_str (next_char);	// 若不是空格、TAB、回车、文件结束符等，
									// 则先加入到记号的字符缓冲区中
	if(isalpha(next_char))			// 若char是A-Za-z，则它一定是函数、关键字、PI、E等
	{	for (;;)
		{	next_char = get_char () ;
			if ( isalnum(next_char) )	add_in_token_str (next_char) ;
			else					break ;
		}
		back_char (next_char) ;
		token = check_token (token_buf);
		token.lexeme = token_buf;
		return token;
	}	
	else if(isdigit(next_char))		// 若是一个数字，则一定是常量
	{	for (;;)
		{	next_char = get_char () ;
			if (isdigit(next_char))	add_in_token_str (next_char) ;
			else				break ;
		}
		if (next_char == '.')
		{	add_in_token_str (next_char) ;
			for (;;)
			{	next_char = get_char() ;
				if (isdigit(next_char))	add_in_token_str (next_char) ;
				else				break ;
			}
			
		} // end of if (next_char == '.')
		back_char (next_char) ;
		token.type = CONST_ID;
		token.value = atof (token_buf);
		return token;
	}
	else	// 不是字母和数字，则一定是符号
	{	switch (next_char)
		{	case ';' : token.type = SEMICO    ; break;
			case '(' : token.type = L_BRACKET ; break;
			case ')' : token.type = R_BRACKET ; break;
			case ',' : token.type = COMMA     ; break;
			case '+' : token.type =	PLUS      ; break;
			case '-' :
				next_char = get_char();
				if (next_char =='-')
				{	while (next_char != '\n' && next_char != EOF) next_char = get_char();
					back_char(next_char);
					return get_token();
				}
				else 
				{	back_char(next_char);
					token.type = MINUS;
					break;
				}
			case '/' :
				next_char = get_char();
				if (next_char =='/') 
				{	while (next_char != '\n' && next_char != EOF) next_char = get_char();
					back_char(next_char);
					return get_token();
				}
				else
				{	back_char(next_char);
					token.type = DIV;
					break;
				}
			case '*' :
				next_char = get_char() ;
				if (next_char == '*')	token.type = POWER ;
				else 
				{	back_char (next_char);	
					token.type = MUL; 
				}
				break;
			default: 
				token.type = ERRTOKEN; 
		} // end of switch
	} // end of else(不是字母和数字，则一定是符号)
	return token;
} // end of get_token


// ----------------------------- parser.h ---------------------------------

#include "scanner.h"

//--------------------------------- 语法分析器类中的类型定义
typedef double (* func_ptr)(double);
typedef struct tree_node				// 语法树节点类型
{	enum token_type op_code;			// PLUS, FUNC, CONST_ID, ...
	union
	{	struct { tree_node *left, *right; } tag_op;
		struct { tree_node *child; func_ptr math_func_ptr; } tag_func;
		double tag_const;
		double * tag_parameter;
	} content;
} * tree_node_ptr;

//--------------------------------- 语法分析器类声明
class parser_class {
protected:
	token_rec token;			// 记号
	double    parameter;		// 参数T的存储空间
	tree_node_ptr start_ptr,	// 绘图起点表达式的语法树
				  end_ptr, 		// 绘图终点表达式的语法树
				  step_ptr,		// 步长表达式的语法树
				  x_ptr,		// 点的横坐标表达式的语法树
				  y_ptr;		// 点的横坐标表达式的语法树
	scanner_class scanner;		// 词法分析器对象

	// --------------- 辅助函数
	void fetch_token ();											// 获取记号
	void match_token (enum token_type the_token);					// 匹配记号
	void syntax_error (int case_of);								// 指出语法错误(调用error_msg)
	void print_syntax_tree(tree_node *root, int indent);			// 打印语法树
	tree_node_ptr make_tree_node(enum token_type opcode,...);		// 构造语法树
	virtual void error_msg(int line, char *descrip, char *string);	// 在Semantics中重置为窗口打印形式


	// ---------------非终结符的递归子程序
	virtual void statement();		// 在Semantics_class中重置
	void program();
	void for_statement ();
	void origin_statement(tree_node_ptr &x_temp, tree_node_ptr &y_temp);
	void rot_statement(tree_node_ptr &angle_tmp);
	void scale_statement(tree_node_ptr &x_temp, tree_node_ptr &y_temp);
	tree_node_ptr expression ();
	tree_node_ptr term ();
	tree_node_ptr factor ();
	tree_node_ptr component ();
	tree_node_ptr atom ();

public:
	parser_class() 		// 置初值
	{
		parameter = 0;
		start_ptr = NULL;
		end_ptr   = NULL;
		step_ptr  = NULL;
		x_ptr	  = NULL;
		y_ptr	  = NULL;
	}
	~parser_class() {}
	void parser(char * file_name);		// 语法分析器接口

private:
	// 下述函数用于语法分析器的跟踪调试, 在Semantics_class中需重置为不起作用
	virtual void enter(char * x);
    virtual void back(char * x);
    virtual void call_match(char * x); 
    virtual void tree_trace(tree_node_ptr x);
};


// ----------------------------- parser.cpp ---------------------------------
// 语法分析器类的定义

#include "parser.h"

// ------------------------ 通过词法分析器接口get_token获取一个记号
void parser_class::fetch_token ()
{	
	token = scanner.get_token () ;
	if (token.type == ERRTOKEN)	syntax_error(1);
}

// ------------------------ 匹配记号
void parser_class::match_token (enum token_type the_token) 
{	
	if (token.type != the_token) syntax_error (2);
	fetch_token();
}

// ------------------------ 语法错误处理
void parser_class::syntax_error (int case_of) 
{
	switch(case_of)
	{	case 1:	error_msg (scanner.line_no," 非法记号 ", token.lexeme) ;
				break;
		case 2: error_msg (scanner.line_no, token.lexeme, " 不是预期记号") ;
				break;
	}
}

// ------------------------ 打印错误信息
void parser_class::error_msg(int line, char *descrip, char *string)
{	
	cout << "Line No " << line << ": " << descrip << string << endl;
	scanner.close_scanner();
	exit(1);
}

// ------------------------ 先序遍历并打印表达式的语法树
void parser_class::print_syntax_tree(tree_node_ptr root, int indent)	
{	
	int		temp;

	for (temp=1; temp<=indent; temp++) cout << "	";	// 缩进
	switch(root->op_code)								// 打印根节点
	{	case PLUS:      cout << "+" << endl;	break;
		case MINUS:     cout << "-" << endl;	break;
		case MUL:       cout << "*" << endl;	break;
		case DIV:       cout << "/" << endl;	break;
		case POWER:     cout << "**" << endl;	break;
		case FUNC:      cout << root->content.tag_func.math_func_ptr << endl;	break;
		case CONST_ID:  cout <<root->content.tag_const << endl;				break;
		case T:         cout << "T" << endl;									break;
		default:        cout << "非法的树节点!" << endl;						exit(0);
	}
	if(root->op_code == CONST_ID || root->op_code == T) return;	// 叶子节点返回
	if(root->op_code == FUNC)									// 递归打印一个孩子的节点
		print_syntax_tree(root->content.tag_func.child,indent+1);
	else														// 递归打印两个孩子的节点
	{	print_syntax_tree(root->content.tag_op.left,  indent+1);
		print_syntax_tree(root->content.tag_op.right, indent+1);
	}
}

// ------------------------ 绘图语言解释器入口（与主程序的外部接口）
void parser_class::parser(char * file_name) 
{	
	enter("parser");
	if(!(scanner.init_scanner(file_name)))		// 初始化词法分析器
	{	cout << "打开文件错误 !" << endl;	
		return;	
	}
	fetch_token();								// 获取第一个记号
	program();									// 递归下降分析
	scanner.close_scanner();					// 关闭词法分析器
	back("parser");
	return;
}

// ------------------------ program 的递归子程序
void parser_class::program ()
{	
	enter("program");
	while (token.type != NONTOKEN)
	{	statement();	
		match_token(SEMICO) ;
	}
	back("program");
}

// ------------------------ statement 的递归子程序
void parser_class::statement()
{
	tree_node_ptr t_ptr;

	enter("statement");
	switch (token.type)
	{	case ORIGIN	:	origin_statement(t_ptr, t_ptr);	break ;
		case SCALE  :	scale_statement(t_ptr, t_ptr);	break ;
		case ROT    :	rot_statement(t_ptr);			break ;
		case FOR    :	for_statement();				break ;
		default     :	syntax_error(2);		
	}
	back("statement");
}

// ------------------------ origin_statement 的递归子程序
void parser_class::origin_statement(tree_node_ptr &x_tmp, tree_node_ptr &y_tmp)
{
	enter("origin_statement");
	match_token (ORIGIN);
	match_token (IS);
	match_token (L_BRACKET);
	x_tmp = expression();

	match_token (COMMA);
	y_tmp = expression();
	match_token (R_BRACKET);
	back("origin_statement");
}

// ------------------------ scale_statement 的递归子程序
void parser_class::scale_statement (tree_node_ptr &x_ptr, tree_node_ptr &y_ptr) 
{
	enter("scale_statement");
	match_token (SCALE);
	match_token (IS);
	match_token (L_BRACKET);
    x_ptr = expression();
	match_token (COMMA);