1、-1-階段四 語義分析-2-項目需求遍歷語法分析的輸出結果-語法分析樹；構造符號表和信息表；進行語義錯誤檢查，輸出語義錯誤信息；把函數標識符和語句中的變量在符號表中的地址信息回填到語法樹中； 輸出符號表。 -3-語法分析器的開發所處位置詞法分析器語法分析器 語義分析源程序目標程序Token序列語法樹目標代碼生成器符號表及回填后的語法樹源程序形式上的識別和處理 編譯程序最實質性工作 -4-一、編譯原理內容-5-一、Semantic ErrorsUse after Declaration（ Declaration related ）標識符沒有聲明; 重復聲明;如何檢查?每當遇到新聲明的標識符,查符

2、號表如果當前有效的所有標識符中有相同名字的,則是重復聲明錯誤;否則生成它的屬性信息,保存到符號表中;每當遇到標識符的使用,查符號表如果沒有找到,說明該標識符沒有聲明; 否則, 得到該標識符的屬性,進行進一步分析;-6-Semantic ErrorsType related errors（ Type related ）各種條件表達式的類型不是布爾類型;運算符的分量類型不相容;賦值語句左右類型不相容;形實參類型不相容;函數調用參數個數不同;f(.)中f不是函數標識符;下標表達式(數組)不是合法類型;函數說明和函數返回類型不相容;-7-二、Symbol TableIdentifier NameAtt

3、ributes xint, variable, pvoid, function, (int i), .-8-Symbol TableInternal representation of IdentifiersInternal representation of TypesInternal representation of Values-9-Internal representation of IdentifiersDifferent Types of IdentifiersConstant nameType nameVariable nameFunction nameProcedure na

4、meField nametypedef enum constKind, typeKind, varKind, procKind, funcKind, fieldKind idKid;-10-Internal representation of IdentifiersAttributes of Different Types of IdentifiersConstant: (類型，值)Type: (類型)Variable: (類型, 層數，偏移)Function: (返回類型, 形參定義, 代碼地址, 空間大小, .)Procedure: (形參定義, 代碼地址, 空間大小, .)Field:

5、(類型, 偏移, 所在結構類型)-11-Attributes for Constant IdentifierTypePtrKindValueconstKindTypePtrpoint to the internal representation of the type of the constant;KindThe kind of identifier, here should be constKind;ValueThe value of the constant;-12-Attributes for Type IdentifierTypePtrKindtypeKindTypePtrpoint

6、 to the internal representation of the type;KindThe kind of identifier, here should be typeKind;-13-Attributes for Variable IdentifierTypePtrKindAccessLevelOffsetvarKindTypePtrpoint to the internal representation of the type of the variable;KindThe kind of identifier, here should be varKind;Access:

7、(dir, indir);Level: 層數Offset:偏移量-14-Attributes for Field IdentifierTypePtrKindOffsetPtrfieldKindTypePtrpoint to the internal representation of the type of the field;KindThe kind of identifier, here should be fieldKind;Offset: 該域名針對所在結構類型的偏移量;Ptr: refers to next field;-15-Attributes for Real Proc/Fun

8、c Identifier(實在過程或者函數)TypePtrKindClassLevelParamCode Size ForwardroutKindactualTypePtr: point to the internal representation of the type of func(void for proc);Kind: the kind of identifier, here should be routKind;Class: actual refers to real procedure or function;Level: 層數where the identifier defin

9、ed;Param: refers to a list of information for formal parameters;Code: refers to the start address of the target code for the procedure or function;Size: the size of the space;Forward: true for forward declaration;-16-Attributes for Formal Proc/Func Identifier (形參過程或者函數)TypePtrKindClassLevelParamOffs

10、et routKindformalTypePtr: point to the internal representation of the type of func(void for proc);Kind: the kind of identifier, here should be routKind;Class: formal refers to formal procedure or function;Level: 層數where the identifier defined;Param: refers to a list of information for formal paramet

