“編譯原理”課程實驗項目介紹

王生原 董 淵 張素琴

摘要:在“編譯原理”課程的教學中,實驗項目是十分關鍵的部分。Decaf/Mind項目是近幾年清華大學計算機系本科生“編譯原理”課程的主體實驗項目,在該項目中,學生在實驗框架基礎上,針對一個簡單面向對象語言的實現開展4～5個階段的編程實驗,對理解和鞏固理論知識以及提高軟件系統的開發能力有較大幫助。本文就Decaf/Mind項目的背景、內容以及實施情況進行簡要介紹。

關鍵詞:編譯原理;課程實驗;Decaf/Mind項目

中圖分類號:G642 文獻標識碼:A

在清華大學計算機系本科生“編譯原理”課程的教學中,Decaf/Mind課程實驗項目從1998級開始,至現在的2007級,經歷了10屆學生。1998～2002年,該項目是選作的(但分值較高的),自2003級之后成為必做的課程實驗項目。本文首先介紹Decaf/Mind項目的背景,然后根據目前的情況(2006～2007級),對該實驗項目的內容以及實施情況進行簡要介紹。

1Decaf/Mind項目的背景

2001年,我們引進了Stanford課程CS143(Compilers, http://www.stanford.edu/class/cs143/, CS143, Stanford University) 的課程實驗框架(其原始框架由Julie Zelenski設計)。該實驗框架設計實現一種簡單面向對象語言Decaf的編譯器,因此我們稱之為Decaf項目。

Decaf是一種強類型的、單繼承的簡單面向對象語言,是一種較為流行的教學語言,曾經在Stanford、MIT、University of Tennessee、Brown、Texas A&M、Southern Adventist等多所大學的相關課程中使用。

在1998級本科生的“編譯原理”課程(2001年秋季學期)中,我們首次采用了Decaf項目,并根據需要對實驗框架進行了一定的調整,包括適應Windows平臺、增加目標代碼在X86的執行以及對源語言進行適當的改動等。比如在2002級,我們對該項目進行一定的簡化之后,稱之為TOOL項目。

從2003級的課程之后,我們對原始的Decaf項目實驗框架進行了3次實質性改動。

在2003～2004級的Decaf項目中,我們將原先實驗框架的開發語言由C++改為Java。

在計50班(2005級“姚”班)的“編譯原理”課程中,我們參考了U.C.Berkeley課程CS164(Programming Languages and Compilers, http://inst.eecs.berkeley.edu/～cs164/archives. html, CS143, University of California at Berkeley)的COOL課程項目以及Cornell大學課程 CS412(Introduction to Compilers, http://www.cs.cornell.edu/ courses/cs412/2003sp/ CS412/413, Cornell University)中所采用的Iota項目,將實驗框架由原來的單遍組織改為多遍組織,我們稱之為Mind(Mind is not decaf)項目,并稱源語言為Mind語言。

由于計50班的編譯課程安排在Java程序設計課程之前,所以首次Mind項目的開發語言為C++。隨后,在2005級其他班的課程中,我們又將開發語言由C++改回Java。

從2006級開始,實驗框架沒有發生大的變動,只是對其進行微調或進行適當簡化。下面是對2006～2007級教學情況的介紹。

2課程實驗項目的內容

Decaf/Mind項目的實驗框架是設計實現Decaf/Mind語言的編譯器,該編譯器的工作原理如圖1所示。

我們將實驗分成如下5個階段:

階段1:詞法和語法分析。借助Lex和Yacc實現詞法和語法分析,一遍掃描后直接產生一種高級中間表示(實驗指定的抽象語法樹AST)。使用的Lex和Yacc版本分別為Flex(Jflex, http://jflex.de/)和BYACC/J(BYACC/J, http:// byaccj.sourceforge.net/)。原始的Decaf項目采用Yacc實現主要編譯階段,實驗的3個階段(詞法、語法分析階段,語義分析階段,生成三地址中間代碼階段)是一個單遍的過程(注:從三地址碼到MIPS匯編代碼的翻譯由實驗框架給定,沒有安排階段實驗)。對于這個單遍的實驗框架,前幾屆學生感覺調試的難度較大,有一些語言特征難以實現,但它可以和理論課學習中語法制導翻譯的部分相呼應。修改框架后,依賴于Yacc工具的部分大大簡化,生成抽象語法樹AST形式后,符號表的建立和靜態語義的檢查工作只需使用樹遍歷算法就可實現,這符合現實中編譯系統的實際情況。這種框架不能與語法制導翻譯的理論直接呼應,但可用于間接指導。

階段2:語義分析。遍歷抽象語法樹構造符號表、實現靜態語義檢查(非上下文無關語法檢查以及類型檢查等),產生帶標注的抽象語法樹。在這一階段中,我們把語義分析分為對抽象語法樹AST的兩趟掃描進行:第一趟掃描時建立符號表的信息,并檢測符號聲明沖突以及跟聲明有關的符號引用問題(例如A繼承于B,但是B沒有定義的情況);第二趟掃描時檢查所有的語句以及表達式的參數數據類型。通過這一階段的實驗工作,學生可以熟練掌握Visitor設計模式的使用。

階段3:中間代碼生成。將帶標注的抽象語法樹(decorated AST)所表示的輸入程序翻譯成適合后期處理的另一種中間表示方式,即三地址碼TAC,并在合適的地方加入諸如檢查數組訪問越界、數組大小非法等運行時錯誤的內容。通過一階段的實驗工作,學生可以掌握常見語言成分的中間代碼翻譯方法,并且可以對過程調用約定、面向對象機制的實現方法、存儲布局等內容有切實的了解。

階段4:中間代碼優化。根據教學計劃,目前的實驗框架只要求基于TAC實現一些簡單的數據流分析,沒有包含中間代碼優化算法的內容。在2005～2007級的實驗中,只要求學生實現活躍變量分析,既包括以基本塊為單位的分析,也包括以基本塊內單個語句為單位的分析。

階段5:目標代碼生成。實驗框架包括匯編指令選擇、寄存器分配和棧幀管理,實驗內容可以設計為對這些部分進行改進?？紤]到學生負擔問題,目前我們沒有安排這一階段的實驗任務。

完成這些階段后,即可產生適合實際MIPS機器的匯編代碼,可以利用由美國Wisconsin大學所開發的MIPS R2000/R3000模擬器SPIM(MIPS SPIM, University of Wisconsin-Madison, http://pages.cs.wisc.edu/～larus/spim.html) 來運行這些匯編代碼。

3課程實驗項目的實施

Decaf/Mind項目一般在“編譯原理”課程學期的第4或第5周開始,歷時8周(遇特殊情況順延),共4個階段,各階段2周。為鼓勵學生積極進取,學生可以對實驗工作自行擴展,自行擴展部分在第4階段截止日的隨后兩周內完成提交。

2006級每一階段的滿分成績為10分,實驗成績滿分40分。2007級實驗成績滿分35分,各階段的分布情況是:第1～3階段為9分,第4階段為8分。自行擴展部分在4個階段的評分完成后統一評分,最高5分,將直接加入總評成績。

各階段評分的依據包括程序部分和實驗報告部分。程序部分主要看輸出結果與標準輸出的一致程度,占每階段成績的80%;報告部分主要看對提交的作業報告的描述,例如是否清楚說明了自己的工作內容等。每階段截止提交2周后,該階段成績將被公布。如有抄襲,將取消階段成績,并給予警告。每名學生共有2天的晚交額度,每超過1天在總成績中扣2分,公布評閱結果時會同時提醒每名學生剩下的晚交額度。

對自行擴展部分的評價是綜合考慮創新性、實用性、合理性、難度、工作量等因素進行的。我們要求該部分選題一定是在已有實驗框架基礎上進行的有意義的改進工作,通常需要與教師或助教溝通后方可確定選題。教師可以對該部分的選題進行必要的引導,以避免一些意義不大的重復性工作。比如引導學生開展如下選題:函數式風格語句的實現、例外處理支持、垃圾回收機制、新的代碼生成機制(必要時增加新的低級表示)、有意義的優化算法(必要時增加新的中間表示)的實現等。

4結語

本文簡要介紹了清華大學計算機系本科生“編譯原理”課程Decaf/Mind課程實驗項目的基本情況,包括該項目的背景、內容以及實施情況。

Decaf/Mind課程實驗項目實施以來受到計算機系學生的重視。對大多數學生而言,這個實驗項目是入學以來遇到的第一個有一定規模的完整的程序設計項目(“編譯原理”課在大三上開設),又由于本課程在計算機系課程體系中具有重要地位,加之項目本身的魅力,學生興致較高,綜合能力有明顯提高。

“編譯原理”課程實驗項目的設計和實施是一項較為復雜的系統工程,期待國內同仁對本文所介紹的實驗項目提出寶貴的意見。

致謝:Decaf/Mind課程實驗項目經過多屆學生的實踐日趨成熟。我們要特別感謝楊俊峰(Stanford助教)、張迎輝(1999～2000級助教)、毛雁華(2000～2001級助教)、劉天淼(2001級助教)、唐碩(2002級助教)、梁英毅(2003～2005級助教)、張鐸(2005～2007級助教)、蔣波等學生的傾情奉獻。還有許多老師和學生對該項目作出了貢獻,但由于失去統計,沒能一一列出他們的名字,這里一并表達感謝。

Introduction to the Course Lab-Project for Principles and Practice of Compiler Construction

WANG Sheng-yuan, DONG Yuan, ZHANG Su-qin

(Department of Computer Science and Technology, Tsinghua University, Beijing 100084,China)

Abstract: The lab-project is very important in the course Principles and Practice of Compiler Construction. The Decaf/Mind project is the major lab-project of this course for the undergraduates in Department of Computer Science and Technology inTsinghua University. In the project, students will come through 4～5 phases of coding experience to implement a simple object-oriented language on the basis of the project framework. The project is helpful for both the theoretical study and the practical training in developing software system. The background, content and arrangement of the Decaf/Mind project are briefly introduced in the paper.

Key words: principles and practice of compiler construction; course lab-project; Decaf/Mind project