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

王濤

（滁州學院 安徽滁州 239000）

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

王濤

（滁州學院 安徽滁州 239000）

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

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

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

在實際的教學過程中，由于編譯原理與匯編語言、計算機組成原理、數據結構、操作系統、高級編程語言等課程的關系緊密，同時對可計算理論、形式語言與自動機等知識有要求，知識體系復雜，是公認的難學、難教的課程[2][3]，探索編譯原理如何成功教學的方法一直是該課程教學研究的熱點問題。

本文作者結合編譯原理的教學特點，提出了一種新的課程教授思路，要點是：一、重視學生的系統思維、邏輯思維和形象思維的鍛煉，讓學生掌握學好編譯原理的方法；二、通過設計并實現一套編譯方法教學軟件，提供直接、形象的感性材料，在解決較復雜的算法問題的時候，有助于學生思維的順利進行。

1.掌握大學生的思維規律是教好編譯方法的關鍵

編譯原理的課時設置相對于其知識體系來講一般偏少，以滁州學院計算機科技與技術專業中對編譯原理的課程設置來看，其理論課時只有48個學時、實驗課時只有16個課時，其它高校的在課時的設置上會有所差異，但最多也只相差10幾個課時上下。在如此短的課時中如何讓學生實現編譯方法課的入門是一個挑戰。

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

因此，在講授類似的概念時要重點讓學生掌握譯方法的系統思維、邏輯思維。

第二，要重視形象教學。思維是在感性材料的基礎上產生的，感性認識是思維活動的源泉和根據。在編譯原理授課時，如果脫離具體形象，特別是在解決比較復雜的問題的時候，由于無法提供直觀的鮮明、生動的示例，會妨礙思維的順利進行。因此，在課程中針對典型的算法要設計要實現一系列可視化的算法程序，讓學生親自參與到算法編寫，并通過可視化的手段實現諸如NFA到DFA的轉化算法，詞法分析相關算法，語法分析的相關算法，語義分析相關算法，目標代碼生成相關算法等，通過動畫形式讓學生理解算法的內涵。

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

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

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

LL(1)是實現語法分析器的經典算法之一，其本質是按文法的產生式，識別輸入符號串是否為一個合法的子句，LL(1)中的第一個L表示從左到右掃描輸入串，第二個L表示最左推導,1表示分析時每一步只需向前查看一個符號。目前已經有基于JAVA語言的編譯原理可視化軟件的報導，考慮到C#語言強大的界面處理功能，本文中的模塊基于C#語言設計并開發。

LL(1)的生成過程是一種自上而下的生成樹的過程，所謂的與輸入串的匹配，即自左向右依次對比生成樹的葉子結點與輸入串的每一個符號是否吻合，否則，輸入串不合法。在進行該算法模塊設計的時候要通過可視化算法重點向學生講授以下內容，

⑴要消除遞歸性。文法的生成式是有遞歸性的，如果利用計算機直接實現一個文法結構會存在若干問題，主要表現在可能會存在左遞歸，使得編譯程序陷入死循環。

⑵要消除“回溯”。由于產生式左部會對應多個候選式，編譯程序如果無法選擇正確的候選式，會讓編譯程序不停的“回溯”，依次嘗試直到找到一個合適的候選式。

⑶消除空符號ε帶來的影響。當一個輸入符號遇到一個非終結符時，可能會產生ε，如何判斷此時為錯誤、無法進行或者可以繼續分析是自上而下分析的另一要注意的內容。

⑷一個文法只有在消除了以上的影響之后，才可以稱為LL(1)文法，在此時要向學生講授LL(1)的詳細定義，概念的內涵和外延，并指出，成為了LL(1)文法才使得自上而下語法分析編譯算法的編程成為可能。

2.2.模塊的設計要點

一般來講，實現LL(1)算法有兩種方法，一種是遞歸下降分析程序，一種是預測分析程序，本文所述的模塊設計采用的是預測分析程序。

（1）可視化算法解決方案的目錄結構。編譯原理可視化軟件采用C#語言和Visio 2010開發完成，在解決方案中添加兩個主要項目，分別為ComilerPrinciples和CompilerDLL，前者用于控制算法界面的可視化邏輯，是界面層，后者用于完成算法的處理，是控制邏輯層。兩者之間通過函數調用實現交互。

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

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

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

