tree.cc

C语言前端编译器,yacc/lex编写,可自行修改代码.

// Copyright 2002 by Keith Vallerio.
// All rights reserved.

#include "tree.h"
#include "database.h"

// utility function: stores values in 'a' or 'b' in 'out'
void vector_merge (RVector<string> a, RVector<string> b,RVector<string> &out)
{
	out.clear();
	MAP (x, a.size()) {
		out.push_back(a[x]);
	}
	MAP (x, b.size()) {
		out.push_back(b[x]);
	}
}

// Constructors
TreeNode::TreeNode () :
	name_(), whitespace_(), subtree_size_(0), parent_(-1), children_()
{
}

TreeNode::TreeNode (string str, string space) :
	name_(str), whitespace_(space), subtree_size_(0), parent_(-1), children_()
{
}

// Returns next tree node which is actually in the source code
// (This is equivalent to saying 'get next leaf node')
long DB::get_next_literal (long tn)
{
	for (long i = tn + 1; i < tree_node_.size(); i++) {
		if (tree_node_[i].subtree_size() == 1)
			return i;
	}
	return -1;
}

// Returns first ancestor of node 'n' with name 's'
long DB::get_ancestor (long n, string s)
{
	long i = n;
	while (tree_node_[i].parent() != -1) {
		if (tree_node_[i].name() == s)
			return i;
		i = tree_node_[i].parent();
	}
	return -1;
}

// Returns first child of 'n' which is a variable
string DB::get_first_var_child (long n, long curr_function)
{
	long i = n - tree_node_[n].subtree_size() + 1;
	string ret_val;

	while (i < n) {
		string str = create_var_name (tree_node_[i].name(), curr_function);
		if ((var_map(str)) != -1) {
			ret_val = str;
			i = n;
		}
		i++;
	}
	return ret_val;
}

// generates a variable name with appropriate extension
// __0 for globals, __# for local variables where # is the function number
string DB::create_var_name (string s, long f)
{
	string tmp_str = s + "__" + to_string(0);

	// first check if 's' is a global variable
	if (var_map_.find(tmp_str) != var_map_.end()) {
		return tmp_str;
	} else {
		return (s + "__" + to_string(f));
	}
}

// Return child index if node 'n' has a child with name 's'
long DB::has_child (long n, string s)
{
	long i = n - tree_node_[n].subtree_size() + 1;

	while (i < n) {
		if (tree_node_[i].name() == s) {
			return i;
		}
		i++;
	}
	return -1;
}

// Get name of child 'c' of node 'n' (starts at 0)
string DB::node_child_name (long n, long c)
{
	Rassert (c < (tree_node_[n].children()).size());
	long t = tree_node_[n].child(c);
	return (tree_node_[t].name());
}

// get the name the parent of node 'n' 
string DB::node_parent_name (long n)
{
	if (tree_node_[n].parent() != -1) 
		return tree_node_[tree_node_[n].parent()].name();
	else
		return (string(""));
}

// adds a node to the abstract syntax tree (AST)
void DB::add_tree_node (string str, int num_subtrees, string space)
{
	RVector<long> node_list;
	tree_node_.push_back(TreeNode(str, space));

	// These two lines find space for the new node
	long last_node = tree_node_.size() - 1;
	long size = 1;

//cout << "\ntoken:(" << last_node << ")  " << str << endl;

	// These lines determine the immediate children of the new node
	// and the size of the whole subtree.  To accomplish this, get
	// the first child and add children and subtrees as long as there
	// are more subtrees to be added.  This also sets the parent
	// value for the children.
	long c = last_node - 1;
	MAP (x, num_subtrees) {
		node_list.push_back(c);
		tree_node_[c].add_parent(last_node);

		size += tree_node_[c].subtree_size();
		c -= tree_node_[c].subtree_size();
	}

	// add the children to the new node
	for (int i = node_list.size() - 1; i >= 0; i--) {
		tree_node_[last_node].add_child(node_list[i]);
	}

	tree_node_[last_node].set_subtree_size(size);
}

