1.1程序實現要求
PL/0語言可以看成PASCAL語言的子集，它的編譯程序是一個編譯解釋執行系統。PL/0的目標程序為假想棧式計算機的匯編語言，與具體計算機無關。
PL/0的編譯程序和目標程序的解釋執行程序都是用JAVA語言書寫的，因此PL/0語言可在配備JDK的任何機器上實現。
其編譯過程采用一趟掃描方式，以語法分析程序為核心，詞法分析和代碼生成程序都作為一個獨立的過程，當語法分析需要讀單詞時就調用詞法分析程序，而當語法分析正確需要生成相應的目標代碼時，則調用代碼生成程序。
用表格管理程序建立變量、常量和過程標示符的說明與引用之間的信息聯系。
用出錯處理程序對詞法和語法分析遇到的錯誤給出在源程序中出錯的位置和錯誤性質。
當源程序編譯正確時，PL/0編譯程序自動調用解釋執行程序，對目標代碼進行解釋執行，並按用戶程序的要求輸入數據和輸出運行結果。
1.2 PL/0語言的BNF描述（擴充的巴克斯范式表示法）
<prog> → program <id>；<block>
<block> → [<condecl>][<vardecl>][<proc>]<body>
<condecl> → const <const>{,<const>};
<const> → <id>:=<integer>
<vardecl> → var <id>{,<id>};
<proc> → procedure <id>（[<id>{,<id>}]）;<block>{;<proc>}
<body> → begin <statement>{;<statement>}end
<statement> → <id> := <exp>
|if <lexp> then <statement>[else <statement>]
|while <lexp> do <statement>
|call <id>（[<exp>{,<exp>}]）
|<body>
|read (<id>{，<id>})
|write (<exp>{,<exp>})
<lexp> → <exp> <lop> <exp>|odd <exp>
<exp> → [+|-]<term>{<aop><term>}
<term> → <factor>{<mop><factor>}
<factor>→<id>|<integer>|(<exp>)
<lop> → =|<>|<|<=|>|>=
<aop> → +|-
<mop> → *|/
<id> → l{l|d} （注：l表示字母）
<integer> → d{d}
注釋：
<prog>：程序 ；<block>：塊、程序體 ；<condecl>：常量說明 ；<const>：常量；<vardecl>：變量說明 ；<proc>：分程序 ； <body>：復合語句 ；<statement>：語句；<exp>：表達式 ；<lexp>：條件 ；<term>：項 ； <factor>：因子 ；<aop>：加法運算符；<mop>：乘法運算符； <lop>：關系運算符。
1.3假想目標機的代碼
LIT 0 ，a 取常量a放入數據棧棧頂
OPR 0 ，a 執行運算，a表示執行某種運算
LOD L ，a 取變量（相對地址為a，層差為L）放到數據棧的棧頂
STO L ，a 將數據棧棧頂的內容存入變量（相對地址為a，層次差為L）
CAL L ，a 調用過程（轉子指令）（入口地址為a，層次差為L）
INT 0 ，a 數據棧棧頂指針增加a
JMP 0 ，a無條件轉移到地址為a的指令
JPC 0 ，a 條件轉移指令，轉移到地址為a的指令
RED L ，a 讀數據並存入變量（相對地址為a，層次差為L）
WRT 0 ，0 將棧頂內容輸出
代碼的具體形式：
其中：F段代表偽操作碼
L段代表調用層與說明層的層差值
A段代表位移量（相對地址）
進一步說明：
INT：為被調用的過程（包括主過程）在運行棧S中開辟數據區，這時A段為所需數據單元個數（包括三個連接數據）；L段恆為0。
CAL：調用過程，這時A段為被調用過程的過程體（過程體之前一條指令）在目標程序區的入口地址。
LIT：將常量送到運行棧S的棧頂，這時A段為常量值。
LOD：將變量送到運行棧S的棧頂，這時A段為變量所在說明層中的相對位置。
STO：將運行棧S的棧頂內容送入某個變量單元中，A段為變量所在說明層中的相對位置。
JMP：無條件轉移，這時A段為轉向地址（目標程序）。
JPC：條件轉移，當運行棧S的棧頂的布爾值為假（0）時，則轉向A段所指目標程序地址；否則順序執行。
OPR：關系或算術運算，A段指明具體運算，例如A=2代表算術運算“＋”；A＝12代表關系運算“>”等等。運算對象取自運行棧S的棧頂及次棧頂。
1.4假想機的結構
兩個存儲器：存儲器CODE，用來存放P的代碼數據存儲器STACK（棧）用來動態分配數據空間
四個寄存器：
一個指令寄存器I:存放當前要執行的代碼
一個棧頂指示器寄存器T：指向數據棧STACK的棧頂
一個基地址寄存器B：存放當前運行過程的數據區在STACK中的起始地址
一個程序地址寄存器P：存放下一條要執行的指令地址該假想機沒有供運算用的寄存器。所有運算都要在數據棧STACK的棧頂兩個單元之間進行，並用運算結果取代原來的兩個運算對象而保留在棧頂
1.5活動記錄：
RA：返回地址
SL：保存該過程直接外層的活動記錄首地址
DL：調用者的活動記錄首地址
過程返回可以看成是執行一個特殊的OPR運算
注意：層次差為調用層次與定義層次的差值
2.1綜述
本PL/0編譯器共包括詞法分析、語法分析、語義分析（包括符號表管理和目標代碼生成）、活動記錄的組織（解釋執行程序）、錯誤處理四大部分組成。
2.2詳細說明
2.2.1詞法分析
根據所給的PL/0語言的BNF描述，該語言的組成單詞包括以下元素：
關鍵字（程序保留字）{program，const，var，procedure，begin，end，if，else，then，call，while，do，read，write}
運算符：{+，-，*，/，odd}
界符：{“，”，“;”，“（”，“）”}
關系運算符：{=，<,<=,>,>=,<>}
數字：只能為整型，且常量不可以是負數
標識符：由用戶定義，以字母開頭，由數字和字母組成
詞法分析程序讀取源文件，識別出上述關鍵字、界符、關系運算符、數字、標識符五種元素，輸出到lex.txt文件中，供後續的語法分析程序使用。其中，
(1)除標識符外，剩余的每一種字符可以用數字表示；
(2)而標識符則統一用一個數字表示其為標識符，再將標識符本身存儲起來；
(3)數字的存儲和標識符存儲類似。
例如：
將關鍵字、界符、關系運算符共29中符號從1到29依次編號，1表示關鍵字program，2表示關鍵字const,以此類推，到29表示關系運算符<>，
為了和下面標識符、數字的存儲統一起來，將識別出的關鍵字以如下形式
保存在lex.txt文件中。如program則存儲為（1，-）。
用30表示是標識符，如定義了一個變量v1，則其存儲為（30，v1）。
用31表示是數字，如12，其存儲為（31，13）。
2.2.2語法分析
語法分析結合BNF產生式，利用遞歸下降的方法實現。具體實現方式是，為每一個非終結符編寫一個子程序，以<prog> → program <id>；<block>此產生式為列，用偽碼描述其子程序如下：
void vardecl(){
if(當前指向的字符==program){
指向下一個字符；
if(當前指向的字符==id){ //是標識符
指向下一個字符；
if(當前指向的字符==；){
block();
}else{
error;
}
}
}else{
error
}
}
說明：由於之前的詞法分析使用數字來描述的，故此處的program，id(即標識符)，分號等都可以用相應的數字代替。
2.2.3語義分析
語義分析在語法分析的基礎上完成，涉及到的操作有符號表的管理和目標代碼的生成，分別對應說明語句和處理語句，下面分開來說。
（1）符號表管理
符號表中存儲以下數據：定義的變量、定義的常量、定義的過程；
定義的變量需要存儲：變量的標識符，變量定義所在層次，相對於該層次基地址的偏移量（對於基地址將在後面活動記錄中詳細說明）
定義的常量需要存儲：常量的標識符，常量的值，定義所在層次
定義的過程需要存儲：過程名，過程處理語句的開始地址（處理語句不是說明語句，說明語句中涉及到符號表的操作，而處理語句中涉及到產生目標代碼的操作），過程定義所在層次；
具體操作用偽碼描述：
a.常量說明的翻譯：
void condecl(){
if(當前指向的字符==const){
指向下一個字符；
const();
while(當前指向的字符==，){
指向下一個字符；
const();
}
}
}
void const(){
if(當前指向的字符==id){
指向下一個字符；
用name記錄下字符；
if(當前指向的字符== := ){
指向下一個字符；
if(當前指向的字符==數字){
用value記錄下值；
enter(name,value,level,addr);//將其記錄到符號表
}
}
}
}
b.變量說明的翻譯：
void vardecl(){
if(當前指向的字符==id){
用name記錄下字符；
enter(name,level,addr);
指向下一個字符；
while(當前指向的字符==，){
指向下一個字符；
if(當前指向的字符==id){
用name記錄下字符；
enter(name,level,addr);
指向下一個字符；
}
}
}
}
c.過程說明的翻譯：
proc的登錄符號表的操作與上述方法類似，不再贅述。
d.補充
但是上面我們並沒有涉及如何求得層次差和偏移量，獲得層次差和偏移量的思路大體如下，在整個語法分析函數中，定義兩個全局變量level和address，level初始化為1，其中主程序是第一層，每次遇到過程嵌套定義就將level加1，過程定義結束後再將其減1，這樣下來就實現了獲得說明語句所在層次的功能；address初始化為0，每次在符號表中登錄變量後就將address加1，其實address的作用是，結合level，可以獲得每一層有幾個變量，這樣在活動記錄的分配（也叫運行時存儲空間的劃分，運行時只為變量事先劃分存儲空間），可以根據該層變量的個數劃分相應的存儲空間。
(2)目標代碼的產生
這部分涉及到翻譯模式相關的知識，由於說明語句是不產生目標代碼的，在結合PL/0的BNF描述，會產生目標代碼的只有<block>、<body>、<statement>、<lexp>、<exp>、<term>、<factor>、<lop>、<mop>,下面一次用偽碼說明其翻譯模式：
a.<block>:
分析可以發現，主程序除去program<id>;,過程除去procedure<id>([id{,id}])，剩下的部分都是block。則進入block有兩種情況：（1）從主程序進入，此時符號表中沒有任何元素，也沒有產生任何目標代碼；（2）從過程進入，此時符號表中有了該子過程所有外層過程定義的變量，常量和過程，並且還產生了一部分目標代碼；對於第一種情況比較簡單，不再贅述，而對於第二種情況，則比較復雜。現在我們將主程序處理語句開始的地址叫做程序的入口，由於嵌套過程的存在，導致尋找程序入口有些麻煩，在這裡我們用到了回填技術:
l 在進入block的第一步就先產生一個無條件跳轉指令，由於中間子過程嵌套還會產生目標代碼 ，導致不知道跳轉到哪裡才是主程序的入口，這裡我們先記下這個無條件跳轉指令在目標代碼中的位置，當程序分析完變量說明、常量說明和過程說明即將進入語句處理的分析時，這時目標代碼的地址就是主程序的入口，我們根據剛才記下的無條件跳轉指令的位置將這個地址回填到跳轉指令的目標地址上，從而目標代碼第一句就是跳轉到主程序入口處的指令，對於程序中嵌套程序，用這個方法依然是可行的；
l 除此之外，在進行其他任何分析之前，還要記錄下主程序或者當前過程的數據量，即符號表中的變量數目，也即address，以便後面活動記錄的劃分可以在結束過程後返回到原來的數據棧的位置；
l 另外，如果是從過程進入到block，在產生過程調用指令需要用到這個入口地址，所以這個過程入口地址也要記錄下來，用來填寫過程調用指令的目標位置。則在進行其他任何分析之前，此時符號表中最新的一項必定是該過程的相關信息，我們可以將本過程的value值設為其入口地址，因為value值對於符號表procedure來說是無用的，即將開始地址登入到符號表，從而在做任何分析前我們也要記錄下符號表中的最新項（記錄其序號），在經過變量說明分析、常量說明分析、過程分析後即將進入語句處理分析時，便得到了該過程的入口地址，將其登錄到剛剛記錄的那個符號表最新項的value域；
可以通過判斷符號表中的最新項的序號是否為0來判斷是從過程進入<block>還是從過程進入<block>
進行完上述三步操作後即可進入語句的處理部分；
在語句的處理部分完成後，生成目標代碼的退出過程或主程序的語句，然後恢復address和符號表的序號。
b.<body>
此部分不直接產生目標代碼
c.<statement>
<statement>中有賦值語句(<id>:=<exp>)、if語句、while語句、call語句、read語句、write語句，下面分別說明其翻譯模式：
l 賦值語句：此部分涉及到活動記錄的組織，先大致說一下:本目標機是哈佛架構，數據存儲器和代碼存儲器是分開的，這裡活動記錄的組織或者說運行時存儲空間的組織是指數據存儲器的組織，（代碼存儲器不需要什麼組織，目標代碼順序存放，解釋程序按目標代碼的意義進行相關控制流的操作等），對於每一個過程或主程序，都要開辟3+變量個數的存儲空間，其中3個是用來存放SL，DL，RA的，這裡我們遇到一個變量就生成STO L,A目標代碼，其中L和A據可由符號表中存儲的相關信息獲得，意思是將此時數據棧棧頂的元素，通過層差L（調用位置和定義位置之差）和偏移地址A找到這個變量在其定義的過程開辟的空間中為該變量開辟的存儲空間，然後將棧頂元素存到這個位置，具體的生成看代碼；
l if語句：用偽碼描述
if <lexp>
產生條件轉移指令“JPC，0，0”；
用記錄cx1上面那條條件轉移指令的位置；
then
<statement>
產生無條件轉移指令“JMP，0，0”；
用cx2記錄上面那條無條件轉移指令的位置；
cx3為即將產生的目標代碼的位置；
用cx3回填cx1和cx2記錄位置的指令
else
<statement>
cx4為即將產生的目標代碼的位置；
用cx4回填cx2記錄位置的指令
l while語句：
while<lexp>do
產生田間轉移指令“JPC，0，0”
用cx1記錄下上面那條條件轉移指令的位置
<statement>
產生無條件轉移指令“JMP,0,0”
cx2為即將產生的目標代碼的位置
用cx2回填cx1記錄位置的指令
l call語句：
產生“CAL，L，A”，意思是通過層差L和過程入口地址A，找到過程的入口地址，這裡A可以有該過程在符號表中的value域的值獲得（原因見<block>的翻譯）
l read語句：
首先從命令行獲取一個值放在棧頂，然後將棧頂值賦值給相應變量(賦值過程見前面賦值語句的翻譯)
l write語句：
直接輸出棧頂值
其他運算的翻譯較為簡單，不再贅述.
2.2.4活動記錄的組織
此部分主要是活動記錄的組織，具體如下：
為每一個過程開辟的新的存儲空間，最低層三個用來存儲SL：保存該過程直接外層的活動首地址；DL：調用者的活動記錄首地址；RA：返回地址；
具體的執行方式見代碼注釋。
2.2.5難點說明
l 變量（常數、過程）作用域的確定，分為兩步：一步是定義變量時，我們要查詢在本層有無同名的變量已經定義，若有，則報錯；二步是變量使用時，首先查詢本層有無定義該變量，若有，則使用本層定義的變量，若無，則尋找本過程直接外層有無定義同名變量，若仍無此變量，則繼續向下一個直接外層尋找，以此類推。若有，則使用最靠近本層的那個定義，若無，則報錯。由於本符號表采用的是數組管理，在實現第一步時，在變量（常數、過程）登錄符號表時記錄其所在的層次和所在層次的名字，若符號表中存在變量（常量、過程）的名字、所在層次和所在層次的名字均相同，則報錯，若無，則將定義的變量加到符號表中。在實現第二步時，結合語法的特點分析，首先在本調用過程所在的過程進行查找有無定義該變量，若有，則就使用本過程的變量，若無，則根據前面在符號表中記錄的本調用過程所在的直接外層的名字查找該直接外層有無定義此變量，以此類推，若最終有定義，則使用該變量，否則保存。
l 過程傳遞參數：我把在過程定義時的形式參數，當作在本過程定義變量進行處理，在調用過程中出傳入的實在參數當作對相應的形式參數進行賦值，具體說來就是用該過程在符號表中的size域存儲該過程中的形參個數，再用一個變量記錄過程中定義參數的個數（具體做法是定義一個變量，每次進入block時置為3，用來存儲SL、DL、RA，然後遇到變量定義就加一來記錄）當遇到過程定義時，將其說明的形參按照在本過程中定義變量的相關屬性登錄到符號表中，並且他們在活動記錄的存儲位置是緊接著SL，DL，RA；在遇到調用過程時，首先根據棧頂、棧頂-1、棧頂-2、棧頂-形參個數+1根據所存儲的位置進行賦值，然後再分配相應的活動存儲空間（如果剛開始就分配，則會導致棧頂更新，失去了原來的棧頂元素），該活動存儲空間的大小應該是參數個數+本過程定義的變量個數+3。
3.1類的作用的說明
l RValue+LexAnalysis+chTable完成詞法分析。
l AllPcode+PerPcode完成目標代碼生成。
l SymTable+TableRow完成符號表管理。
l Interpreter完成解釋執行程序。
l MpgAnalysis的一個函數showError完成錯誤處理程序。
l MpgAnalysis綜合上述類完成編譯功能。
3.2具體函數功能的說明
PL/0 Compiler
