“編譯原理”課程實(shí)驗(yàn)項(xiàng)目介紹

王生原 董 淵 張素琴

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

關(guān)鍵詞:編譯原理;課程實(shí)驗(yàn);Decaf/Mind項(xiàng)目

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:A

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

1Decaf/Mind項(xiàng)目的背景

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

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

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

從2003級(jí)的課程之后,我們對(duì)原始的Decaf項(xiàng)目實(shí)驗(yàn)框架進(jìn)行了3次實(shí)質(zhì)性改動(dòng)。

在2003～2004級(jí)的Decaf項(xiàng)目中,我們將原先實(shí)驗(yàn)框架的開(kāi)發(fā)語(yǔ)言由C++改為Java。

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

由于計(jì)50班的編譯課程安排在Java程序設(shè)計(jì)課程之前,所以首次Mind項(xiàng)目的開(kāi)發(fā)語(yǔ)言為C++。隨后,在2005級(jí)其他班的課程中,我們又將開(kāi)發(fā)語(yǔ)言由C++改回Java。

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

2課程實(shí)驗(yàn)項(xiàng)目的內(nèi)容

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

我們將實(shí)驗(yàn)分成如下5個(gè)階段:

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

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

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

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

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

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

3課程實(shí)驗(yàn)項(xiàng)目的實(shí)施

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

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

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

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

4結(jié)語(yǔ)

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

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

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

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

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