編譯原理符號表.ppt

1、第七章: 符號表管理技術(shù),7.1 概述 7.2 符號表的組織與內(nèi)容 7.3 非分程序結(jié)構(gòu)語言的符號表組織 7.4 分程序結(jié)構(gòu)語言的符號表組織,7.1 概述,(1)什么是符號表? 在編譯過程中，編譯程序用于記錄源程序中各種名字的特性信息， 所以也稱為名字特性表。 名字： 程序名、過程名、函數(shù)名、用戶定義類型、變量名、符號名字。 特性信息：名字種類、類型、維數(shù)、參數(shù)個數(shù)及目標(biāo)地址（存儲單元地址）等。,(2) 建表和查表的必要性 (符號表在編譯過程中的作用),源程序中變量要先聲明，然后才能引用。 用戶通過聲明語句，聲明各種名字，以及給出它們的類型維數(shù)等信息，編譯程序在出來這些聲明語句時，因?qū)⒙暶髦械?/p>

2、名字以及信息登錄到符號表中，同時編譯還要給變量分配存儲單元，而存儲單元地址也必須登錄在符號表中。 當(dāng)編譯程序編譯到引用所聲明的變量時（賦值或引用其值）要進(jìn)行語法語義正確性檢查 類型是否符合要求和生成相應(yīng)的目標(biāo)程序，這就需要查符號表來取得相關(guān)信息。,1.語法分析和語義分析 說明語句賦值語句的語法規(guī)則 上下文有關(guān)分析；是否聲明； 類型一致性檢查 2. 生成目標(biāo)代碼 LOAD a 的地址 ADD b 的地址 STO x 的地址,例: int x,a,b; L: x:=a+b; ,建表 分配存貯,符號表,數(shù)據(jù)區(qū),(3) 有關(guān)符號表的操作：填表和查表,填表:當(dāng)分析到程序中的說明或定義語句時應(yīng)將說明或定義

3、的名字以及與之有關(guān)的信息填入符號表中 例：Procedure P() 查表: (1) 填表前查表檢查在程序的同一作用域內(nèi)名字是否重復(fù)定義 (2) 檢查名字的種類是否與說明一致 (3)對于強(qiáng)類型語言要檢查表達(dá)式中各變量的類型是否一致 (4) 生成目標(biāo)指令時要取得所需要的地址,7.2 符號表的組織與內(nèi)容,(1)符號表的結(jié)構(gòu)與內(nèi)容 符號表的基本結(jié)構(gòu)如下 名字 特性(信息) “名字”域:存放名字。一般為標(biāo)識符的符號串，也可為指向標(biāo)識符字符串串指針,“特性”域：可包括多個子域，分別表示標(biāo)識符的有 關(guān)信息。如： 名字（標(biāo)識符）的種類：變量、函數(shù)、過程、數(shù)組、標(biāo)號、參數(shù)等 類型：如整型、浮點(diǎn)型、字符型、指針

4、等 性質(zhì)：變量形參、值形參等 名字：常量名 地址：變量所分配單元的首址或地址位移 大?。核嫉淖止?jié)數(shù),名字 特性(信息),作用域的嵌套層次,對于數(shù)組：維數(shù)、上下界值、計算下標(biāo)量地址所用的信息以及數(shù)組元素類型等 對于記錄（結(jié)構(gòu)、聯(lián)合）：域的個數(shù)、每個域名、地址位移、類型等 對于過程或函數(shù)：形參個數(shù)、所在層次、函數(shù)返回值類型、局部變量所占空間大小等 對于指針：所指對象類型等,(2) 組織方式,1.統(tǒng)一符號表:無論什么名字都填入統(tǒng)一格式的符號表中 符號表表項應(yīng)按信息量最大的名字設(shè)計 填表 查表比較方便 結(jié)構(gòu)簡單 但是浪費(fèi)大量空間 2.對于不同種類的名字分別建立各種符號表 節(jié)省空間 但是填表和查表不方

