analysis.cpp

学编译原理时的课程作业,里面包含抽象语法树和程序源代码.

#include <iostream>
#include <fstream>
#include <string>
#include <deque>
#include "Scaner.h"


/*This class define a node in the tree*/
class Node {
	
public:
	Node * leftChild;	//left child pointer
	Node * rightChild;	//righr child pointer
	int op;				//store operator 
	int value;			//store value of left op right
	Node() {			//default constructor
		
		leftChild = NULL;
		rightChild = NULL;
		op = NULL;
		value = 0;
	}
};

/*This class analysis the express and caculate the result, ouput the result and the tree to the file out.txt*/
class Analysis{

private:
	ofstream  out;	//out is a output stream
	Node *	root;	//root of the tree
public:
	Analysis() {
		
		Node temp;
		out.open("out.txt");//create a output stream
		root = &temp;
	}

	/*free all nodes in the tree through destructor*/
	~Analysis() {
	
		freeNode(root);
	}

	/*This function is to free all the nodes recursively*/
	void freeNode(Node * & p) {

		if (p != NULL) {
			Node * t = p;
			p = NULL;
			if (t->leftChild == NULL && t->rightChild == NULL) {

				free(p);
			}
		
			freeNode(t->leftChild);
			freeNode(t->rightChild);
		}
	}

	/*This public method simply invokes the inner buildTree method with two arguments*/
	void buildTree() {

		int result =  buildTree(root, pairs);
		
		out << "results = " << result << endl << endl;
		cout << "results = " << result << endl;
	}

	void printTree() {

		printTree(root);
	}
	
	/*This fucntion output the tree detail into the file out.txt*/
private :
	void printTree(Node * p) {

		if (p != NULL) {
			out << "Node: " << p << endl;
			out << "value: " << p->value << endl;
			out << "operator: " ;
			switch (p->op) {

				case ADD: {

					out << "+" << endl;
					break;
				}

				case MINUS: {

					out << "-" << endl;
					break;
				}
					
				case MULT: {
					
					out << "*" << endl;
					break;
			   }
				default :
					out << "no" << endl;
			}
			out << "leftChild: " ;
			if (p->leftChild) {
				out << p->leftChild << endl;
			}
			else {
				out << "no left child" << endl;
			}
			out << "rightChild: " ;
			if (p->rightChild) {
				out << p->rightChild << endl;
			}
			else {
				out << "no right child" << endl;
			}
			out << endl;

			printTree(p->leftChild);
			printTree(p->rightChild);
		}
	}

private:
	/*This is a private function, it builds a tree through invoking it recursively*/
	int buildTree(Node * & np, deque<Pair *>  & pairs) {

		np = new Node();
		if (0 == pairs.size()) {
	
			return 0;
		}
		else if (pairs.size() == 1) {
		
			if (pairs[0]->type == INT) {//when the type of token is int
			
				np->value = pairs[0]->value;
				return np->value;
			}
			else {//when it is not what expected
				
				cout << "Error Token Type!";
				return 0;
			}
		}
		else if (pairs.size() >= 5 ) {
			
			
				if (pairs[0]->type != B11) {
					
					cout << "Error lack ( in the beggening!" << endl;
					return 0;
				}
				else if (pairs[pairs.size()-1]->type != B12){
				
					cout << "Error lack ) in the end!" << endl;
					return 0;
				}
				else {
					
					pairs.pop_back();//delete the first '('
					
					pairs.pop_front();//delete the last ')'

					if (pairs[0]->type == ADD || pairs[0]->type == MINUS || pairs[0]->type == MULT) {

						np->op = pairs[0]->type;
						pairs.pop_front(); //delete the operator

						deque<Pair *> leftSeq;
						
							if (pairs.front()->type == INT) {//when left sequence is a int

								leftSeq.push_back(pairs.front());
								pairs.pop_front();
								//left sequences is in leftSeq, right sequence remains pairs
							}
							else if (pairs.front()->type == B11) {//when it starts with '('

								int counter = 0;
								do {
							
									leftSeq.push_back(pairs.front());
									if (B11 == pairs.front()->type) {
										counter++;
									}
									else if (B12 == pairs.front()->type) {
										counter--;
									}
									pairs.pop_front();
									if (pairs.size() == 0 && counter != 0) {
										cout << "Error lack ) " << endl;
										break;
									}
								}while (counter);
								//Now left sequences is in leftSeq, right sequence remains pairs 
							}
							else {//It starts with neither ( nor int, illegal char
						
								cout << "It starts with neither ( nor int, illegal char" << endl;
								return 0;
							}
							
							int leftResult = buildTree(np->leftChild, leftSeq) ;//get value of left child
							int rightResult =  buildTree(np->rightChild, pairs);//get value of right child
							
							/*This block frees all Pairs*/
							while (!leftSeq.empty()) {
						
								free(leftSeq.front());
								leftSeq.pop_front();
							}
							while (!pairs.empty()) {

								free(pairs.front());
								pairs.pop_front();
							}

							int result;
							if (np->op == ADD) {

								result = leftResult + rightResult;
							}
							else if (np->op == MULT) {
							
								result = leftResult * rightResult;
							}
							else {
					
								result = leftResult - rightResult;
							}
								
							np->value = result;
							return result;							
					}
					else {
						
						cout << "Error Illegal operator!" << endl;
						return 0;
					}
				}
		}
		else {
		
			cout << "Error in Struct of Express!" << endl;
			return 0;
		}
	}
};


int main(int argc, char * argv[]) {

	ifstream in;//input stream

	in.open("input.txt");
		
	if (!in) {//faild to initialis it
		cout << "Can't open file: input.txt" << endl;
		exit(-1);
	}

	Scaner scaner(in);//create a Scaner object to distill the tokens
	

	Analysis analysiser;//create a Analysis object to analysis the express
	scaner.scan();//distill the tokens in the expres.
	analysiser.buildTree();//try to build a tree and process it.
	analysiser.printTree();
	return 0;
}