編譯原理修改后地PL0報告材料

實用文案一、上機實踐要求“編譯原理與技術”的上機實驗要求你對 PL/0語言及其編譯器進行擴充和修改。 每個擴充或修改方式可得到不同的分數(shù)，滿分為 100分。完成上機作業(yè)后，必須提交下列文檔：1）修改后的PL/0語言文本。包含詞法分析（正規(guī)式），語法分析（BNF）。2）有關修改后的PL/0編譯/解釋器的說明。詳細說明你的編譯器是如何編譯新的PL/0語言程序的。指出你的程序中最精彩的部分，以及你為什么這樣做，你是如何控制和恢復語義錯誤的。3）給出你所改動后的編譯器源程序清單，并標記出你所修改的部分。比較你的編譯器和原來的編譯器之間的差別。4）說明你的編譯器中可能存在的錯誤。5）總結經(jīng)驗與教訓，如果重做一遍，你會有哪些新的改進？對現(xiàn)存的PL/0編譯程序可做如下修改或擴充，其中（ 1）、（2）、（11）和（12）必須完成，剩余的均可任意選擇，但總分必須超過 70分。1）注釋（5分）注釋由(*和*)包含，不允許嵌套。2）布爾類型的數(shù)據(jù)（10分）布爾類型的BNF為：var_option →ε|varvar_decl_listvar_decl_list →var_decl|var_decl_listvar_declvar_decl →ident_list:data_typedata_type →integer |boolean標準文檔實用文案這種修改包括：（i） 區(qū)別整型與布爾型變量、常量和表達式。（ii） 增加按嚴格計算的布爾類型運算符 and、or和not。這些算符以及己有的運算符的優(yōu)先級與Pascal語言相同。（iii） 能夠使用布爾常量 true和false。iv）把PL/0語言中的“條件”概念一般化為Pascal語言那樣。v）布爾表達式可以比較大?。篺alse<true3）布爾表達式的短路計算（5分）增加布爾類型（見（2），除（2）的（ii）外），但對and和or采取短路計算。4）數(shù)組（10分）增加由任何數(shù)據(jù)類型構造的一維數(shù)組。數(shù)組的下標限于純量類型。注意：數(shù)組可以由其它的數(shù)組來構造，因而必須考慮多維數(shù)組的情況。數(shù)組的上下界可為任意的純量常數(shù)。數(shù)組的定義如下：data_type →integer |boolean |array[const..const] ofdata_typeconst →ident |number語言中允許有數(shù)組說明，對數(shù)組元素賦值，在表達式中引用數(shù)組元素。 為了便于解釋執(zhí)行，可能要增加新的PL/0機器操作指令。5）參數(shù)（10分）語法同Pascal，采用值-結果方式傳遞（不用var聲明）。6）函數(shù)（10分）語法同Pascal。7）else子句和repeat語句（5分）8）for語句，語法參照Pascal或C語言（5分）標準文檔實用文案（9） exit語句（退出當前執(zhí)行過程）和 break語句（跳出包含它的最內(nèi)層循環(huán)），（5分）10）記錄（結構）,語法同Pascal語言（10分）。11）更有力的語法錯誤恢復機制（20分）12）分離解釋和編譯器（5分）注意：上面的這些要求有時會互相影響 ：例如實現(xiàn)布爾類型數(shù)據(jù)，則數(shù)組和參數(shù)就應該能處理其相互組合的情況，如布爾型數(shù)組（包括多維數(shù)組）、布爾型作為下標的數(shù)組、布爾型作為參數(shù)傳遞。甚至能夠實現(xiàn)數(shù)組作為參數(shù)傳遞等。另外，為了實現(xiàn)以上功能，你可任意增加 PL/0處理機的指令。但要注意指令的簡單與合理。選做題：此題不計入總分，僅做為學生在有余力的情況下的進一步練習。實現(xiàn)PL/0語言的輸入、輸出語句。其語法、語義定義和 Pascal語言相同?？梢詢H僅實現(xiàn)一次輸入或輸出一個值的語句——語句參數(shù)固定；也可以實現(xiàn)完全和 Pascal語言一樣，能夠接受任意個數(shù)參數(shù)的輸入或輸出語句。二、實驗原理：就像一個翻譯要把漢語翻譯成英語，必須對漢語和英語的單詞、語法結構都很精通，才有可能翻譯得準確無誤。另外，編譯程序既然是為了完成這種功能的一個程序，就存在用什么語言來編寫這個程序的問題。這些問題在本節(jié)將逐步介紹。現(xiàn)對PL/0語言編譯程序的功能用“ T”型圖表示，并用圖形概括描述 PL/0編譯程序的結構框架。用語法圖描述語法規(guī)則的優(yōu)點是直觀、 易讀。在圖1.1的語法圖中用橢圓和圓圈中的英文字表示終結符，用長方形內(nèi)的中文字表示非終結符。所謂終結符，是構成語言文法的單詞，是語法成分的最小單位，而每個非終結符也是一個語法成分。但非終結符可由其它文法符號定義，終結符不能由其它文法符號定義。例如，程序是由非終結符 '標準文檔實用文案分程序'和終結符"."組成的串定義的。由于對某些非終結符可以遞歸定義，如圖1.1(b)、2.1(c)、2.1(e)中：分程序、表達式和語句。第一個非終結符'程序'為文法的開始符號。程序.分程序1.1（a）語句序列語句;1.1(c)條件 odd 表達式表達式>== <> < > <=表達式標準文檔實用文案1.1(e)分程序=const ident number,;var ident,;;procedure ident; 程序體標準文檔實用文案語句1.1(b)語句identcallifbeginwhile

