編譯原理符號(hào)表的原理及典型實(shí)例

1、編編 譯譯 原原 理理第九章第九章 符號(hào)表符號(hào)表在編譯程序工作的過(guò)程中在編譯程序工作的過(guò)程中,需要需要。這些信息一般以這些信息一般以表格形式存儲(chǔ)于系統(tǒng)中。如表格形式存儲(chǔ)于系統(tǒng)中。如等等，統(tǒng)稱為等等，統(tǒng)稱為符號(hào)表符號(hào)表。對(duì)于對(duì)于符號(hào)表符號(hào)表方法的好方法的好壞會(huì)直接影響壞會(huì)直接影響的運(yùn)行效率。的運(yùn)行效率。第九章第九章 符號(hào)表符號(hào)表一、符號(hào)表的作用和功能一、符號(hào)表的作用和功能l收集符號(hào)屬性收集符號(hào)屬性l上下文語(yǔ)義的合法性檢查的依據(jù)上下文語(yǔ)義的合法性檢查的依據(jù)l作為目標(biāo)代碼生成階段地址分配的依據(jù)作為目標(biāo)代碼生成階段地址分配的依據(jù) 例：例：C語(yǔ)言程序段：語(yǔ)言程序段：int a; a=1;MOV #1,R

2、0MOV R0,memal詞法分析：詞法分析：a是一個(gè)單詞；是一個(gè)單詞；l語(yǔ)法分析：語(yǔ)法分析：a出現(xiàn)在一條變量聲明語(yǔ)句和一條出現(xiàn)在一條變量聲明語(yǔ)句和一條賦值語(yǔ)句中；賦值語(yǔ)句中；l語(yǔ)義分析：語(yǔ)義分析：a是一個(gè)整形變量，并分配地址。是一個(gè)整形變量，并分配地址。二、符號(hào)表的內(nèi)容二、符號(hào)表的內(nèi)容l標(biāo)識(shí)符的名字標(biāo)識(shí)符的名字l與標(biāo)識(shí)符有關(guān)的信息與標(biāo)識(shí)符有關(guān)的信息 類型信息（包括種類和屬性）類型信息（包括種類和屬性） 地址碼地址碼 層次信息層次信息 行號(hào)信息行號(hào)信息 二、符號(hào)表的內(nèi)容二、符號(hào)表的內(nèi)容例：例：Pascal語(yǔ)言的名字信息表語(yǔ)言的名字信息表nametabname kind lev typ norm

3、al ref adr/val/size link01tx名字標(biāo)識(shí)符名字標(biāo)識(shí)符名字種類，可以是常量名字種類，可以是常量(constant)、變量、變量(variable)、類、類型型(type)、過(guò)程、過(guò)程(procedure)名字所在的程序體的靜態(tài)層次。規(guī)名字所在的程序體的靜態(tài)層次。規(guī)定主程序的層次為定主程序的層次為1，主程序中定，主程序中定義的層次為義的層次為2，依次類推，依次類推名字的類型，類型有整型名字的類型，類型有整型(ints)、字符型、字符型(chars)、布爾型、布爾型(bool)、數(shù)組、數(shù)組(arrays)，對(duì)，對(duì)于無(wú)類型的名字填入于無(wú)類型的名字填入notype一個(gè)布爾量，用于

4、標(biāo)明名字是否為變量形參一個(gè)布爾量，用于標(biāo)明名字是否為變量形參名，當(dāng)名字是否為變量形參名時(shí)填入名，當(dāng)名字是否為變量形參名時(shí)填入false，其他情況填入其他情況填入true或不填或不填當(dāng)名字為數(shù)組類型或數(shù)組變量名時(shí)，當(dāng)名字為數(shù)組類型或數(shù)組變量名時(shí)，ref指向該數(shù)組在數(shù)指向該數(shù)組在數(shù)組信息表中的位置；當(dāng)名字為過(guò)程名時(shí)，組信息表中的位置；當(dāng)名字為過(guò)程名時(shí)，ref指向該過(guò)程指向該過(guò)程在程序體表在程序體表(btab)中的位置；其他情況中的位置；其他情況ref為為0adr, 當(dāng)名字為變量名時(shí)當(dāng)名字為變量名時(shí)(包括形參，存入該變量包括形參，存入該變量(或形參或形參)在相應(yīng)活動(dòng)記錄在相應(yīng)活動(dòng)記錄中分類的存貯單元

5、的相對(duì)地址；對(duì)于過(guò)程名，填入他們相應(yīng)代碼的入口地中分類的存貯單元的相對(duì)地址；對(duì)于過(guò)程名，填入他們相應(yīng)代碼的入口地址址val, 當(dāng)名字為變量名時(shí)，填入他們的相應(yīng)值當(dāng)名字為變量名時(shí)，填入他們的相應(yīng)值size, 當(dāng)名字為類型名時(shí)，填入該類型數(shù)據(jù)所需存貯單元的數(shù)目當(dāng)名字為類型名時(shí)，填入該類型數(shù)據(jù)所需存貯單元的數(shù)目指向同一程序體中定義的上一個(gè)名字指向同一程序體中定義的上一個(gè)名字在在nametab中的位置，每個(gè)程序體在中的位置，每個(gè)程序體在nametab中登記的第一個(gè)名字的中登記的第一個(gè)名字的link為為0二、符號(hào)表的內(nèi)容二、符號(hào)表的內(nèi)容例：例：Pascal語(yǔ)言的名字信息表語(yǔ)言的名字信息表nametabt

6、ype a=array1.10, 1.10 of integer;name kindtypref katype arraysntxnametab例：例：Pascal語(yǔ)言的數(shù)組信息表語(yǔ)言的數(shù)組信息表atabinxtypeltyp elref lowhigh elsizesize12ax數(shù)組的下標(biāo)類型數(shù)組的下標(biāo)類型數(shù)組元素類型數(shù)組元素類型當(dāng)元素為數(shù)組時(shí)，它指向當(dāng)元素為數(shù)組時(shí)，它指向該元素?cái)?shù)組信息在該元素?cái)?shù)組信息在atab表表中的位置，其他情況為中的位置，其他情況為0數(shù)組下限數(shù)組下限數(shù)組上限數(shù)組上限數(shù)組元素的體積數(shù)組元素的體積數(shù)組本身的體積數(shù)組本身的體積二、符號(hào)表的內(nèi)容二、符號(hào)表的內(nèi)容type a=

