5-Semantic Analysis

Semantic Analysis: 

2301373 Semantic Analysis 1 Semantic Analysis Checking what parsers cannot

Outline: 

2301373 Semantic Analysis 2 Outline Overview Attribute grammar Attribute Semantic rule Computing attributes Evaluation order Synthesized and Inherited attribute Computation of attributes during parsing Type checking Type declaration Type inference Symbol table

Overview: 

2301373 Semantic Analysis 3 Overview Semantics Static semantics Data type (in some languages e.g. C, FORTRAN) Names Run-time semantics Data value Data type (in other languages e.g. Perl) Semantic analyzer Determine if the semantic of the program is correct according to the definition of the language Concern only static semantics

Overview (cont’d): 

2301373 Semantic Analysis 4 Overview (cont’d) How to describe semantics Associated to syntax Syntax-directed semantics An attribute represents a semantic concept. A semantic rule (or attribute equation) is associated to a syntactic rule. A semantic rule describes the relationship between attributes of symbols in a syntactic rule.

Attribute Grammar: 

2301373 Semantic Analysis 5 Attribute Grammar Language construct Variables, function declarations, statements Attribute Property of language construct Name, address, type, value, and scope are attributes of variables. Return type, parameter types, return address, and scope are attributes of functions. Syntax tree is an attributes of code sections. Attribute equation (semantic rule) Associated with grammar production Specify the relationship between attributes of construct in a syntactic rule. Attribute grammar Set of attribute equations

Example of Attribute Grammar: 

2301373 Semantic Analysis 6 Example of Attribute Grammar Construct: num digit Attribute: val Grammar num -> num digit num -> digit digit -> 0|1|…|9 Grammar rule Semantic rule num 1 -> num 2 digit num 1 .val= num 2 .val*10+ digit.val num -> digit num.val = digit.val digit -> 0 digit.val = 0 digit -> 1 digit.val = 1 digit -> 2 digit.val = 2 digit -> 3 digit.val = 3 digit -> 4 digit.val = 4 digit -> 5 digit.val = 5 digit -> 6 digit.val = 6 digit -> 7 digit.val = 7 digit -> 8 digit.val = 8 digit -> 9 digit.val = 9

Parse Tree with Attributes: 

2301373 Semantic Analysis 7 Parse Tree with Attributes num val = 45*10+5 num val = 4*10+5 digit val = 5 num val = 4 digit val = 5 digit val = 4 5 4 5 Grammar rule Semantic rule num 1 -> num 2 digit num 1 .val= num 2 .val*10+ digit.val num -> digit num.val = digit.val digit -> 0 digit.val = 0 digit -> 1 digit.val = 1 digit -> 2 digit.val = 2 digit -> 3 digit.val = 3 digit -> 4 digit.val = 4 digit -> 5 digit.val = 5 digit -> 6 digit.val = 6 digit -> 7 digit.val = 7 digit -> 8 digit.val = 8 digit -> 9 digit.val = 9

Attribute Grammar for Data Type Declaration: 

2301373 Semantic Analysis 8 Attribute Grammar for Data Type Declaration Grammar Rule dec -> type varList type -> int type -> float varList 1 -> id , varList 2 varList -> id Semantic Rule varList.dtype = type.dtype type.dtype = int type.dtype = real id.dtype = varList 1 .dtype varList 2 .dtype= varList 1 .dtype id.dtype = varList.dtype type dec varList float id varList , id dtype= real dtype=real dtype=real dtype=real dtype=real

Another Example of Attribute Grammar: 

2301373 Semantic Analysis 9 Another Example of Attribute Grammar Grammar Rule Bnum -> num baseC baseC ->o baseC -> d num 1 -> num 2 digit num -> digit digit -> 0|1|…|7 digit -> 8 | 9 val=19 base=8 val=3 base=8 val=19 base=8 base=8 val=2 base=8 val=2 Bnum num num o baseC digit digit Semantic Rule num.base=baseC.base Bnum.val=num.val baseC.base=8 baseC.base=10 num 2 .base=num 1 .base digit.base=num 1 .base num 1 .val= if digit.val=error then error else num 2 .val*num 1 .base + digit.val num.val=digit.val digit.base=num.base digit.val = numval(D), where D is 0, 1,…,7 digit.val = if digit.base =8 then error else numval (D), where D is 8,9

Evaluation Order: 

2301373 Semantic Analysis 10 Evaluation Order From semantic rule X.a = f ( X 1 .a 1 , X 2 .a 2 ,…, X n .a n ) Value of a in node X depends on the values of a 1 in X 1 , a 2 in X 2 ,…, and a n in X n . The order of evaluation can be shown in a dependency graph , which is a directed acyclic graph (DAG). X.a X 2 .a 2 X 1 .a 1 X n .a n … X.a X 2 .a 2 X 1 .a 1 X n .a n … X.a X 2 .a 2 X 1 .a 1 X n .a n … X.a X 2 .a 2 X 1 .a 1 X n .a n …

Dependency Graph: Example 1: 

2301373 Semantic Analysis 11 Dependency Graph: Example 1 num val = 45*10+5 num val = 4*10+5 digit val = 5 num val = 4 digit val = 5 digit val = 4 5 4 5 Grammar rule Semantic rule num 1 -> num 2 digit num 1 .val= num 2 .val*10+ digit.val num -> digit num.val = digit.val digit -> 0 digit.val = 0 digit -> 1 digit.val = 1 digit -> 2 digit.val = 2 digit -> 3 digit.val = 3 digit -> 4 digit.val = 4 digit -> 5 digit.val = 5 digit -> 6 digit.val = 6 digit -> 7 digit.val = 7 digit -> 8 digit.val = 8 digit -> 9 digit.val = 9

