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