(8.2)--Samuel's Ch6_2编译原理与实践英文版.ppt

《(8.2)--Samuel's Ch6_2编译原理与实践英文版.ppt》由会员分享，可在线阅读，更多相关《(8.2)--Samuel's Ch6_2编译原理与实践英文版.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter 6Semantic Analysis Symbol Table Manager&Type Checking some some symbolssymbols must must be be collected collected and and be be put put together together into into tablesSymbol Table.tablesSymbol Table.There There are are two two functions functions in in symbol symbol table,table,the the f

2、irst first one one is is to to help help check check if if the the semantic semantic is is correct,correct,the the second second one one is is to to assist generating the code.assist generating the code.To To sum sum up,up,this this chapter chapter would would introduce introduce the the functions,f

3、unctions,content,structurecontent,structure and and operationoperation of symbol table.of symbol table.6.1 The Functions of Symbol Tables The The functions functions of symbol table are:of symbol table are:（1 1）Store informationStore information （2 2）Types CheckingTypes Checking （3 3）Data AddressDat

4、a AddressStore information:Store information:BeforeBefore store store information,information,we we firstlyfirstly should should divided divided the the data data into into different different types,types,then then put put them them into into the the corresponded corresponded tables.tables.Sometimes

5、 Sometimes information information is is stored stored in in table table during during lexical lexical analysis,sometimes it is done in semantic analysis.analysis,sometimes it is done in semantic analysis.If If the the data data is is an an identifier,identifier,it it would would be be stored stored

6、 in in an an identifier identifier tabletable，else else if if the the data data is is a a constant,constant,it it will will be be put put into into a a constant table.constant table.Types CheckingA A compilercompiler uses uses a a symbol symbol table table to to keep keep track track of of the the t

7、ype type and binding information about names.and binding information about names.The The symbol symbol table table is is searched searched every every time time by by a a name name that that is is encountered in the source text.encountered in the source text.If If a a new new name name or or new new

8、 information information about about an an existing existing name name is discovered,the table is changed.is discovered,the table is changed.Data Address:When When a a data data was was stored,stored,the the datas datas address address in in the the table table was also recorded as an attribute of t

9、he table.was also recorded as an attribute of the table.In In the the period period of of code code generation generation in in compiler,compiler,the the data data address address can can be be obtained obtained from from the the symbol symbol table table and and can can be be used directly.used dir

10、ectly.6.2 The Attribute of Symbol Table Symbol table is created according to Symbol table is created according to symbols namesymbols name,so the,so the keyword of the symbol table is symbols name.Except name keyword of the symbol table is symbols name.Except name attribute,there are also six attrib

11、utes of a symbol in symbol attribute,there are also six attributes of a symbol in symbol table using for semantic checking.table using for semantic checking.1.1.Constant declarationsConstant declarations const int size=199;const int size=199;2.2.Type declarationsType declarationsstruct Entrystruct E

12、ntry char*name;char*name;int count;int count;struct Entry*next;struct Entry*next;3.3.Variable declarationsVariable declarationsint a,b100;int a,b100;4.4.Function declarationsFunction declarations9Basic DeclarationsThe six attributes of a symbol as follow:Attribute of kindAttribute of kindAttribute o

13、f dimension or sizeAttribute of dimension or sizeAttribute of parameterAttribute of parameterAttribute of addressAttribute of addressAttribute of level in programAttribute of level in programAttribute of line position in source programAttribute of line position in source programAttribute of Attribut

14、e of kindkind Kind Kind can can describe describe the the characteristics characteristics of of a a symbol.symbol.Every Every symbol symbol has has its its own own type,type,such such as as constant,constant,variable variable and and procedure.procedure.Attribute of Attribute of dimension or sizedim

15、ension or size If If an an identifier identifier is is a a name name of of an an array,array,then then we we should should store store the the dimension dimension and and boundary boundary of of identifier identifier value value as as an an attribute of it.attribute of it.Attribute of Attribute of p

16、arameterparameter If If an an identifier identifier is is a a name name of of a a procedure,procedure,the the parameters parameters of of the procedure should be recorded as an attribute.the procedure should be recorded as an attribute.Attribute of Attribute of addressaddress In In source source pro