:= 表達式ident語句序列條件 then 語句enddo條件 語句標準文檔實用文案1.1(d)表達式+項1.1(f)項

- + -項因子/*因子標準文檔實用文案1.1(g)因子identnumber( 表達式 )1.1(h)如：{*}表示*重復任意次，{*}38表示*重復3-8次。[]：方括號表示其內(nèi)的成分為任選項。()：表示圓括號內(nèi)的成分優(yōu)先。例：用EBNF描述<整數(shù)>文法的定義 ：<整數(shù)>∷=[+|-]< 數(shù)字>{<數(shù)字>}<數(shù)字>∷=0|1|2|3|4|5|6|7|8|9或更好的寫法整數(shù)>∷=[+|-]<非零數(shù)字>{<數(shù)字>}|0非零數(shù)字>∷=1|2|3|4|5|6|7|8|9標準文檔實用文案數(shù)字>∷=0|<非零數(shù)字>PL/0語言文法的EBNF表示為：〈程序〉∷=〈分程序〉．〈分程序〉∷=[〈常量說明部分〉][〈變量說明部分〉][〈過程說明部分〉]〈語句〉〈常量說明部分〉∷=CONST〈常量定義〉{，〈常量定義〉}；〈常量定義〉∷=〈標識符〉=〈無符號整數(shù)〉〈無符號整數(shù)〉∷=〈數(shù)字〉{〈數(shù)字〉}〈變量說明部分〉∷=VAR〈標識符〉{，〈標識符〉}；〈標識符〉∷=〈字母〉{〈字母〉|〈數(shù)字〉}〈過程說明部分〉∷=〈過程首部〉〈分程序〉{；〈過程說明部分〉}；〈過程首部〉∷=PROCEDURE〈標識符〉；〈語句〉∷=〈賦值語句〉|〈條件語句〉|〈當型循環(huán)語句〉|〈過程調(diào)用語句〉|〈讀語句〉|〈寫語句〉|〈復合語句〉|〈空〉〈賦值語句〉∷=〈標識符〉∶=〈表達式〉〈復合語句〉∷=BEGIN〈語句〉{；〈語句〉}END〈條件〉∷=〈表達式〉〈關系運算符〉〈表達式〉|ODD〈表達式〉〈表達式〉∷=[+|-]〈項〉{〈加法運算符〉〈項〉}〈項〉∷=〈因子〉{〈乘法運算符〉〈因子〉}〈因子〉∷=〈標識符〉|〈無符號整數(shù)〉|'('〈表達式〉')'〈加法運算符〉∷=+|-〈乘法運算符〉∷=*|/〈關系運算符〉∷=#|=|＜|＜=|＞|＞=標準文檔實用文案〈條件語句〉∷=IF〈條件〉THEN〈語句〉〈過程調(diào)用語句〉∷=CALL〈標識符〉〈當型循環(huán)語句〉∷=WHILE〈條件〉DO〈語句〉〈讀語句〉∷=READ'('〈標識符〉{，〈標識符〉}')'〈寫語句〉∷=WRITE'('〈表達式〉{，〈表達式〉}')'〈字母〉∷=a|b|?|X|Y|Z〈數(shù)字〉∷=0|1|2|?|8|9EBNF表示的符號說明?！担河米笥壹饫ㄌ柪ㄆ饋淼闹形淖直硎菊Z法構造成分，或稱語法單位，為非終結符?！?：該符號的左部由右部定義，可讀作'定義為'。|：表示'或'，為左部可由多個右部定義。{}：花括號表示其內(nèi)的語法成分可以重復。在不加上下界時可重復 0到任意次數(shù)，有上下界時為可重復次數(shù)的限制。用語法圖描述語言的語法與 EBNF描述相比較：語法圖描述： 直觀，易讀，易寫。EBNF表示：形式化強，易機器識別。無論用語法圖或 EBNF作為描述程序設計語言語法的工具，對描述的語法可以檢查哪些符號序列是所給語言的合法程序，一個程序設計語言如 C或JAVA，用戶可用它寫出成千上萬個不同的程序， 但C或JAVA它們各自的語法只有一個，這就使得無窮的句子集可用有窮的文法（語法）描述。PL/0編譯程序的使用限制標識符的有效長度是10數(shù)字最多為14位標準文檔實用文案

過程最多可嵌套三層，可遞歸調(diào)用

標識符的作用域同 PASCAL，內(nèi)層可引用包圍它的外層定義的標識符（如：變量名，過程名，常量名）目標指令有8條：①LIT：將常量值取到運行棧頂。 a域為常數(shù)值。LOD：將變量放到棧頂。a域為變量在所說明層中的相對位置,l為調(diào)用層與說明層的層差值。③STO：將棧頂?shù)膬?nèi)容送入某變量單元中。 a,l域的含意同LOD指令。④CAL：調(diào)用過程的指令。a為被調(diào)用過程的目標程序入口地址， l為層差。INT：為被調(diào)用的過程(或主程序)在運行棧中開辟數(shù)據(jù)區(qū)。a域為開辟的單元個數(shù)。⑥JMP：無條件轉移指令，a為轉向地址。⑦JPC：條件轉移指令，當棧頂?shù)牟紶栔禐榉钦鏁r，轉向 a域的地址，否則順序執(zhí)行。⑧OPR：關系運算和算術運算指令。將棧頂和次棧頂?shù)膬?nèi)容進行運算，結果存放在次棧頂，此外還可以是讀寫等特殊功能的指令，具體操作由 a域值給出。（詳見解釋執(zhí)行程序）。類pcode代碼指令的詳細解釋（指令功能表）認識目標代碼類pcode目標代碼類pcode是一種假想棧式計算機的匯編語言。指令格式：f l a功能碼l層次差 （標識符引用層減去定義層）標準文檔實用文案根據(jù)不同的指令有所區(qū)別指令功能表LIT0a將常數(shù)值取到棧頂，a為常數(shù)值LODla將變量值取到棧頂，a為偏移量，l為層差STOla將棧頂內(nèi)容送入某變量單元中，a為偏移量，l為層差CALla調(diào)用過程，a為過程地址，l為層差INT0a在運行棧中為被調(diào)用的過程開辟a個單元的數(shù)據(jù)區(qū)JMP0a無條件跳轉至a地址JPC0a條件跳轉，當棧頂布爾值非真則跳轉至a地址，否則順序執(zhí)行OPR00過程調(diào)用結束后,返回調(diào)用點并退棧OPR01棧頂元素取反OPR02次棧頂與棧頂相加，退兩個棧元素，結果值進棧OPR03次棧頂減去棧頂，退兩個棧元素，結果值進棧OPR04次棧頂乘以棧頂，退兩個棧元素，結果值進棧OPR05次棧頂除以棧頂，退兩個棧元素，結果值進棧OPR06棧頂元素的奇偶判斷，結果值在棧頂標準文檔實用文案OPR07OPR08 次棧頂與棧頂是否相等，退兩個棧元素，結果值進棧OPR09 次棧頂與棧頂是否不等，退兩個棧元素，結果值進棧OPR010 次棧頂是否小于棧頂，退兩個棧元素，結果值進棧OPR011 次棧頂是否大于等于棧頂，退兩個棧元素，結果值進棧OPR012 次棧頂是否大于棧頂，退兩個棧元素，結果值進棧OPR013 次棧頂是否小于等于棧頂，退兩個棧元素，結果值進棧OPR014 棧頂值輸出至屏幕OPR015 屏幕輸出換行OPR016 從命令行讀入一個輸入置于棧頂PL/0語言可看成是PASCAL語言的子集，它的編譯程序是一個編譯解釋執(zhí)行系統(tǒng)。 PL/0的目標程序為假想棧式計算機的匯編語言，與具體計算機無關。 PL/0的編譯程序和目標程序的解釋執(zhí)行程序都是用PASCAL語言書寫的，因此 PL/0語言可在配備PASCAL語言的任何機器上實現(xiàn)。其編譯過程采用一趟掃描方式，以語法分析程序為核心，詞法分析程序和代碼生成程序都作為一個獨立的過程，當語法分析需要讀單詞時就調(diào)用詞法分析程序， 而當語法分析正確需生成相應的目標代碼時， 則調(diào)用代碼生成程序。此外，用表格管理程序建立變量、常量和過程標識符的說明與引用之間的信息聯(lián)系。用出錯處理程序對標準文檔實用文案詞法和語法分析遇到的錯誤給出在源程序中出錯的位置和錯誤性質。 當源程序編譯正確時，PL/0編譯程序自動調(diào)用解釋執(zhí)行程序，對目標代碼進行解釋執(zhí)行，并按用戶程序要求輸入數(shù)據(jù)和輸出運行結果。本書所提供的PL/0語言編譯器的基本工作流程如圖 1-1所示：源程序詞法分析語法分析符錯誤號診表語義分析斷管處理理代碼生成代碼執(zhí)行執(zhí)行結果圖1-1PL/0 編譯器基本工作流程標準文檔實用文案由于PL/0編譯程序采用一趟掃描方法，所以語法分析過程 BLOCK是整個編譯過程的核心。下面我們將在圖2.4中先給出編譯程序的總體流程，以弄清 BLOCK過程在整個編譯程序中的作用。在流程圖 2.4中可以看出，主程序置初值后先調(diào)用讀單詞過程 GETSYM取一個單詞，然后再調(diào)用語法分析過程BLOCK，直到遇源程序的結束符 "．"為止。語法分析過程 BLOCK是整個編譯過程的核心，是指開始由主程序調(diào)用 GETSYM取一個單詞，再調(diào)用語法分析過程BLOCK，BLOCK由當前單詞根據(jù)語法規(guī)則再調(diào)用其它過程， 如說明處理、代碼生成或出錯處理等過程進行分析，當分析完一個單詞后， BLOCK再調(diào)用GETSYM取下一個單詞，一直重復到當前單詞為結束符"．"表明源程序已分析結束。若未取到結束符 "．"，而源程序已沒有輸入符號，這時表明源程序有錯誤，無法再繼續(xù)分析。PL/0的詞法分析程序 GETSYM(圖2.5)是一個獨立的過程，其功能是為語法分析提供單詞用的，是語法分析的基礎，它把輸入的字符串形式的源程序分割成一個個單詞符號。為此 PL/0編譯程序設置了三個全程量的公用單元如下：SYM：存放每個單詞的類別，用內(nèi)部編碼形式表示。ID：存放用戶所定義的標識符的值。即標識符字符串的機內(nèi)表示。NUM：存放用戶定義的數(shù)。標準文檔實用文案單詞的種類有五種?；咀郑阂部煞Q為保留字或關鍵字，如 BEGIN，END，IF，THEN等。運算符：如：+、-、*、／、∶=、#、＞=、＜=等。標識符：用戶定義的變量名、常數(shù)名、過程名。常數(shù)：如：10，25，100等整數(shù)。界符：如：'，'、'.'、'；'、'('、')'等。如果我們把基本字、運算符、界符稱為語言固有的單詞，而對標識符、常數(shù)稱為用戶定義的單詞。那么經(jīng)詞法分析程序分出的單詞，對語言固有的單詞只給出類別存放在 SYM中，而對用戶定義的單詞(標識符或常數(shù))既給類別又給值，其類別放在 SYM中，值放在ID或NUM中，全部單詞種類由編譯程序定義的純量類型 SYMBOL給出，也可稱為語法的詞匯表。如下面提到的 IFSYM，THENSYM，IDENT，NUMBER均屬SYMBOL中的元素。當識別到字母開頭的字母數(shù)字串時，先查關鍵字表。若查不到則為標識符，查到則為關鍵字。 PL/0編譯程序文本中主程序開始對關鍵字表置初值如下：關鍵字表為：word[1]:='begin' ；word[2]:='call' ；...word[13]:='write' ；每個數(shù)組元素的字符長度為 10，不滿10個字符時，以空格補滿。查到時找到關鍵字相應的內(nèi)部表示為：Wsym[1]:=beginsym;wsym[2]:=callsym ；?wsym[13]:=writesym ；標準文檔實用文案PL/0編譯程序文本中開始對類型的定義中給出單詞定義為：typesymbol=(nul,ident,number,plus, ?,varsym,procsym) ；定義單詞是純量/枚舉類型，又定義了 3個全程量為：sym:symbol;id:alfa;num:integer;因此詞法分析程序 GETSYM將完成下列任務：濾空格：空格在詞法分析時是一種不可缺少的界符，而在語法分析時則是無用的，所以必須濾掉。識別保留字：設有一張保留字表。對每個字母打頭的字母、數(shù)字字符串要查此表。若查著則為保留字，將對應的類別放在SYM中。如IF對應值IFSYM，THEN對應值為THENSYM。若查不著，則認為是用戶定義的標識符。(3)識別標識符：對用戶定義的標識符將IDENT放在SYM中，標識符本身的值放在ID中。(4)拼數(shù)：當所取單詞是數(shù)字時，將數(shù)的類別NUMBER放在SYM中，數(shù)值本身的值存放在NUM中。拼復合詞：對兩個字符組成的算符如：＞=、∶=、＜= 等單詞，識別后將類別送 SYM中。輸出源程序：為邊讀入字符邊輸出(可輸出在文件中)。GETCH所用單元說明：CH：存放當前讀取的字符，初值為空。LINE：為一維數(shù)組，其數(shù)組元素是字符，界對為 1∶80。用于讀入一行字符的緩沖區(qū)。LL和CC為計數(shù)器，初值為 0。標準文檔實用文案GETSYM流程圖的工作單元說明：A：一維數(shù)組，數(shù)組元素為字符，界對 [1∶10]。ID：同A。WORD：保留字表，一維數(shù)組，數(shù)組元素是以字符為元素的一維數(shù)組。界對為 [1∶13]。查表方式采用二分法。單個字符對應的單詞表的建立是，首先在主程序中定義了下標為字符的數(shù)組 ssym，數(shù)組ssym的元素為單詞，主程序開始對下標為字符的所有數(shù)組元素置初值為 nul，對PL/0語言用到的單個字符為單詞的，將其字符作為數(shù)組下標的元素置初值為對應的單詞。如：ssym['+']:=plus;ssym['-']:=minus;?ssym[';']:=semicolon;PL/0編譯程序的語法分析PL/0編譯程序語法、語義分析是整個編譯程序設計與實現(xiàn)的核心部分 ,要求學員努力學習掌握實現(xiàn)技術和方法?，F(xiàn)分別說明語法分析實現(xiàn)的主要思想方法和語義分析的實現(xiàn)。語法分析的任務是識別由詞法分析給出的單詞符號序列在結構上是否符合給定的文法規(guī)則。 PL/0語言的文法規(guī)則已在 2.1節(jié)中給出。本節(jié)將以語法圖描述的語法形式為依據(jù)，給出語法分析過程的直觀思想。PL/0編譯程序的語法分析采用了自頂向下的遞歸子程序法。什么是自頂向下的語法分析？可形象地對該程序自頂向下構造一棵倒掛著的語法分析樹，其構造方法是：（1）由開始符號非終結符'程序'作為分析樹的根結點，由非終結符 '程序'規(guī)則的右部為子結點。（2）對分析樹中的每個非終結符結點，選擇它規(guī)則的一個右部為子結點構造分析樹的下一層。標準文檔實用文案（3）重復（2）直到分析樹中的末端結點只有終結符。（4）若分析樹中的末端結點從左到右連接的終結符號串剛好是輸入的程序終結符號串，則說明所給程序在語法上是正確的。粗略地說：自頂向下的遞歸子程序法就是對應每個非終結符語法單元，編一個獨立的處理過程 (或子程序)。語法分析從讀入第一個單詞開始由非終結符'程序'即開始符號出發(fā)，沿語法描述圖箭頭所指出的方向進行分析。當遇到非終結符時，則調(diào)用相應的處理過程，從語法描述圖看也就進入了一個語法單元，再沿當前所進入的語法描述圖的箭頭方向進行分析，當遇到描述圖中是終結符時，則判斷當前讀入的單詞是否與圖中的終結符相匹配，若匹配，則執(zhí)行相應的語義程序(就是翻譯程序)。再讀取下一個單詞繼續(xù)分析。遇到分支點時將當前的單詞與分支點上的多個終結符逐個相比較，若都不匹配時，可能是進入下一非終結符語法單位或是出錯。如果一個PL/0語言的單詞序列在整個語法分析中，都能逐個得到匹配，直到程序結束符'.'，這時就說所輸入的程序是正確的。對于正確的語法分析做相應的語義翻譯，最終得出目標程序。以上所說語法分析過程非常直觀粗淺，實際上應用遞歸子程序法構造語法分析程序時，對文法有一定的要求和限制，這個問題我們將在第5章詳細討論。此外，從PL/0的語法描述圖中可以清楚地看到，當對PL/0語言進行語法分析時，各個非終結符語法單元所對應的分析過程之間必須存在相互調(diào)用的關系。這種調(diào)用關系可用圖1-2表示。也可稱為PL/0語法的依賴圖，在圖中箭頭所指向的程序單元表示存在調(diào)用關系，從圖中不難看出這些子程序在語法分析時被直接或間接遞歸調(diào)用。由圖1-2PL/0語法調(diào)用關系圖可以看出對分程序和語句為直接遞歸調(diào)用， 對表達式為間接遞歸調(diào)用。程序程序體標準文檔 語句實用文案標準文檔實用文案表達式的EBNF〈表達式〉∷=[+|-]〈項〉{（+|-）〈項〉}〈項〉∷=〈因子〉{（*|/）〈因子〉}〈因子〉∷=〈標識符〉|〈無符號整數(shù)〉|‘（’〈表達式〉‘）’〈表達式〉的遞歸子程序實現(xiàn)procedureexpr;beginifsymin[plus,minus]thenbegingetsym;term;endelseterm;whilesymin[plus,minus]dobegingetsym;term;endend;〈項〉的遞歸子程序實現(xiàn)procedureterm;beginfactor;whilesymin[times,slash]do標準文檔實用文案begingetsym;factor;endend;〈因子〉的遞歸子程序實現(xiàn)procedurefactor;beginifsym<>identthenbeginifsym<>numberthenbeginifsym= ‘(‘thenbegingetsym;expr;ifsym= ‘)’thengetsymelseerrorendelseerrorend標準文檔實用文案endend;語法分析程序除總控外主要有兩大部分的功能，即對說明部分的處理和對程序體部分的處理，也就是在語法單元中的分程序功能。PL/0編譯程序語法、語義分析的的核心程序是 BLOCK過程，在BLOCK過程內(nèi)又定義了許多嵌套及并列的過程。在過程BLOCK內(nèi)對說明部分及程序體部分的分析說明如下：說明部分的分析由于PL/0語言允許過程調(diào)用語句，且允許過程嵌套定義。因此每個過程應有過程首部以定義局部于它自己過程的常量、變量和過程標識符，也稱局部量。每個過程所定義的局部量只能供它自己和它自己定義的內(nèi)過程引用。對于同一層并列過程的調(diào)用關系是先定義的可以被后定義的引用，反之則不行。說明部分的處理任務就是對每個過程的說明對象造名字表，填寫所在層次、標識符的屬性和分配的相對位置等。標識符的屬性不同時，所需要填寫的信息也有所不同。登錄信息是調(diào)用 ENTER過程完成的。說明部分的處理對主程序看成是第 0層過程，主程序定義的過程為第 1層，隨著嵌套的深度增加而層次數(shù)加大。PL/0允許最大層次為 3。所造名字表放在全程量一維數(shù)組 TABLE表中。TX為索引表的指針，表中的每個元素為記錄型數(shù)據(jù)。LEV給出層次，DX給出每層局部量當前已分配到的相對位置，可稱地址指示器，每說明完一個變量后DX指示器加1。PL/0編譯程序文本中對名字表定義有：說明類型的定義：typeobject=(constant,variable,procedur)標準文檔實用文案（定義為純量/枚舉類型）名字表的定義：table:array[0..txmax]ofrecordname:alfa;casekind:objectofconstant:(val:integer);variable:procedur:(level,adr,size:integer);end；例如：一個過程的說明部分為：CONSTA=35,B=49 ；VARC，D，E；PROCEDUREP；VARG,...對常量，變量和過程說明分析后，在 TABLE表中的信息如表2.2所示。在說明處理后TABLE表中的信息對于過程名的 ADR域，是在過程體的目標代碼生成后再反填過程體的入口地址。例中在處理 P過程的說明時對 LEV就增加1。在P過程中的變量名的層次為 LEV+1后的值。對過程還有一項數(shù)據(jù) SIZE，是記錄該過程體運行時所需的數(shù)據(jù)空間。 至于在造表和查表的過程中，如何保證每個過程的局部量不被它的外層引用，請讀者閱讀完 PL/0編譯程序后自己總結。過程體的分析程序的主體是由語句構成的。處理完過程的說明后就處理由語句組成的過程體，從語法上要對語句逐句分析。當語法正確時就生成相應語句功能的目標代碼。 當遇到標識符的引用時就調(diào)用 POSITION函標準文檔實用文案數(shù)查TABLE表，看是否有過正確的定義，若已有，則從表中取相應的有關信息，供代碼的生成用。若無定義則出錯。PL/0編譯程序的目標代碼結構和代碼生成編譯程序的目標代碼是在分析程序體時生成的，在處理說明部分時并不生成目標代碼，而當分析程序體中的每個語句時，當語法正確則調(diào)用目標代碼生成過程以生成與 PL/0語句等價功能的目標代碼，直到編譯正常結束。PL/0語言的代碼生成是由過程 GEN完成的。GEN過程有三個參數(shù)，分別代表目標代碼的功能碼、層差和位移量(對不同的指令含意不同)。生成的代碼順序放在數(shù)組 CODE中。CODE為一維數(shù)組，數(shù)組元素為記錄型數(shù)據(jù)。每一個記錄就是一條目標指令。 CX為指令的指針，由 0開始順序增加。實際上目標代碼的順序是內(nèi)層過程的排在前邊，主程序的目標代碼在最后。下面我們給出一個 PL/0源程序和對應的目標程序的清單。PL/0編譯程序的目標代碼生成是由 GEN過程完成的 ，當語法分析正確則調(diào)用目標代碼生成過程以生成與PL/0語句等價功能的目標代碼，直到編譯正常結束。除了過程說明部分外，變量和常量的說明都不產(chǎn)生目標代碼。在block入口處生成一條(jmp,0,0)指令，作為過程體入口指令，該指令的第3區(qū)域的'0'需分析到過程體入口時才返填。目標代碼生成時所用到的變量地址和層差等信息是由名字表 table提供的，而名字表的信息是在說明時填寫的。在代碼生成時查名字表，這就是表格管理的作用。這些信息之間的連接關系學員必須弄清。下面對一些重要程序段給予扼要的解釋。（ gen過程的實現(xiàn)很簡單不再解釋）對分程序體人口的處理（見程序文本 block 的過程體）begin(*block*)dx:=3;tx0:=tx; （*保留當前table表指針值,實際為過程名在 table表中的位置*）標準文檔實用文案table[tx].adr:=cx; （*保留當前code指針值到過程名的 adr域*）gen(jmp,0,0);（*生成轉向過程體入口的指令，該指令的地址為 cx已保留在過程名的 adr域，真正的過程體入口地址，等生成過程體入口的指令時，再由 table[tx].adr 中取出 cx將過程體入口返填到 cx所指目標代碼，即:（jmp,0,0）的第3區(qū)域，同時填到table[tx].adr 中*)程體入口時的處理code[table[tx0].adr].a:=cx; （cx為過程入口地址，填寫在 code中）withtable[tx0]dobeginadr:=cx; （過程的入口填寫在 table表的過程名中）size:=dx; （過程需要的空間填寫在 table中）end;cxo:=cx; （保留過程在code中的入口地址在輸出目標代碼時用）gen(int,0,dx); （生成過程入口指令）請?zhí)貏e注意dx、tx、cx的作用和如何處理信息之間的連接關系。PL/0編譯程序的語法錯誤處理編寫一個程序，往往難于一次成功，常常會出現(xiàn)各種類型的錯誤。 一般有語法錯、語義錯及運行錯。出錯的原因是多方面的，這就給錯誤處理帶來不少困難。就語法錯來說，任何一個編譯程序在進行語法分析遇到錯誤時，總不會就此停止工作，而是希望能準確地指出出錯位置和錯誤性質并盡可能進行校正，以便使編譯程序能繼續(xù)工作。但對所有的錯誤都做到這樣的要求是很困難的，主要困難在校正上，因為編譯程序不能完全確定程序人員的意圖。例如在一個表達式中，圓括號不配對時，就不能確定應補在何標準文檔實用文案處。有時由于校正得不對反而會影響到后邊，導致出現(xiàn)誤判錯誤的情況。因此編譯程序只能采取一些措施，對源程序中的錯誤盡量查出，加以修改，以便提高調(diào)試速度。PL/0編譯程序對語法錯誤的處理采用兩種辦法：對于一些易于校正的錯誤，如丟了逗號、分號等，則指出出錯位置，并加以校正。校正的方式就是補上逗號或分號。對某些錯誤編譯程序難于確定校正的措施，為了使當前的錯誤不致影響整個程序的崩潰，把錯誤盡量局限在一個局部的語法單位中。這樣就需跳過一些后面輸入的單詞符號，直到讀入一個能使編譯程序恢復正常語法分析工作的單詞為止。具體做法是：當語法分析進入以某些關鍵字(保留字)或終結符集合為開始符的語法單元時，通常在它的入口和出口處，調(diào)用一個測試程序 TEST(見圖2.9)。例如：語句的開始符是 begin，if，while，call，read，write；說明的開始符是var，const，procedure ；因子的開始符是"("，ident，number。當語法分析進入這樣的語法單元前，可用測試程序檢查當前單詞符號是否屬于它們開始符號的集合，若不是則出錯。請讀者對照圖 2.1各語法描述圖直觀地找出每個非終結符語法單元的開始符號集合，與表 2.3進行比較，驗證對開始符號集合理解的正確性。對于一個文法符號的開始符號集合的形式定義將在第 5章詳細介紹。現(xiàn)給出 PL/0文法部分非終結符語法單元的開始符號和后繼符號的集合。另外由于PL/0編譯程序采用自頂向下的分析方法，一個語法單元分析程序調(diào)用別的語法單元的分析程序時，以參數(shù)形式(文本中以FSYS定義為單詞符號集合作為形參 )給出被調(diào)用的語法分析程序出口時合法的后繼單詞符號集合(如表2.3所給出)，在出口處也調(diào)用測試程序。若當前單詞符號是屬于所給集合，則語法分析正常進行，否則出錯。單詞符號集合 FSYS參數(shù)是可傳遞的，隨著調(diào)用語法分析程序層次的深入，F(xiàn)SYS的集合逐步補充合法單詞符。非終結符（S） FIRST(S) FOLLOW(S)程序體 constvarprocedureident .;標準文檔實用文案callifbeginwhile語句identcallbeginifwhile.;end條件odd+-(identnumberthendo表達式+-(identnumber.;)Rendthendo項identnumber(.;)R+-endthendo因子identnumber(.;)R+-*/endthendo注：表2.3中'R'表示關系運算符集合,如=，＃，＜，＜=，＞，＞=。在進入某個語法單位時，調(diào)用TEST,檢查當前符號是否屬于該語法單位的開始符號集合。 若不屬于，則濾去開始符號和后繼符號集合外的所有符號。在語法單位分析結束時，調(diào)用TEST,檢查當前符號是否屬于調(diào)用該語法單位時應有的后繼符號集合。若不屬于，則濾去后繼符號和開始符號集合外的所有符號。TEST測試過程有三個參數(shù)，它們的含意是：S1：當語法分析進入或退出某一語法單元時當前單詞符號應屬于的集合，它可能是一個語法單元開始符號的集合或后繼符號的集合。②S2：在某一出錯狀態(tài)時，可恢復語法分析繼續(xù)正常工作的補充單詞符號集合。因為當語法分析出錯時，即當前單詞符號不在S1集合中，為了繼續(xù)編譯，需跳過后邊輸入的一些單詞符號，直到當前輸入的單詞符號是屬于S1或S2集合的元素。③n:整型數(shù)，出錯信息編號。為了進一步明確S1，S2集合的含意，現(xiàn)以因子(FACTOR)的語法分析程序為例，在過程FACTOR的入口處調(diào)用了一次TEST過程，它的實參S1是因子開始符號的集合(文本中的FACBEGSYS)。S2是每個過程的形參FSYS調(diào)用時實參的傳遞值。當編譯程序第一次調(diào)用BLOCK時，F(xiàn)SYS實參為[·]與說明開始符和語句開始符集合的和。 以后隨著調(diào)用語法分析程序層次的深入逐步增標準文檔實用文案加。如調(diào)用語句時增加了 [；]和[endsym],在表達式語法分析中調(diào)用項時又增加了 [+]和[-]，而在項中調(diào)用因子時又增加了[*]和[/]，這樣在進入因子分析程序時即使當前符號不是因子開始符，出錯后只要跳過一定的符號，遇到當時輸入的單詞符號在 FSYS中或在因子開始符號集合中，均可繼續(xù)正常進行語法分析。而在因子過程的出口處也調(diào)用了測試程序，不過這時 S1和S2實參恰恰相反。說明當時的 FSYS集合的單詞符號都是因子正常出口時允許的單詞符號，而因子的開始符號為可恢復正常語法分析的補充單詞符號。從PL/0編譯程序文本中因子過程的處理片段說明上述問題。（1）PL/0編譯程序文本中給出關于某些語法單位開始符號集合的定義為：symset=setofsymbol; （見PL/0文本類型說明部分）declbegsys,statbegsys,facbegsys:symset;declbegsys:=[constsym,varsym,procsym]; （見PL/0文本主程序置初值部分）statbegsys:=[beginsym,callsym,ifsym,whilesym,readsym,writesym];facbegsys:=[ident,number,lparen];（2）后繼符號集合 fsys作為參數(shù)傳遞（見 PL/0文本相應過程的說明部分）proceduretest(s1,s2:symset;n:integer);procedureblock(lev,tx:integer;fsys:symset);procedurestatement(fsys:symset);procedureexpression(fsys:symset);procedureterm(fsys:symset);procedurefactor(fsys:symset);（3）因子過程的處理片段test過程有三個參數(shù)：標準文檔實用文案可允許的下一個符號集合 S1，如果當前符號不在此集合中，當即得到一個錯誤號；另加的停止符號集合 S2，有些符號的出現(xiàn)，雖然無疑是錯的，但它們絕對不應被忽略而跳過；整數(shù)n，表示有關錯誤的診斷號：voidtest(symsets1,symsets2,intn){symsets;if(!inset(sym,s1)){error(n);s=uniteset(s1,s2);while(!inset(sym,s))getsym();destroyset(s);}}（4）由于后繼符號集合 fsys作為參數(shù)傳遞，隨著調(diào)用語法分析程序層次的深入后繼符號集合逐步增加，但對調(diào)用同一個過程所需增加的后跟符與調(diào)用位置有關。例如： 在write語句和factor 中調(diào)用expression(fsys); 所增加的后繼符號不完全相同?！rite語句的語法：<寫語句>∷=write(<exp>{,<exp>});處理在（ ）內(nèi)調(diào)用expression 時在fsys中應增加 rparen,comma 。標準文檔實用文案expression([rparen,comma]+fsys);·factor 的語法：<因子>∷=...|'('exp')在處理（ ）內(nèi)調(diào)用expression 時在fsys中應增加rparen。expression([rparen]+fsys);然而PL/0編譯程序對測試程序 TEST的調(diào)用有一定的靈活性。對語義錯誤，如標識符未加說明就引用，或雖經(jīng)說明，但引用與說明的屬性不一致。這時只給出錯誤信息和出錯位置，編譯工作可繼續(xù)進行。而對運行錯，如溢出，越界等，只能在運行時發(fā)現(xiàn)，由于 PL/0編譯程序的功能限制無法指出運行錯在源程序中的錯誤位置。出錯編號出錯原因1：常數(shù)說明中的"="寫成"∶="。2：常數(shù)說明中的"="后應是數(shù)字。3：常數(shù)說明中的標識符后應是"="。4：const,var,procedure后應為標識符。5：漏掉了'，'或'；'。6：過程說明后的符號不正確(應是語句開始符，或過程定義符)。7：應是語句開始符。8：程序體內(nèi)語句部分的后跟符不正確。9：程序結尾丟了句號'.'。10：語句之間漏了'；'。11：標識符未說明。12：賦值語句中，賦值號左部標識符屬性應是變量。13：賦值語句左部標識符后應是賦值號'∶='。標準文檔實用文案14：call后應為標識符。15：call后標識符屬性應為過程。16：條件語句中丟了'then'。17：丟了'end"或'；'。18：while型循環(huán)語句中丟了'do'。19：語句后的符號不正確。20：應為關系運算符。21：表達式內(nèi)標識符屬性不能是過程。22：表達式中漏掉右括號')'。23：因子后的非法符號。24：表達式的開始符不能是此符號。31：數(shù)越界。32：read語句括號中的標識符不是變量。PL/0編譯程序的目標代碼解釋執(zhí)行時的存儲分配當源程序經(jīng)過語法分析，如果未發(fā)現(xiàn)錯誤時，由編譯程序調(diào)用解釋程序，對存放在 CODE中的目標代碼CODE[0]開始進行解釋執(zhí)行。當編譯結束后，記錄源程序中標識符的 TABLE表已沒有作用。因為計算每個變量在運行棧中相對本過程基地址的偏移量 dx的值，放在table表中的adr域，生成目標代碼時再從 adr域中取出基地址的偏移量 ，放在code中的a域。因此數(shù)據(jù)空間只需以數(shù)組 CODE存放的只讀目標程序和運行時的數(shù)據(jù)棧 S。S是由解釋程序定義的一維整型數(shù)組。由于 PL/0語言的目標程序是一種假想的棧式計算機的匯編語言，仍用 PASCAL語言解釋執(zhí)行。解釋執(zhí)行時的數(shù)據(jù)空間 S為棧式計算機的存儲空間。遵循后進先出規(guī)則，對每個過程(包括主程序)當被調(diào)用時，才分配數(shù)據(jù)空間，退出過程時，則所分配的數(shù)據(jù)空間被釋放。標準文檔實用文案解釋程序還定義了 4個寄存器。I：指令寄存器。存放著當前正在解釋的一條目標指令。(2)P：程序地址寄存器。指向下一條要執(zhí)行的目標程序的地址(相當目標程序CODE數(shù)組的下標)。(3)T：棧頂寄存器。由于每個過程當它被運行時，給它分配的數(shù)據(jù)空間(下邊稱數(shù)據(jù)段)可分成兩部分。靜態(tài)部分：包括變量存放區(qū)和三個聯(lián)系單元 (聯(lián)系單元的作用見后)。動態(tài)部分：作為臨時工作單元和累加器用。需要時隨時分配，用完后立即釋放。棧頂寄存器 T指出了當前棧中最新分配的單元 (T也是數(shù)組S的下標)。(4)B：基址寄存器。指向每個過程被調(diào)用時，在數(shù)據(jù)區(qū) S中給它分配的數(shù)據(jù)段起始地址，也稱基地址。為了實現(xiàn)對每個過程調(diào)用時給它分配數(shù)據(jù)段，也就是對即將運行的過程所需數(shù)據(jù)段進棧；過程運行結束后釋放數(shù)據(jù)段，即該數(shù)據(jù)段退棧；以及嵌套過程之間對標識符引用的尋址問題。 每個過程被調(diào)用時，在棧頂分配三個聯(lián)系單元，這三個單元存放的內(nèi)容分別為：SL：靜態(tài)鏈：它是指向定義該過程的直接外過程(或主程序)運行時最新數(shù)據(jù)段的基地址。DL：動態(tài)鏈：它是指向調(diào)用該過程時正在運行過程的數(shù)據(jù)段基地址。(3)RA：返回地址：記錄調(diào)用該過程時目標程序的斷點，即當時的程序地址寄存器 P的值。也就是調(diào)用過程指令的下一條指令的地址。具體的過程調(diào)用和結束，對上述寄存器及三個聯(lián)系單元的填寫和恢復由下列目標指令完成。(1)INT0A每個過程目標程序的入口都有這樣一條指令，用以完成開辟數(shù)據(jù)段的工作。 A域的值指出數(shù)據(jù)段的大小，即為局部變量個數(shù) +3(聯(lián)系單元個數(shù)為3)。由編譯程序的代碼生成給出。開辟數(shù)據(jù)段的結果是改變棧頂寄存器 T的值，即T∶=T+A；。標準文檔實用文案(2)OPR00是每個過程出口處的一條目標指令。用以完成該過程運行結束后釋放數(shù)據(jù)段的工作，即退棧工作?；謴驼{(diào)用該過程前正在運行的過程 (或主程序)的數(shù)據(jù)段基地址寄存器的值，和棧頂寄存器 T的值，并將返回地址送到指令地址寄存器 P中，以使調(diào)用前的程序從斷點開始繼續(xù)執(zhí)行。CALLA；為調(diào)用過程的目標指令，其中L：為層次差，它是尋找靜態(tài)鏈的依據(jù)。在解釋程序中由 BASE(L)函數(shù)來計算，L為參數(shù)，實參為所給層差。A：為被調(diào)用過程的目標程序入口。CAL指令還完成填寫靜態(tài)鏈、動態(tài)鏈、返回地址，給出被調(diào)用過程的基地址值，送入基址寄存器 B中，目標程序的入口地址 A的值送指令地址寄存器 P中，使指令從A開始執(zhí)行。由于PL/0編譯程序是用PASCAL語言編寫的(若文件名為PL0.PAS)，所以要對PL/0語言的源程序進行編譯，如在PC機上，首先必須對 PL0.PAS進行編譯、匯編、連接得到 PL0.EXE文件。運行PL0.EXE文件才是啟動 PL/0的編譯程序。因此執(zhí)行命令。RUNPL0<回車>啟動PL/0編譯程序，輸出一些詢問信息，需用戶回答。輸出信息 回答信息INPUTFILE? PL/0源程序文件名<回車>LISTOBJECTCODE? Y或N<回車>目標程序輸出的次序是，最內(nèi)層的過程體在最前邊，主程序體在最后。源程序清單中的序號，是該語句在目標程序中對應的起始位置。但需指出例題中序號為0，1指令的內(nèi)容為：0jmp088為主程序入口1jmp022為過程P的入口標準文檔實用文案三、實驗結果：測試