自己动手写C语言编译器（2）

 

直接上代码 ：

支持：左右结合性

// MyCompiler.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <fstream>
#include <list>
#include <map>
#include <string>
#include <iostream>
#include <vector>
//把Token转换为字符串
#define  ATokenToString(l, r) if(l == r)return #r;
using namespace std;
namespace tokens{
	enum TOKEN
	{
		INVALID_TYPE,
			WHITE_SPACE,
			NAME,
			NUMBER,
			END,
			PLUS,
			MINUS,
			MUL,
			DIV,
			PRINT,
			ASSIGN,
			LP,
			RP,
	};
	static string MyTokenToString(TOKEN token)
	{
		ATokenToString(token, WHITE_SPACE)
			ATokenToString(token, NAME)
			ATokenToString(token, NUMBER)
			ATokenToString(token, END)
			ATokenToString(token, PLUS)
			ATokenToString(token, MINUS)
			ATokenToString(token, MUL)
			ATokenToString(token, DIV)
			ATokenToString(token, PRINT)
			ATokenToString(token, ASSIGN)
			ATokenToString(token, LP)
			ATokenToString(token, RP)
			return "";
	}
}

class tokenizer
{
	int mTokenTypes[256];
	string mCurrentStrToken;
	tokens::TOKEN mCurrentTokenType;
	istream& mIfStream;
public:
	tokenizer(istream& infile):mIfStream(infile)
	{
		memset(mTokenTypes, 0, 256);
		mTokenTypes['+'] = tokens::PLUS;
		mTokenTypes['-'] = tokens::MINUS;
		mTokenTypes['*'] = tokens::MUL;
		mTokenTypes['/'] = tokens::DIV;
		mTokenTypes[';'] = tokens::PRINT;
		mTokenTypes['='] = tokens::ASSIGN;
		mTokenTypes['('] = tokens::LP;
		mTokenTypes[')'] = tokens::RP;
		mTokenTypes['\t'] = tokens::WHITE_SPACE;
		mTokenTypes[' '] = tokens::WHITE_SPACE;
		char ch = 0;
		for (ch = 'a'; ch <= 'z'; ch ++)
		{
			mTokenTypes[ch] = tokens::NAME; 
		}
		for(ch = 'A'; ch <= 'Z'; ch ++)
		{
			mTokenTypes[ch] = tokens::NAME; 
		}
		for(ch = '0'; ch <= '9'; ch ++)
		{
			mTokenTypes[ch] = tokens::NUMBER; 
		}
		mTokenTypes['.'] = tokens::NUMBER;
		
	}
	bool hasNext()
	{
		char temptoken = 0;
		if(mIfStream.get(temptoken))
		{
			mIfStream.putback(temptoken);
			return true;
		}
		return false;
	}
	const string getCurrent()
	{
		return mCurrentStrToken;
	}
	tokens::TOKEN getTokenType()
	{
		return mCurrentTokenType;
	}
	const string getNext()
	{
		string strValue;
		char ch = 0;
		mIfStream>>ch;
		mCurrentTokenType = (tokens::TOKEN)mTokenTypes[ch];
		mIfStream.putback(ch);
		mIfStream>>strValue;
		mCurrentStrToken = strValue;
		return strValue;
	}
};
class Node;
struct NodeVisitor
{
	virtual void BeginVisitTree(Node* nod) = 0;
	virtual void VisitNode(Node* nod) = 0;
	virtual void EndVisitTree(Node* nod) = 0;
};

class Node
{
	char m_Data;

	NodeVisitor* m_pGetNode;
public:
	Node* m_pLeftChild;
	Node* m_pRightChild;
	Node* m_pParent;
	int m_priority_level;
public:
	char getData()
	{
		return m_Data;
	}
	
	Node()
	{
		m_Data = 0;
		m_pLeftChild = NULL;
		m_pRightChild = NULL;
		m_pParent = NULL;
		//空的Node，优先级最低
		m_priority_level = 0;
	}
	
	Node(char data)
	{
		m_Data = data;
		m_pLeftChild = NULL;
		m_pRightChild = NULL;
		m_pParent = NULL;
		m_priority_level = 0;
	}
	
	void set(Node* pL, Node* pR)
	{
		m_pLeftChild = pL;
		m_pRightChild = pR;
	}
	
	void setLeft(Node* pLeft)
	{
		m_pLeftChild = pLeft;
	}
	
	void setRight(Node* pRight)
	{
		m_pRightChild = pRight;
	}
	
