編譯原理算法的形象教學(xué)

摘要:本文探討如何在“編譯原理”教學(xué)過程中形象地演示復(fù)雜的算法過程，提出了一個演示算法步驟的方案，展示算法步驟的進行以及步驟進行時的數(shù)據(jù)聯(lián)動，對于不同的動作、不同意義的數(shù)據(jù)，用圖形元素和顏色加以區(qū)分，并以LR分析算法為例說明了如何分解復(fù)雜步驟，如何用圖形和顏色展示移進、歸約、接受、出錯等分析動作以及相關(guān)數(shù)據(jù)的變化。

關(guān)鍵詞:算法演示;形象教學(xué);編譯原理;LR算法分析

編譯原理的每個階段，從詞法分析、語法分析，直到代碼生成，包含大量的算法。很多算法過程較為復(fù)雜，比如語法分析的LR分析過程包含很多步驟，不同的動作，如移進、歸約、接受等，涉及的數(shù)據(jù)結(jié)構(gòu)包括堆棧、表、流等，要形象地展示這些元素，使學(xué)生較為輕松地接受，是一項充滿挑戰(zhàn)的任務(wù)。

國內(nèi)外已經(jīng)有很多人從事可視化演示計算機科學(xué)的算法工作，比如紐約大學(xué)計算機系的算法可視化項目(http://www.cs.nyu.edu/algvis/)，以及北京航空航天大學(xué)教學(xué)用的PL/0編譯系統(tǒng)的可視化跟蹤軟件(http://compile.buaa.edu.cn/)。

我們課題組曾經(jīng)嘗試運用Flash動畫展示編譯原理的算法，圖1是鄭宏老師等設(shè)計的DFA簡化算法演示截圖。

本文探討如何借助形象的教學(xué)方式清晰展示這些復(fù)雜的算法，使學(xué)生較為輕松地理解。我們以LR分析算法為例，說明如何以不同的顏色展示算法的步驟、不同的動作和每一步的相關(guān)數(shù)據(jù)，形成一個動態(tài)形象展示算法的課件。

1算法演示方案

本節(jié)我們介紹一個展示算法的方案，并以LR分析算法[1-2]說明。

算法一般包括以下要素:步驟、動作、數(shù)據(jù)，這里僅分析LR算法步驟中包括的動作及聯(lián)動的數(shù)據(jù)。根據(jù)當(dāng)前輸入符號和分析棧頂?shù)臓顟B(tài)來查分析表，并以此決定下一步的動作，包括移進、歸約、接受、出錯四類，每一類涉及的數(shù)據(jù)操作又各不相同。主要數(shù)據(jù)結(jié)構(gòu)包括:輸入記號流緩沖、分析棧、分析表和產(chǎn)生式表。分析動作中以歸約最復(fù)雜，涉及產(chǎn)生式、棧頂若干符號和狀態(tài)的彈出、壓入歸約后的符號、轉(zhuǎn)移到新的狀態(tài)等子動作。

算法演示方案包含以下要素:

界面上包含算法過程中涉及的數(shù)據(jù)結(jié)構(gòu)

能夠逐步演示算法從開始到結(jié)束的每一個步驟，復(fù)雜步驟最好能分解成小步驟

用顏色或閃爍等手段突出顯示算法的動作關(guān)聯(lián)

因此，要清晰展示LR分析算法的步驟、動作和相關(guān)數(shù)據(jù)的變化過程，必須在演示界面上顯示分析表、分析棧、輸入符號流、產(chǎn)生式等數(shù)據(jù)，如圖2所示。

一個動作要執(zhí)行時，我們用特殊的顏色、閃爍或者高亮表示該動作及其關(guān)聯(lián)的數(shù)據(jù)。動作執(zhí)行完畢，更新顯示所有涉及的數(shù)據(jù)，如分析棧數(shù)據(jù)及指針、輸入符號流指針等。對于較復(fù)雜的動作，我們進行分解演示，每個分解動作也對相關(guān)數(shù)據(jù)進行特殊顯示。

這些動作的分解和涉及的數(shù)據(jù)操作如表1所示。