// Analyze the tree.  (Does a significant amount of processing.)
void DB::interpret_tree()
{
	// These 2 vars record when we start/end analyzing a function
	long curr_function = 0;
	long curr_function_end = 0;

	// These 3 vectors record when we start/end analyzing a function call
	RVector<long> func_call;
	RVector<long> func_call_end;
	RVector<string> func_call_name;

	//These strings store info on variable names and type info
	string type, str;
	RVector<string> stype_full, stype_one, stype_all;

	// Add a special function for global definitions
	func_def_name_list_.push_back("global_defs");

	//**********************************************************
	// FOR EACH NODE IN THE TREE...
	//-----------------------------
	// Pass through tree once.  Take actions based on current node (x)
	// and current state (variables listed above)
	//**********************************************************
	MAP (x, tree_node_.size()) {
//cout << tree_node_[x].name() << endl;

		/////////////////////////////
		// Cleanup section goes first
		//---------------------------
		// Determine if end of func def or func call is reached
		// and adjust variables accordingly.
		///////////////////////////// 
		// End of func def -> set curr_function to zero
		if (x > curr_function_end) {
			curr_function = 0;
		}
		// If currently analyzing a function
		if (func_call.size()) {
			// If we reached the end of the most recent func call
			if (x > func_call_end[func_call_end.size() - 1]) {
				// Add function call to curr_functions func_call list.
				// Make sure it has the correct number of commas.
				// And pop func_call stacks.
				function_[curr_function].add_action(
						func_call_name[func_call.size()-1], FN_END, x-1);
				if (tree_node_[func_call_end[func_call.size()-1]].subtree_size() 
								!= 5) {
					function_[curr_function].balance_func_call_commas(
										func_call[func_call.size()-1]);
				}
				func_call.pop_back();
				func_call_end.pop_back();
				func_call_name.pop_back();
			}
		}

		/////////////////////////////
		// Analysis
		//---------
		// Analyze current node in this section
		///////////////////////////// 

		// creates a variable name...checks to see if it's a global first
		str = create_var_name (tree_node_[x].name(), curr_function);

		// inside a struct declaration throw out variables and data types
		if (get_ancestor(x, "struct_declaration_list") != -1) {

		// undefined structs
		} else if (tree_node_[x].name() == "struct") {
			long next = get_next_literal(x);
			if (tree_node_[get_next_literal(next)].name() == ";") {			
//				cout << tree_node_[next].name() << endl;			
				undefined_structs_.insert("struct " + tree_node_[next].name());
			}

		// Handle identifiers (funcs, params, vars, user-defined data types
		} else if (node_parent_name(x) == "identifier") {
			long a1,a2,a3;
			if ((a1 = get_ancestor (x, "function")) != -1) {
				// function def/decl parameters
				if ((a2 = get_ancestor (x, "parameter_list")) != -1) {
					Rassert(curr_function);
					vector_merge(stype_one, stype_all, stype_full);
					add_parameter(curr_function, str, type, stype_full);

				// function definition
				} else if ((a3 = get_ancestor (x, "function_definition")) != -1) {
					Rassert(!curr_function);
					vector_merge(stype_one, stype_all, stype_full);
					curr_function = 
								add_function(tree_node_[x].name(),type,stype_full);
					curr_function_end = a3;
					set_function_defined (curr_function);
					func_def_name_list_.push_back(tree_node_[x].name());

				// function declaration
				} else {
					Rassert(!curr_function);
					vector_merge(stype_one, stype_all, stype_full);
					curr_function = 
								add_function(tree_node_[x].name(),type, stype_full);
					curr_function_end = get_ancestor (x, "declaration");
				}

			// don't count user-defined data types as variables!!!
			} else if ((type_map_lookup(tree_node_[x].name())) != -1) {
//				cout << tree_node_[x].name() << " DATA TYPE...not a variable\n";

			// variable declaration
			} else if ((a1 = get_ancestor (x, "declaration")) != -1) { 
				long arr_size = 1;

				// if it's an array, try to determine size
				if ((a2 = get_ancestor (x, "array_decl")) != -1) {
					long tmp_x = x;
					bool done = false;
//					cout << "Array:  " << str << "  ";
					while (!done) {
						long tn = get_next_literal(tmp_x);
						Rassert(tn != -1);
						if (tree_node_[tn].name() == "[") {
							tn = get_next_literal(tn);
							long tmp_val = Conv(tree_node_[tn].name());
							arr_size *= tmp_val;
//							cout << tree_node_[tn].name() << " ";
							tn = get_next_literal(tn);

// If calculation embedded in [], then just give up on guessing array size
							if (tree_node_[tn].name() != "]") {
								done = true;
								arr_size = ArgPack::ap().pointer_size();
							}
							tmp_x = tn;
						} else {
							done = true;
						}
					}
//					cout << " is " << arr_size << endl;
				}
				if ((type_map_lookup(str)) == -1) {
					vector_merge(stype_one, stype_all, stype_full);
					add_variable (curr_function, str, type, stype_full, arr_size);
					function_[curr_function].add_action(str, VAR_DECL, x);
				}
			}

		// variable usage (including inside of a function call)
		} else if ((var_map(str)) != -1) {
			if (func_call.size()) {
				long tmp = func_call[func_call.size() - 1];
				Rassert(var_map(str) != -1);
				add_func_call_arg(curr_function, tmp, var_map(str), VAR);
			}
			function_[curr_function].add_var_use (str);
			function_[curr_function].add_action (str, VAR_USE, x);
			//添加函数返回参数  return后的变量
			/*
			int cup2=get_ancestor(x,"jump_statement");
			if(cup>=0){ 
			   long cup1 = cup2 - tree_node_[cup2].subtree_size() + 1;
			   if(cup1>=0 && tree_node_[cup1].name()=="return")
			     //add_parameter(curr_function, str, type, stype_full);
			     function_[curr_function].add_parameter(var_map_.find(str));
			}
			*/
			// 此处以UNIX中的为标准  上面隐藏的程序不正确
			
			//添加以下代码，为了分辨出条件还是执行体,并同时去掉上一语句
			//int cup=get_ancestor(x,"expr");
			//string bottle="";
			//if(cup>=0)bottle=node_parent_name(cup);
			//if(bottle=="selection_statement"||bottle=="iteration_statement")
			//   function_[curr_function].add_action (str, VAR_USE_COND, x);
		        // else function_[curr_function].add_action (str, VAR_USE, x);

		// function call
		} else if ((func_map(tree_node_[x].name())) != -1) {
			// fn_call_root is the root node of the func call subtree
			long fn_call_root = get_ancestor (x, "function_call");
			if (fn_call_root != -1) {
				if (func_call.size()) {
					long fc_num = func_call[func_call.size() - 1];
					long fnum = func_map(tree_node_[x].name());
					Rassert(fnum != -1);
					add_func_call_arg(curr_function, fc_num, fnum, FUNC);
				}
				string fn_call_name = tree_node_[x].name();
				function_[curr_function].add_action(fn_call_name, FN_START, x);
				func_call.push_back(
							add_func_call(curr_function,fn_call_name,fn_call_root,x));
				func_call_end.push_back(fn_call_root);
				func_call_name.push_back(fn_call_name);
			}

		// storage class specifiers (adjectives for data types)
		} else if ((tree_node_[x].name() == "extern") || 
						(tree_node_[x].name() == "static") ||
						(tree_node_[x].name() == "const") ||