為了更好說明LL(1)可視化算法的運行過程，以表達式“為例進行分析說明。

3.1.詞法分析

如圖1所示，首先啟動編譯原理可視化算法軟件，在菜單中調用LL (1)分析模塊。在進行語法分析前先完成詞法分析，將表達式中的每一個單詞符號解析出來，這一步是后續分析的基礎，并且詞法分析的結果將作為語法分析的輸入使用。

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

通過此功能可以向學生講授目前常用的編程環境IDE的工作原理，IDE的核心功能是按所支持的編程言語的格式完成代碼的編寫。在不考慮編譯器的情況下，IDE和普通的文本編譯工具是沒有區別的，正是由于存在了編譯器模塊才使得IDE可以將我們輸入的文本字符串轉換為編譯器可以識別的單詞符號串。有了這樣的認識，首先可以讓學生破除對編譯原理的神秘感，其次通過親自動手可以讓學生直觀的理解符號串的生成以及后續的語法分析的關系[8]。

詞法分析器所基于的算法是基于DFA的單詞符號識別算法，單詞識別完成后的輸出結果如表1所示。

表1:單詞符號識別結果

3.2.預測分析表生成模塊

在LL(1)分析中預測分析表的本質是一個以非終結符和終結符為坐標的二維矩陣，其形如M[A,a]，其中A為非終結符，a為終結符，坐標A和坐標a所對應的元素為一個產生式。

圖2:預測分析表界面示意圖

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

⑴圖2的左上方為產生式輸入區域，分別輸入產生式的左部(head)和產生式的右部(body)，并提供了添加、刪除、上移和下移功能。

⑵隨著產生式的添加會自動的生成所要分析的文法結構G，如圖2右上方所示。

⑶文法結構生成并檢查無誤后，單擊“預測分析表”功能，可以自動生成語法分析程序所需的預測分析表。

預測分析表的生成算法的核心步驟如下：

⑴對文法G中的每一個文法符號X（X為終結符或者非終結符）構造First(X)，并對文法G中的每一個非終結符A構造Follow(A)，構造完成后執行第⑵步。

⑵對文法G的每一個產生式A→a執行第⑶和⑷步。

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

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

⑸對所有無定義的矩陣部分標記為錯誤。

預測分析表生成后，在C#中采用Hashtable數據結構保存矩陣M[A, a]，矩陣的產生式用自定義的數據模型保存，用戶自定義模型ModelProduction中只實現Get與Set方法，并以產生式的左部和右部為數據模型，ModelProduction的結構如圖3所示。

圖3:產生式存儲模型ModelProduction

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

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

⑴若X=a=’#’，則分析結束。

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

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

基于以上分析步驟所實現的分析界面如圖4所示。

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

在本功能中提供了預測分析表調用功能，用于修正預測分析表，添加了“起始步”、“上一步”、“下一步”、“結束步”等功能，并顯示分析過程中每一步的執行狀態以及棧的存儲狀態。

對于抽象的語法分析樹則通過樹形生成算法利用可視化進行展示，如圖5所示，分別給出了第4步、第6步、第8步、第10步、第12步、第16步的語法樹形態，學生也可以利用本軟件任意查看語法分析過程中每一步的語法樹形態，從而對語法樹有一個直觀的認識，并通過這種直觀認識加強對算法的理解[9]。

圖5:語法分析過程中每一步的語法樹形態

總結

本文針對編譯原理的教學特點，提出了一種強調思維鍛煉并結合可視化教學軟件實現編譯方法順利教學的新觀點，思維鍛煉是基本，可視化教學軟件用于提供感性材料。同時本文中以LL(1)為例闡述了如何設計編譯原理可視化教學軟件。

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

[2]陳文宇.關于 “編譯原理”課程教學的思考 [J].實驗科學與技術, 2008(12):80-82.

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

本文得到滁州學院校級優質課程“編譯方法”(項目號2014yzkc07編譯方法)項目的資助。