/*
*改造parser()成功
*專心處理函數(shù)Createtab()來生成語法樹。
*/
/*2008-6-25
*處理函數(shù)時，local_size的值沒變化
*運(yùn)行時就沒有進(jìn)入全局變量處理的區(qū)域。
*/

/*2008-6-27
 *符號表成功完成，后繼步驟為靜態(tài)語義檢查和中間代碼生成。
 *有兩個疑問，
 *(1).一個是函數(shù)輸出時 entryAddr="0"，留著后面處理，留下了懸念
 *(2).<child varName="eee" varType="int" isArray="1" arraySize="1" Rva="4" />
 *中的arraySize = "1",表示其為一維數(shù)組。 還是什么？
 *
 *
*/

//在函數(shù)定義中，當(dāng)無參時，第一孩子為空，但第二孩子不空，不能使用if(T->child[0] == NULL) 為判空條件
//我們這里假設(shè)第一、第二為空則孩子節(jié)點(diǎn)為空 ，應(yīng)該if(T->child[0] == NULL && T->child[1] == NULL)

#include<iostream>
#include<string>
#include<fstream>
using namespace std;

//typedef string NodeType ;
typedef string TokenType;
const int Max = 500;
const int Tab_length = 100;   //表的長度
class Tree;
class Token;
class Tree;
ifstream inFile;
ofstream outFile;
ofstream fout;

int blanks = 4;

//-------------------------------------class Token-------------------------------------------------------
class Token    //用來讀詞法分析生成的東西
{
public:
 string str;   //單詞字符串  
 TokenType ttype; //單詞的類型
 int line;           //所在的行數(shù)
public:
 Token();
 ~Token();
};
Token::Token()
{
 str  = "";
 ttype = "";
 line = -1;
}
Token::~Token()
{}
//-----------------------------------class TreeNode------------------------------------------------------

class TreeNode
{
private:
 friend class Tree;

 int    lineno;
 TreeNode  *child[5];
 TreeNode  *sibling; //兄弟節(jié)點(diǎn)
 string   ntype; //節(jié)點(diǎn)類型 FunDecl .VarDel,
 string   nodestr; //保存標(biāo)識符的名稱，便于在語法樹中顯示
 string   vartype; //用于標(biāo)明變量類型int char float
 string   rettype; //函數(shù)返回類型void int char float   
 int    isarray;
public:
 TreeNode();

 ~TreeNode(){};
};
TreeNode::TreeNode()
{
 lineno  = -1;
 child[0] = NULL;
 child[1] = NULL;
 child[2] = NULL;
 child[3] = NULL;
 child[4] = NULL;
 sibling  = NULL;
 ntype  = "";
 nodestr  = "";
 vartype  = "";
 rettype  = "";
 isarray  = -1;
}

Token TokenArray[Max];
Token token;
int totalline = 0;
int varline   = 0;
//--------------------------------------class Tree----------------------------------------------------------
class Tree
{
private:
 TreeNode* root;
public:

 Tree(){root = NULL;};
 void parser();
 void match(TokenType);
 Token getNextToken();
 Token Restore(int) ;        //輸入curline = varline，修改varline值用于回退(恢復(fù)現(xiàn)場),并返回一個Token對象
 int  getFirstSpecifier(int pos);    //如果返回1，表示為函數(shù)申明，找第一個界符
 void ParserError(string ,int);
 TreeNode* program();    //建立和返回一棵語法樹
 TreeNode* fun_decl();
 TreeNode* var_decl();
 TreeNode* param_list();
 TreeNode* compound_stmt();
 TreeNode* statement();
 TreeNode* if_stmt();
 TreeNode* while_stmt();
 TreeNode* return_stmt();
 TreeNode* exp_stmt();
 TreeNode* expression();
 TreeNode* var();
 TreeNode*   assign_exp();
 TreeNode* simple_exp();
 TreeNode* additive_exp();
 TreeNode* term();
 TreeNode* factor();
 TreeNode* assign_exp(TreeNode*);
 TreeNode*   funcall(TreeNode*);
 TreeNode*   arg_list();

 void printNodeInfo(TreeNode *); 
 void DispTree(TreeNode *);
 //*************************************************************************************
 void    CreateTab();
 void processVar(TreeNode* );
 void    processFun(TreeNode* );
 void PrintTable();
 

 void DestroyTree(TreeNode *);
 void    Final();                        //調(diào)用DestroyTree()。
 void    blanksPlus();                   //用來設(shè)置xml 格式，加空格
 void blanksMinus();                 //減空格
 void    blanksPrint();

 ~Tree(){};
};

//*****************************************************************************************
class Vartable   //變量符號表
{
public:
 string var_name ;  //變量名
 string var_type;  //變量類型
 int isarray;    //數(shù)組標(biāo)拭
 int array_size; //數(shù)組大小
 int rva;   //偏移量，相對于前面的變量而言
};
class Funtable   //函數(shù)符號表
{
public:
 int fun_id;   //函數(shù)標(biāo)拭符
 string fun_name;    //函數(shù)名
 string rt_type;    //函數(shù)返回類型
 int para_size;   //函數(shù)中參數(shù)的占的空間大小
 int local_size;   //函數(shù)中變量占的空間
 int entry_address;  //函數(shù)入口的地址
 int para_list;       //參數(shù)的入口地址
 int local_list;  //變量的入口地址
};
Vartable vartable[Tab_length];
Vartable grobalvartable[Tab_length];
Funtable funtable[Tab_length];

