編譯原理英文課件：SemanticAnlysis-1

1、Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-1-Compiler Construction Principles & Implementation TechniquesDr. Zheng XiaojuanProfessorSoftware College of Northeast Normal UniversityMay. 2014Software College of Northeast Normal U

2、niversity Compiler Construction Principles & Implementation Techniques-2-Main Content of Chapter 66. Semantic Analysis 6.1 Overview of Semantic Analysis 6.2 Symbol Table 6.3 Semantic Analysis of Types 6.4 Semantic Analysis of Declaration 6.5 Semantic Analysis of Body 6.6 Attribute Grammar and Ac

3、tion GrammarSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-3-Role of Semantic Analysis in a CompilerLexical Analysis scanningSyntax Analysis ParsingSemantic AnalysisIntermediate Code OptimizationIntermediate Code GenerationTarget Code

4、 Generationanalysis/front endsynthesis/back endSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-4-Review the process of Natural Language TranslationYou can put your dream into reality through your efforts!你你 能夠能夠 通過你的努力通過你的努力 實(shí)現(xiàn)你的夢想！實(shí)現(xiàn)你

5、的夢想！句子句子主語主語謂語謂語狀語狀語youyou詞組詞組through your effortsthrough your effortscan put your dream into realitycan put your dream into realitybookbookbesides deskbesides deskSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-5-6.1 Overview of Seman

6、tic Analysis The differences between Syntax and Semantics The necessity of semantic analysis Classification of Semantics for Programming Languages How to describe semantics of a programming language formally? The main task of Semantic AnalysisSoftware College of Northeast Normal University Compiler

7、Construction Principles & Implementation Techniques-6-Differences between Syntax & Semantics Syntax: Rules for describing the structure of a well-defined program; Semantics: The meaning of syntactic structures of a well-defined program;Software College of Northeast Normal University Compiler

8、 Construction Principles & Implementation Techniques-7-The Necessity of Semantic Analysis A syntactically correct program can not guarantee that it is meaningful! The semantic errors for programming languages Undeclared identifier The type of operands does not match for their operator; .Software

9、 College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-8-Classification of Semantics for Programming Languages Static semantics Can be checked during compilation For instance： Undeclared identifier Dynamic semantics Can only be checked during executi

10、on For instance： divide zeroSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-9-Formal Description of Semantics Formal Semantics for Programming Languages Attribute Grammar (for static semantics) Operational Semantics Denotational Semant

11、ics Algebra Semantics Axiomatic Semantics Not as mature as Syntax Analysis Postgraduate CourseSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-10-Main Task of Semantic Analysis Establish Symbol Table from declaration part Store attribut

12、es of identifiers for checking semantic errors and code generation; Check semantic errors throughout the whole program Use after declaration Type related Normally Semantic Analysis will be done along with parsing;Software College of Northeast Normal University Compiler Construction Principles &

13、Implementation Techniques-11-Semantic Errors Use after Declaration（ Declaration related ）標(biāo)識符沒有聲明標(biāo)識符沒有聲明; ; 重復(fù)聲明重復(fù)聲明; ; 如何檢查如何檢查? ?每當(dāng)遇到新聲明的標(biāo)識符每當(dāng)遇到新聲明的標(biāo)識符, ,查符號表查符號表 如果當(dāng)前有效的所有標(biāo)識符中有相同名字的如果當(dāng)前有效的所有標(biāo)識符中有相同名字的, ,則是重復(fù)聲明則是重復(fù)聲明錯誤錯誤; ; 否則生成它的屬性信息否則生成它的屬性信息, ,保存到符號表中保存到符號表中; ;每當(dāng)遇到標(biāo)識符的使用每當(dāng)遇到標(biāo)識符的使用, ,查符號表查符號表 如果沒

14、有找到如果沒有找到, ,說明該標(biāo)識符沒有聲明說明該標(biāo)識符沒有聲明; ; 否則否則, , 得到該標(biāo)識符的屬性得到該標(biāo)識符的屬性, ,進(jìn)行進(jìn)一步分析進(jìn)行進(jìn)一步分析; ;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-12-Semantic Errors Type related errors（ Type related ）各種條件表達(dá)式的類型不是布爾類型各種條件表達(dá)式的類型不是布爾類型; ;運(yùn)算符的分量類型不相容運(yùn)算符的分