根據(jù)表1所列的動作分類，在演示過程中按照對應(yīng)的演示方法逐步演示，直到程序接受或者出錯為止。較為復(fù)雜的歸約動作發(fā)生時，顯示的界面如圖3所示，該歸約動作完成后程序界面如圖4所示。

在圖3中，分析棧當(dāng)前狀態(tài)為5，當(dāng)前輸入記號(token)為’$’，歸約動作為r1，將要用規(guī)則1(E->T+E)進行歸約。歸約時，分析棧將彈出棧頂?shù)?個符號(‘E’， ‘+’和‘T’)以及3個狀態(tài)(5，3和2)，回到狀態(tài)3。歸約動作完成后，分析棧頂被壓入新的非終結(jié)符E，并由狀態(tài)3轉(zhuǎn)移到新的狀態(tài)5，如圖4所示。

通過這些分步演示，學(xué)生可以清楚地觀察到LR分析算法的動作以及數(shù)據(jù)結(jié)構(gòu)的動態(tài)變化，理解LR分析算法的各個步驟。

2演示軟件的設(shè)計和實現(xiàn)

在演示軟件的開發(fā)過程中，我們按照以下要求設(shè)計:

算法模塊和演示模塊獨立設(shè)計。

算法模塊的實現(xiàn)要考慮到演示需要，比如復(fù)雜的步驟要分成子動作，子動作完成后要等待顯示，接受到下一步的指令后再進行下一個子動作，所有子動作完成后進行下一步驟。

這兩個模塊既相互獨立又互相耦合，主程序調(diào)用算法模塊，每進行一個步驟或者一個子步驟后，再調(diào)用相應(yīng)的顯示模塊顯示進行的步驟以及相關(guān)聯(lián)的數(shù)據(jù)和變化。

能適應(yīng)不同的例子。

由于算法模塊是獨立的，因此很容易適應(yīng)不同的輸入例子。這也是比用Flash動畫設(shè)計演示軟件更具優(yōu)勢的一方面。

程序示例可以按一定規(guī)則寫成文本，演示軟件能讀入示例文本并加以解析，初始化相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。圖5為圖3、圖4例子的部分輸入文本。

因此LR算法演示程序的流程如圖6所示。

圖中的LR單步分析引擎根據(jù)分析表的內(nèi)容進行移進、歸約等動作，每個動作如果有子動作，則單步執(zhí)行子動作，等待用戶指示進入下一個子動作。

我們的LR算法演示程序用Visual C++實現(xiàn)，運行于Windows操作系統(tǒng)上。

3結(jié)論

本文提出一個講解算法的形象演示方案，使學(xué)生學(xué)習(xí)復(fù)雜算法時能清楚地觀察算法的步驟、動作及關(guān)聯(lián)的數(shù)據(jù)。我們以LR分析算法為例，先對分析動作進行分解，在演示算法步驟的過程中對每個子動作及關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)進行動態(tài)形象的展示。

編譯原理課程包含大量的算法，所涉及的動作和數(shù)據(jù)結(jié)構(gòu)各種各樣，要動態(tài)形象地展示所有算法是一個富有挑戰(zhàn)的任務(wù)，需要投入人力物力設(shè)計和開發(fā)演示軟件。

參考文獻:

[1] Alfred V. Aho. Compilers: Principles， Techniques Tools[M].2nd ed. 北京:機械工業(yè)出版社，2007.

[2] Andrew Appel， Maia Ginsburg. Modern Compiler Implementation in C[M]. 北京:人民郵電出版社，2005.

Algorithm Visualization for Teaching Principles of Compiler

WANG Qiang， FENG Yan

(College of Computer Science and Technology， Zhejiang University， Hangzhou 310027， China)

Abstract: This paper explores how to visualize the algorithms in courses of teaching principles of compiler. A scheme is proposed to demonstrate the algorithm steps. The scheme shows the actions and datum using different graph elements and colors， and thus shows the algorithm steps and connected datum clearly. It is used to demonstrate LR parsing algorithm， showing how to decompose the complicated steps into sub-steps and use graph elements and colors to reveal the parsing actions， such as shift， reduce， accepting and errors， and connected datum are showing simultaneously.

Key words: algorithm visualization; visualizing teaching; principles of compiler; LR Parsing