符號表管理技術授課：胡靜符號表管理技術2023/9/5編譯原理2目錄概述符號表的組織與內容非分程序結構語言的符號表組織分程序結構語言的符號表組織2023/8/3編譯原理2目錄概述2023/9/5編譯原理3符號表概述符號表的作用：在編譯過程中，編譯程序用來記錄源程序中各種名字的特性信息，所以也稱為名字特性表名字：程序名、過程名、函數(shù)名、用戶定義類型名、變量名、常量名、枚舉值名、標號名等。特性信息：上述名字的種類、類型、維數(shù)、參數(shù)個數(shù)、數(shù)值及目標地址（存儲單元地址）等。2023/8/3編譯原理3符號表概述符號表的作用：2023/9/5編譯原理4建表和查表的必要性源程序中變量要先聲明，然后才能引用。用戶通過聲明語句，聲明各種名字，并給出它們的類型、維數(shù)等信息，編譯程序在處理這些聲明語句時，應該將聲明中的名字及其信息登錄到符號表中，同時編譯程序還要給變量分配存儲單元，而存儲單元地址也必須登錄在符號表中。當編譯程序編譯到引用所聲明的變量時(賦值或引用其值)，要進行語法語義正確性檢查(類型是否符合要求)和生成相應的目標程序，這就需要查符號表以取得相關信息。2023/8/3編譯原理4建表和查表的必要性源程序中變量要先2023/9/5編譯原理5建表，分配存儲查表2023/8/3編譯原理5建表，查表2023/9/5編譯原理6符號表的操作:填表和查表ProcedureP()填表：當分析到程序中的說明或定義語句時，應將說明或定義的名字，以及與之有關的信息填入符號表中。查表:(1)填表前查表，檢查在程序的同一作用域內名字是否重復定義；(2)檢查名字的種類是否與說明一致;(3)對于強類型語言，要檢查表達式中各變量的類型是否一致;(4)生成目標指令時，要取得所需要的地址。2023/8/3編譯原理6符號表的操作:填表和查表Proce2023/9/5編譯原理7符號表的內容符號表的基本結構：“名字”域：存放名字，一般為標識符號串，也可以為指向標識符字符串的指針?！疤匦浴庇颍嚎砂鄠€子域，表示標識符的有關信息：名字的種類:簡單變量、函數(shù)、過程、數(shù)組、標號、參數(shù)等類型:如整型、浮點型、字符型、指針等性質:變量形參、值形參等值:常量名所代表的數(shù)值地址:變量所分配單元的首址或地址位移大小:所占的字節(jié)數(shù)作用域的嵌套層次:2023/8/3編譯原理7符號表的內容符號表的基本結構：2023/9/5編譯原理8符號表的內容“特性”域：對于數(shù)組:維數(shù)、上下界值、計算下標變量地址所用的信息(數(shù)組信息向量)以及數(shù)組元素類型等。對于記錄(結構、聯(lián)合)：域的個數(shù)，每個域的域名、地址位移、類型等。對于過程或函數(shù)：形參個數(shù)、所在層次、函數(shù)返回值類型、局部變量所占空間大小等。對于指針：所指對象類型等。2023/8/3編譯原理8符號表的內容“特性”域：2023/9/5編譯原理9符號表的組織方式1.統(tǒng)一符號表：不論什么名字都填入統(tǒng)一格式的符號表中符號表表項應按信息量最大的名字設計，填表、查表比較方便，結構簡單，但是浪費大量空間。2.對于不同種類的名字分別建立各種符號表節(jié)省空間，但是填表和查表不方便。3.折中辦法：大部分共同信息組成統(tǒng)一格式的符號表，特殊信息另設附表，兩者用指針連接。2023/8/3編譯原理9符號表的組織方式1.統(tǒng)一符號表：不2023/9/5編譯原理102023/8/3編譯原理102023/9/5編譯原理11非分程序結構語言的符號表組織(1)非分程序結構語言:每個可獨立進行編譯的程序單元是一個不包含有子模塊的單一模塊，如FORTRAN語言。2023/8/3編譯原理11非分程序結構語言的符號表組織(12023/9/5編譯原理12非分程序結構語言的符號表組織(2)標識符的作用域及基本處理辦法:1.作用域:全局：子程序名，函數(shù)名和公共區(qū)名。

局部：程序單元中定義的變量。2.符號表的組織:3.基本處理辦法:<1>子程序、函數(shù)名和公共區(qū)名填入全局符號表。<2>在子程序(函數(shù))聲明部分讀到標識符，造局部符號表。2023/8/3編譯原理12非分程序結構語言的符號表組織(22023/9/5編譯原理13非分程序結構語言的符號表組織(2)標識符的作用域基本處理辦法:3.基本處理辦法:<3>在語句部分讀到標識符，查表：<4>程序單元結束:釋放該程序單元的局部符號表。<5>程序編譯完成:釋放全部符號表。2023/8/3編譯原理13非分程序結構語言的符號表組織(22023/9/5編譯原理14符號表的組織方式1.無序符號表：按掃描順序建表，查表要逐項查找。查表操作的平均長度為(n+1)/22.有序符號表：符號表按照變量名進行字典式排序線性查表：(n+1)/2折半查表：3.散列符號表（Hash表）：符號表地址=Hash(標識符)2023/8/3編譯原理14符號表的組織方式1.無序符號表：2023/9/5編譯原理15數(shù)組簡單的實現(xiàn)方案：array每個符號一個入口查詢時掃描整個數(shù)組，對每個名字都進行比較缺點：表格有確定的大小需要預先知道實體的個數(shù)2023/8/3編譯原理15數(shù)組簡單的實現(xiàn)方案：array2023/9/5編譯原理16列表動態(tài)的數(shù)據(jù)結構：list對表格中的一個入口，指定一個單元可以在編譯過程中動態(tài)增長缺點：對大型的符號表來說，效率低下平均來說，需要掃描一般的列表2023/8/3編譯原理16列表動態(tài)的數(shù)據(jù)結構：list2023/9/5編譯原理17哈希表高效的實現(xiàn)：hashtable是列表的數(shù)組(buckets)使用哈希函數(shù)將符號名稱映射到相應的bucket:hashfunc:string→int好的哈希函數(shù)：在bucket之間平均的分配?hashfunc(“m”)=0,hashfunc(“foo”)=32023/8/3編譯原理17哈希表高效的實現(xiàn)：hashta2023/9/5編譯原理18分程序結構語言的符號表組織(1)分程序結構語言:模塊內可嵌入子模塊(2)標識符的作用域和基本處理方法作用域：標識符局部于所定義的模塊(最小模塊)①模塊中所定義的標識符作用域是定義該標識符的子程序2023/8/3編譯原理18分程序結構語言的符號表組織(1)2023/9/5編譯原理19分程序結構語言的符號表組織(2)標識符的作用域和基本處理方法作用域：標識符局部于所定義的模塊(最小模塊)②過程或函數(shù)說明中定義的標識符(包括形參)其作用域為本過程體。2023/8/3編譯原理19分程序結構語言的符號表組織(2)2023/9/5編譯原理20分程序結構語言的符號表組織(2)標識符的作用域和基本處理方法作用域：標識符局部于所定義的模塊(最小模塊)③循環(huán)語句中定義的標識符，其作用域為該循環(huán)語句。不能從循環(huán)體外轉到循環(huán)體內。循環(huán)語句應看作一層2023/8/3編譯原理20分程序結構語言的符號表組織(2)2023/9/5編譯原理21分程序結構語言的符號表組織(2)標識符的作用域和基本處理方法基本處理辦法：建查符號表均要遵循標識符的作用域規(guī)定進行。建表:不能重復，不能遺漏查表:按標識符作用域2023/8/3編譯原理21分程序結構語言的符號表組織(2)2023/9/5編譯原理22分程序結構語言的符號表組織(2)標識符的作用域和基本處理方法基本處理辦法：在程序聲明部分讀到標識符時(聲明性出現(xiàn))，建表在語句中讀到標識符(引用性出現(xiàn))，查表2023/8/3編譯原理22分程序結構語言的符號表組織(2)2023/9/5編譯原理23分程序結構語言的符號表組織(2)標識符的作用域和基本處理方法基本處理辦法：標準標識符的處理：主要是語言定義的一些標準過程和函數(shù)的名字，它們是標識符的子集。如：sin，cos，abs……2023/8/3編譯原理23分程序結構語言的符號表組織(2)2023/9/5編譯原理242023/8/3編譯原理24棧式符號表結構2023/9/5編譯原理25棧式符號表結構2023/8/3編譯原理252023/9/5編譯原理262023/8/3編譯原理262023/9/5編譯原理272023/8/3編譯原理272023/9/5編譯原理28Example2023/8/3編譯原理28Example