15、量類型不相容; ;賦值語句左右類型不相容賦值語句左右類型不相容; ;形實(shí)參類型不相容形實(shí)參類型不相容; ;函數(shù)調(diào)用參數(shù)個數(shù)不同函數(shù)調(diào)用參數(shù)個數(shù)不同; ;f(f(.).)中中f f不是函數(shù)標(biāo)識符不是函數(shù)標(biāo)識符; ;下標(biāo)表達(dá)式下標(biāo)表達(dá)式( (數(shù)組數(shù)組) )不是合法類型不是合法類型; ;函數(shù)說明和函數(shù)返回類型不相容函數(shù)說明和函數(shù)返回類型不相容; ; Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-13-Main Conten

16、t of Chapter 66. Semantic Analysis 6.1 Overview of Semantic Analysis 6.2 Symbol Table 6.3 Semantic Analysis of Types 6.4 Semantic Analysis of Declaration 6.5 Semantic Analysis of Body 6.6 Attribute Grammar and Action GrammarSoftware College of Northeast Normal University Compiler Construction Princi

17、ples & Implementation Techniques-14-6.2 Symbol Table What is a symbol table? Symbol table can be seen as a mapping from identifier name to its attributes; stating the identifiers declared in a program and their attributes;Identifier NameAttributes xint, variable, pvoid, function, (int i), .Softw

18、are College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-15-6.2 Symbol Table Why we need symbol table during Semantic Analysis? From the token definition of an identifier, we only know the name of the identifier, but have no idea about its attribute

19、s such as type, what kind of identifier it is, More information about identifiers are needed to do semantic analysis, to check semantic errors;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-16-6.2 Symbol Table In order to represent th

20、e attributes of identifiers, we need to establish Internal representation of Identifiers Internal representation of Types Internal representation of Values Organization of Symbol Table Scope of identifiers Localized Symbol Table Globalized Symbol Table Interface Functions for Symbol TableSoftware Co

21、llege of Northeast Normal University Compiler Construction Principles & Implementation Techniques-17-Knowledge Relation GraphSemantic AnalysisNeed more information about identifiersSymbol TableAttribute for identifiersInternal representation of identifierInternal representation of typeInternal r

22、epresentation of valueSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-18-Internal representation of Identifiers Different Types of Identifiers Constant name Type name Variable name Function name Procedure name Field nametypedef enum co

23、nstKind, typeKind, varKind, procKind, funcKind, fieldKind idKid;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-19-Internal representation of Identifiers Attributes of Different Types of Identifiers Constant: (類型，值類型，值) Type: (類型類型) )

24、Variable: (類型類型, , 層數(shù)，偏移層數(shù)，偏移) Function: (返回類型返回類型, , 形參定義形參定義, , 代碼地址代碼地址, , 空間大小空間大小, .) Procedure: (形參定義形參定義, , 代碼地址代碼地址, , 空間大小空間大小, .) Field: (類型類型, , 偏移偏移, , 所在結(jié)構(gòu)類型所在結(jié)構(gòu)類型)Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-20-Attribu

25、tes for Constant IdentifierTypePtrKindValueconstKind TypePtr point to the internal representation of the type of the constant; Kind The kind of identifier, here should be constKind; Value The value of the constant;Software College of Northeast Normal University Compiler Construction Principles &

26、 Implementation Techniques-21-Attributes for Type IdentifierTypePtrKindtypeKind TypePtr point to the internal representation of the type; Kind The kind of identifier, here should be typeKind;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniq

27、ues-22-Attributes for Variable IdentifierTypePtrKindAccessLevelOffsetvarKind TypePtr point to the internal representation of the type of the variable; Kind The kind of identifier, here should be varKind; Access: (dir, indir); Level: 層數(shù)層數(shù) Offset:偏移量偏移量Software College of Northeast Normal University C