17、gram,program,an an identifier identifier or or a a constant constant are are often often related related with with a a unit unit address address to to accomplish accomplish some some operation.operation.So So the addresses of them are put in symbol table as an attribute.the addresses of them are put

18、 in symbol table as an attribute.Attribute of Attribute of levellevel in program in program Symbol Symbol in in program program or or subprogram,subprogram,the the level level of of its its position position in in program program should should be be written written as as an an attribute attribute in

19、 in symbol symbol table.table.In In some some source source languages,languages,identifiers identifiers can can have have same same name name in in different different level level of of program,program,so so attribute attribute of of level level in in program program could could help help recognize

20、recognize them.them.A A blockblock in in a a programming programming language language is is any any construct construct that that can can contain declarations.contain declarations.In In C,C,the the blocks blocks are are files,files,function function declarations,declarations,compound compound state

21、ments,structures,class definitions(in OO languages).statements,structures,class definitions(in OO languages).A A language language is is block block structuredstructured if if it it permits permits the the nesting nesting of of blocks blocks inside inside other other blocks blocks and and if if the

22、the scope scope of of declarations declarations in in a a block block are are limited limited to to that that block block and and other other blocks blocks contained contained in in that block,subject to the that block,subject to the most closely nested rulemost closely nested rule:given given sever

23、al several different different declarations declarations of of the the same same name,name,the the declaration declaration that that applies applies to to a a reference reference is is the the one one in in the the most most closely nested block to the reference.closely nested block to the reference

24、.14Block Structureint i,j;int i,j;int f(int size)int f(int size)char i,temp;char i,temp;double j;double j;char*j;char*j;15ExampleAttribute ofAttribute of line line position in source programposition in source program Sometimes Sometimes the the line line position position of of symbol symbol in in s

25、ource source program program is is needed needed to to be be stored stored as as an an attribute attribute in in symbol symbol table in order to obtain the correct semantic checking.table in order to obtain the correct semantic checking.Attribute of Attribute of constantconstant value value If If th

26、e the symbol symbol is is a a constantconstant,then then the the value value of of it it should should been stored as a value attribute in symbol table.been stored as a value attribute in symbol table.Attributes Attributes above above are are not not all all the the attributes attributes a a symbol

27、symbol table table has,has,some some symbols symbols used used for for special special may may has has particular particular attributes.attributes.To To sum sum up,up,the the function function of of symbol symbol table table is is for for checking checking up up if if the the semantic semantic in so

28、urce program is correct.in source program is correct.Example 6.1The definition of constants is:The definition of constants is:Const pi=3.14 Const pi=3.14 r=10r=10 Its symbol table is:Its symbol table is:Name pi r Kind real int Value 3.14 10Example 6.2Example 6.2 The definition of variables is:The de

29、finition of variables is:Var i,j:integer;Var i,j:integer;x,y:real;x,y:real;Its symbol table is Its symbol table is Name Kind Address i int 100 j int 102 x real 104 y real 108Example 6.3Example 6.3 The definition of procedure is:The definition of procedure is:Procedure Max Procedure Max；Var h,l:integ

30、er;Var h,l:integer;2 2 in in size size attribute attribute means means there there are are two two parameters parameters in in the the procedureprocedure Name Kind Level AddressSize Max H lProcedure int int 0 1 1 308 300 30626.3 The Design of Symbol TableTarget Target symbol symbol table:table:high

31、high running running efficientefficient and and save save the the storagestorage of symbol table.of symbol table.This This section,section,we we begin begin to to discuss discuss the the storage storage and and the the scopescope of of symbols symbols in in various various parts parts of of a a prog

32、ram.program.Then Then we we study study how how to to design design the the structure structure of of a a symbol symbol attribute attribute in in local local symbol symbol table.table.In In order order to to obtain obtain high high running running efficient efficient and and save save the the storag

33、e storage of symbol table,we should take into account a lot of things.of symbol table,we should take into account a lot of things.Firstly,Firstly,what what are are the the features features of of program program languagelanguage?How How many many parts parts are are in in program?program?Which Which