int funlen = 0;   //函數(shù)表的長度
int varlen = 0;   //local變量表的長度
int gvarlen = 0;   //grobal變量表的長度
int globa_num = 0;//全局變量的個數(shù)
int para_num = 0;  //函數(shù)參數(shù)的個數(shù)
int var_num;  //函數(shù)局部變量的個數(shù)
int para_address = -1;  //參數(shù)的入口地址
int var_address = -1;  //變量的入口地址

//-----------------------------groble variable---------------------------------------------

//------------------------------------main()-----------------------------------------------------
int main()
{
 inFile.open("scanner.txt");
 if(!inFile.is_open())
 {
  cout<<"Can't open the input file!"<<endl;
  cin.get();
  exit(EXIT_FAILURE);
 }
 outFile.open("parser.xml");
 int ltemp = 0;
 TokenType ttemp = "";
 string    ntemp = "";
 //---------------------------Token op--------------------------
 int i = 0;
 inFile>>ltemp>>ttemp>>ntemp;
 while(!inFile.eof())
 {
  TokenArray[i].line = ltemp;
  TokenArray[i].ttype = ttemp;
  TokenArray[i].str = ntemp;
  i ++;
  inFile>>ltemp>>ttemp>>ntemp; 
 }
 totalline = i  ;   

 //---------------------------construct tree--------------------------

 Tree tree;
 tree.parser();
 tree.CreateTab();

 tree.Final();

 system("pause");
 return 0;
}

void Tree::ParserError(string errinfo,int lineno)
{

 outFile<< errinfo <<" at line "<<lineno<<endl;
 cin.get();
 exit(0);
}

void Tree::match(TokenType expected)
{ 
 if(token.ttype == expected)
  token = getNextToken();
 else
  ParserError((expected +" expected"),token.line);
}

Token Tree::getNextToken()
{//此處不設(shè)定結(jié)束條件，varline < totalline + 1   調(diào)用處設(shè)定 
 int i = varline;
 varline ++;
 return TokenArray[i];
}

Token Tree::Restore(int curline)  //記住當(dāng)前位置，用于恢復(fù)現(xiàn)場 
{
 varline = curline;
 return TokenArray[varline - 1];
}

int  Tree::getFirstSpecifier(int pos)
{ 
 int j = pos ;
 while(j < totalline)
 { 
  if(TokenArray[j].ttype == "LPAREN")
   return 1;
  else if(TokenArray[j].ttype == "SEMI" || TokenArray[j].ttype == "COMMA")
   return 0;
  else if(TokenArray[j].ttype == "LSQUAR" || TokenArray[j].ttype == "RSQUAR")
   return 0;
  else if(TokenArray[j].ttype == "LBRACE" || TokenArray[j].ttype == "RBRACE")
   return 0;
  else if(TokenArray[j].ttype == "PLUS" || TokenArray[j].ttype == "MINUS")
   return 0;
  else if(TokenArray[j].ttype == "STAR" || TokenArray[j].ttype == "DIV")
   return 0;
  else if(TokenArray[j].ttype == "ASSIGN" || TokenArray[j].ttype == "EQ")
   return 0;
  else if(TokenArray[j].ttype == "LT" || TokenArray[j].ttype == "GT")
   return 0;
  else if(TokenArray[j].ttype == "LTEQ" || TokenArray[j].ttype == "GTEQ")
   return 0;
  j++;  
 }
 return 0;
}

void Tree::parser()
{ outFile<<"<?xml version=\"1.0\"?>"<<endl;
outFile<<"<root>"<<endl;
token = getNextToken();
root = program();
DispTree(root);

outFile<<"</root>"<<endl;
}

//1) program →  { var-declaration | fun-declaration  }
/*從program()開始，進(jìn)行語法分析，構(gòu)建語法樹。一個program是由多個全局變量聲明或者普通函數(shù)定義或者類定義構(gòu)成的；
* 分別將一個全局變量、一個函數(shù)定義構(gòu)造為一棵語法樹。
* 結(jié)構(gòu)如下： 全局變量聲明 --> 子函數(shù)1 --> 主函數(shù)
* var-declaration → int [ID-list | array-list] ;
* fun-declaration →  type-specifier ID( params ) compound-stmt
* type-specifier → int | void
*/

