王生原 董 淵 張素琴

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

關(guān)鍵詞:編譯原理;課程實驗;Decaf/Mind項目

中圖分類號:G642 文獻標(biāo)識碼:A

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

1Decaf/Mind項目的背景

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

Decaf是一種強類型的、單繼承的簡單面向?qū)ο笳Z言,是一種較為流行的教學(xué)語言,曾經(jīng)在Stanford、MIT、University of Tennessee、Brown、Texas A&M、Southern Adventist等多所大學(xué)的相關(guān)課程中使用。

在1998級本科生的“編譯原理”課程(2001年秋季學(xué)期)中,我們首次采用了Decaf項目,并根據(jù)需要對實驗框架進行了一定的調(diào)整,包括適應(yīng)Windows平臺、增加目標(biāo)代碼在X86的執(zhí)行以及對源語言進行適當(dāng)?shù)母膭拥?。比如?002級,我們對該項目進行一定的簡化之后,稱之為TOOL項目。

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

在2003～2004級的Decaf項目中,我們將原先實驗框架的開發(fā)語言由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大學(xué)課程 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程序設(shè)計課程之前,所以首次Mind項目的開發(fā)語言為C++。隨后,在2005級其他班的課程中,我們又將開發(fā)語言由C++改回Java。

從2006級開始,實驗框架沒有發(fā)生大的變動,只是對其進行微調(diào)或進行適當(dāng)簡化。下面是對2006～2007級教學(xué)情況的介紹。

2課程實驗項目的內(nèi)容

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

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

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

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

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

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

階段5:目標(biāo)代碼生成。實驗框架包括匯編指令選擇、寄存器分配和棧幀管理,實驗內(nèi)容可以設(shè)計為對這些部分進行改進。考慮到學(xué)生負擔(dān)問題,目前我們沒有安排這一階段的實驗任務(wù)。

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

3課程實驗項目的實施

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

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

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

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

4結(jié)語

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

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

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

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

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