編譯原理LL(1)語(yǔ)法分析的可視化教學(xué)方法

王濤

（滁州學(xué)院 安徽滁州 239000）

編譯原理LL(1)語(yǔ)法分析的可視化教學(xué)方法

王濤

（滁州學(xué)院 安徽滁州 239000）

編譯原理是公認(rèn)的難教難學(xué)的課程之一，其主要原因是編譯原理要求的知識(shí)體系復(fù)雜，并且算法抽象。本文的作者針對(duì)編譯原理課程的特征提出了一種教學(xué)觀點(diǎn)，即重視對(duì)學(xué)生的概念教學(xué)和形象教學(xué)。為了說(shuō)明形象教學(xué)在編譯原理教學(xué)中的重要性，在本文以LL(1)語(yǔ)法分析為例提出了一種編譯原理可視化軟件的設(shè)計(jì)方法，并給了軟件實(shí)例。教學(xué)實(shí)踐證明，由于可視化教學(xué)為學(xué)生提供了直觀的感性材料，極大的提高了學(xué)生理解相關(guān)概念并掌握相關(guān)算法的能力。

思維模式 LL(1)算法 可視化

編譯原理在計(jì)算機(jī)科學(xué)中的地位非常重要，編譯原理知識(shí)掌握較好的學(xué)生在從事編程工作時(shí)，往往都具有較好的編程語(yǔ)言運(yùn)用能力和對(duì)新語(yǔ)言的學(xué)習(xí)能力。在ACM/IEEE-CS發(fā)布的CSC2013（Computer Science Curricula 2013）中將編譯原理相關(guān)的知識(shí)體系列入到Programming Language知識(shí)體系的核心課程中[1]。

在實(shí)際的教學(xué)過(guò)程中，由于編譯原理與匯編語(yǔ)言、計(jì)算機(jī)組成原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、高級(jí)編程語(yǔ)言等課程的關(guān)系緊密，同時(shí)對(duì)可計(jì)算理論、形式語(yǔ)言與自動(dòng)機(jī)等知識(shí)有要求，知識(shí)體系復(fù)雜，是公認(rèn)的難學(xué)、難教的課程[2][3]，探索編譯原理如何成功教學(xué)的方法一直是該課程教學(xué)研究的熱點(diǎn)問(wèn)題。

本文作者結(jié)合編譯原理的教學(xué)特點(diǎn)，提出了一種新的課程教授思路，要點(diǎn)是：一、重視學(xué)生的系統(tǒng)思維、邏輯思維和形象思維的鍛煉，讓學(xué)生掌握學(xué)好編譯原理的方法；二、通過(guò)設(shè)計(jì)并實(shí)現(xiàn)一套編譯方法教學(xué)軟件，提供直接、形象的感性材料，在解決較復(fù)雜的算法問(wèn)題的時(shí)候，有助于學(xué)生思維的順利進(jìn)行。

1.掌握大學(xué)生的思維規(guī)律是教好編譯方法的關(guān)鍵

編譯原理的課時(shí)設(shè)置相對(duì)于其知識(shí)體系來(lái)講一般偏少，以滁州學(xué)院計(jì)算機(jī)科技與技術(shù)專業(yè)中對(duì)編譯原理的課程設(shè)置來(lái)看，其理論課時(shí)只有48個(gè)學(xué)時(shí)、實(shí)驗(yàn)課時(shí)只有16個(gè)課時(shí)，其它高校的在課時(shí)的設(shè)置上會(huì)有所差異，但最多也只相差10幾個(gè)課時(shí)上下。在如此短的課時(shí)中如何讓學(xué)生實(shí)現(xiàn)編譯方法課的入門(mén)是一個(gè)挑戰(zhàn)。

第一，在教學(xué)中首先要重視概念的教學(xué)，思維過(guò)程是分析、綜合、比較、抽象、概括、判斷和推理的過(guò)程，首先要形成概念，然后才能判斷和推理，使學(xué)生真正的理解相關(guān)的定理、定義。

因此，在講授類似的概念時(shí)要重點(diǎn)讓學(xué)生掌握譯方法的系統(tǒng)思維、邏輯思維。

