編譯原理上機實習指導書(2015-11修改)

1、編譯原理上機實習指導書一、上機實習目的理解編譯程序的構(gòu)造原理，掌握編譯程序的構(gòu)造方法與技術。通過實習，使學生既加深對編譯原理基礎理論的理解，又提高動手能力，特別是提高軟件設計能力。二、上機實習要求在理解編譯原理基本思想的基礎上，選擇一個自己熟悉的程序設計語言，完成編譯程序的設計和實現(xiàn)過程。編譯程序的設計可以采用自頂向下和自底向上兩種不同的方法。由于許多高級語言（如PASCAL，C）中的語法成分都是遞歸定義的，所以本實驗要求學生采用遞歸下降分析技術，這是一種自頂向下的的編譯方法，其基本思想是對語言的每個（或若干個）語法成分編制一個處理子程序，從處理<程序>這個語法成分的子程序開始，在

2、分析過程中調(diào)用一系列過程或函數(shù)，對源程序進行語法和語義分析，直到整個源程序處理完畢為止。本上機實習是為C語言(子集)設計一個編譯程序，完成詞法分析、語法分析、語義分析等功能，并生成某種機器上的目標代碼(匯編語言)或中間代碼(四元式)。三、上機實習步驟1閱讀上機實習指導書。2根據(jù)設計要求寫算法，畫程序框圖3根據(jù)框圖編寫編譯程序4輸入編譯程序并上機調(diào)試5撰寫上機實習報告四、上機實習內(nèi)容1、題目：C語言小子集編譯程序的實現(xiàn)2、C語言小子集的文法規(guī)則：<程序>:main（）<分程序> <分程序>:=<變量說明部分>；<語句部分> <變量

3、說明部分>:=<變量說明><標識符表><變量說明>:=int<標識符表>:=<標識符表>，<標識符><標識符表>:=<標識符> <標識符>:=<字母><標識符>:=<標識符><字母><標識符>:=<標識符><數(shù)字> <語句部分>:=<語句部分>；<語句>|<語句><語句>:<賦值語句>|<條件語句>|<循環(huán)語句

4、>|<賦值語句>:=<標識符>=<表達式> <條件>:=<表達式><關系運算符><表達式> <表達式>:=<項>|<表達式><加法運算符><項><項>:=<因子>|<項><乘法運算符><因子><因子>:<標識符>|<常量>|(<表達式>)<常量>:<無符號整數(shù)><無符號整數(shù)>:=<數(shù)字序列>&

5、lt;數(shù)字序列>:=<數(shù)字序列><數(shù)字><數(shù)字序列>:=<數(shù)字><加法運算符>:+|-<乘法運算符>:=*|<關系運算符>:<|>|!=|>=|<=|=<復合語句>:=<語句部分><語句1>:<語句>|<復合語句><條件語句>:=if（<條件>）<語句1>else<語句1><循環(huán)語句>:=while（<條件>）do<語句1><字母&g

6、t;:=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z<數(shù)字>:=0|1|2|3|4|5|6|7|8|93、實現(xiàn)功能：(1)詞法分析掃描源程序，根據(jù)詞法規(guī)則，識別單詞，填寫相應的表。(2)語法分析對源程序作語法分析，確定是否屬于C語言小子集，同時揭示出程序的內(nèi)在結(jié)構(gòu)。 (3)語法錯誤檢查根據(jù)C語言小子集的文法規(guī)則設置檢測手段，通過查錯子程序或一些查錯語句，報告源程序出錯位置、性質(zhì)等，直至整個程序結(jié)束為止。(4)語義分析與目標代碼生成在語法分析的基礎上，進行語義分析，生成輸入源程序的目標代碼。輸入源程序的目標代碼可以建立在一個假

7、想的處理機（虛擬機）上，或者以所學的匯編語言為基礎，也可以生成四元式序列。輸入源程序樣本：main () int a,b,y,max;a=10; b= ;while (a>0) b=a+b*a;a=a-1;x=a+b; y=b+b;if (x>y) max=x else max=y五、附錄：PL0編譯程序的實現(xiàn)1 PL0概述PL0語言是一種類PASCAL語言，是教學用程序設計語言，它比PASCAL語言簡單，作了一些限制。PL0的程序結(jié)構(gòu)比較完全，賦值語句作為基本結(jié)構(gòu)，構(gòu)造概念有順序執(zhí)行、條件執(zhí)行和重復執(zhí)行，分別由BEGIN/END、IF和WHILE語句表示。此外，PL0還具有子程序