	void accept(NodeVisitor* pGetIt)
	{
		m_pGetNode = pGetIt;
	}
	
	void Postorder_Traversal(NodeVisitor* pVisiter)
	{
		if(m_pLeftChild != NULL)
			m_pLeftChild->Postorder_Traversal(pVisiter);
		if (m_pRightChild != NULL)
			m_pRightChild->Postorder_Traversal(pVisiter);
		pVisiter->VisitNode(this);
	}
	
	void Inorder_Traversal(NodeVisitor* pVisiter)
	{
		//Begin Tree.
		pVisiter->BeginVisitTree(this);
		
		if(m_pLeftChild != NULL)m_pLeftChild->Inorder_Traversal(pVisiter);
		
		//Visit this node. 
		//Node should not be diffrent from tree.
		pVisiter->VisitNode(this);
		
		if (m_pRightChild != NULL)m_pRightChild->Inorder_Traversal(pVisiter);
		
		//End Tree.
		pVisiter->EndVisitTree(this);
	}
	

};

class ExpressionVisiter: public NodeVisitor
{
public:
	void BeginVisitTree(Node* nod)
	{
		if (nod->m_pLeftChild != NULL && nod->m_pRightChild != NULL)
		{
			printf("%c", '(');
		}
	}
	void VisitNode(Node* nod)
	{
		printf("%c", nod->getData());
	}
	void EndVisitTree(Node* nod)
	{
		if (nod->m_pLeftChild != NULL && nod->m_pRightChild != NULL)
		{
			printf("%c", ')');
		}
	}
};


class Tree
{
public:
	Tree()
	{
		pHead = new Node();
	}
	Node* pHead;
	~Tree()
	{
		
	}
	Node* getNext()
	{
		
	}
	void Postorder_Traversal(NodeVisitor* pVisiter)
	{
		if(pHead->m_pLeftChild!=NULL)
			pHead->m_pLeftChild->Postorder_Traversal(pVisiter);
	}
	void Inorder_Traversal(NodeVisitor* pVisiter)
	{
		if(pHead->m_pLeftChild!=NULL)
			pHead->m_pLeftChild->Inorder_Traversal(pVisiter);
	}
	Node* getCurrent()
	{
	}
	
	Node* getFirst()
	{
		
	}
	
	bool bHasNext()
	{
	}
	void setValue(Node* pNode)
	{
		pHead->m_pLeftChild = pNode;
	}
};


//打印一个字符串的所有排列。
void printSequence(char* pChara)
{	
	int i = 0;
	static int MAX_LEN = strlen(pChara);
	if (pChara[0] == '\0')
	{
		for (int i = 0; i < MAX_LEN; i ++)
		{
			printf("%c", pChara[i + 1]);
		}
		printf("\n", "");  
	}
	
	char* tempChar = pChara;
	while (*tempChar != '\0' )
	{
		char* pMyString = new char[MAX_LEN + 1];
		memcpy(pMyString, pChara, MAX_LEN + 1);
		memcpy(pMyString + i, pMyString + i + 1, MAX_LEN - i);
		pMyString[MAX_LEN] = *tempChar;
		printSequence(pMyString);
		tempChar ++;
		i ++;
		delete[] pMyString;
	}
}

#ifdef TEST
int main(int argc, char* argv[])
{
	
	ExpressionVisiter visister;
	Tree* pTree = new Tree();
	Node* pNode1 = new Node('-');
	
	
	Node* pNode11 = new Node('+');
	Node* pNode12 = new Node('/');
	
	Node* pNode111 = new Node('a');
	Node* pNode112 = new Node('*');
	Node* pNode121 = new Node('e');
	Node* pNode122 = new Node('f');
	
	
	Node* pNode1121 = new Node('b');
	Node* pNode1122 = new Node('-');
	
	Node* pNode11221 = new Node('c');
	Node* pNode11222 = new Node('d');
	
	
	pNode1->set(pNode11, pNode12);
	pNode11->set(pNode111, pNode112);
	pNode12->set(pNode121, pNode122);
	pNode112->set(pNode1121, pNode1122);
	pNode1122->set(pNode11221, pNode11222);
	pTree->setValue(pNode1);
	pTree->Inorder_Traversal(&visister);
	
	//printSequence("a");
	system("PAUSE");
	return 1;
}
#else

