本系列文章介紹如何用C#實現一個類似于查詢分析器的計算器。該計算器接受表達式輸入，支持多行表達式，可選擇部分表達式進行計算，能定位語法錯誤的位置，并且支持數值、字符串和邏輯值的計算，內置多種運算符和函數，并且可以根據需要擴展出更多的運算符和函數。程序中包含一些細節上的bug，有興趣的朋友可以完善一下。 本篇介紹如何實現語法分析，將記號列表分析成樹視圖。

相關文章：1.初步分析  2.記號對象  3.詞法分析
上一篇中介紹通過詞法分析將表達式轉換成TokenRecord對象列表。在第一篇中提到將表達式用樹形結構表示，然后就可以很方便的從下級節點取值計算了。那么如何將列表分析成一棵樹的結構呢？
還是以例子來說明，比如3*7+56/8-2*5，分析成TokenRecord列表就是

分析成樹就是

根據實際的算術規則，運算符優先級高的要先計算，然后由低優先級的運算符去調用它的運算結果。表現在樹視圖上就是高優先級的節點是低優先級節點的下級，即優先級越高，其位置越靠近樹葉。因為這里采用統一的對象，把所有元素都用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.列表分析狀態：
堆棧分析：當前堆棧為空，將當前分析的TokenRecord壓棧。
堆棧對應樹視圖：


2.列表分析狀態：
堆棧分析：棧頂為TokenValue，當前TokenRecord為TokenMultiply，TokenValue優先級最高。遵循高出低入原則，將TokenValue彈棧并添加到TokenMultiply的ChildList中，然后將TokenMultiplay壓棧。
堆棧對應樹視圖：


3.列表分析狀態
堆棧分析：棧頂為TokenMultiplay，當前TokenRecord為TokenValue，TokenMultiply優先級高于TokenValue，則將TokenValue加入TokenMultiplay的ChildList中。
堆棧對應樹視圖：

4.列表分析狀態

堆棧分析：棧頂為TokenMultiply，當前TokenRecord為TokenPlus，TokenMultiply優先級高于TokenPlus。遵循高出低入原則，將TokenMultiply彈棧并添加到TokenPlus的ChildList中，然后將TokenPlus壓棧。

堆棧對應樹視圖：


5.列表分析狀態

堆棧分析：棧頂為TokenPlus，當前TokenRecord為TokenValue，TokenPlus優先級低于TokenValue。遵循高出低入原則，不需要彈棧，直接將TokenValue壓棧。
堆棧對應樹視圖：


6.列表分析狀態  堆棧分析：棧頂為TokenValue，當前TokenRecord為TokenDivide，TokenValue優先級高于TokenDivide。遵循高出低入原則，將TokenValue彈棧并加入TokenDivide的ChildList中。此時棧頂為TokenPlus，TokenDivide優先級高于TokenPlus，遵循高出低入原則，將TokenDivide壓棧。  堆棧對應樹視圖：


7.列表分析狀態  堆棧分析：棧頂為TokenDivide，當前TokenRecord為TokenValue，TokenDivide優先級高于TokenValue。遵循高出低入原則，將TokenValue加入TokenDivide的ChildList中。  堆棧分析：棧頂是TokenMultiply，當前是TokenValue，TokenMultiply優先級高于TokenValue。遵循高出低入原則，將TokenValue加入TokenMultiply的ChildList中。
堆棧對應樹視圖：


12.堆棧分析：此時列表分析結束，堆棧不為空，需要對堆棧進行處理。經過上面的堆棧分析，遵循高出低入原則，堆棧中的TokenRecord肯定是棧底優先級最低，棧頂優先級最高。只需要將堆棧中的TokenRecord依次彈棧，然后加入到新棧頂的ChildList中即可。最后彈棧的一個TokenRecord就是整個樹視圖的根節點，也就是返回值。到此，堆棧為空，也得到了預期的樹視圖，返回根節點TokenRecord即可。

上面是對語法分析整個流程的分析，下面給出具體的代碼。程序中的語法分析放在一個單獨的文件中，SyntaxTreeAnalyse.cs，文件中也只有一個SyntaxTreeAnalyse類，專門用于語法樹的分析。這個類只有一個入口即一個公開方法SyntaxTreeGetTopTokenAnalyse，傳入TokenRecord列表，經過分析后返回一個頂級TokenRecord對象，即樹形結構的根節點。具體代碼如下：

代碼中對括號進行了特殊處理，遇到左括號之后需要查找到配對的右括號，然后對這一段調用SyntaxTreeGetTopTokenAnalyse進行遞歸處理，找出括號中的頂級節點。而對于方法也需要特殊處理，方法必須帶括號，而且括號中不止一個根節點。處理過程是以逗號為分隔符，依次找出括號中的幾個節點，然后添加到方法的ChildList中。實際的代碼在SyntaxTreeMethodAnalyse方法中實現。

這一篇寫的我自己都頭暈了，呵呵，堆棧一個個分析，截圖都挺煩。代碼里方法互相遞歸調用，也是比較讓人容易頭暈的，希望有人能看懂吧。
代碼下載：https://files.cnblogs.com/conexpress/ConExpress_MyCalculator.rar