TreeNode* Tree::program()         //建立和返回一棵語法樹
{ 
 TreeNode *root ;
 TreeNode *p ;
 TreeNode *q ;
 if(varline < totalline + 1)  //結(jié)束條件為varline < total + 1,原因可以看我筆記本上的講解 
 {
  if(getFirstSpecifier(varline - 1) == 1)    //減1的原因與varline 有關(guān)，理由同上
   root = fun_decl(); //函數(shù)定義
  else
   root = var_decl(); //全局變量的聲明 

  p = root;  //記錄根節(jié)點(diǎn)
  while(p->sibling != NULL)
   p = p->sibling; 

  while(varline < totalline + 1) //可能由多個部分組成；文件末尾由varline = totalline + 1標(biāo)志，原因可以看我筆記本上的講解
  { 
   if(getFirstSpecifier(varline - 1) == 1) //函數(shù)聲明
    q = fun_decl(); //函數(shù)定義
   else
    q = var_decl(); //全局變量的聲明

   p->sibling = q; //設(shè)置兄弟節(jié)點(diǎn)；從這里可以表明全局變量與函數(shù)定義之間是同級關(guān)系
   while(p->sibling != NULL)
    p=p->sibling;
  }
 }
 return root;
}

/*4) var-declaration→int ID-list;| int array-list;
/*10) ID-list → ID, | ID-list ID | empty  //可以聲明多個變量
11) array-list → ID[NUM] | array-list[NUM]  //多維數(shù)組
* 變量聲明可能為簡單變量或者數(shù)組變量；構(gòu)建語法節(jié)點(diǎn)：
* 簡單變量的屬性信息有數(shù)據(jù)類型、類型修飾符、變量名、是否數(shù)組；
* 對于數(shù)組變量，可以將數(shù)組大小表示為節(jié)點(diǎn)的屬性信息，也可以用子節(jié)點(diǎn)來表示；這里采用第二種方法。
* 后面的語義判斷時，如果判斷到node.IsArray=0,表明不是數(shù)組變量；node.IsArray=1,表明是數(shù)組變量，其數(shù)組大小由node.child[0]指示；
*/
//實現(xiàn)了 多個變量的聲明； 多維數(shù)組尚未實現(xiàn)

TreeNode* Tree::var_decl()
{ 
 TreeNode *vardeclNode   = NULL;
 TreeNode *nextNode      = NULL;
 TreeNode *curNode       = NULL;   
 string tmpvartype = "";           //僅用來存 int    
 //用while循環(huán)來依次構(gòu)造下一個變量；首先遇到int，然后遇到ID時進(jìn)行構(gòu)造變量節(jié)點(diǎn)，遇到‘，’表明是多個變量聲明，記錄前面的屬性信息，直接用于下一個類型節(jié)點(diǎn)的構(gòu)造；
 //返回的變量節(jié)點(diǎn)的第一個節(jié)點(diǎn)，后可能跟多個兄弟節(jié)點(diǎn)

 while(token.ttype != "SEMI")
 { 
  if(token.ttype == "INT")
  {
   tmpvartype = token.str;
   match(token.ttype);
  }
  else if(token.ttype == "ID")     //遇到變量，創(chuàng)建節(jié)點(diǎn)
  {
   nextNode = new TreeNode;
   nextNode->ntype = "VarDecl";
   nextNode->nodestr = token.str;
   nextNode->lineno = token.line;
   nextNode->vartype = tmpvartype;
   nextNode->isarray =0;
   nextNode->sibling = NULL;
   if(vardeclNode == NULL)
    vardeclNode = nextNode;
   else
    curNode->sibling = nextNode;
   curNode=nextNode;
   match(token.ttype);
  }
  else if(token.ttype == "LSQUAR") //數(shù)組變量
  {
   match("LSQUAR");
   curNode->isarray = 1;
   if(token.ttype == "NUM")  //需要擴(kuò)展為是表達(dá)式的情況
   {       
    TreeNode* sizeNode = new TreeNode();
    sizeNode->ntype = "ConstID";
    sizeNode->nodestr = token.str;
    sizeNode->lineno = token.line;
    curNode->child[0] = sizeNode;
    match("NUM");
   }
   else  
    ParserError("Array var Declaration error",token.line);
   match("RSQUAR"); 
  }
  else if(token.ttype == "COMMA")       //匹配“，”，用來構(gòu)成ID-list → ID, | ID-list ID | empty 
   match(token.ttype);           // array-list → ID[NUM] | array-list[NUM] 
  else
   ParserError("uninterpreted token",token.line);
 }

 match("SEMI");
 return vardeclNode; 

}

/*5) fun-declaration→  type-specifier ID( params ) compound-stmt
type-specifier → int| void
18) params → param-list | void
19) param-list→ param{,param}
20) param→  int ID |int ID[ ]
21) compound-stmt→ { local-declarations   statement-list }
22) local-declarations→  var-declaration |empty
23) statement-list→  statement∣empty
24) statement→ expression-stmt∣compound-stmt∣selection-stmt∣iteration-stmt | return-stmt
*/  /* 函數(shù)定義節(jié)點(diǎn)，屬性信息包括返回類型，函數(shù)名，它的第一個子節(jié)點(diǎn)指向參數(shù)列表，第二個子節(jié)點(diǎn)指向函數(shù)體
*/
TreeNode* Tree::fun_decl()
{
 TreeNode* fundeclNode = new TreeNode();
 fundeclNode->ntype = "FunDecl";

 while(token.ttype != "LPAREN")
 { 
  if(token.ttype == "INT" ||token.ttype == "VOID")
  {
   fundeclNode->rettype = token.str;
   match(token.ttype);
  }
  else if( token.ttype == "ID")
  {
   fundeclNode->nodestr = token.str;
   fundeclNode->lineno = token.line;

   match(token.ttype);   
  }
  else
   ParserError("uninterpreted token",token.line);
 }

 match("LPAREN"); 
 if(token.ttype != "RPAREN")   //匹配參數(shù)列表，構(gòu)造第一個子節(jié)點(diǎn)
 {
  TreeNode* paramsNode = param_list();
  fundeclNode->child[0] = paramsNode;
 }

 match("RPAREN");
 TreeNode* stmtNode = compound_stmt(); //函數(shù)體，第二個子節(jié)點(diǎn)
 fundeclNode->child[1] = stmtNode;
 return fundeclNode;
}