第二，要重視形象教學(xué)。思維是在感性材料的基礎(chǔ)上產(chǎn)生的，感性認(rèn)識(shí)是思維活動(dòng)的源泉和根據(jù)。在編譯原理授課時(shí)，如果脫離具體形象，特別是在解決比較復(fù)雜的問(wèn)題的時(shí)候，由于無(wú)法提供直觀的鮮明、生動(dòng)的示例，會(huì)妨礙思維的順利進(jìn)行。因此，在課程中針對(duì)典型的算法要設(shè)計(jì)要實(shí)現(xiàn)一系列可視化的算法程序，讓學(xué)生親自參與到算法編寫(xiě)，并通過(guò)可視化的手段實(shí)現(xiàn)諸如NFA到DFA的轉(zhuǎn)化算法，詞法分析相關(guān)算法，語(yǔ)法分析的相關(guān)算法，語(yǔ)義分析相關(guān)算法，目標(biāo)代碼生成相關(guān)算法等，通過(guò)動(dòng)畫(huà)形式讓學(xué)生理解算法的內(nèi)涵。

在本文的其余部分，將以LL(1)算法為例說(shuō)明如何設(shè)計(jì)編譯原理可視化教學(xué)模塊。

2.LL(1)算法可視化模塊的設(shè)計(jì)

2.1 LL(1)中相關(guān)概念的邏輯關(guān)系

LL(1)是實(shí)現(xiàn)語(yǔ)法分析器的經(jīng)典算法之一，其本質(zhì)是按文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)合法的子句，LL(1)中的第一個(gè)L表示從左到右掃描輸入串，第二個(gè)L表示最左推導(dǎo),1表示分析時(shí)每一步只需向前查看一個(gè)符號(hào)。目前已經(jīng)有基于JAVA語(yǔ)言的編譯原理可視化軟件的報(bào)導(dǎo)，考慮到C#語(yǔ)言強(qiáng)大的界面處理功能，本文中的模塊基于C#語(yǔ)言設(shè)計(jì)并開(kāi)發(fā)。

LL(1)的生成過(guò)程是一種自上而下的生成樹(shù)的過(guò)程，所謂的與輸入串的匹配，即自左向右依次對(duì)比生成樹(shù)的葉子結(jié)點(diǎn)與輸入串的每一個(gè)符號(hào)是否吻合，否則，輸入串不合法。在進(jìn)行該算法模塊設(shè)計(jì)的時(shí)候要通過(guò)可視化算法重點(diǎn)向?qū)W生講授以下內(nèi)容，

⑴要消除遞歸性。文法的生成式是有遞歸性的，如果利用計(jì)算機(jī)直接實(shí)現(xiàn)一個(gè)文法結(jié)構(gòu)會(huì)存在若干問(wèn)題，主要表現(xiàn)在可能會(huì)存在左遞歸，使得編譯程序陷入死循環(huán)。

⑵要消除“回溯”。由于產(chǎn)生式左部會(huì)對(duì)應(yīng)多個(gè)候選式，編譯程序如果無(wú)法選擇正確的候選式，會(huì)讓編譯程序不停的“回溯”，依次嘗試直到找到一個(gè)合適的候選式。

⑶消除空符號(hào)ε帶來(lái)的影響。當(dāng)一個(gè)輸入符號(hào)遇到一個(gè)非終結(jié)符時(shí)，可能會(huì)產(chǎn)生ε，如何判斷此時(shí)為錯(cuò)誤、無(wú)法進(jìn)行或者可以繼續(xù)分析是自上而下分析的另一要注意的內(nèi)容。

⑷一個(gè)文法只有在消除了以上的影響之后，才可以稱為L(zhǎng)L(1)文法，在此時(shí)要向?qū)W生講授LL(1)的詳細(xì)定義，概念的內(nèi)涵和外延，并指出，成為了LL(1)文法才使得自上而下語(yǔ)法分析編譯算法的編程成為可能。

2.2.模塊的設(shè)計(jì)要點(diǎn)

一般來(lái)講，實(shí)現(xiàn)LL(1)算法有兩種方法，一種是遞歸下降分析程序，一種是預(yù)測(cè)分析程序，本文所述的模塊設(shè)計(jì)采用的是預(yù)測(cè)分析程序。

（1）可視化算法解決方案的目錄結(jié)構(gòu)。編譯原理可視化軟件采用C#語(yǔ)言和Visio 2010開(kāi)發(fā)完成，在解決方案中添加兩個(gè)主要項(xiàng)目，分別為ComilerPrinciples和CompilerDLL，前者用于控制算法界面的可視化邏輯，是界面層，后者用于完成算法的處理，是控制邏輯層。兩者之間通過(guò)函數(shù)調(diào)用實(shí)現(xiàn)交互。