8、概念，包括過程說明和過程調(diào)用語句。在數(shù)據(jù)類型方面，PL0只包含唯一的整型，可以說明這種類型的常量和變量。運算符有+，-，*，/，=，<>，<，>，<=，>=，(，)。說明部分包括常量說明、變量說明和過程說明。2 PL0語言的文法規(guī)則<程序>:<分程序> <分程序>:=<常量說明部分)；<變量說明部分>；<過程說明部分>；<語句部分> <常量說明部分>:=const<常量定義>，<常量定義> <常量定義>:<標識符><

9、無符號整數(shù)> <無符號整數(shù)>:=<數(shù)字><數(shù)字> <變量說明部分>:=var<標識符><標識符> <標識符>:=<字母><字母>|<數(shù)字> <過程說明部分>:=<過程首部><分程序><過程首部>:=procedure<標識符><語句部分>:=<語句>|<復合語句><復合語句>:=begin<語句>；<語句>end<語句>:<

10、;賦值語句>|<條件語句>|<當型循環(huán)語句>|<過程調(diào)用語句>| <讀語句>|<寫語句>|<復合語句>|<空語句> <賦值語句>:=<標識符>:=<表達式> <條件>:=<表達式><關系運算符><表達式>|odd<表達式> <表達式>:=+|-<項>|<表達式><加法運算符><項><項>:=<因子>|<項><乘

11、法運算符><因子><因子>:<標識符>|<常量>|(<表達式>)<常量>:<無符號整數(shù)><加法運算符>:+|-<乘法運算符>:=*|<關系運算符>:<|>|<>|>=|<=|=<條件語句>:=if<條件>then<語句><過程調(diào)用語句>:=call<標識符><當型循環(huán)語句>:=while<條件>do<語句><讀語句>:=read

12、(<標識符>，<標識符>) <寫語句>:=write(<表達式>，<表達式>)<字母>:=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z<數(shù)字>:=0|1|2|3|4|5|6|7|8|93 PL0編譯程序的設計思想編譯程序的設計可以采用自頂向下和自底向上兩種不同的方法。由于許多高級語言（如PASCAL，C）中的語法成分都是遞歸定義的，PL0也是如此，所以本實驗采用遞歸子程序法，這是一種自頂向下的的編譯方法，其基本思想是對源程序的每個（或若干個）語法成分編制

13、一個處理子程序，從處理<程序>這個語法成分的子程序開始，在分析過程中調(diào)用一系列過程或函數(shù)，對源程序進行語法和語義分析，直到整個源程序處理完畢為止。4PL0編譯程序的功能(1)語法分析 對由PL0語言編制的程序作語法分析，確定是否屬于PL0語言，同時揭示出程序的內(nèi)在結(jié)構(gòu)。 (2)語法錯誤檢查 根據(jù)PL0語言的文法規(guī)則設置檢測手段，通過查錯子程序和一些查錯語句，報告源程序出錯位置、性質(zhì)等，直至整個程序結(jié)束為止。 (3)生成目標代碼 PL0語言的目標代碼是建立在一個假想的處理機上，此處理機稱為PL0處理機。 (4)執(zhí)行目標代碼 PL0處理機是一種假想的處理機，其目標代碼不能在實際的機器上

14、執(zhí)行，故此編譯程序設置了一個子程序，它對PL0語言的目標代碼逐條解釋執(zhí)行，最后得出所需結(jié)果。5PL0編譯程序的有關過程及函數(shù)在PL0語言的編譯文本中，除了常量和變量說明外，共有18個相互嵌套或并列的過程(或函數(shù))?，F(xiàn)對這些過程和函數(shù)作扼要說明。(1)error(n)：其功能是報告PL0源程序的出錯信息。n為錯誤類型號，共可查出36種錯誤。(2)getsym：詞法分析子程序。其功能為讀單詞。getch：讀字符子程序。它嵌套于讀單詞子程序中。(3)gen(x，y，z)，偽代碼生成子程序。其功能是根據(jù)不同的x、y、z生成不同的偽代碼。x表示指令碼，y表示層差，z表示位移量或數(shù)。 (4)test(sl

15、，s2，n)：查錯子程序。其功能是檢測源程序中的語法錯誤。(5)block(1ev，tx，fsys)：分程序處理模塊。其功能為對分程序進行處理。lev表示層差，tx表示標識符表的下標，fsys是符號集，表示可能出現(xiàn)的符號。分程序處理模塊是整個編譯程序的核心，它包含以下的過程和函數(shù)。enter(k)：其功能是造符號表table。k表示符號的類型，其取值范圍是(constant， variable，proceable)，即此子程序?qū)ΤＡ?、變量和過程造符號表table，以備檢查標識符是否說明過。position(id)：其功能是查符號表，它是一個函數(shù)。 id是所檢查的標識符，若查到則給出標識符id在