// params → param { , param } | void
// param →int ID [ [ ] ]
TreeNode* Tree::param_list()
{ 
 if(token.ttype == "VOID")
 {
  match("VOID");
  return NULL;
 }
 TreeNode* paramNode = NULL;
 TreeNode* curNode = NULL;
 TreeNode* tmpNode = NULL;
 while(token.ttype != "RPAREN") //參數(shù)列表中不要出現(xiàn)函數(shù)調(diào)用的情況；不然可能會出錯
 { 
  if(token.ttype == "INT")
  {
   curNode = new TreeNode();
   curNode->ntype = "Para";
   curNode->vartype = token.str;
   match(token.ttype);
  }

  if(token.ttype == "ID")
  {
   if(curNode == NULL) //當(dāng)前節(jié)點(diǎn)為空，表示該id是類型   for example :fun()
   {
    curNode = new TreeNode();
    curNode->ntype = "Para";
    curNode->vartype = token.str; //這里表明該id是類型
   }
   else //否則，是參數(shù)變量名                       for example :fun(int a)
   {
    curNode->nodestr = token.str;
    curNode->lineno = token.line;
    curNode->isarray = 0;
   }
   match("ID");
  }

  else if(token.ttype == "LSQUAR")  //函數(shù)定義中參數(shù)列表，參數(shù)是數(shù)組的情況在這里處理； 
  { match("LSQUAR");
  curNode->isarray = 1;
  //數(shù)組大小為空，表示參數(shù)為數(shù)組類型，其大小由傳進(jìn)參數(shù)確定
  if(token.ttype != "RSQUAR")  
   ParserError("fun para array error, should not appoint the size of array when in para",token.line);
  match("RSQUAR"); 
  } 
  else if(token.ttype == "COMMA") //表明多個參數(shù)
  {
   if(curNode == NULL)
    ParserError("function para error",token.line);
   if(paramNode == NULL)
    paramNode = curNode;
   else
    tmpNode->sibling = curNode;
   tmpNode = curNode;
   match("COMMA");
  }
  else
   ParserError("para error",token.line);
 }

 if(paramNode == NULL)
  paramNode = curNode;
 else
  tmpNode->sibling = curNode;
 return paramNode;
}

// 14) compound-stmt→ { local-declarations statement-list }
// 16) local-declarations → { var-declaration }
// 18) statement-list → { statement }
/* 復(fù)合語句，將為每一條語句構(gòu)建一個語法節(jié)點(diǎn)，不論該語句是用于局部變量聲明還是程序語句；
* 這樣，返回第一條語句的節(jié)點(diǎn)指針，其它語句依次作為兄弟節(jié)點(diǎn)鏈接起來。
* 注意：這里的實現(xiàn)中，將多個局部變量聲明語句的處理放到了local_declar()函數(shù)中，
* 而將多條程序執(zhí)行語句關(guān)系的處理放在函數(shù)compound_stmt()中；statement()只是用來處理單條程序語句。
*/
TreeNode* Tree::compound_stmt()
{
 TreeNode* stmtNode = NULL, *tmpNode = NULL,  *curNode = NULL;
 match("LBRACE");
 while(token.ttype != "RBRACE")
 {
  if(token.ttype == "INT")  
   tmpNode = var_decl();
  else
   tmpNode = statement();   
  if(stmtNode == NULL)
  {
   stmtNode = tmpNode; 
   curNode = tmpNode;
  }
  else
   curNode->sibling = tmpNode;
  while( curNode->sibling != NULL )
   curNode = curNode->sibling;
 }
 match("RBRACE");
 return stmtNode;
}

// 19) statement→ expression-stmt∣compound-stmt∣selection-stmt∣iteration-stmt∣return-stmt
TreeNode* Tree::statement()
{
 TreeNode* stmtNode = NULL;
 if(token.ttype == "LBRACE")
  stmtNode = compound_stmt();
 else if(token.ttype == "IF")
  stmtNode = if_stmt();
 else if(token.ttype == "WHILE")
  stmtNode = while_stmt();
 else if(token.ttype == "RETURN")
  stmtNode = return_stmt();
 else
  stmtNode = exp_stmt();
 return stmtNode;
}

