編譯原理符號表的原理及典型實例

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

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

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

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

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

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

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

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

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

10、的數(shù)據(jù)結(jié)構(gòu)四、符號表的數(shù)據(jù)結(jié)構(gòu)l線性表線性表符號表項按照符號被掃描到的先符號表項按照符號被掃描到的先 后順序登錄后順序登錄 a b a d c b 四、符號表的數(shù)據(jù)結(jié)構(gòu)四、符號表的數(shù)據(jù)結(jié)構(gòu)l有序表有序表符號表項按照符號的字符代碼串符號表項按照符號的字符代碼串 的值的大小排列的值的大小排列 a b a d c b 四、符號表的數(shù)據(jù)結(jié)構(gòu)四、符號表的數(shù)據(jù)結(jié)構(gòu)l散列表散列表符號表項的位置由對該符號進(jìn)行符號表項的位置由對該符號進(jìn)行 某種函數(shù)操作所得到的函數(shù)值來確定某種函數(shù)操作所得到的函數(shù)值來確定 a b a d c b 五、符號表與作用域五、符號表與作用域 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