16、標識符表中的位置，否則給0。constdeclaration：常量造表子程序。其功能是為常量造一張常量表，內(nèi)填常量名、常量值。它通過調(diào)用子程序enter(k)完成，此時kconstant。vardeclaration：變量造表子程序。其功能是為變量造一張變量表，內(nèi)填變量名、所處層號。它也是通過調(diào)用子程序enter(k)來完成的，此時k=variable。listcode，打印(偽)代碼子程序。其功能是輸出生成的目標代碼。statement(fsys)：語句處理子程序。其功能是處理語句，它是遞歸調(diào)用的核心部分。其遞歸調(diào)用順序如下：expression(fsys)：處理算術表達式子程序；term(

17、fsys)：處理項子程序；condition(fsys)：處理因子子程序。(6)interpret，執(zhí)行目標代碼子程序。其功能是對編譯過程中生成的目標代碼(偽代碼)逐條解釋執(zhí)行。 base(l)：提供計算靜態(tài)鏈信息子程序。它為過程調(diào)用提供調(diào)用所需的基地址。整個PL0編譯程序通過主程序調(diào)用分程序處理模塊block，再通過block遞歸調(diào)用上述的子程序，達到對PL0語言的程序進行編譯的目的。6編譯步驟程序中用數(shù)組word存貯PL0語言的所有保留字。保留字有begin、call、const、do、end、if、odd、procedure、read、then、var、while、write；用數(shù)組sw

18、ym存貯保留字所對應的符號表symbol中的符號；用數(shù)組ssym存貯關系運算符及特殊符號+、-、*、/、(、)、=、，、<、>及；所對應的符號表symbol中的符號；用數(shù)組mnemonic存貯目標代碼的指令碼部分。其具體步驟如下：在主程序中給出編譯程序所需的初始值。置字符字數(shù)cc、行長ll、代碼分配下標cx、錯誤個數(shù)err等為0。調(diào)getsym讀單詞；調(diào)block模塊，進入分程序處理；判斷所讀單詞是否為常量說明符號constsym，是則轉(zhuǎn)4），否則轉(zhuǎn)5）。讀單詞并作常量說明處理；查所讀單詞是否為“，”，是則重復本步；否則判斷此單詞是否為“；”，是則讀單詞，否則給出出錯信息。進行下一

19、步；所讀單詞是否為變量說明符號variable，是則讀單詞并作變量說明處理，再讀單詞并判斷是否為“，”，是則重復本步；否則判斷此單詞是否為“；”，是則讀單詞，否則給出出錯信息。進行下一步；cxl:=cx，并生成jmp 0，0指令，判斷所讀單詞是否為過程說明符號proceduresym，是則讀單詞轉(zhuǎn)7），否則轉(zhuǎn)11）；判斷所讀單詞是否為標識符，是則轉(zhuǎn)8），否則給出出錯信息再進行下一步；標識符填表，再讀單詞。判斷所讀單詞是否為“；”，是則讀單詞，否則給出出錯信息。進行下一步；遞歸調(diào)用分程序處理子程序block； 最近所讀單詞是否為“；”，是則繼續(xù)讀一單詞，否則給出出錯信息。轉(zhuǎn)6）；codecxl.

20、a:=cx，生成分配局部變量指令，語句處理，生成opr 0，0指令；返回主程序，err是否為0，是則調(diào)子程序interpret，轉(zhuǎn)13），否則給出出錯信息，結(jié)束編譯；解釋執(zhí)行生成的目標代碼，列出結(jié)果。 PL0編譯程序及主要參數(shù)1)PL0編譯程序program plO(input，output，ff，fi，fw2)；帶有代碼生成的PL0編譯程序 label 99； const norw13； 保留字個數(shù) txmax=100， 標識符表的長度nmax=14， 數(shù)中數(shù)字的最大個數(shù)a1=10； 標識符的長度amax20471；最大地址 levmax3； 程序體嵌套的最大深度cxmax200； 代碼數(shù)組