// 23) selection-stmt → if ( expression ) statement [ else statement ]
/* 對于if語句，根節(jié)點(diǎn)是if，第一個孩子節(jié)點(diǎn)表示條件，第二個孩子節(jié)點(diǎn)是條件為真的時候的執(zhí)行語句，
* 第三個孩子節(jié)點(diǎn)是else部分的執(zhí)行語句（如果有的話）
*/
TreeNode* Tree::if_stmt()
{ 
 TreeNode* ifNode = new TreeNode();
 ifNode->nodestr = "if";
 ifNode->lineno = token.line;
 match("IF"); //if
 match("LPAREN"); //(  
 ifNode->child[0] = expression(); //判斷條件
 match("RPAREN"); //)
 if(token.ttype == "LBRACE")
  ifNode->child[1] = compound_stmt(); //條件為真的時候的執(zhí)行語句，這里應(yīng)該可能有多條語句
 else
  ifNode->child[1] = statement();
 if(token.ttype == "ELSE")
 {
  match(token.ttype); //else
  ifNode->ntype = "IfElseStm";
  if(token.ttype == "LBRACE")
   ifNode->child[2] = compound_stmt(); //條件為真的時候的執(zhí)行語句，這里應(yīng)該可能有多條語句
  else
   ifNode->child[2] = statement();
 }
 else
  ifNode->ntype = "IfStm";
 return ifNode;
}

// 24) iteration-stmt→ while( expression ) statement
TreeNode* Tree::while_stmt()
{
 TreeNode* whileNode = new TreeNode();
 whileNode->ntype = "WhileStm";
 whileNode->nodestr = "while";
 whileNode->lineno = token.line;
 match("WHILE"); //while
 match("LPAREN"); //(   
 whileNode->child[0] = expression();
 match("RPAREN"); //)
 whileNode->child[1] = statement();
 return whileNode;
}

// 27) return-stmt → return [expression] ;
/* return語句，如果有返回值，則將返回值作為return節(jié)點(diǎn)的第一個孩子節(jié)點(diǎn) */
TreeNode* Tree::return_stmt()
{
 TreeNode*  returnNode = new TreeNode();
 returnNode->ntype = "ReturnStm";
 returnNode->nodestr = "return";
 returnNode->lineno = token.line;
 match("RETURN"); //return   
 if(token.ttype != "SEMI")
  returnNode->child[0] = expression();
 match("SEMI");
 return returnNode;
}

// 21) expression-stmt → [ expression ] ;
TreeNode* Tree::exp_stmt()
{
 TreeNode* expNode = NULL;
 if(token.ttype != "SEMI")
 {
  expNode = expression();
 }
 match("SEMI");
 return expNode;   
}

// 28) expression→ var = expression | simple-expression
/* 表達(dá)式分兩種情況：賦值表達(dá)式or簡單表達(dá)式；兩種情況都由可能是以var開頭；
* 我們需要進(jìn)行前向搜索以決定是哪一種表達(dá)式。
* head(assign-exp) --> head(var)
* head(simple-exp) --> head(additive-exp) --> head(term)
*     --> head(factor) --> head(var)
* 其中：head(var) --> ID  以及  head(call) --> ID
*/

TreeNode* Tree::expression()
{ 
 TreeNode* varNode = NULL;
 TreeNode* expNode = NULL;
 if(token.ttype == "ID")
 {
  int curline;
  curline = varline;
  varNode = var();
  if(token.ttype == "ASSIGN")
   expNode = assign_exp(varNode);
  else
  {
   token = Restore(curline);   //恢復(fù)現(xiàn)場
   expNode = simple_exp();
  }
 }
 else
  expNode = simple_exp();
 return expNode;
}

/*17) var→ID | ID[expression] */
TreeNode* Tree::var()
{ 
 TreeNode* varNode = NULL;

 varNode = new TreeNode();
 varNode->nodestr = token.str;
 varNode->lineno = token.line;
 match("ID");
 varNode->ntype = "VarID";

 if(token.ttype == "LSQUAR")  //數(shù)組的情況
 {
  match("LSQUAR");
  if(token.ttype != "RSQUAR")
  {
   varNode->child[0] = expression();
   varNode->isarray = 1;
  }
  match("RSQUAR");
 }
 else
  varNode->isarray = 0;
 return varNode;
}