⑵LL(1)可視化算法模塊的核心類文件。在LL(1)可視化算法模塊中的界面層中的核心類文件是DlgForcastAnalysisTable.cs和LL1_Analysis. cs，分別用于預(yù)測(cè)分析表和LL(1)算法的可視化。在控制邏輯層中的核心類文件是LL1_Analysis.cs和Model_LL1_StepStatus.cs，分別用于完成LL(1)預(yù)測(cè)算法的控制邏輯以及分步驟呈現(xiàn)算法的實(shí)現(xiàn)過(guò)程。

⑶模塊的復(fù)用。在進(jìn)行軟件設(shè)計(jì)的時(shí)候，盡量的考慮到控制邏輯與界面層的組件復(fù)用，例如在LL(1)分析模塊中，會(huì)復(fù)用到詞法分析的所有功能，因此通過(guò)繼承關(guān)系和組件化調(diào)用盡量的復(fù)用現(xiàn)有模塊，從而提高編程的效率。

3.基于C#的LL(1)算法可視化模塊實(shí)例

為了更好說(shuō)明LL(1)可視化算法的運(yùn)行過(guò)程，以表達(dá)式“為例進(jìn)行分析說(shuō)明。

3.1.詞法分析

如圖1所示，首先啟動(dòng)編譯原理可視化算法軟件，在菜單中調(diào)用LL (1)分析模塊。在進(jìn)行語(yǔ)法分析前先完成詞法分析，將表達(dá)式中的每一個(gè)單詞符號(hào)解析出來(lái)，這一步是后續(xù)分析的基礎(chǔ)，并且詞法分析的結(jié)果將作為語(yǔ)法分析的輸入使用。

圖1：詞法分析界面示意圖

通過(guò)此功能可以向?qū)W生講授目前常用的編程環(huán)境IDE的工作原理，IDE的核心功能是按所支持的編程言語(yǔ)的格式完成代碼的編寫(xiě)。在不考慮編譯器的情況下，IDE和普通的文本編譯工具是沒(méi)有區(qū)別的，正是由于存在了編譯器模塊才使得IDE可以將我們輸入的文本字符串轉(zhuǎn)換為編譯器可以識(shí)別的單詞符號(hào)串。有了這樣的認(rèn)識(shí)，首先可以讓學(xué)生破除對(duì)編譯原理的神秘感，其次通過(guò)親自動(dòng)手可以讓學(xué)生直觀的理解符號(hào)串的生成以及后續(xù)的語(yǔ)法分析的關(guān)系[8]。

詞法分析器所基于的算法是基于DFA的單詞符號(hào)識(shí)別算法，單詞識(shí)別完成后的輸出結(jié)果如表1所示。

表1:單詞符號(hào)識(shí)別結(jié)果

3.2.預(yù)測(cè)分析表生成模塊

在LL(1)分析中預(yù)測(cè)分析表的本質(zhì)是一個(gè)以非終結(jié)符和終結(jié)符為坐標(biāo)的二維矩陣，其形如M[A,a]，其中A為非終結(jié)符，a為終結(jié)符，坐標(biāo)A和坐標(biāo)a所對(duì)應(yīng)的元素為一個(gè)產(chǎn)生式。

圖2:預(yù)測(cè)分析表界面示意圖

本模塊的作用是按照一定的文法結(jié)構(gòu)生成矩陣M[A,a]，如圖2所示。本模塊的構(gòu)成分為三個(gè)部分：

⑴圖2的左上方為產(chǎn)生式輸入?yún)^(qū)域，分別輸入產(chǎn)生式的左部(head)和產(chǎn)生式的右部(body)，并提供了添加、刪除、上移和下移功能。

⑵隨著產(chǎn)生式的添加會(huì)自動(dòng)的生成所要分析的文法結(jié)構(gòu)G，如圖2右上方所示。

⑶文法結(jié)構(gòu)生成并檢查無(wú)誤后，單擊“預(yù)測(cè)分析表”功能，可以自動(dòng)生成語(yǔ)法分析程序所需的預(yù)測(cè)分析表。

預(yù)測(cè)分析表的生成算法的核心步驟如下：

⑴對(duì)文法G中的每一個(gè)文法符號(hào)X（X為終結(jié)符或者非終結(jié)符）構(gòu)造First(X)，并對(duì)文法G中的每一個(gè)非終結(jié)符A構(gòu)造Follow(A)，構(gòu)造完成后執(zhí)行第⑵步。

