編譯原理 符號(hào)表10

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

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

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

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

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

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

7、 標(biāo)識(shí)符的作用域和基本處理方法作用域:標(biāo)識(shí)符局部于所定義的模塊(最小模塊)模塊中所定義的標(biāo)識(shí)符作用域是定義該標(biāo)識(shí)符的子程序16 A為內(nèi)分程序局部變量 A為內(nèi)分程序全局變量都是局部變量Real A;Real A;Real A;Real A;Real A;Real A;B:=A;17begin procedure P(i,j); begin L end goto L; P(3,5); End;過(guò)程或函數(shù)說(shuō)明中定義的標(biāo)識(shí)符（包括形參） 其作用域?yàn)楸具^(guò)程體例:18循環(huán)語(yǔ)句中定義的標(biāo)識(shí)符，其作用域?yàn)樵撗h(huán)語(yǔ)句for do begin L end goto L; 不能從循環(huán)體外轉(zhuǎn)到循環(huán)體內(nèi)循環(huán)語(yǔ)句應(yīng)看作一

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