// 34) simple-expression→ additive-expression [ relop additive-expression]
// 35) relop→ < | <= | > | >= | == | !=
/* 對于簡單表達(dá)式，根節(jié)點(diǎn)是關(guān)系操作符，左邊的表達(dá)式構(gòu)成第一個孩子節(jié)點(diǎn)，
* 右邊的表達(dá)式構(gòu)成第二個孩子節(jié)點(diǎn)（如果存在的話） 
*/
TreeNode* Tree::simple_exp()
{
 TreeNode* simpleExpNode = NULL;
 TreeNode* additiveExpNode = NULL;
 additiveExpNode = additive_exp();
 if(token.ttype == "LT" || token.ttype == "LTEQ"||token.ttype == "GT"
  ||token.ttype =="GTEQ" || token.ttype == "NEQ" || token.ttype =="EQ")
 {
  simpleExpNode = new TreeNode();

  if(token.ttype == "LT")
   simpleExpNode->ntype = "RLT" ;
  else if(token.ttype == "LTEQ")
   simpleExpNode->ntype = "RNGT";
  else if(token.ttype == "GT")
   simpleExpNode->ntype = "RGT";
  else if(token.ttype =="GTEQ")
   simpleExpNode->ntype = "RNLT";
  else if(token.ttype == "EQ")
   simpleExpNode->ntype = "REQ";
  else if(token.ttype == "NEQ")
   simpleExpNode->ntype = "RNEQ";
  else
   simpleExpNode->ntype = "ERROR";
  simpleExpNode->nodestr = token.str;
  simpleExpNode->lineno = token.line;
  simpleExpNode->child[0] = additiveExpNode; 
  match(token.ttype);
  simpleExpNode->child[1] = additive_exp();
 }
 else
  simpleExpNode = additiveExpNode;
 return simpleExpNode;
}

/*assign-exp → var = expression | var = new ID ( args )
* 賦值語句的語法節(jié)點(diǎn)構(gòu)造：根節(jié)點(diǎn)為賦值號，第一個子節(jié)點(diǎn)為賦值號左邊的表達(dá)式，
* 第二個子節(jié)點(diǎn)直線賦值號右邊的表達(dá)式
*/
TreeNode* Tree::assign_exp(TreeNode*  varNode)
{
 TreeNode* assignNode = new TreeNode();   
 assignNode->ntype = "AssignStm";
 assignNode->nodestr = "=";
 assignNode->lineno = token.line;
 match("ASSIGN");
 assignNode->child[0] = varNode;
 assignNode->child[1] = expression();
 return assignNode;
}

// 39) additive-expression → term { ( + | - ) term }
TreeNode* Tree::additive_exp()
{
 TreeNode* additiveExpNode = NULL;
 additiveExpNode = term();

 while(token.ttype == "PLUS" || token.ttype == "MINUS")
 {
  TreeNode* tempNode = new TreeNode();
  if(token.ttype == "PLUS")
   tempNode->ntype = "ADD";
  else if(token.ttype == "MINUS")
   tempNode->ntype = "SUB";
  else
   tempNode->ntype = "ERROR";
  tempNode->nodestr = token.str;
  tempNode->lineno = token.line;
  tempNode->child[0] = additiveExpNode;
  match(token.ttype);

  tempNode->child[1] = term();
  additiveExpNode = tempNode;
 }
 return additiveExpNode;
}

// 43) term → factor { ( * | / ) factor }
TreeNode* Tree::term()
{
 TreeNode* termNode = NULL;
 termNode = factor();
 while(token.ttype == "STAR" || token.ttype == "SLASH")
 {
  TreeNode* tempNode = new TreeNode();
  if(token.ttype == "STAR")
   tempNode->ntype = "MUL";
  else if(token.ttype == "SLASH")
   tempNode->ntype = "DIV";
  else
   tempNode->ntype = "ERROR";
  tempNode->nodestr = token.str;
  tempNode->lineno = token.line;
  tempNode->child[0] = termNode; 
  match(token.ttype);
  tempNode->child[1] = factor();
  termNode = tempNode;
 }
 return termNode;
}

// 44) factor→ ( expression )| var | call | NUM
TreeNode* Tree::factor()
{
 TreeNode*  factorNode = NULL;
 if(token.ttype == "LPAREN")
 {
  match("LPAREN");
  factorNode = expression();
  match("RPAREN");
 }
 else if(token.ttype == "NUM")
 {
  factorNode = new TreeNode();
  factorNode->ntype = "ConstID";
  factorNode->nodestr = token.str;
  factorNode->lineno = token.line;
  match(token.ttype);
 }
 else if(token.ttype == "ID")
 {
  TreeNode* varNode = var();
  if(token.ttype == "LPAREN")
  {
   factorNode = funcall(varNode);                            
  }
  else
   factorNode = varNode;
 }
 return factorNode;
}

//45) call→ ID( arg_list )
TreeNode* Tree::funcall(TreeNode* varNode)
{
 TreeNode* funCallNode = varNode;
 if(varNode->child[0] != NULL)
  varNode = varNode->child[0];
 varNode->ntype = "FunCall";
 varNode->isarray = -1;
 match("LPAREN");
 varNode->child[0] = arg_list();
 match("RPAREN");
 return funCallNode;

}

// 46) args→ arg-list | empty
// 47) arg-list → expression arg-list’
// 48) arg-list’→ , expression arg-list’| null
// 49) args → [ expression { , expression } ]
TreeNode* Tree::arg_list()
{
 if(token.ttype == "RPAREN") //參數(shù)為空的情況
  return NULL;
 TreeNode* argNode = expression();
 TreeNode* tempNode = argNode;
 while(token.ttype == "COMMA")
 {
  match("COMMA");
  if(tempNode != NULL)
  {
   tempNode->sibling = expression();
   tempNode = tempNode->sibling;
  }
 }
 return argNode;
}