28、ompiler Construction Principles & Implementation Techniques-23-Attributes for Field IdentifierTypePtrKindOffsetPtrfieldKind TypePtr point to the internal representation of the type of the field; Kind The kind of identifier, here should be fieldKind; Offset: 該域名針對所在結(jié)構(gòu)類型的偏移量該域名針對所在結(jié)構(gòu)類型的偏移量; Ptr: r

29、efers to next field;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-24-Attributes for Real Proc/Func Identifier(實(shí)在過程或者函數(shù)實(shí)在過程或者函數(shù)) )TypePtrKindClassLevelParamCode Size ForwardroutKindactualTypePtr: point to the internal representation o

30、f 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: 層數(shù)層數(shù)where the identifier defined;Param: refers to a list of information for formal parameters;Code: refers to the start address of the target code for the

31、 procedure or function;Size: the size of the space;Forward: true for forward declaration;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-25-Attributes for Formal Proc/Func Identifier (形參過程或者函數(shù)形參過程或者函數(shù))TypePtrKindClassLevelParamOffset r

32、outKindformalTypePtr: 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: 層數(shù)層數(shù)where the identifier defined;Param: refers to a list of information for formal parameter

33、s;Offset: 在形參列表中的偏移在形參列表中的偏移;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-26- 層數(shù)層數(shù)(level)(level)過程過程/ /函數(shù)的定義可以嵌套函數(shù)的定義可以嵌套主程序的層數(shù)為主程序的層數(shù)為0;0; 偏移量偏移量(offset)(offset)執(zhí)行過程執(zhí)行過程/ /函數(shù)的調(diào)用時函數(shù)的調(diào)用時, , 需要為其中的變量分配空間需要為其中的變量分配空間; ;偏移量指的是變量針對其所在過程偏

34、移量指的是變量針對其所在過程/ /函數(shù)的空間的首地函數(shù)的空間的首地址的偏移量址的偏移量; ;Levels and offsets for Variables (including parameters)Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-27-Levels and offsets for Variables (including parameters)Program A var x, y: integer;

35、Begin End.Procedure P() var k:array1.9 of real; m: integer;Begin End;Procedure R()var x:real;Begin End;Function f(i:integer)var j:integer;Begin End;層數(shù)為層數(shù)為0層數(shù)為層數(shù)為1層數(shù)為層數(shù)為2層數(shù)為層數(shù)為1x : (0, 0)y : (0, 1)k : (1, 0)m : (1,18)i : (2, 0)j : (2, 1)x : (1, 0)Software College of Northeast Normal University Compil

36、er Construction Principles & Implementation Techniques-28-Levels and offsets for Variables (including parameters)typedef struct int number; char name10; example; int i;example p; real x;void p(int i) real x, y; void main() 層數(shù)為層數(shù)為0層數(shù)為層數(shù)為1層數(shù)為層數(shù)為1i : (0, 0)p: (0, 1)x : (0, 12)i : (1, 0)x : (1, 1)y

37、: (1, 3)Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-29-Internal representation of Types Types for Programming Languages Basic type Integer Real Bool Char Structural type Array Structure Union Enumeration(枚舉類型枚舉類型) PointerWhy we nee

38、d Internal Representation for Types?- Type is the important attribute for ID;- Type checking is most important part of Semantic Analysis;- The structure of a type is necessary for type checking;Software College of Northeast Normal University Compiler Construction Principles & Implementation Tech

39、niques-30-Internal representation of Basic TypesintPtrintSizeintTySize KindboolPtrboolSizeboolTyrealPtrrealSizerealTycharPtrcharSizecharTySoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-31-Internal representation of Array size = sizeof

40、(ElemTyp) (Up-Low+1) ElemTy: pointer to its element type;Size Kind LowUpElemTyarrayTy array 2.9 of integer; (8, arrayTy, 2, 9, intPtr) int 7; (7, arrayTy, 0, 6, intPtr)Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-32-Internal represe

41、ntation of StructureSize Kind BodystrutTy Body: 指向結(jié)構(gòu)體中域定義鏈表指向結(jié)構(gòu)體中域定義鏈表 Size: 所有域的類型的所有域的類型的sizesize的總和的總和; ;BodyOffsetNexttypedef struct int i; char name10; real x; example;FieldNameFieldTypeSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniq

