遞歸下降計算器
全文5頁1405字 敘述詳盡
一、 實驗題目
1、 重寫程序清單4-1的遞歸下降計算器，使其根據(jù)3.3.2節(jié)的聲明返回一個語法樹。
2、 寫出一個以語法樹作為參數(shù)的函數(shù)，它得到上面的代碼生成的語法樹，并由移動樹返回計算的值。
二、 分析算法
此次實驗要求采用遞歸下降的方法產(chǎn)生輸入串的語法樹，并用移動樹來計算最終的值。因此我采用VC++軟件開發(fā)平臺來完成，主要考慮到生成語法樹需要采用結(jié)構(gòu)體來表示每個結(jié)點，而在c++中我們可以用類來完好的封裝一個結(jié)點類，使程序更加直觀。封裝好結(jié)點類后，我們就可以用其提供的接口進行語法樹的構(gòu)造了。然后可以對書上的程序進行改造，在書上程序中計算的地方，我們就用構(gòu)造語法樹的代碼來替代。最終形成語法樹。在計算最終結(jié)果的代碼中，我采用后序遍歷語法樹的方法來計算最終結(jié)果。
三、 算法思路
1、 采用的數(shù)據(jù)結(jié)構(gòu)：
typedef enum { add,minus,mulop,none } OpKind; //枚舉操作類型
streeNode類用來存儲語法樹中的結(jié)點。
2、 采用的方法：
A） 實現(xiàn)構(gòu)建語法樹：用streeNode表示語法樹的結(jié)點，對書上的程序進行改造，在書上程序中計算的地方，我們就用構(gòu)造語法樹的代碼來替代。最終形成語法樹。
B） 計算最終結(jié)果：后序遍歷語法樹即可。
六、 實驗體會
通過這次實驗，加深了我對編譯器設(shè)計中遞歸下降方法和構(gòu)造語法樹的了解。在此次實驗中，采用C＋＋封裝結(jié)點類使程序更直觀，在設(shè)計過程中，碰到了如何區(qū)分葉子結(jié)點和分支結(jié)點的問題，其實可以采用建立兩個類分別表示葉子結(jié)點和分支結(jié)點的方法來區(qū)分，然而這會影響程序設(shè)計的復(fù)雜性和可讀性。所以最后我就采取統(tǒng)一一個類表示兩種結(jié)點的方法來完成設(shè)計。其實，這個實驗并不難，算法也很簡單，只要自己去做，就能完成它。