上一篇中介紹通過詞法分析將表達式轉換成TokenRecord對象列表。在第一篇中提到將表達式用樹形結構表示，然後就可以很方便的從下級 節點取值計算了。那麼如何將列表分析成一棵樹的結構呢？
還是以例子來說明，比如3*7+56/8-2*5，分析成TokenRecord列表就是
記號對象 對應表達式 TokenValue 3 TokenMultiply * TokenValue 7 TokenPlus + TokenValue 56 TokenDivide / TokenValue 8 TokenMinus - TokenValue 2 TokenMultiply * TokenValue 5分析成樹就是
根據實際的算術規則，運算符優先級高的要先計算，然後由低優先級的運算符去調用它的運算結果。表現在樹視圖上就是高優先級的節點是 低優先級節點的下級，即優先級越高，其位置越靠近樹葉。因為這裡采用統一的對象，把所有元素都用TokenRecord表示，所以TokenValue也是 有優先級的。而通過對樹視圖的分析，所有的TokenValue都是處在葉子的位置，則TokenValue的優先級最高。
分析到這裡就要用代碼實現了。這裡需要用到TokenRecord中的優先級Priority屬性，還要用到堆棧。和詞法分析一樣，也是需要用循環依 次分析各個TokenRecord。拿上面的TokenRecord列表進行分析，粗體字代表當前分析的TokenRecord。分析的過程中有一個原則叫“高出 低入原則”，需要解釋一下。
“高出低入原則”是指：
1.棧頂TokenRecord的優先級高於當前TokenRecord的優先級，則將棧頂TokenRecord彈棧（高出）到臨時變量。
1.1如果堆棧為空，將臨時變量中的TokenRecord加入當前TokenRecord的ChildList中，然後將當前TokenRecord壓棧（低入）。
1.2如果堆棧不為空，找出棧頂TokenRecord和當前TokenRecord中優先級高的一個（相同則按棧頂高算），將臨時變量中的TokenRecord加入 高優先級TokenRecord的ChildList中。再用高出低入原則處理棧頂和當前TokenRecord。
2.棧頂TokenRecord的優先級低於當前TokenRecord的優先級，則將當前TokenRecord直接壓棧。
可能文字表述的並不清晰，其中涉及到循環和遞歸的操作，具體的過程通過下面的例子來講解。
1.列表分析狀態：
TokenValue(3) TokenMultiplay TokenValue(7) …...堆棧分析：當前堆棧為空，將當前分析的TokenRecord壓棧。
TokenValue(3) 棧底堆棧對應樹視圖：
2.列表分析狀態：
TokenValue(3) TokenMultiply TokenValue(7) …...堆棧分析：棧頂為TokenValue，當前TokenRecord為TokenMultiply，TokenValue優先級最高。遵循高出低入原則，將TokenValue彈棧並添加 到TokenMultiply的ChildList中，然後將TokenMultiplay壓棧。
TokenMultiply 棧底堆棧對應樹視圖：
3.列表分析狀態
…... TokenMultiply TokenValue(7) TokenPlus …...堆棧分析：棧頂為TokenMultiplay，當前TokenRecord為TokenValue，TokenMultiply優先級高於TokenValue，則將TokenValue加入 TokenMultiplay的ChildList中。
TokenMultiply 棧底堆棧對應樹視圖：
4.列表分析狀態
堆棧分析：棧頂為TokenMultiply，當前TokenRecord為TokenPlus，TokenMultiply優先級高於TokenPlus。遵循高出低入原則，將 TokenMultiply彈棧並添加到TokenPlus的ChildList中，然後將TokenPlus壓棧。
TokenPlus 棧底堆棧對應樹視圖：
5.列表分析狀態
…… TokenPlus TokenValue(56) TokenDivide …...堆棧分析：棧頂為TokenPlus，當前TokenRecord為TokenValue，TokenPlus優先級低於TokenValue。遵循高出低入原則，不需要彈棧，直接 將TokenValue壓棧。
TokenValue(56) TokenPlus 棧底堆棧對應樹視圖：
6.列表分析狀態
…… TokenValue(56) TokenDivide TokenValue(8) …...堆棧分析：棧頂為TokenValue，當前TokenRecord為TokenDivide，TokenValue優先級高於TokenDivide。遵循高出低入原則，將TokenValue 彈棧並加入TokenDivide的ChildList中。此時棧頂為TokenPlus，TokenDivide優先級高於TokenPlus，遵循高出低入原則，將TokenDivide壓棧 。
TokenDivide TokenPlus 棧底堆棧對應樹視圖：
7.列表分析狀態
…… TokenDivide TokenValue(8) TokenMinus …...堆棧分析：棧頂為TokenDivide，當前TokenRecord為TokenValue，TokenDivide優先級高於TokenValue。遵循高出低入原則，將TokenValue 加入TokenDivide的ChildList中。
TokenDivide TokenPlus 棧底堆棧對應樹視圖：
8列表分析狀態
…… TokenValue(8) TokenMinus TokenValue(2) ……堆棧分析：棧頂為TokenDivide，當前TokenRecord為TokenMinus，TokenDivde優先級高於TokenMinus。遵循高出低入原則，將TokenDivide彈棧 到臨時變量。檢測到堆棧不為空，此時棧頂為TokenPlus，TokenPlus優先級和TokenMinus一樣。這裡相同優先級的按高優先級處理，遵循高出 低入原則，則將臨時變量中的TokenDivide加入高優先級TokenPlus的ChildList中。繼續用高出低入原則，將TokenPlus彈棧並加入TokenMinus 的ChildList中，再將TokenMinus壓棧。
TokenMinus 棧底
堆棧對應樹視圖：
9.列表分析狀態
…… TokenMinus TokenValue(2) TokenMultiply …...堆棧分析：棧頂是TokenMinus，當前TokenRecord是TokenValue，TokenMinus優先級低於TokenValue。遵循高出低入原則，將TokenValue壓 棧。
TokenValue(2) TokenMinus 棧底堆棧對應樹視圖：
10.列表分析狀態
…… TokenValue(2) TokenMultiply TokenValue(5)堆棧分析：棧頂是TokenValue，當前TokenRecord是TokenMultiply，TokenValue優先級高於TokenMultiply。遵循高出低入原則，將TokenValue 彈棧到臨時變量，檢測堆棧不為空，此時棧頂為TokenMinus，TokenMinus優先級低於TokenMultiply，則將臨時變量中的TokenValue加入 TokenMultiplay的ChildList中。遵循高出低入原則，將TokenMultiplay加入到棧頂TokenMinus的ChildList中。
TokenMultiply TokenMinus 棧底
堆棧對應樹視圖：
11.列表分析狀態
…… TokenValue(2) TokenMultiply TokenValue(5)堆棧分析：棧頂是TokenMultiply，當前是TokenValue，TokenMultiply優先級高於TokenValue。遵循高出低入原則，將TokenValue加入 TokenMultiply的ChildList中。
TokenMultiply TokenMinus 棧底堆棧對應樹視圖：
12.堆棧分析：此時列表分析結束，堆棧不為空，需要對堆棧進行處理。經過上面的堆棧分析，遵循高出低入原則，堆棧中的TokenRecord肯 定是棧底優先級最低，棧頂優先級最高。只需要將堆棧中的TokenRecord依次彈棧，然後加入到新棧頂的ChildList中即可。最後彈棧的一個 TokenRecord就是整個樹視圖的根節點，也就是返回值。到此，堆棧為空，也得到了預期的樹視圖，返回根節點TokenRecord即可。
上面是對語法分析整個流程的分析，下面給出具體的代碼。程序中的語法分析放在一個單獨的文件中，SyntaxTreeAnalyse.cs，文件中也只 有一個SyntaxTreeAnalyse類，專門用於語法樹的分析。這個類只有一個入口即一個公開方法SyntaxTreeGetTopTokenAnalyse，傳入 TokenRecord列表，經過分析後返回一個頂級TokenRecord對象，即樹形結構的根節點。具體代碼如下：
/// <summary>
/// 語法樹分析
/// </summary>
/// <remarks>Author:Alex Leo</remarks>
internal class SyntaxTreeAnalyse
{
/// <summary>
/// 記號段提取，提取頂級操作記號
/// </summary>
/// <param name="IndexStart">起始序號</param>
/// <param name="IndexEnd">結束序號</param>
/// <returns>傳入記號段的頂級操作記號記錄對象</returns>
/// <remarks>Author:Alex Leo</remarks>
internal static TokenRecord SyntaxTreeGetTopTokenAnalyse(List<TokenRecord> TokenList, int IndexStart, int IndexEnd)
{
int intIndexCurrent = IndexStart;//當前處理序號
int intIndexSubStart = IndexStart;//子記號段的起始序號
TokenRecord Token;//獲取當前Token
Stack<TokenRecord> StackCompart = new Stack<TokenRecord>();//括號堆棧
Stack<TokenRecord> StackOperate = new Stack<TokenRecord>();//操作記號堆棧
for (int intIndex = IndexStart; intIndex <= IndexEnd; intIndex++)
{
Token = TokenList[intIndex];
intIndexCurrent = intIndex;
if (Token is TokenLeftBracket)
{
StackCompart.Push(TokenList[intIndexCurrent]);//把左括號壓棧
//獲取該括號對中包含的記號段
intIndexSubStart = intIndexCurrent + 1;//設置子記號段的起始序號
//提取記號段
//如果語法錯誤，比如在記號段的末尾沒有配對的右括號記號，則會出錯，這裡假設為語法正確
while (StackCompart.Count > 0)
{
intIndexCurrent += 1;
if (intIndexCurrent >= TokenList.Count)
{
//Error or auto add lossed bracket
throw new SyntaxException(Token.Index, Token.Length, "缺少配對的 括號");
}
if (TokenList[intIndexCurrent] is TokenLeftBracket)
{
StackCompart.Push(TokenList[intIndexCurrent]);
}
else if (TokenList[intIndexCurrent] is TokenRightBracket)
{
StackCompart.Pop();
}
}
TokenRecord TokenInnerTop = SyntaxTreeGetTopTokenAnalyse(TokenList, intIndexSubStart, intIndexCurrent - 1);
if (TokenInnerTop != null)//只有在取得括號中的頂級節點才添加
{
Token.ChildList.Add(TokenInnerTop);
}
else
{
//無法獲取括號內的頂級節點
throw new SyntaxException(Token.Index, Token.Length, "括號內不包含計算表 達式");
}
intIndex = intIndexCurrent;//移動序號到當前序號
SyntaxTreeStackAnalyse(StackOperate, Token);
}//if token is TokenLeftBracket
else if (Token is TokenMethod)//方法處理
{
//檢查方法後是否接著左括號
if (intIndexCurrent >= IndexEnd || !(TokenList[intIndexCurrent + 1] is TokenLeftBracket))
{
throw new SyntaxException(Token.Index, Token.Length, "方法後缺少括號 ");
}
intIndexSubStart = intIndexCurrent;//設置子記號段的起始序號
intIndexCurrent += 1;//指針後移
StackCompart.Push(TokenList[intIndexCurrent]);//把左括號壓棧
//提取記號段
//如果語法錯誤，比如在記號段的末尾沒有配對的右括號記號，則會出錯，這裡假設為語法正確
while (StackCompart.Count > 0)
{
intIndexCurrent += 1;
if (intIndexCurrent >= TokenList.Count)
{
//Error or auto add lossed bracket
throw new SyntaxException(Token.Index, Token.Length, "缺少配對的 括號");
}
if (TokenList[intIndexCurrent] is TokenLeftBracket)
{
StackCompart.Push(TokenList[intIndexCurrent]);
}
else if (TokenList[intIndexCurrent] is TokenRightBracket)
{
StackCompart.Pop();
}
}
if ((intIndexCurrent - intIndexSubStart) == 2)//如果右括號的序號和方法的序號之差是2， 說明中間只有一個左括號
{
throw new SyntaxException(TokenList[intIndexCurrent - 1].Index, 1, "括號 內不包含計算表達式");
}
//分析方法記號段，因為方法括號段中可能有多個運算結果，比如if，max等，不能用獲取頂級節 點的方法SyntaxTreeGetTopTokenAnalyse
SyntaxTreeMethodAnalyse(TokenList, intIndexSubStart, intIndexCurrent);
intIndex = intIndexCurrent;//移動序號到當前序號
SyntaxTreeStackAnalyse(StackOperate, Token);
}//if token is TokenKeyword
else if (Token is TokenSymbol || Token is TokenValue)
{
SyntaxTreeStackAnalyse(StackOperate, Token);
}
else
{
//不做處理
throw new SyntaxException(Token.Index, Token.Length, "運算符位置錯誤");
}
}
return SyntaxTreeStackGetTopToken(StackOperate);//返回頂級記號
}
/// <summary>
/// 方法記號段分析（處於括號中間的代碼段）
/// </summary>
/// <param name="ListToken">記號列表</param>
/// <param name="IndexStart">括號開始的序號</param>
/// <param name="IndexEnd">括號結束的序號</param>
/// <remarks>只處理完整的方法段，比如if(), round()</remarks>
/// <remarks>Author:Alex Leo</remarks>
private static void SyntaxTreeMethodAnalyse(List<TokenRecord> ListToken, int IndexStart, int IndexEnd)
{
int intIndexSubStart = IndexStart;//子記號段的起始序號
intIndexSubStart = IndexStart + 2;//移動子記號段的開始序號到括號後面
int intIndexSubEnd = IndexEnd;//子記號段的結束序號
TokenRecord TokenMethod = ListToken[IndexStart];//方法記號對象
TokenRecord TokenCurrent;//獲取當前Token
Stack<TokenRecord> StackCompart = new Stack<TokenRecord>();//分隔符堆棧
for (int intIndex = IndexStart; intIndex <= IndexEnd; intIndex++)
{
TokenCurrent = ListToken[intIndex];
if (TokenCurrent is TokenLeftBracket)
{
StackCompart.Push(TokenCurrent);
}
else if (TokenCurrent is TokenRightBracket)
{
StackCompart.Pop();
if (StackCompart.Count == 0)//如果是最後一個右括號
{
intIndexSubEnd = intIndex - 1;//設置段結束序號
TokenMethod.ChildList.Add(SyntaxTreeGetTopTokenAnalyse(ListToken, intIndexSubStart, intIndexSubEnd));//遞歸
}
}
else if (TokenCurrent is TokenComma)
{
if (StackCompart.Count == 1)//如果是方法的子段
{
intIndexSubEnd = intIndex - 1;//設置段結束序號
TokenMethod.ChildList.Add(SyntaxTreeGetTopTokenAnalyse(ListToken, intIndexSubStart, intIndexSubEnd));//遞歸
intIndexSubStart = intIndex + 1;//把子記號段序號後移
}
}
else
{
//不作處理
}
}
//TokenMethod.GetType().GetMethod("CheckChildCount").Invoke(TokenMethod, new object[] { "運算元素數量不合法" });
}
/// <summary>
/// 語法樹堆棧分析，基於記號的優先級
/// </summary>
/// <param name="SyntaxTreeStack">語法樹堆棧</param>
/// <param name="NewToken">新記號</param>
/// <remarks>Author:Alex Leo</remarks>
private static void SyntaxTreeStackAnalyse(Stack<TokenRecord> SyntaxTreeStack, TokenRecord NewToken)
{
if (SyntaxTreeStack.Count == 0)//如果語法樹堆棧中不存在記號，則直接壓棧
{
SyntaxTreeStack.Push(NewToken);
}
else//否則，比較優先級進行棧操作
{
//比較優先級，如果新Token優先級高，則壓棧；
//如果新Token優先級低，則彈棧，把彈出的Token設置為新Token的下級，並把新Token壓棧；
//相同優先級也彈棧，並將新Token壓棧
//if (this.m_DicTokenTypePriority[SyntaxTreeStack.Peek().TokenType] < this.m_DicTokenTypePriority[NewToken.TokenType])//低進
if (SyntaxTreeStack.Peek().Priority < NewToken.Priority)//低進
{
SyntaxTreeStack.Push(NewToken);//低進
}
else
{
TokenRecord TempToken = null;
//如果堆棧中有記號，並且棧頂的記號優先級大於等於新記號的優先級，則繼續彈棧
while (SyntaxTreeStack.Count > 0 && (SyntaxTreeStack.Peek().Priority >= NewToken.Priority))
{
TempToken = SyntaxTreeStack.Pop();
if (SyntaxTreeStack.Count > 0)//檢測棧頂是否可能為空，如果為空則退出
{
if (SyntaxTreeStack.Peek().Priority >= NewToken.Priority)
{
SyntaxTreeStack.Peek().ChildList.Add(TempToken);
}
else
{
NewToken.ChildList.Add(TempToken);
}
}
else
{
NewToken.ChildList.Add(TempToken);
}
}
SyntaxTreeStack.Push(NewToken);//壓棧
}
}
}
/// <summary>
/// 獲取語法樹堆棧的頂級記號
/// </summary>
/// <param name="SyntaxTreeStack">語法樹堆棧</param>
/// <returns>頂級記號</returns>
/// <remarks>Author:Alex Leo</remarks>
private static TokenRecord SyntaxTreeStackGetTopToken(Stack<TokenRecord> SyntaxTreeStack)
{
TokenRecord TempToken = null;
if (SyntaxTreeStack.Count > 0)
{
TempToken = SyntaxTreeStack.Pop();
while (SyntaxTreeStack.Count > 0)
{
SyntaxTreeStack.Peek().ChildList.Add(TempToken);
TempToken = SyntaxTreeStack.Pop();
}
}
return TempToken;
}
}//class SyntaxTreeAnalyse
代碼中對括號進行了特殊處理，遇到左括號之後需要查找到配對的右括號，然後對這一段調用SyntaxTreeGetTopTokenAnalyse進行遞歸處理 ，找出括號中的頂級節點。而對於方法也需要特殊處理，方法必須帶括號，而且括號中不止一個根節點。處理過程是以逗號為分隔符，依次找 出括號中的幾個節點，然後添加到方法的ChildList中。實際的代碼在SyntaxTreeMethodAnalyse方法中實現。
這一篇寫的我自己都頭暈了，呵呵，堆棧一個個分析，截圖都挺煩。代碼裡方法互相遞歸調用，也是比較讓人容易頭暈的，希望有人能看懂 吧。
本文配套源碼