void Tree::printNodeInfo(TreeNode* T)
{
 if(T != NULL)
 {
  outFile<<"<tree line =\""<<T->lineno<<"\" nodetype =\""<<T->ntype<<"\" nodestring=\""<<T->nodestr<<"\"";
  if(T->vartype != "")
   outFile<<" vartype=\""<<T->vartype<<"\"";
  if(T->rettype != "")
   outFile<<" rettype=\""<<T->rettype<<"\"";
  if(T->isarray == 0 || T->isarray == 1)
   outFile<<" isarray=\""<<T->isarray<<'\"';
 }

}

void Tree::DispTree(TreeNode * T)
{ 

 if(T != NULL)
 { 
  blanksPrint();
  printNodeInfo(T);

  if(T->child[0] == NULL && T->child[1] == NULL)   ////在函數(shù)定義中，當(dāng)無參時，第一孩子為空，但第二孩子不空，我們這里假設(shè)第一、第二為空則孩子節(jié)點(diǎn)為空
   outFile<<"/>"<<endl;
  else
   outFile<<'>'<<endl;

  for(int i = 0;i < 5;i ++)
   if(T->child[i] != NULL)
   { blanksPlus();/////////////////////////////////////////////////-----------------------------------
  blanksPrint();
  outFile<<"<child>"<<endl;
  blanksPlus();//*****************************************************
  DispTree(T->child[i]);
  blanksMinus();//**************************************************
  blanksPrint();
  outFile<<"</child>"<<endl;
  blanksMinus();//////////////////////////////////////////////------------------------------------
  }

  if(T->child[0] != NULL || T->child[1] != NULL)
  {
   blanksPrint(); 
   outFile<<"</tree>"<<endl;
  }

  DispTree(T->sibling);

 }
}

void Tree::DestroyTree(TreeNode *T)
{
 if(T != NULL)
 {
  DestroyTree(T->sibling);
  for(int i = 0;i < 5; i ++)  
   if(T->child[i] != NULL )
   {
    DestroyTree(T->child[i]);
   }

   delete T;
 } 
}

void Tree::Final()
{
 DestroyTree(root);

}

void Tree::blanksPlus()                   //用來設(shè)置xml 格式，加空格
{
 blanks = blanks + 4;
}
void Tree::blanksMinus()
{
 blanks = blanks - 4;
}
void Tree::blanksPrint()
{
 for(int i = 0;i < blanks;i ++)
  outFile<<' ';
}

//********************************************************************
void Tree::CreateTab()
{ 
 TreeNode* T = NULL;
 T = root;
 while(T != NULL)
 {
  if (T->ntype == "VarDecl")
  {//全局變量申明
   processVar(T);

  }
  else if (T->ntype == "FunDecl")
  {//函數(shù)申明
   processFun(T);

  }
  else
  {
   cout<<"undefined declaration."<<endl;
   break;
  }
  T = T->sibling;
 }
 PrintTable();

}

void Tree::processVar(TreeNode*  T)
{
 if(T->isarray)
  grobalvartable[gvarlen].isarray = 1;
 else
  grobalvartable[gvarlen].isarray = 0;
 grobalvartable[gvarlen].array_size = T->isarray;
 grobalvartable[gvarlen].var_name = T->nodestr;
 grobalvartable[gvarlen].var_type = T->vartype;
 grobalvartable[gvarlen].rva = gvarlen;  //偏移地址為變量的個數(shù)
 gvarlen++;  
 
 
}
 