⑵對(duì)文法G的每一個(gè)產(chǎn)生式A→a執(zhí)行第⑶和⑷步。

⑶對(duì)每個(gè)終結(jié)符a∈FFirst(a)，把A→a添加到矩陣M[A,a]。

⑷若ε∈First(a)，則對(duì)任何b∈Follow(A)把A→a添加到矩陣M [A,a]。

⑸對(duì)所有無(wú)定義的矩陣部分標(biāo)記為錯(cuò)誤。

預(yù)測(cè)分析表生成后，在C#中采用Hashtable數(shù)據(jù)結(jié)構(gòu)保存矩陣M[A, a]，矩陣的產(chǎn)生式用自定義的數(shù)據(jù)模型保存，用戶自定義模型ModelProduction中只實(shí)現(xiàn)Get與Set方法，并以產(chǎn)生式的左部和右部為數(shù)據(jù)模型，ModelProduction的結(jié)構(gòu)如圖3所示。

圖3:產(chǎn)生式存儲(chǔ)模型ModelProduction

3.3.LL(1)可視化分析過(guò)程

預(yù)測(cè)分析表生成后，基于表1生成的符號(hào)串可以完成LL(1)語(yǔ)法分析。由于LL(1)的預(yù)測(cè)分析程序需要棧作為輔助數(shù)據(jù)結(jié)構(gòu)，在C#中可以直接使用Stack數(shù)據(jù)類型完成，并在棧底保存一個(gè)字符“#”。Stack的棧頂元素為X，表1中的當(dāng)前輸入符號(hào)為a，預(yù)測(cè)分析的核心步驟為：

⑴若X=a=’#’，則分析結(jié)束。

⑵若X=a≠’#’，則X出棧，指向下一人符號(hào)。

⑶若X為非終結(jié)符則查看分析表M[A,a]。

基于以上分析步驟所實(shí)現(xiàn)的分析界面如圖4所示。

圖4:LL(1)分析界面示意圖

在本功能中提供了預(yù)測(cè)分析表調(diào)用功能，用于修正預(yù)測(cè)分析表，添加了“起始步”、“上一步”、“下一步”、“結(jié)束步”等功能，并顯示分析過(guò)程中每一步的執(zhí)行狀態(tài)以及棧的存儲(chǔ)狀態(tài)。

對(duì)于抽象的語(yǔ)法分析樹(shù)則通過(guò)樹(shù)形生成算法利用可視化進(jìn)行展示，如圖5所示，分別給出了第4步、第6步、第8步、第10步、第12步、第16步的語(yǔ)法樹(shù)形態(tài)，學(xué)生也可以利用本軟件任意查看語(yǔ)法分析過(guò)程中每一步的語(yǔ)法樹(shù)形態(tài)，從而對(duì)語(yǔ)法樹(shù)有一個(gè)直觀的認(rèn)識(shí)，并通過(guò)這種直觀認(rèn)識(shí)加強(qiáng)對(duì)算法的理解[9]。

圖5:語(yǔ)法分析過(guò)程中每一步的語(yǔ)法樹(shù)形態(tài)

總結(jié)

本文針對(duì)編譯原理的教學(xué)特點(diǎn)，提出了一種強(qiáng)調(diào)思維鍛煉并結(jié)合可視化教學(xué)軟件實(shí)現(xiàn)編譯方法順利教學(xué)的新觀點(diǎn)，思維鍛煉是基本，可視化教學(xué)軟件用于提供感性材料。同時(shí)本文中以LL(1)為例闡述了如何設(shè)計(jì)編譯原理可視化教學(xué)軟件。

[1]The Joint Task Force on Computing Curricula Association for Computing Machinery(ACM)IEEE Computer Society.Computer Science Curricula 2013.

[2]陳文宇.關(guān)于 “編譯原理”課程教學(xué)的思考 [J].實(shí)驗(yàn)科學(xué)與技術(shù), 2008(12):80-82.

[3]王順曄.“編譯原理”課程教學(xué)方法的研究與實(shí)踐[J].計(jì)算機(jī)教育，2010(3):36-38.

本文得到滁州學(xué)院校級(jí)優(yōu)質(zhì)課程“編譯方法”(項(xiàng)目號(hào)2014yzkc07編譯方法)項(xiàng)目的資助。