Dependency Graph: Example 2: 

2301373 Semantic Analysis 12 Dependency Graph: Example 2 Grammar Rule dec -> type varList type -> int type -> float varList 1 -> id , varList 2 varList -> id Semantic Rule varList.dtype = type.dtype type.dtype = int type.dtype = real id.dtype = varList 1 .dtype varList 2 .dtype= varList 1 .dtype id.dtype = varList.dtype type dec varList float id varList , id dtype= real dtype=real dtype=real dtype=real dtype=real

Dependency Graph:Example 3: 

2301373 Semantic Analysis 13 Dependency Graph:Example 3 Grammar Rule Semantic Rule Bnum -> num baseC num.base=baseC.base Bnum.val=num.val baseC ->o baseC.base=8 baseC -> d baseC.base=10 num 1 -> num 2 digit num 2 .base=num 1 .base digit.base=num 1 .base num 1 .val= if digit.val=error then error else num 2 .val*num 1 .base + digit.val num -> digit num.val=digit.val digit.base=num.base digit -> 0|1|…|7 digit.val = numval(D), where D is 0, 1,…,7 digit -> 8 | 9 digit.val = if digit.base =8 then error else numval (D), where D is 8,9 Bnum num num o baseC digit digit

Rule-based Attribute Evaluation: 

2301373 Semantic Analysis 14 Rule-based Attribute Evaluation Order of attribute evaluation can be fixed at compiler construction Attribute grammar is to be analyzed in order to find the orger of evaluation Used often in practice Not general method Two types of attributes Synthesized attributes Inherited attributes

Synthesized Attributes: 

2301373 Semantic Analysis 15 Synthesized Attributes An attribute a is a synthesized attribute if for a grammar rule A ->X 1 X 2 … X n , an attribute equation with a on the LHS is of the form A. a = f( X 1 . a 1 , X 2 . a 2 , … X n . a n ), or all dependencies point from child to parent in the parse tree If all attributes in an attribute grammar are synthesized attributes, the grammar is called an S-attributed grammar . Grammar rule Semantic rule num 1 -> num 2 digit num 1 .val= num 2 .val*10+ digit.val num -> digit num.val = digit.val digit -> 0|1|…|9 digit.val = val (D) num num digit num digit digit 5 4 5

Order of Evaluation for Synthesized Attributes: 

2301373 Semantic Analysis 16 Order of Evaluation for Synthesized Attributes Use postorder (or bottom-up) evaluation Procedure PostEval ( T :node) { for each child C of T { PostEval( C ); } compute all synthesized attributes of T } num num digit num digit digit 5 4 5 4 4 5 45 5 5 455

Inherited Attributes: 

2301373 Semantic Analysis 17 Inherited Attributes An attribute is an inherited attribute if it is not a synthesized attribute. An attribute grammar is an L-attributed grammar if for each inherited attribute a j at X i in each grammar rule X -> X 1 X 2 … X n depends on the value of attributes of symbols X, X 1 , X 2 ,…, X i-1 . Grammar Rule Semantic Rule dec -> type varList varList.dtype = type.dtype type -> int type.dtype = int type -> float type.dtype = real varList 1 -> id , varList 2 id.dtype = varList 1 .dtype varList -> id id.dtype = varList.dtype type dec varList float id varList , id

Order of Evaluation for Inherited Attributes: 

2301373 Semantic Analysis 18 Order of Evaluation for Inherited Attributes Use preorder and inorder evaluation together Procedure Eval (T:node) { case nodeType(T) of dec: { Eval(typeChild(T)); varList.dtype=type.dtype; Eval(varChild(T)); } type: { if child(T) is int then T.dtype=int; if child(T) is float then T.dtype=real; } varList: { leftChild(T).dtype=T.dtype; if (rightmostChild(T) is not null) then {rightmostChild(T).dtype=T.dtype; Eval(rightChild(T));} } } type dec varList float id varList , id float float float float float

Another Example of Inherited Attributes: 

2301373 Semantic Analysis 19 Another Example of Inherited Attributes Proc Eval(T:node) { case Nodetype(T) of Bnum: { Eval(rightChild(T)); (leftChild(T)).base= (rightChild(T)).base; Eval(leftChild(T)); T.val=leftChild(T).val; } baseC: { if child(T)=o then T.base=8; if child(T)=d thenT.base=10;} num: { leftChild(T).base=T.base; Eval(leftChild(T)); if (rightChild(T)!=null) then { rightChild(T).base=T.base; Eval(rightChild(T); T.val=f(T); } else T.val=leftChild(T).val; cal val} digit: { … } } Grammar Rule Semantic Rule Bnum -> num baseC num.base=baseC.base; Bnum.val=num.val baseC ->o baseC.base=8 baseC -> d baseC.base=10 num 1 -> num 2 digit num 2 .case=num 1 .base; digit.base=num 1 .base; num 1 .val= if digit.val=error then error else num 2 .val*num 1 .base + digit.val num -> digit num.val=digit.val; digit.base=num.base digit -> 0|1|…|7 digit.val = numval(D) digit -> 8 | 9 digit.val = if digit.base =8 then error else numval (D) Bnum num num o baseC digit digit base=8 base=8 base=8 val=5 base=8 val=5 base=8 val=4 val=44 val=44

Evaluation Order for Synthesized + Inherited Attributes: 

2301373 Semantic Analysis 20 Evaluation Order for Synthesized + Inherited Attributes Procedure CombinedEval(T:node) { for each child C of T { compute all inherited attributes of C; CombinedEval(C); } compute all synthesized attributes of T; }

Attribute Computation During Parsing: 

2301373 Semantic Analysis 21 Attribute Computation During Parsing