21、的大小writex=20；type symbol=(nul，ident，number，plus，minus，times，slash，oddsym，eql，neq，lss，leq，gtr，geq，lparen，rparen，comma，semicolon，period，becomes，beginsym， endsym，ifsym，thensym，whilesym，dosym，callsym，constsym，varsym，procsym，readsym，writesym，upcomma) ；alfapacked array1.a1 of char；object(constant，variable

22、，proceable) ；symsetset Of symbol；fct=(1it，opr，lod，sto，cal，int，jmp，jpc)；functionsinstruction=packed recordf：fct ； 功能碼l: 0.1evmax；層a：0.amax； 相對地址end； lit 0，a ：取常數(shù)a opr 0，a：執(zhí)行運算a lod l，a：取層差為l，相對地址為a的常量 sto l，a：存到層差為l，相對地址為a的變量 cal l，a：調(diào)用層差為l的過程 int 0，a：t寄存器增加a jmp 0，a: 轉(zhuǎn)移到指令地址a處 jpc 0，a：條件轉(zhuǎn)移到指令地址a處 va

23、r ff,fi：text； 輸入文件名ff和fifw2：text； 輸出文件名fw2ch：char； 最近讀到的字符sym：symbol； 最近讀到的符號id：alfa； 最近讀到的標識符num：integer； 最近讀到的數(shù)cc：integer； 字符計數(shù)ll：integer； 行長wx：integer；kk，err，cw：integer；cx：integer； 代碼分配下標line：array1.81of char；a：alfa；chwr：array1.writex of alfa；code：array0.cxmax of instruction；word：array1.norw of a

24、lfa；wsym：array1.norw of symbol；ssym：arraychar of symbol；mnemonic：arrayfct of packed array1.3 of char；declbegsys，statbegsys，facbegsys：symset；table：array0.txmax of recordname：alfa；case kind：object of constant：(val：integer)； variable，proceable：(1evel，dr：integer)；end；procedure error(n:integer)； 出錯顯示子程序

