編譯原理第9章清華大學(xué).ppt

《編譯原理第9章清華大學(xué).ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理第9章清華大學(xué).ppt（20頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第9章 符號表,9.1符號表的作用和地位 9.2符號的主要屬性及作用 9.3符號表的組織,符號表的作用和地位-----語義檢查的依據(jù) 目標(biāo)代碼生成階段地址分配的依據(jù),在編譯程序中符號表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識符的屬性信息，符號表中所登記的信息在編譯的不同階段都要用到。 在語義分析中，符號表所登記的內(nèi)容將用于語義檢查（如檢查一個名字的使用和原先的說明是否一致）和產(chǎn)生中間代碼。 在目標(biāo)代碼生成階段，當(dāng)對符號名進行地址分配時，符號表是地址分配的依據(jù)。對一個多遍掃描的編譯程序，不同遍所用的符號表也往往各有不同。因為每遍所關(guān)心的信息各有差異。,,一張符號表的每一項（或稱入口才包含兩大欄（或稱區(qū)段、字域），即名字欄和信息欄。 名字欄(NAME) 信息欄(INFORMATION） 第1項（入口1） 第2項（入口2） … 第n項（入口n） 信息欄包含許多子欄和標(biāo)志位，用來記錄相應(yīng)名字和種種不同屬性，由于查填符號表一般是通過匹配名字來寮現(xiàn)的，因此，名字欄也稱主欄。主欄的內(nèi)容稱為關(guān)鍵字（key word）。,,在整個編譯期間，對于符號表的操作大致可歸納為五類： ? 對給定名字，查詢名字是否已在表中； ? 往表中填入一個新的名字； ? 對給定名字，訪問它的某些信息； ? 對給定名字，填寫或更新它的某些信息； ? 刪除一個或一組無用的項。 不同種類的表格所涉及的操作往往也是不同的。上述五個方面只是一些基本的共同操作。,屬性(信息）,幾種通常都是需要的。 1 名子 2 類型 3 存儲類別 4 作用域及可視性 5 存儲分配信息 6 其它屬性 （１） 數(shù)組內(nèi)情向量 （２） 記錄結(jié)構(gòu)型的成員信息 （３） 函數(shù)及過程的形參,符號表的組織,總體組織和表項屬性信息組織 第一種： 把屬性種類完全相同的那些符號組織在一起，構(gòu)造出表項是分別為等長的多個符號表 第二種： 把所有語言中的符號都組織在一張符號表中。組成一張包括了所有屬性的龐大的符號表 第三種折衷方式是根據(jù)符號屬性相似程度分類組織成若干張表，每張表中記錄的符號都有比較多的相同屬性。,,編譯程序按名字的不同種屬分別使用許多符號表，如常數(shù)表、變量名表、過程名表等等。 SUBROUTINE INCWAP（M，N） 10 K＝M＋1 M＝M＋4 N＝K RETURN END 經(jīng)編譯頭三階段后所產(chǎn)生的主要表格有：符號名表SNT、常數(shù)表CT、入口名表ENT、標(biāo)號表LT和四元式表QT,,符號名表SNT NAME INFORMATION （1）M 啞元，整數(shù)，變量 （2）N 啞元，整數(shù)，變量 （3）K 整數(shù)，變量,常數(shù)表CT 值（VALUE） (1) 1 （2） 4,入口名表ENT NAME INFORMATION （1）INCWAP 二目子程序，入口QT(1) /*記錄入口名INCWAP的入口地址＊／ 標(biāo)號表LT LABLE INFORMATION （1）10 QT(4) /*記錄了標(biāo)號10對應(yīng)的四元式序列號＊／,四元式表QT,,符號表項的排列,符號表作為一個多元組，表中元組的排列組織是構(gòu)造符號表的重要成分。在編譯程序的整個工作過程中，符號表被頻繁地用來建立表項，找查表項，填充和引用表項的屬性。因此表項的排列組織對該系統(tǒng)運行的效率起著十分重要的作用。在編譯程序中，符號表項的組織傳統(tǒng)上采用三種構(gòu)造方法。即線性法，二分法及散列法。,關(guān)鍵字域的組織,符號表的關(guān)鍵字域（段）就是符號名稱 等長關(guān)鍵字域（段）符號表 不等長關(guān)鍵字段符號表---采用關(guān)鍵字池的索引結(jié)構(gòu)。,分程序結(jié)構(gòu)的符號表,對于具有分程序型結(jié)構(gòu)的語言程序，不同層次分程序中定義的標(biāo)識符號具有不同的作用域和不同的可視性規(guī)則。通常對于具有分程序結(jié)構(gòu)的語言可用兩種方式組織它們的符號表： 一是對每個分程序建立一個獨立的分表結(jié)構(gòu)的符號表；一是把各分程序符號組織在一張單表結(jié)構(gòu)的符號表中,分表結(jié)構(gòu)的組織管理,其基本思想是，每當(dāng)編譯程序掃描到一個分程序結(jié)構(gòu)開始時，為該分程序建立一張符號表，在該分程序中定義的標(biāo)識符，都被登錄在該符號表中。而當(dāng)編譯程序掃描到一個分程序的結(jié)束時，編譯程序釋放為該分程序所建立的符號表。這種符號表的分表結(jié)構(gòu)與源程序的分程序?qū)哟谓Y(jié)構(gòu)一一對應(yīng),單表結(jié)構(gòu)的組織管理,其基本思想是，所有分程序中定義的標(biāo)識符都集中在單張符號表中。為了實現(xiàn)分程序構(gòu)造中標(biāo)識符的作用域和可視性規(guī)則的要求,在符號表中可設(shè)立一個屬性域用來登錄符號所在分程序的層次 進入分程序時，層次要增加一層.在退出一個分程序時，層次降低一層，且需要把符號表中，所有在退出的分程序中登錄的符號項清除。,,嵌套結(jié)構(gòu)型程序設(shè)計語言（Pascal）的特點，可采用的辦法： ．將其符號表設(shè)計為棧符號表，當(dāng)新的名字出現(xiàn)總是從棧頂填入。查找操作從符號表的棧頂往底部查（保證先查最近出現(xiàn)的名字）。因為程序是分層的，并且一個過程結(jié)束時將釋放相應(yīng)的子符號表，因此查找范圍與線性表比相對要小一些。 ．引入一個顯示（DISPLAY）層次關(guān)系表，稱為過程的嵌套層次表。其作用是為了描述過程的嵌套層次，指出當(dāng)前正在活動著的各嵌套的過程（或函數(shù)）相應(yīng)的子符號表在棧符號表中的起始位置（相對地址）。DISPLAY表也是一個棧，棧頂指針為level。當(dāng)進入一個新過程時，level增加1；每當(dāng)退出一個過程時，level減1。DISPLAY(level)總是指向當(dāng)前正在處理的最內(nèi)層的過程的子符號表在棧符號表中的起始位置。 ．在符號表的信息欄中引入一個指針域（previous）用以鏈接它在同一過程內(nèi)的前一域名字在表中的下標(biāo)（相對位置）。每一層的最后一個域名字，其previous之值為0。這樣，每當(dāng)需要查找一個新名字時，就能通過DISPLAY找出當(dāng)前正在處理的最內(nèi)層的過程及所有外層的子符號表在棧符號表中的位置。然后，通過previous可以找到同一過程內(nèi)的所有被說明的名字。,說明部分的分析與處理,對每個過程說明的對象（變量，常量和過程）造名字表 填寫標(biāo)識符的所在層次、屬性和分配的相對位置。標(biāo)識符的屬性不同時，所需填入的信息也不同。登錄信息由ENTER過程完成。,說明部分的分析與處理（程序）,說明類型的定義： object= (constant, variable,procedur) （定義純量/枚舉類型） 名字表的定義 table:array[0txmax] of record name:alfa; case kind:object of constant:(val:integer); variable:procedur:(level,adr,size: integer);,,,例程序說明部分為： CONST A=35，B=49； VAR C，D，E； PROCEDURE P； VAR G ；…,,名字 類型 層次/值 地址 存儲空間,Const（常量）無層次,對應(yīng)名字表,PL/0編譯程序,Table表的下標(biāo)指針tx補充說明：,,,,,主程序,,,,,,,,BLOCK,第1次調(diào)用block BLOCK（0，0，…）,0,0,.,BLOCK,,,BLOCK（LEV+1,TX，…） (遞歸進入分程序),LEV,tx,LEV,tx,,（6）,6 （9）,1,tx是BLOCK的 實際值參,