void Tree::processFun(TreeNode* T)
{
 funtable[funlen].fun_id = funlen; 
 funtable[funlen].fun_name = T->nodestr;
 funtable[funlen].rt_type = T->rettype;
 funtable[funlen].entry_address=0;   //函數(shù)入口地址,代碼產(chǎn)生時再分配？？？？？？？？？？？？？？？？？？？
 
 //對參數(shù)進(jìn)行處理,處理的是變量表，某些信息保留到最后放入函數(shù)中
 TreeNode* tmpNode = T->child[0];
 while (tmpNode != NULL && tmpNode->ntype == "Para")
 {
  if(para_address == -1)
   para_address = varlen;    //第一個參數(shù)在符號表中的位置
  if(tmpNode->isarray)
   vartable[varlen].isarray = 1;
  else
   vartable[varlen].isarray = 0;
  vartable[varlen].array_size = tmpNode->isarray;
  vartable[varlen].var_name = tmpNode->nodestr;
  vartable[varlen].var_type = tmpNode->vartype;
  vartable[varlen].rva = para_num;   //偏移地址為參數(shù)的個數(shù)
  varlen++;
  para_num++;   //

  tmpNode = tmpNode->sibling;
 }

 //處理局部變量
 TreeNode* tmpvarNode = T->child[1];
 while (tmpvarNode != NULL && tmpvarNode->ntype == "VarDecl")
 {
  //cout<<"in local processer()----------------------------------"<<endl;
  if(var_address == -1)
   var_address = varlen;    //第一個變量在符號表中的位置
  if(tmpvarNode->isarray)
   vartable[varlen].isarray = 1;
  else
   vartable[varlen].isarray = 0;
  vartable[varlen].array_size=tmpvarNode->isarray;
  vartable[varlen].var_name = tmpvarNode->nodestr;
  vartable[varlen].var_type = tmpvarNode->vartype;
  vartable[varlen].rva = var_num;  //偏移地址為變量的個數(shù)
  varlen++;  
  var_num++;    //變量個數(shù)加一

  tmpvarNode = tmpvarNode->sibling;
 }

 //把某些參數(shù)回填到函數(shù)符號表中

 funtable[funlen].para_list = para_address;
 funtable[funlen].para_size = para_num;    //參數(shù)的個數(shù)
 funtable[funlen].local_list = var_address;
 funtable[funlen].local_size = var_num;    //變量的個數(shù)
 para_address = -1;
 var_address = -1;
 para_num = 0;
 var_num = 0;
 funlen++;

}
void Tree::PrintTable()
{ 
 fout.open("SymbolTable.xml");
 
 fout<<"<?xml version=\"1.0\"?>"<<endl;
 fout<<"<root>"<<endl;
 //輸出全局變量
 fout<<"    <grobalVar>"<<endl;
 for (int i = 0;i < gvarlen;i ++)
 {
  //輸出參數(shù)成分
  /*<grobalVar>
  * <child varName="a" varType="int" isArray="0" arraySize="0" Rva="0" />
  * <child varName="b" varType="int" isArray="0" arraySize="0" Rva="1" />
  *</grobalVar>
  */
  fout<<"        <child varName="<<'\"'<<grobalvartable[i].var_name<<'\"'<<' ';
  fout<<"varType="<<'\"'<<grobalvartable[i].var_type<<'\"'<<' ';
  fout<<"isArray="<<'\"'<<grobalvartable[i].isarray<<'\"'<<' ';
  fout<<"arraySize="<<'\"'<<grobalvartable[i].array_size<<'\"'<<' ';
  fout<<"Rva="<<'\"'<<grobalvartable[i].rva<<'\"'<<' '<<"/>";
  fout<<endl;
 }
 fout<<"    </grobalVar>"<<endl;

 //輸出函數(shù)部分
 for (int i = 0;i < funlen;i ++)
 {
  //<tree funID="1" funName="main" retType="void" entryAddr="0" paraVarSize="0" localVarSize="2" tryblockCount="0" unwindCount="0">
  fout<<"    <tree funID="<<'\"'<<funtable[i].fun_id<<'\"'<<' ';
  fout<<"funName="<<'\"'<<funtable[i].fun_name<<'\"'<<' ';
  fout<<"retType="<<'\"'<<funtable[i].rt_type<<'\"'<<' ';
  fout<<"entryAddr="<<'\"'<<funtable[i].entry_address<<'\"'<<' ';
  fout<<"paraVarSize="<<'\"'<<funtable[i].para_size<<'\"'<<' ';
  fout<<"localVarSize="<<'\"'<<funtable[i].local_size<<'\"'<<'>';
  fout<<endl;

  //輸出參數(shù)成分
  /*<paraVar>
  * <child varName="a" varType="int" isArray="0" arraySize="0" Rva="0" />
  * <child varName="b" varType="int" isArray="0" arraySize="0" Rva="1" />
  *</paraVar>
  */

  if (funtable[i].para_size != 0)
  {
   fout<<"        <paraVar>"<<endl;
   for(int j = funtable[i].para_list;j < funtable[i].para_list + funtable[i].para_size;j ++)
   {
    fout<<"            <child varName="<<'\"'<<vartable[j].var_name<<'\"'<<' ';
    fout<<"varType="<<'\"'<<vartable[j].var_type<<'\"'<<' ';
    fout<<"isArray="<<'\"'<<vartable[j].isarray<<'\"'<<' ';
    fout<<"arraySize="<<'\"'<<vartable[j].array_size<<'\"'<<' ';
    fout<<"Rva="<<'\"'<<vartable[j].rva<<'\"'<<' '<<"/>";
    fout<<endl;
   }
   fout<<"        </paraVar>"<<endl;
  }

  //輸出local成分
  // <child varName="d" varType="int" varModifier="" isArray="0" arraySize="0" Rva="0" />
  if (funtable[i].local_size != 0)
  {
   fout<<"        <localVar>"<<endl;
   for (int j = funtable[i].local_list;j < funtable[i].local_list + funtable[i].local_size;j ++ )
   {
   
   fout<<"            <child varName="<<'\"'<<vartable[j].var_name<<'\"'<<' ';
   fout<<"varType="<<'\"'<<vartable[j].var_type<<'\"'<<' ';
   fout<<"isarray="<<'\"'<<vartable[j].isarray<<'\"'<<' ';
   fout<<"arraySize="<<"\""<<vartable[j].array_size<<'\"'<<' ';
   fout<<"Rva="<<'\"'<<vartable[j].rva<<'\"'<<" />"<<endl;
   }
   fout<<"        </localVar>"<<endl;
  }
  fout<<"    </tree>"<<endl;

  
  
 }
 fout<<"</root>"<<endl;
 fout.close();
}