//字符的类型
class SH_CHARACTER_TYPE
{
public:
	enum CHARACTER_TYPE
	{
		ILLIGAL_CHAR = 0x00000000,
		DIGITAL_CHAR = 0x00000001,
		NON_DIGITAL_CHAR = 0x00000002,
		UNIVERSAL_CHAR = 0x00000004,
		INTEGER_CONSTANT_CHAR = 0x00000008,
		FLOATING_CONSTANT_CHAR = 0x00000010,
		ENUMERATION_CONSTANT_CHAR = 0x00000020,
		CHARACTER_CONSTANT_CHAR = 0x00000040,
		STRING_LITERAL_CHAR =  0x00000080,
		PUNCTUATOR_CHAR = 0x00000100,
		EOL_CHAR = 0x00000200,
		EOF_CHAR = 0x00000400,
		WHITESPACE_CHAR = 0x00000800,
		OPERATOR_CHAR = 0x00001000,
	};
};


class sh_ctype
{
private:
	int ctypeTable[256];
public:
	void clear()
	{
		//清除
		for (int i = 0; i < 256;  ++ i)
		{
			ctypeTable[i] = SH_CHARACTER_TYPE::ILLIGAL_CHAR;
		}
	}
	sh_ctype()
	{
		clear();
		
		setCtype('a', 'z', SH_CHARACTER_TYPE::NON_DIGITAL_CHAR);
		setCtype('A', 'Z', SH_CHARACTER_TYPE::NON_DIGITAL_CHAR);

		setCtype('0', '9', SH_CHARACTER_TYPE::DIGITAL_CHAR);
		
		setCtype('0', '9', SH_CHARACTER_TYPE::INTEGER_CONSTANT_CHAR);
		setCtype('x', SH_CHARACTER_TYPE::INTEGER_CONSTANT_CHAR);
		setCtype('X', SH_CHARACTER_TYPE::INTEGER_CONSTANT_CHAR);
		setCtype('u', SH_CHARACTER_TYPE::INTEGER_CONSTANT_CHAR);
		setCtype('U', SH_CHARACTER_TYPE::INTEGER_CONSTANT_CHAR);
		setCtype('l', SH_CHARACTER_TYPE::INTEGER_CONSTANT_CHAR);
		setCtype('L', SH_CHARACTER_TYPE::INTEGER_CONSTANT_CHAR);
		
		
		setCtype('0', '9', SH_CHARACTER_TYPE::FLOATING_CONSTANT_CHAR);
		setCtype('e', SH_CHARACTER_TYPE::FLOATING_CONSTANT_CHAR);
		setCtype('E', SH_CHARACTER_TYPE::FLOATING_CONSTANT_CHAR);
		setCtype('l', SH_CHARACTER_TYPE::FLOATING_CONSTANT_CHAR);
		setCtype('L', SH_CHARACTER_TYPE::FLOATING_CONSTANT_CHAR);
		setCtype('f', SH_CHARACTER_TYPE::FLOATING_CONSTANT_CHAR);
		setCtype('F', SH_CHARACTER_TYPE::FLOATING_CONSTANT_CHAR);

		//标点符号字符
		setCtype(0x21,0x2F, SH_CHARACTER_TYPE::PUNCTUATOR_CHAR);
		setCtype(0x3a,0x40, SH_CHARACTER_TYPE::PUNCTUATOR_CHAR);
		setCtype(0x5B,0x60, SH_CHARACTER_TYPE::PUNCTUATOR_CHAR);

		//空白字符
		setCtype(0x20, SH_CHARACTER_TYPE::WHITESPACE_CHAR);
		setCtype(0x09, 0x0D, SH_CHARACTER_TYPE::WHITESPACE_CHAR);

		setCtype('+', SH_CHARACTER_TYPE::OPERATOR_CHAR);
	}
	
	//断定是否是某种类型
	bool assert(char ch, SH_CHARACTER_TYPE::CHARACTER_TYPE type)
	{
		if ((getCtype(ch)&type) == type)
		{
			return true;
		}
		return false;
	}

	void setCtype(char from, char to, SH_CHARACTER_TYPE::CHARACTER_TYPE type)
	{
		for (char ch = from; ch <= to ; ++ ch)
		{
			ctypeTable[ch] = ctypeTable[ch]|type;
		}
	}

	void setCtype(char ch, SH_CHARACTER_TYPE::CHARACTER_TYPE type)
	{
		ctypeTable[ch] = ctypeTable[ch]|type;
	}

	int getCtype(char ch)
	{
		return ctypeTable[ch];
	}
};