5、便 3.折中辦法: 大部分共同信息組成統(tǒng)一格式的符號表。 特殊信息另設(shè)附表,兩者用指針連接.,例：begin array B1.100end,補(bǔ)充 指針連接,7.3非分程序結(jié)構(gòu)語言的符號表組織,(1) 分程序的結(jié)構(gòu)語言:每個可獨(dú)立進(jìn)行編譯的程序單元是一個不包含有子模塊的單一模塊.如Fortran語言 Fortran程序構(gòu)造 主程序 子程序 及函數(shù),主程序和子程序中可定義common語句,(2) 標(biāo)識符的作用域及基本處理辦法,1.作用域: 全局: 子程序名,函數(shù)名和公共區(qū)名 局部: 程序單元中定義的變量 2. 符號表的組織 3.基本處理辦法 子程序函數(shù)名和公共區(qū)變量填入全局符號表, 在聲明部分讀

6、到標(biāo)識符,造局部符號表 查本程序單元局部 符號表,有無同名 在語句部分讀到標(biāo)識符 查表 查本程序單元局部 符號表有無同名,有,重復(fù)聲明,報錯 無,造表,有,即已聲明 無,查全局變量表,有 全局量 無 無定義 標(biāo)識符,(3) 符號表的組織方式,4.程序單元結(jié)束:釋放該程序單元的局部符號表 5.程序編譯完成:釋放全部符號表 1.無序符號表:按掃描順序建表,查表要逐項查找 查表操作的平均長度為:n+1/2,2. 有序符號表符號表按變量名進(jìn)行字典式排序 線性查表:n+1/2 折半查表:log2n-1 3.散列符號表(Hash) 表: 符號表地址=Hash(標(biāo)識符) 解決:沖突,7.4分程序結(jié)構(gòu)語言的符

7、號表組織,(1) 分程序的結(jié)構(gòu)語言: 塊內(nèi)可嵌入子模塊 (2) 標(biāo)識符的作用域和基本處理方法 作用域:標(biāo)識符局部于所定義的模塊(最小模塊) 模塊中所定義的標(biāo)識符作用域是定義該標(biāo)識符的子程序,A為內(nèi)分程序局部變量 A為內(nèi)分程序全局變量,都是局部變量,Real A;,Real A;,Real A;,Real A;,Real A;,Real A;,B:=A;,begin procedure P(i,j); begin L end goto L; P(3,5); End;,過程或函數(shù)說明中定義的標(biāo)識符（包括形參） 其作用域?yàn)楸具^程體 例:,循環(huán)語句中定義的標(biāo)識符，其作用域?yàn)樵撗h(huán)語句,for do b

8、egin L end goto L; ,不能從循環(huán)體外轉(zhuǎn)到循環(huán)體內(nèi) 循環(huán)語句應(yīng)看作一層,建查符號表均要遵循標(biāo)識符作用域規(guī)定進(jìn)行 建表不能重復(fù) 不能遺漏 查表按標(biāo)識符作用域,基本處理辦法：,Real x,A,B Integer x,y; procedure p() begin real x; A:=x+2.0; end B:=x+2.0,定義重復(fù)錯誤 必須填表 查表是本層的 查表是本層的(最外層的),處理方法,假設(shè)標(biāo)識符是先聲明后引用(標(biāo)號例外,要特殊處理) a.在程序聲明部分讀到標(biāo)識符時 聲明性出現(xiàn) 建表 查本層符號表 有無重名 b.在語句中讀到標(biāo)識符(引用性出現(xiàn))查表 查本層符號表 有無重名,有 重復(fù)聲明 報錯 無 填入符號表,有 即已聲明 已取該名字 信息 局部量 無 是否是最外層?,是 未聲明標(biāo)識符 報錯 否 轉(zhuǎn)到直接外層,c.標(biāo)準(zhǔn)標(biāo)識符的處理 主要是語言定義的一些標(biāo)準(zhǔn)過程和函數(shù)的名字,它們是標(biāo)識