25、begin writeln(fw2，*,：cc，n：2)： err:=err+1； end；procedure getsym； 讀單詞子程序 var i，j，k：integer； procedure getch; 讀字符子程序 begin if cc=ll then begin if eof(ff) then begin write(fw2，program incompletet)； goto 99；end； ll:=O；cc:=0；write(fw2，cw：5， )；cw:=cw+1； while not(eoln(ff) do begin ll:=ll+1 ；read(ff，ch) ；wr

26、ite(fw2，ch) ； linell:=ch； end； writeln(fw2)；ll:=ll+1；read(ff，1inell) ； end； cc:=cc+l；ch:=linecc ； end； 讀字符子程序結(jié)束 begin 讀單詞子程序開始 while ch do getch； if ch in a.z then begin kc:=0； repeat if k<a1 then begin k:=k+1；ak:=ch； end； getch； until not(ch ina.z，0.9)； if k>=kk then kk:=k else repeat akk:= ；

27、kk:=kk-1； untll kk=k； id:=a；i:=1；j:=norw； repeat k=(i+j) div 2； if id<=wordk then j:=k-1； if id>=wordk then i:=k+1； untll i>j； if i-1>j then sym:=wsymk e1se sym:=ident； end 標識符或保留字處理結(jié)束 else if ch in 0.9 then begin 數(shù)處理 k:=0；num:=0；sym:=number； repeat num:=10*num+(Ord(ch)一Ord(0)； k:=k+1；ge

28、tch； until not(ch in0.9) ； if k>nmax then error(30) end 數(shù)處理結(jié)束 e1se if ch: then begin getch； if ch= then begin sym:=becomes；getch； end else sym:=nul； end else case ch of +，-，*，,(，)，=, ；,.：begin sym:=ssymch ； getch； end；>：begin getch； if ch= then begin sym:=geq；getch；end else sym:=gtr； end； <

29、：begin getch； if ch= then begin sym:=leq；getch；end else if ch=> then begin sym:=neq；getch；end else sym:=lss；end end ； case end； 讀單詞子程序結(jié)束procedure gen(x：fct；y，z：integer) ； 代碼生成子程序 begin if cx>cxmax then begin write(program too long) ； goto 99 end； with codecx do begin f:=x；l:=y；a:=z end； cx:=cx

30、+1end； 代碼生成子程序結(jié)束 procedure test(s1，s2：symset；n：integer) ； begin if not(sym in s1) then begin error(n)；s1:=s1+s2； while not(sym in s1)do getsym end； end；procedure block(1ev，tx：integer；fsys：symset)； 分程序處理模塊 var dx ：integer； 數(shù)據(jù)分配下標 txO：integer； 起始標識符的下標 cxO：integer； 起始代碼的下標 procedure enter(k：object)；把o

31、bject填入標識符表中 begin tx：tx+1； with tabletx do begin name:=id；kind:=k； case kind of constant：begin if num>amax then begin error(30)；num:=0 ； end； val:=num； end； variable：begin level:=levl；dr:=dx；dx:=dx+l；end； proceable：level:=lev end case end end； 填標識符表子程序結(jié)束 function position(id：alfa)：integer； 在標識符表

32、中查標識符id var i：integer； begin :=id；i:=tx； while tableI.name<>id do i:=i-1； position:=i； end； position procedure constdeclaration； 常量說明處理子程序 begin if sym=ident then begin getsym； if sym in eql，becomes then begin if symbecomes then error(1)； getsym； if sym=number then begin enter(const

33、ant) ； getsym； end else error(2) end else error(3) end else error(4) end； constdeclaration procedure vardeclaration； 變量說明處理子程序 begin if sym=ident then begin enter(variable) ；getsym； end else error(4) end； vardeclaration procedure listcode； 列出本程序體生成的代碼子程序 var i：integer； begin for i:=cxO to cx-1 do wi

34、th codei do writeln(fw2，i，mnemonici：5，l:3，a：5) end； listcode procedure statement(fsys：symset)；語句處理子程序 var i，cxl，cx2integer； procedure expression(fsys:symset)； 表達式處理子程序 var addop：symbol； procedure term(fsys:symset) ； 項處理子程序 var mulop：symbol； procedure factor(fsys：symset)； 因子處理子程序 var i：integer； begin

35、 test(facbegsys，fsys，24) ； while sym in facbegsys do begin if sym=ident then begin i:=position(id)； if i=0 then error(11) else with tablei do case kind of constant：gen(1it，0，val)； variable：gen(lod，lev-level，dr)； proceable：error(21) end； getsym； end else if sym=number then begin if num>amax then b

36、egin error(30) ；num:=O；end； gen(lit，0，num)；getsym； end else if sym=lparen then begin getsym； expression(rparen+fsys)； if sym=rparen then getsym else error(22) end； test(fsys，1paren，23) end end； factor begin 項處理子程序開始 factor(fsys+times，slash) ； while sym intimes，slash do begin mulop:=sym；getsym； facto

37、r(fsys+times，slash) ； if mulop=times then gen(opr，0，4) else gen(opr，0，5) end end； 項處理子程序結(jié)束 begin 表達式處理子程序開始) if sym in plus，minus then begin addop:=sym；getsym； term(fsys+plus，minus) ； if addop=minus then gen(opr，0，1) end else term(fsys+plus，minus)； while sym in plus，minus do begin addp:=sym；getsym；

38、term(fsys+plus，minus)； if addop=plus then gen(opr，0，2) else gen(opr，0，3) endend；exprssion procedure condition(fsys:symset)； 條件表達式處理子程序開始 var relop:symbol； begin if sym=oddsym then begin getsym；expression(fsys) ；gen(opr，0，6)； end else begin expression(eql，neq，1ss，gtr，leq，geq+fsys) ； if not(sym ineql，

39、neq，1ss，leq，gtr，geq) then error(20) else begin relop:=sym；getsym； expression(fsys)； case relop of eql：gen(opr，0，8)； neq：gen(opr，0，9)； lss：gen(opr，0，10)； geq: gen(opr，0，11) ； gtr：gen(opr，0，12) ； 1eq：gen(opr，0，13) ； end end end end； conditionbegin 語句處理子程序開始 if sym=ident then 賦值語句處理 begin i:=position(id) ； if i0 then error(11) else if tablei.kind<>variable then begin error(12) ； 對非變量賦值 i:=0； end； getsym； if sym=becomes then getsym else error(13) ； expression(fsys) ； if i<>0 then with tablei do gen(sto，1ev-