7、array1.10, 1.10 of integer;name kindtypref katype arraysntxnametabinxtyp eltypelreflow high elsize size nintsarraysm11010100 mintsints0110110axatab三、符號(hào)表的組織三、符號(hào)表的組織l按照屬性種類完全相同的那些符號(hào)組織按照屬性種類完全相同的那些符號(hào)組織 在一起；在一起；l把所有語(yǔ)言中的符號(hào)都組織在一張符號(hào)把所有語(yǔ)言中的符號(hào)都組織在一張符號(hào) 表中；表中；l根據(jù)符號(hào)屬性相似程度分類組織成若干根據(jù)符號(hào)屬性相似程度分類組織成若干 張表，每張表中記錄的符號(hào)都有比

8、較多張表，每張表中記錄的符號(hào)都有比較多 的相同屬性。的相同屬性。三、符號(hào)表的組織三、符號(hào)表的組織假設(shè)有下列三類符號(hào)及其所需屬性假設(shè)有下列三類符號(hào)及其所需屬性第一類符號(hào)第一類符號(hào)屬性屬性1 1屬性屬性2 2屬性屬性3 3第二類符號(hào)第二類符號(hào)屬性屬性1 1屬性屬性2 2屬性屬性4 4第三類符號(hào)第三類符號(hào)屬性屬性2 2屬性屬性5 5屬性屬性6 6第一種組織法：按屬性分類第一種組織法：按屬性分類優(yōu)點(diǎn)：管理一致，空間效率高優(yōu)點(diǎn)：管理一致，空間效率高缺點(diǎn)：管理復(fù)雜缺點(diǎn)：管理復(fù)雜三、符號(hào)表的組織三、符號(hào)表的組織假設(shè)有下列三類符號(hào)及其所需屬性假設(shè)有下列三類符號(hào)及其所需屬性第一類符號(hào)第一類符號(hào)屬性屬性1 1屬性

9、屬性2 2屬性屬性3 3第二類符號(hào)第二類符號(hào)屬性屬性1 1屬性屬性2 2屬性屬性4 4第三類符號(hào)第三類符號(hào)屬性屬性2 2屬性屬性5 5屬性屬性6 6第二種組織法：?jiǎn)我唤M織第二種組織法：?jiǎn)我唤M織優(yōu)點(diǎn)：管理一致，集中單一優(yōu)點(diǎn)：管理一致，集中單一缺點(diǎn)：管理復(fù)雜缺點(diǎn)：管理復(fù)雜三、符號(hào)表的組織三、符號(hào)表的組織假設(shè)有下列三類符號(hào)及其所需屬性假設(shè)有下列三類符號(hào)及其所需屬性第一類符號(hào)第一類符號(hào)屬性屬性1 1屬性屬性2 2屬性屬性3 3第二類符號(hào)第二類符號(hào)屬性屬性1 1屬性屬性2 2屬性屬性4 4第三類符號(hào)第三類符號(hào)屬性屬性2 2屬性屬性5 5屬性屬性6 6第三種組織法：折中方法第三種組織法：折中方法四、符號(hào)表

10、的數(shù)據(jù)結(jié)構(gòu)四、符號(hào)表的數(shù)據(jù)結(jié)構(gòu)l線性表線性表符號(hào)表項(xiàng)按照符號(hào)被掃描到的先符號(hào)表項(xiàng)按照符號(hào)被掃描到的先 后順序登錄后順序登錄 a b a d c b 四、符號(hào)表的數(shù)據(jù)結(jié)構(gòu)四、符號(hào)表的數(shù)據(jù)結(jié)構(gòu)l有序表有序表符號(hào)表項(xiàng)按照符號(hào)的字符代碼串符號(hào)表項(xiàng)按照符號(hào)的字符代碼串 的值的大小排列的值的大小排列 a b a d c b 四、符號(hào)表的數(shù)據(jù)結(jié)構(gòu)四、符號(hào)表的數(shù)據(jù)結(jié)構(gòu)l散列表散列表符號(hào)表項(xiàng)的位置由對(duì)該符號(hào)進(jìn)行符號(hào)表項(xiàng)的位置由對(duì)該符號(hào)進(jìn)行 某種函數(shù)操作所得到的函數(shù)值來(lái)確定某種函數(shù)操作所得到的函數(shù)值來(lái)確定 a b a d c b 五、符號(hào)表與作用域五、符號(hào)表與作用域 int main()int a=0;int b=0;int b=1;int a=2;printf(“%d,%dn”,a,b);int b=3;printf(“%d,%dn”,a,b);printf(“%d,%dn”,a,b);printf(“%d,%dn”,a,b);B2B3B1B0 int main()int a=0; int b=0