34、 one one should should be be checked checked by semantic?by semantic?Secondly,Secondly,we we should should discuss discuss the the running running environmentenvironment,for for example,example,target target machine machine performance,performance,what what kind kind of of target target code it will

35、 produce.code it will produce.Thirdly,Thirdly,we we should should think think of of the the operation operation systemsystem that that offer offer the way of storage and management.the way of storage and management.Finally,Finally,how how many many passespasses and and how how many many tablestables

36、 according according to the passes we should pay attention to.to the passes we should pay attention to.To To sum sum up,up,if if we we want want to to design design a a symbol symbol table,table,we we should should take take all all those those elements elements into into account account in in order

37、 order to to build build a a reasonable symbol table.reasonable symbol table.There are There are two stepstwo steps to build the symbol table:to build the symbol table:(1)Build the attribute of symbol table.(1)Build the attribute of symbol table.(2)Design the organization of symbol table.(2)Design t

38、he organization of symbol table.The The first first one one we we will will discuss discuss in in this this section,section,the the second second one would be introduced in next section.one would be introduced in next section.In In the the part part of of attribute attribute of of symbol symbol tabl

39、e,table,we we mainly mainly introduce introduce the the attribute attribute of of name,name,attribute attribute of of type type and and the the identifier of array typeidentifier of array type.(1)The attribute of name (1)The attribute of name There There are are three three waysways to to store stor

40、e identifiers identifiers name name in in symbol symbol table.table.thethe first first way way is is shown shown by by Table Table 6.1,6.1,it it means means we we put put the the name name with with all all letters letters in in name name attribute,attribute,the the name name length length is is 10

41、that is a definite.10 that is a definite.Name pi r Kind real int Value 3.14 10(1)The attribute of name (1)The attribute of name There There are are three three waysways to to store store identifiers identifiers name name in in symbol symbol table.table.The The secondsecond way way is is expressed ex

42、pressed in in Fig Fig 6.1(a),6.1(a),letters letters of of name name are are stored stored in in chain chain table,table,namely,namely,in in name name attribute attribute there there are are length length of of the the name name and and the the name name address address of of connect connect table.ta

43、ble.(1)The attribute of name (1)The attribute of name There There are are three three waysways to to store store identifiers identifiers name name in in symbol symbol table.table.TheThe third third way way is is denoted denoted by by Fig.6.1(b),Fig.6.1(b),you you can can only only see see name name

44、address address in in name name attribute,attribute,the the name name length length and and name name letters are written in its chain table.letters are written in its chain table.If a length of identifiers name is 2 bites,using symbol table If a length of identifiers name is 2 bites,using symbol ta

45、ble in first way to store it needs 8 bites,on the other hand storing in first way to store it needs 8 bites,on the other hand storing it by symbol table in second or third way would save the it by symbol table in second or third way would save the space,but it spends a lot of searching time.Totally,

46、using space,but it spends a lot of searching time.Totally,using which way is up to you.which way is up to you.(2)The attribute of type(2)The attribute of typeThere are also There are also three waysthree ways to represent the type attribute.to represent the type attribute.TheThe firstfirst way way i

47、s is putting putting the the type type directlydirectly into into the the type type attribute,shown in Table 6.1.attribute,shown in Table 6.1.Name pi r Kind real int Value 3.14 10(2)The attribute of type(2)The attribute of typeThere are also There are also three waysthree ways to represent the type

48、attribute.to represent the type attribute.TheThe firstfirst way way is is putting putting the the type type directlydirectly into into the the type type attribute,shown in Table 6.1.attribute,shown in Table 6.1.The The second second way way is is creating creating a a 4 4 bites bites tabletable that

49、 that is is shown shown in in Fig.Fig.6.2,6.2,the the first first bite bite in in Table Table 6.2 6.2 is is 1,1,the the type type is is integer,integer,the the second second bite bite is is 1,1,it it is is real,real,the the third third bite bite 1 1 means means logic logic type type and and fourth f

50、ourth one one represent represent character character type.type.(2)The attribute of type(2)The attribute of typeThere are also There are also three waysthree ways to represent the type attribute.to represent the type attribute.TheThe firstfirst way way is is putting putting the the type type directl