11、ers;Offset: 在形參列表中的偏移;-17-層數(level)過程/函數的定義可以嵌套主程序的層數為0;偏移量(offset)執行過程/函數的調用時, 需要為其中的變量分配空間;偏移量指的是變量針對其所在過程/函數的空間的首地址的偏移量;Levels and offsets for Variables (including parameters)-18-Levels and offsets for Variables (including parameters)Program A var x, y: integer;Begin End.Procedure P() var k:array

12、1.9 of real; m: integer;Begin End;Procedure R()var x:real;Begin End;Function f(i:integer)var j:integer;Begin End;層數為0層數為1層數為2層數為1x : (0, 0)y : (0, 1)k : (1, 0)m : (1,18)i : (2, 0)j : (2, 1)x : (1, 0)-19-Levels and offsets for Variables (including parameters)typedef struct int number; char name10; ex

13、ample; int i;example p; real x;void p(int i) real x, y; void main() 層數為0層數為1層數為1i : (0, 0)p: (0, 1)x : (0, 12)i : (1, 0)x : (1, 1)y : (1, 3)-20-Internal representation of TypesTypes for Programming LanguagesBasic typeIntegerRealBoolChar Structural typeArrayStructureUnionEnumeration(枚舉類型)Pointer-21-I

14、nternal representation of Basic TypesintPtrintSizeintTySize KindboolPtrboolSizeboolTyrealPtrrealSizerealTycharPtrcharSizecharTy-22-Internal representation of Arraysize = sizeof(ElemTyp) (Up-Low+1)ElemTy: pointer to its element type;Size Kind LowUpElemTyarrayTyarray 2.9 of integer;(8, arrayTy, 2, 9,

15、intPtr)int 7;(7, arrayTy, 0, 6, intPtr)-23-Internal representation of StructureSize Kind BodystrutTyBody: 指向結構體中域定義鏈表Size: 所有域的類型的size的總和;BodyOffsetNexttypedef struct int i; char name10; real x; example;FieldNameFieldType-24-Internal representation of UnionSize Kind BodyunionTyBody: 指向聯合體中域定義鏈表Size:

16、 所有域的類型的size中最大值;BodyFieldTypeNextFieldNametypedef union int i; char name10; real x; test;-25-Internal representation of PointerSize Kind BaseTypeptrTyBaseType: 指向指針的基類型;Size:指針的空間大小(通常為一個單元);-26-Internal representation of EnumerationSize Kind EListenumTyEList: 枚舉常量鏈表;Size:枚舉類型值的空間大小(通常為一個單元);-27-In

17、ternal representation of Values可表示的值IntegerRealFalse, true(通常對應0和1)char: ASCII碼值枚舉類型: 對應整數結構值數組結構聯合指針-28-struct symbtablechar idname10;AttributeIR attrIR;struct symbtable * next;SymbTable;符號表的數據結構 -29-typedef struct struct typeIR * idtype;/*指向標識符的類型內部表示*/IdKind kind;/*標識符的類型*/union struct AccessKind

18、 access;int level; int off;VarAttr; /*變量標識符的屬性*/structint level;ParamTable * param; /*參數表*/int code;int size;ProcAttr; /*過程名標識符的屬性*/More;/*標識符的不同類型有不同的屬性*/AttributeIR;typedef IdKind=typeKind, varKind, procKind -30-struct typeIR int size; /*類型所占空間大小*/ TypeKindkind; union struct struct typeIR* indexTy

19、; struct typeIR * elemTy; ArrayAttr; fieldChain * body; /*記錄類型中的域鏈*/ More;TypeIR;typedef Typekind=intTy,charTy ,arrayTy, recordTy, boolTy -31-三、Organization of Symbol TableScope of identifiers (作用域)Localized Symbol Table (符號表的局部化)Globalized Symbol Table (符號表的全局化)Interface Functions for Symbol Table

20、(接口函數)-32- 幾乎在編譯程序工作的全部過程中，都需要對符號表進行頻繁的訪問，查表和填表等操作，是編譯程序的一筆很大的開銷。因此，合理地組織符號表，并相應地選擇好查表和填表的方法，是提高編譯程序工作效率的重要一環。 -33-Scope of Identifier作用域(scope)An identifier has its scope in a program;A scope for an identifier is a piece of program where it is visible or effective; 一個標識符的作用域是該標識符有效的一段程序, 稱為程序的局部化單位