42、ues-33-Internal representation of UnionSize Kind BodyunionTy Body: 指向聯(lián)合體中域定義鏈表指向聯(lián)合體中域定義鏈表 Size: 所有域的類型的所有域的類型的sizesize中最大值中最大值;BodyFieldTypeNextFieldNametypedef union int i; char name10; real x; test;Software College of Northeast Normal University Compiler Construction Principles & Implementatio

43、n Techniques-34-Internal representation of PointerSize Kind BaseTypeptrTy BaseType: 指向指針的基類型指向指針的基類型; ; Size:指針的空間大小指針的空間大小( (通常為一個單元通常為一個單元);Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-35-Internal representation of EnumerationSize

44、 Kind EListenumTy EList: 枚舉常量鏈表枚舉常量鏈表; ; Size:枚舉類型值的空間大小枚舉類型值的空間大小( (通常為一個單元通常為一個單元););Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-36-Internal representation of Values 可表示的值可表示的值 Integer Real False, true(通常對應(yīng)通常對應(yīng)0 0和和1 1) char: ASC

45、II碼值碼值枚舉類型枚舉類型: : 對應(yīng)整數(shù)對應(yīng)整數(shù) 結(jié)構(gòu)值結(jié)構(gòu)值數(shù)組數(shù)組結(jié)構(gòu)結(jié)構(gòu)聯(lián)合聯(lián)合指針指針Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-37-Knowledge Relation GraphSemantic AnalysisNeed more information about identifiersSymbol TableAttribute for identifiersInternal represent

46、ation of identifierInternal representation of typeInternal representation of valueSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-38-Organization of Symbol Table Scope of identifiers (作用域作用域) Localized Symbol Table (符號表的局部化符號表的局部化) Glo

47、balized Symbol Table (符號表的全局化符號表的全局化) Interface Functions for Symbol Table (接口函數(shù)接口函數(shù))Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-39-Scope of Identifier 作用域作用域(scope) An identifier has its scope in a program; A scope for an identifi

48、er is a piece of program where it is visible or effective; 一個標(biāo)識符的作用域是該標(biāo)識符有效的一段程序一個標(biāo)識符的作用域是該標(biāo)識符有效的一段程序, , 稱為稱為程序的局部化單位程序的局部化單位, , 通常一個程序局部化單位是一個子通常一個程序局部化單位是一個子程序程序( (函數(shù)函數(shù)) )或者分程序或者分程序; ;一個標(biāo)識符的作用域從聲明該標(biāo)識符的位置開始到其所一個標(biāo)識符的作用域從聲明該標(biāo)識符的位置開始到其所在的局部化單位的結(jié)束在的局部化單位的結(jié)束( (其中要去掉其內(nèi)部聲明的同名標(biāo)其中要去掉其內(nèi)部聲明的同名標(biāo)識符的作用域識符的作用域);)

49、;特別地特別地, , 域名的作用域是包含該域名的結(jié)構(gòu)或者聯(lián)合體域名的作用域是包含該域名的結(jié)構(gòu)或者聯(lián)合體; ;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-40-Scope of Identifierint i , j ;void test(int j) real x ; int x ; . void main() char i ; int i ; Question: what about “test”and “mai

50、n”? Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-41-Dealing with Symbol Tableint i , j ;void test ( 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: (voidP

51、tr, 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, 0, dir)i: (intPtr, varKind, 1, 1, dir)Software College of Northeast Normal University Compiler Construction Principles & Implemen

52、tation Techniques-42-Dealing with Symbol Table During Semantic Analysis Identifier declaration(標(biāo)識符聲明標(biāo)識符聲明) Check whether declared already by searching symbol table; If yes, error; If no, establish internal representation, insert into symbol table; Identifier usage(標(biāo)識符使用標(biāo)識符使用) Check whether declared

53、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;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-43-Organization of Symb

54、ol Table Easy for searching 順序查找順序查找 折半查找折半查找 散列表散列表(hash table) Reflect the scope of identifiers, guarantee that each time the effective attributes for the identifiers can be found;局部化局部化: : 每個局部化單位的符號表作為一個獨(dú)立的表處理每個局部化單位的符號表作為一個獨(dú)立的表處理, , 即把每個局部化單位的符號表作為建表和查表單位即把每個局部化單位的符號表作為建表和查表單位; ;全局化全局化: :把整個程序的

55、符號表統(tǒng)一處理把整個程序的符號表統(tǒng)一處理; ;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-44-局部化符號表局部化符號表 Scope棧保存當(dāng)前所有局部化單位符號表的首地址棧保存當(dāng)前所有局部化單位符號表的首地址; ; 局部化實(shí)現(xiàn)原理局部化實(shí)現(xiàn)原理: :進(jìn)入局部化單位進(jìn)入局部化單位, ,建立一個新的空符號表建立一個新的空符號表, ,并將地址壓入并將地址壓入ScopeScope棧棧; ;遇到定義性標(biāo)識符遇到定義性標(biāo)識符(

56、 (聲明聲明),), 查當(dāng)前符號表判定是否有重查當(dāng)前符號表判定是否有重復(fù)定義復(fù)定義, ,如果沒有則將其屬性登記到當(dāng)前符號表中如果沒有則將其屬性登記到當(dāng)前符號表中; ;遇到使用性標(biāo)識符遇到使用性標(biāo)識符, ,查符號表查符號表( (從當(dāng)前符號表查從當(dāng)前符號表查, ,如果沒有如果沒有, ,再依次查再依次查scopescope棧中下一個符號表棧中下一個符號表, ,如果都沒有如果都沒有, ,沒有聲沒有聲明錯明錯; ;否則否則, ,找到對應(yīng)的屬性找到對應(yīng)的屬性););結(jié)束一個局部化單位時結(jié)束一個局部化單位時, ,刪除當(dāng)前符號表刪除當(dāng)前符號表, , 彈出彈出scopescope棧棧頂元素頂元素; ; 每個局部

57、化單位的符號表可以是每個局部化單位的符號表可以是線性表線性表; ; 二叉樹二叉樹; ; 散列表散列表Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-45-局部化符號表局部化符號表int i , j ;void test ( int j ) real x ; j int x ; . void main() char i ; int i ; Scope棧棧0Software College of Northeast Nor

58、mal University Compiler Construction Principles & Implementation Techniques-46-全局化符號表全局化符號表 全局化實(shí)現(xiàn)原理全局化實(shí)現(xiàn)原理整個程序用一個符號表整個程序用一個符號表, , 該符號表的組織可以是該符號表的組織可以是 線性表線性表; ; 二叉樹二叉樹; ; 散列表散列表每個局部化單位對應(yīng)一個唯一的局部化編號每個局部化單位對應(yīng)一個唯一的局部化編號num;num;符號表的表項為符號表的表項為(num, id, attributes);(num, id, attributes);初始化初始化: Current

59、Num = 0;: CurrentNum = 0;進(jìn)入局部化單位進(jìn)入局部化單位, CurrentNum+;, CurrentNum+;遇到定義性標(biāo)識符遇到定義性標(biāo)識符( (聲明聲明),),檢查所有對應(yīng)檢查所有對應(yīng)CurrentNumCurrentNum的表項的表項, ,判定是否有重復(fù)定義判定是否有重復(fù)定義, ,如果沒有則將其屬性及其如果沒有則將其屬性及其CurrentNumCurrentNum登記到符號表中登記到符號表中; ;遇到使用性標(biāo)識符遇到使用性標(biāo)識符, ,查符號表查符號表, ,如果都沒有如果都沒有, ,沒有聲明錯沒有聲明錯; ;否否則則, ,找到對應(yīng)的屬性找到對應(yīng)的屬性; ;結(jié)束一個局

60、部化單位時結(jié)束一個局部化單位時, ,刪除所有刪除所有CurrentNumCurrentNum對應(yīng)的表項對應(yīng)的表項, , CurrentNum -;CurrentNum -;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-47-全局化符號表全局化符號表 Search for attributes for identifier X Depend on how to organize the symbol table? The main idea (1)Num = CurrentNum; (2) search for (X, Num, attr) item in Symbol table, If does exist return attr; If not exist, Num-; if Num0 return false el