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方法中實現。
這一篇寫的我自己都頭暈了，呵呵，堆棧一個個分析，截圖都挺煩。代碼裡方法互相遞歸調用，也是比較讓人容易頭暈的，希望有人能看懂 吧。