bool bIsRightAttach(char  ch)
{
	if (ch == '=')
	{
		return true;
	}
	return false;
}
int getLevel(char ch)
{
	switch(ch)
	{
	case ',':
		return 0;
	case '=':
		return 1;
	case '|': 
	    return 2;
	case '^':
		return 3;

	case '>': case '<':
		return 5;
	case '+' : case '-':
		return 6;
	case '*': case '/':
		return 7;
	case '&':
		return 8;
	case '.':
		return 9;
	default:
		return INT_MAX;

	}
}

static int const INVALID = 0;
static int const EXPRESSION = 0x0001;
static int const LVALUE = 0x0002;
static int const OPERATOR_LEFT = 0x0004;
static int const OPERATOR_RIGHT = 0x0008;

int main(int argc, char* argv[])
{
	sh_ctype ct;
	Node* pHead = NULL;
	Node* preTreeOperator = NULL;
	char ch;
	while (cin.get(ch) && ch != '\n')
	{
		//如果目前没有操作子Tree
		if (preTreeOperator == NULL)
		{
			preTreeOperator = new Node(ch);
			preTreeOperator->m_priority_level = getLevel(ch);
			pHead = preTreeOperator;
			continue;
		}
		else
		{
		   Node* no = new Node(ch);
		   no->m_priority_level = getLevel(ch);
		   Node* theTree = preTreeOperator;

		   //头节点的优先级为INTMAX（说明是标识符，而不是操作符），
		   //并且新节点的优先级也是INTMAX（说明是标识符，而不是操作符），
		   //那么说明两个叶子相邻，因此报错。
		   if(pHead->m_priority_level == no->m_priority_level
			   && pHead->m_priority_level == INT_MAX)
		   {
				std::cout<<"Unkown symbol "<<"\""<<ch<<"\"";
				system("PAUSE");
				return;
		   }

			
		   if (no->m_priority_level < pHead->m_priority_level)
		   {

				 pHead->m_pParent = no;
				 no->m_pLeftChild = pHead;
				 pHead = no;
				 preTreeOperator = no;
				 continue;
		   }
		   else
		   {
			   //优先级相等的情况下
			   if(no->m_priority_level == pHead->m_priority_level)
			   {
					//左结合，先算左边，因此左边优先级比右边优先级高。
				    //no插在pHead之上，pHead作为no的左节点。
					if (!bIsRightAttach(ch))
					{
							
						//设置左节点
						no->m_pLeftChild = pHead;
						//设置父节点
						pHead->m_pParent = no;

						//保存新的pHead 和 preTreeOperator
						pHead = no;
						preTreeOperator = no;
						continue;
					}
					else
					{
						/************************************************************************/
						/*右结合，先算右边。也就是说，右边优先级比左边高。
						/no插在pHead 和 pHead->m_pRightChild之间。
						/pHead->m_pRightChild 从pHead的右边，设置到no的左边。                   */
						/************************************************************************/
						
						
						//设置父节点。
						no->m_pParent = pHead;
						//设置左节点
						no->m_pLeftChild = pHead->m_pRightChild;
						//连接pHead
						pHead->m_pRightChild = no;


						//保存新的preTreeOperator，头节点没有变化
						preTreeOperator = no;
						continue;
					}
			   }
		   }

		   if(theTree->m_priority_level == no->m_priority_level
			   && theTree->m_priority_level == INT_MAX)
		   {
				std::cout<<"Unkown symbol "<<"\""<<ch<<"\"";
				system("PAUSE");
				return;
		   }

		   //找到一个theTree， 它优先级比no小。

		   //在优先级相等的情况下，如果是右结合，那么theTree就相当于优先级比no小。此时，循环应跳出。
		   //否则就相当于theTree优先级比no大，需要继续循环。
		   while (theTree!= NULL&& theTree->m_priority_level >= no->m_priority_level)
		   {
			   if (theTree->m_priority_level == no->m_priority_level)
			   {
				   if (bIsRightAttach(ch))
				   {
					   break;
				   }
				   else
				   {
					  theTree = theTree->m_pParent;
				   }
			   }
			   theTree = theTree->m_pParent;
		   }

		   if (theTree != NULL)
		   {
				no->m_pLeftChild = theTree->m_pRightChild;
				no->m_pParent = theTree;
				theTree->m_pRightChild = no;
				preTreeOperator = no;
		   }
		}
	}
	Tree tree;
	ExpressionVisiter vister;
	tree.setValue(pHead);
	tree.Inorder_Traversal(&vister);
	system("PAUSE");
}
#endif