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