21、, 通常一個程序局部化單位是一個子程序(函數)或者分程序;一個標識符的作用域從聲明該標識符的位置開始到其所在的局部化單位的結束(其中要去掉其內部聲明的同名標識符的作用域);特別地, 域名的作用域是包含該域名的結構或者聯合體;-34-Scope of Identifierint i , j ;void test(int j) real x ; int x ; . void main() char i ; int i ; Question: what about “test”and “main”? -35-Dealing with Symbol Tableint i , j ;void test

22、( int j ) real x ; j int x ; . void main() char i ; int i ; j: (intPtr, varKind, 0, 1, dir)i: (intPtr, varKind, 0, 0, dir)test: (voidPtr, routKind, 0, )j: (intPtr, varKind, 1, 0, dir)x: (realPtr, varKind, 1, 1, dir)x: (intPtr, varKind, 1, ?, dir)main: (voidPtr, routKind, 0, )i: (charPtr, varKind, 1,

23、 0, dir)i: (intPtr, varKind, 1, 1, dir)-36-Dealing with Symbol Table During Semantic AnalysisIdentifier declaration(標識符聲明)Check whether declared already by searching symbol table;If yes, error;If no, establish internal representation, insert into symbol table;Identifier usage(標識符使用)Check whether dec

24、lared by searching symbol table;If yes, get its attributes for further semantic analysis;If no, error;Exit from 局部化單位, delete identifiers that are declared in it;-37-Organization of Symbol TableEasy for searching順序查找折半查找散列表(hash table)Reflect the scope of identifiers, guarantee that each time the ef

25、fective attributes for the identifiers can be found;局部化: 每個局部化單位的符號表作為一個獨立的表處理, 即把每個局部化單位的符號表作為建表和查表單位;全局化:把整個程序的符號表統一處理;-38-局部化符號表Scope棧保存當前所有局部化單位符號表的首地址;局部化實現原理:進入局部化單位,建立一個新的空符號表,并將地址壓入Scope棧;遇到定義性標識符(聲明), 查當前符號表判定是否有重復定義,如果沒有則將其屬性登記到當前符號表中;遇到使用性標識符,查符號表(從當前符號表查,如果沒有,再依次查scope棧中下一個符號表,如果都沒有,沒有聲明

26、錯;否則,找到對應的屬性);結束一個局部化單位時,刪除當前符號表, 彈出scope棧頂元素;每個局部化單位的符號表可以是線性表; 二叉樹; 散列表-39-局部化符號表int i , j ;void test ( int j ) real x ; j int x ; . void main() char i ; int i ; Scope棧0-40-全局化符號表全局化實現原理整個程序用一個符號表, 該符號表的組織可以是線性表; 二叉樹; 散列表每個局部化單位對應一個唯一的局部化編號num;符號表的表項為(num, id, attributes);初始化: CurrentNum = 0;進入局部化

27、單位, CurrentNum+;遇到定義性標識符(聲明),檢查所有對應CurrentNum的表項,判定是否有重復定義,如果沒有則將其屬性及其CurrentNum登記到符號表中;遇到使用性標識符,查符號表,如果都沒有,沒有聲明錯;否則,找到對應的屬性;結束一個局部化單位時,刪除所有CurrentNum對應的表項, CurrentNum -;-41-全局化符號表Search for attributes for identifier XDepend on how to organize the symbol table?The main idea(1)Num = CurrentNum; (2) s

28、earch for (X, Num, attr) item in Symbol table, If does exist return attr;If not exist, Num-; if Num0 return false else goto (2);-42-全部化符號表int i , j ;void test ( int j ) real x ; j int x ; . void main() char i ; int i ; ( 0, id, attributes )Symbol Table-43-Interfaces for Symbol TableCreate symbol tableDestroy symbol tableAppend one item to symbol tableFind entry to an identifierFind attrib