?? pl-0語言編譯程序分析.htm
字號:
href="http://dev.csdn.net/articlelist.aspx?c=10">游戲開發</A> (<A
href="http://www.csdn.net/Rss/RssFeed.aspx?rssid=1&bigclassid=10">rss</A>) </TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/articlelist.aspx?c=12">網站制作技術</A> (<A
href="http://www.csdn.net/Rss/RssFeed.aspx?rssid=1&bigclassid=12">rss</A>) </TD></TR></TBODY></TABLE>
<TABLE style="MARGIN-BOTTOM: 4px" cellSpacing=0 cellPadding=0
width="95%" align=center border=0>
<TBODY>
<TR>
<TD style="COLOR: #0033ff; BORDER-BOTTOM: #b0c4de 1px dashed"
align=right><FONT style="FONT-SIZE: 8pt">數據庫</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/articlelist.aspx?c=8">數據庫開發</A> (<A
href="http://www.csdn.net/Rss/RssFeed.aspx?rssid=1&bigclassid=8">rss</A>) </TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=0 width="95%" align=center
border=0>
<TBODY>
<TR>
<TD style="COLOR: #0033ff; BORDER-BOTTOM: #b0c4de 1px dashed"
align=right><FONT style="FONT-SIZE: 8pt">軟件工程</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/articlelist.aspx?c=13">其他</A> (<A
href="http://www.csdn.net/Rss/RssFeed.aspx?rssid=1&bigclassid=13">rss</A>) </TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><BR>
<TABLE cellSpacing=1 cellPadding=0 width="100%" bgColor=#000000
border=0><TBODY>
<TR>
<TD vAlign=top bgColor=#ededed>
<TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
<TBODY>
<TR>
<TD align=right background=PL-0語言編譯程序分析.files/top.gif
height=27><FONT
class=fonttitle>積極原創作者 </FONT></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=1 cellPadding=2 width="100%" border=0>
<TBODY>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/girlspicy">girlspicy</A> <FONT
color=#ff0000>(2)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/suspension">suspension</A> <FONT
color=#ff0000>(2)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/neverfly">neverfly</A> <FONT
color=#ff0000>(1)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/scarf">scarf</A> <FONT
color=#ff0000>(1)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/s98">s98</A> <FONT
color=#ff0000>(1)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/walkinhill">walkinhill</A> <FONT
color=#ff0000>(2)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/skywind">skywind</A> <FONT
color=#ff0000>(2)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/freeagle">freeagle</A> <FONT
color=#ff0000>(5)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/lovepower1982">lovepower1982</A> <FONT
color=#ff0000>(1)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/kanshangren">kanshangren</A> <FONT
color=#ff0000>(1)</FONT></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD>
<TD vAlign=top width=786>
<TABLE cellPadding=4 width="100%" border=0>
<TBODY>
<TR>
<TD width=10 height=19></TD>
<TD height=19>
<TABLE cellSpacing=3 cellPadding=3 width="100%" border=0>
<TBODY>
<TR>
<TD><A href="http://www.csdn.net/">CSDN</A> - <A
href="http://dev.csdn.net/">文檔中心</A> - <FONT color=#003399><A
id=ArticleTitle1_ArticleTitle1_hlClass
href="http://dev.csdn.net/articlelist.aspx?c=13">其他</A></FONT>
</TD>
<TD align=right>閱讀：<SPAN
id=ArticleTitle1_ArticleTitle1_lblReadCount>3217</SPAN>
評論： <SPAN
id=ArticleTitle1_ArticleTitle1_lblCommentCount>9</SPAN>
<A
href="http://dev.csdn.net/Develop/article/14/14701.shtm#Comment">參與評論</A>
</TD></TR></TBODY></TABLE>
<TABLE cellSpacing=3 cellPadding=3 width="100%" bgColor=#eeeeee
border=0>
<TBODY>
<TR>
<TD noWrap width=60 height=0></TD>
<TD></TD></TR>
<TR>
<TD noWrap align=middle bgColor=#003399 height=16><FONT
color=#ffffff>標題</FONT></TD>
<TD><B> <SPAN
id=ArticleTitle1_ArticleTitle1_lblTitle>PL/0語言編譯程序分析</SPAN></B>
選擇自 <A id=ArticleTitle1_ArticleTitle1_AuthorLink
href="http://dev.csdn.net/user/lifanxi">lifanxi</A> 的 Blog
</TD></TR>
<TR>
<TD align=middle bgColor=#003399 height=16><FONT
color=#ffffff>關鍵字</FONT></TD>
<TD width=500> <SPAN
id=ArticleTitle1_ArticleTitle1_lblKeywords>PL/0
編譯</SPAN></TD></TR>
<TR>
<TD align=middle bgColor=#003399 height=16><FONT
color=#ffffff>出處</FONT></TD>
<TD> <SPAN
id=ArticleTitle1_ArticleTitle1_lblSource></SPAN></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD width=10></TD>
<TD><SPAN id=ArticleContent1_ArticleContent1_lblContent>
<P
align=left><BR> PL/0語言是Pascal語言的一個子集，我們這里分析的PL/0的編譯程序包括了對PL/0語言源程序進行分析處理、編譯生成類PCODE代碼，并在虛擬機上解釋運行生成的類PCODE代碼的功能。<BR> PL/0語言編譯程序采用以語法分析為核心、一遍掃描的編譯方法。詞法分析和代碼生成作為獨立的子程序供語法分析程序調用。語法分析的同時，提供了出錯報告和出錯恢復的功能。在源程序沒有錯誤編譯通過的情況下，調用類PCODE解釋程序解釋執行生成的類PCODE代碼。
</P>
<DIV></DIV>
<P> 詞法分析子程序分析：<BR> 詞法分析子程序名為getsym，功能是從源程序中讀出一個單詞符號（token），把它的信息放入全局變量sym、id和num中，語法分析器需要單詞時，直接從這三個變量中獲得。（注意！語法分析器每次用完這三個變量的值就立即調用getsym子程序獲取新的單詞供下一次使用。而不是在需要新單詞時才調用getsym過程。）getsym過程通過反復調用getch子過程從源程序過獲取字符，并把它們拼成單詞。getch過程中使用了行緩沖區技術以提高程序運行效率。<BR> 詞法分析器的分析過程：調用getsym時，它通過getch過程從源程序中獲得一個字符。如果這個字符是字母，則繼續獲取字符或數字，最終可以拼成一個單詞，查保留字表，如果查到為保留字，則把sym變量賦成相應的保留字類型值；如果沒有查到，則這個單詞應是一個用戶自定義的標識符（可能是變量名、常量名或是過程的名字），把sym置為ident，把這個單詞存入id變量。查保留字表時使用了二分法查找以提高效率。如果getch獲得的字符是數字，則繼續用getch獲取數字，并把它們拼成一個整數，然后把sym置為number，并把拼成的數值放入num變量。如果識別出其它合法的符號（比如：賦值號、大于號、小于等于號等），則把sym則成相應的類型。如果遇到不合法的字符，把sym置成nul。</P>
<P> 語法分析子程序分析：<BR> 語法分析子程序采用了自頂向下的遞歸子程序法，語法分析同時也根據程序的語意生成相應的代碼，并提供了出錯處理的機制。語法分析主要由分程序分析過程（block）、常量定義分析過程（constdeclaration）、變量定義分析過程（vardeclaration）、語句分析過程（statement）、表達式處理過程（expression）、項處理過程（term）、因子處理過程（factor）和條件處理過程（condition）構成。這些過程在結構上構成一個嵌套的層次結構。除此之外，還有出錯報告過程（error）、代碼生成過程（gen）、測試單詞合法性及出錯恢復過程（test）、登錄名字表過程（enter）、查詢名字表函數（position）以及列出類PCODE代碼過程（listcode）作過語法分析的輔助過程。<BR> 由PL/0的語法圖可知：一個完整的PL/0程序是由分程序和句號構成的。因此，本編譯程序在運行的時候，通過主程序中調用分程序處理過程block來分析分程序部分（分程序分析過程中還可能會遞歸調用block過程），然后，判斷最后讀入的符號是否為句號。如果是句號且分程序分析中未出錯，則是一個合法的PL/0程序，可以運行生成的代碼，否則就說明源PL/0程序是不合法的，輸出出錯提示即可。<BR> 下面按各語法單元分析PL/0編譯程序的運行機制。</P>
<P> 分程序處理過程：<BR> 語法分析開始后，首先調用分程序處理過程（block）處理分程序。過程入口參數置為：0層、符號表位置0、出錯恢復單詞集合為句號、聲明符或語句開始符。進入block過程后，首先把局部數據段分配指針設為3，準備分配3個單元供運行期存放靜態鏈SL、動態鏈DL和返回地址RA。然后用tx0記錄下當前符號表位置并產生一條jmp指令，準備跳轉到主程序的開始位置，由于當前還沒有知到主程序究竟在何處開始，所以jmp的目標暫時填為0，稍后再改。同時在符號表的當前位置記錄下這個jmp指令在代碼段中的位置。在判斷了嵌套層數沒有超過規定的層數后，開始分析源程序。首先判斷是否遇到了常量聲明，如果遇到則開始常量定義，把常量存入符號表。接下去用同樣的方法分析變量聲明，變量定義過程中會用dx變量記錄下局部數據段分配的空間個數。然后如果遇到procedure保留字則進行過程聲明和定義，聲明的方法是把過程的名字和所在的層次記入符號表，過程定義的方法就是通過遞歸調用block過程，因為每個過程都是一個分程序。由于這是分程序中的分程序，因此調用block時需把當前的層次號lev加一傳遞給block過程。分程序聲明部分完成后，即將進入語句的處理，這時的代碼分配指針cx的值正好指向語句的開始位置，這個位置正是前面的jmp指令需要跳轉到的位置。于是通過前面記錄下來的地址值，把這個jmp指令的跳轉位置改成當前cx的位置。并在符號表中記錄下當前的代碼段分配地址和局部數據段要分配的大小（dx的值）。生成一條int指令，分配dx個空間，作為這個分程序段的第一條指令。下面就調用語句處理過程statement分析語句。分析完成后，生成操作數為0的opr指令，用于從分程序返回（對于0層的主程序來說，就是程序運行完成，退出）。</P>
<P> 常量定義過程：<BR> 通過循環，反復獲得標識符和對應的值，存入符號表。符號表中記錄下標識符的名字和它對應的值。</P>
<P> 變量定義過程：<BR> 與常量定義類似，通過循環，反復獲得標識符，存入符號表。符號表中記錄下標識符的名字、它所在的層及它在所在層中的偏移地址。
</P>
<P> 語句處理過程：<BR> 語句處理過程是一個嵌套子程序，通過調用表達式處理、項處理、因子處理等過程及遞歸調用自己來實現對語句的分析。語句處理過程可以識別的語句包括賦值語句、read語句、write語句、call語句、if語句、while語句。當遇到begin/end語句時，就遞歸調用自己來分析。分析的同時生成相應的類PCODE指令。</P>
<P> 賦值語句的處理：<BR> 首先獲取賦值號左邊的標識符，從符號表中找到它的信息，并確認這個標識符確為變量名。然后通過調用表達式處理過程算得賦值號右部的表達式的值并生成相應的指令保證這個值放在運行期的數據棧頂。最后通過前面查到的左部變量的位置信息，生成相應的sto指令，把棧頂值存入指定的變量的空間，實現了賦值操作。</P>
<P> read語句的處理：<BR> 確定read語句語法合理的前提下（否則報錯），生成相應的指令：第一條是16號操作的opr指令，實現從標準輸入設備上讀一個整數值，放在數據棧頂。第二條是sto指令，把棧頂的值存入read語句括號中的變量所在的單元。</P>
<P> write語句的處理：<BR> 與read語句相似。在語法正確的前提下，生成指令：通過循環調用表達式處理過程分析write語句括號中的每一個表達式，生成相應指令保證把表達式的值算出并放到數據棧頂并生成14號操作的opr指令，輸出表達式的值。最后生成15號操作的opr指令輸出一個換行。</P>
<P> call語句的處理：<BR> 從符號表中找到call語句右部的標識符，獲得其所在層次和偏移地址。然后生成相應的cal指令。至于調用子過程所需的保護現場等工作是由類PCODE解釋程序在解釋執行cal指令時自動完成的。</P>
<P> if語句的處理：<BR> 按if語句的語法，首先調用邏輯表達式處理過程處理if語句的條件，把相應的真假值放到數據棧頂。接下去記錄下代碼段分配位置（即下面生成的jpc指令的位置），然后生成條件轉移jpc指令（遇0或遇假轉移），轉移地址未知暫時填0。然后調用語句處理過程處理then語句后面的語句或語句塊。then后的語句處理完后，當前代碼段分配指針的位置就應該是上面的jpc指令的轉移位置。通過前面記錄下的jpc指令的位置，把它的跳轉位置改成當前的代碼段指針位置。</P>
<P> begin/end語句的處理：<BR> 通過循環遍歷begin/end語句塊中的每一個語句，通過遞歸調用語句分析過程分析并生成相應代碼。</P>
<P> while語句的處理：<BR> 首先用cx1變量記下當前代碼段分配位置，作為循環的開始位置。然后處理while語句中的條件表達式生成相應代碼把結果放在數據棧頂，再用cx2變量記下當前位置，生成條件轉移指令，轉移位置未知，填0。通過遞歸調用語句分析過程分析do語句后的語句或語句塊并生成相應代碼。最后生成一條無條件跳轉指令jmp，跳轉到cx1所指位置，并把cx2所指的條件跳轉指令的跳轉位置改成當前代碼段分配位置。</P>
<P> 表達式、項、因子處理：<BR> 根據PL/0語法可知，表達式應該是由正負號或無符號開頭、由若干個項以加減號連接而成。而項是由若干個因子以乘除號連接而成，因子則可能是一個標識符或一個數字，或是一個以括號括起來的子表達式。根據這樣的結構，構造出相應的過程，遞歸調用就完成了表達式的處理。把項和因子獨立開處理解決了加減號與乘除號的優先級問題。在這幾個過程的反復調用中，始終傳遞fsys變量的值，保證可以在出錯的情況下跳過出錯的符號，使分析過程得以進行下去。</P>
<P> 邏輯表達式的處理：<BR> 首先判斷是否為一元邏輯表達式：判奇偶。如果是，則通過調用表達式處理過程分析計算表達式的值，然后生成判奇指令。如果不是，則肯定是二元邏輯運算符，通過調用表達式處理過程依次分析運算符左右兩部分的值，放在棧頂的兩個空間中，然后依不同的邏輯運算符，生成相應的邏輯判斷指令，放入代碼段。</P>
<P> 判斷單詞合法性與出錯恢復過程分析：<BR> 本過程有三個參數，s1、s2為兩個符號集合，n為出錯代碼。本過程的功能是：測試當前符號（即sym變量中的值）是否在s1集合中，如果不在，就通過調用出錯報告過程輸出出錯代碼n，并放棄當前符號，通過詞法分析過程獲取一下單詞，直到這個單詞出現在s1或s2集合中為止。<BR> 這個過程在實際使用中很靈活，主要有兩個用法：<BR> 在進入某個語法單位時，調用本過程，檢查當前符號是否屬于該語法單位的開始符號集合。若不屬于，則濾去開始符號和后繼符號集合外的所有符號。<BR> 在語法單位分析結束時，調用本過程，檢查當前符號是否屬于調用該語法單位時應有的后繼符號集合。若不屬于，則濾去后繼符號和開始符號集合外的所有符號。<BR> 通過這樣的機制，可以在源程序出現錯誤時，及時跳過出錯的部分，保證語法分析可以繼續下去。</P>
<P> 語法分析過程中調用的其它子過程相對比較簡單，請參考源程序的注釋。</P>
<P> 類PCODE代碼解釋執行過程分析<BR> 這個過程模擬了一臺可以運行類PCODE指令的棧式計算機。它擁有一個棧式數據段用于存放運行期數據、擁有一個代碼段用于存放類PCODE程序代碼。同時還擁用數據段分配指針、指令指針、指令寄存器、局部段基址指針等寄存器。<BR> 解釋執行類PCODE代碼時，數據段存儲分配方式如下：<BR> 對于源程序的每一個過程（包括主程序），在被調用時，首先在數據段中開辟三個空間，存放靜態鏈SL、動態鏈DL和返回地址RA。靜態鏈記錄了定義該過程的直接外過程（或主程序）運行時最新數據段的基地址。動態鏈記錄調用該過程前正在運行的過程的數據段基址。返回地址記錄了調用該過程時程序運行的斷點位置。對于主程序來說，SL、DL和RA的值均置為0。靜態鏈的功能是在一個子過程要引用它的直接或間接父過程（這里的父過程是按定義過程時的嵌套情況來定的，而不是按執行時的調用順序定的）的變量時，可以通過靜態鏈，跳過個數為層差的數據段，找到包含要引用的變量所在的數據段基址，然后通過偏移地址訪問它。
<BR> 在過程返回時，解釋程序通過返回地址恢復指令指針的值到調用前的地址，通過當前段基址恢復數據段分配指針，通過動態鏈恢復局部段基址指針。實現子過程的返回。對于主程序來說，解釋程序會遇到返回地址為0的情況，這時就認為程序運行結束。<BR> 解釋程序過程中的base函數的功能，就是用于沿著靜態鏈，向前查找相差指定層數的局部數據段基址。 這在使用sto、lod等訪問局部變量的指令中會經常用到。<BR> 類PCODE代碼解釋執行的部分通過循環和簡單的case判斷不同的指令，做出相應的動作。當遇到主程序中的返回指令時，指令指針會指到0位置，把這樣一個條件作為終至循環的條件，保證程序運行可以正常的結束。</P>
<P>以下源程序是以清華大學出版社《編譯原理》中的源代碼為基礎作了少量改動而成。</P>
<P>程序在Turbo Pascal 7.0上編譯運行通過。</P>
<P>************************************************************************************</P><PRE>program pl0(fa,fa1,fa2); (* PL/0編譯程序與代碼生成解釋運行程序 *)
(* PL/0 compiler with code generation *)
label 99; (* 聲明出錯跳轉標記 *)
(* 在Turbo Pascal 7.0中已不允許跨過程的GOTO轉移，因此后面的GOTO語句均被我去除了，因此這里的label也沒有意義了 *)
const (* 常量定義 *)
norw = 13; (* of reserved words *) (* 保留字的個數 *)
txmax = 100; (* length of identifier table *) (* 標識符表的長度（容量） *)
nmax = 14; (* max number of digits in numbers *) (* 數字允許的最長位數 *)
al = 10; (* length of identifiers *) (* 標識符最長長度 *)
amax = 2047; (* maximum address *) (* 尋址空間 *)
levmax = 3; (* max depth of block nesting *) (* 最大允許的塊嵌套層數 *)
cxmax = 200; (* size of code array *) (* 類PCODE目標代碼數組長度（可容納代碼行數） *)
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, writesym, readsym, dosym, callsym,
constsym, varsym, procsym); (* symobl類型標識了不同類型的詞匯 *)
alfa = packed array[1..al] of char; (* alfa類型用于標識符 *)
object1 = (constant, variable, procedur); (* object1為三種標識符的類型 *)
(* 原程序在此使用object作為類型名稱，在支持面向對象的Turbo Pascal 7.0中編譯不能通過 *)
(* wirth used the word "procedure" there, whick won't work! *)
(* 上面一行是課本上的程序清單中的注釋，說本程序的原作者Wirth在這里用了procedure這個詞作為標識符類型，是不可以的。
事實上Wirth原本在這里用的詞是prozedure，是可以的。 *)
symset = set of symbol; (* symset是symbol類型的一個集合類型，可用于存放一組symbol *)
fct = (lit, opr, lod, sto, cal, int, jmp, jpc); (* fct類型分別標識類PCODE的各條指令 *)
instruction = packed record
f: fct; (* function code *)
l: 0..levmax; (* level *)
a: 0..amax; (* displacement addr *)
end; (* 類PCODE指令類型，包含三個字段：指令f、層差l和另一個操作數a *)
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -