编译原理教学课件：Chapter 6 - Semantic Analysis

1、2022-4-261Semantic Analysis2022-4-262nWe have seen how we can write a parser that tells us if a statement is valid or not based on some grammarnBut what exactly does the statement mean?nSemantic Analysis provides additional information needed to compile a program2022-4-263Semantic Analysis PhasenPur

2、pose: compute additional information needed for compilation that is beyond the capabilities of Context-Free Grammars and Standard Parsing AlgorithmsnStatic semantic analysis: Take place prior to execution (Such as building a symbol table、performing type inference and type checking) 2022-4-264Classif

3、icationnAnalysis of a program required by the rules of the programming language to establish its correctness and to guarantee proper executionnAnalysis performed by a compiler to enhance the efficiency of execution of the translated programThis Chapter includes: 2022-4-265nDescription of the static

4、semantic analysis qAttribute grammar nidentify attributes of language entities that must be computed nand to write attribute equations or semantic rules that express how the computation of such attributes is related to the grammar rules of the languageqWhich is most useful for languages that obey th

5、e principle of Syntax-Directed Semanticsnmeaning that, based on a representation of source code, they:qperform analysesqgenerate target code2022-4-266nImplementation of the static semantic analysis: qNot as clearly expressible as parsing algorithms because of the addition problem caused by the timin

6、g of the analysis during the compilation processqMulti-pass (more common) or single pass lead to totally different process2022-4-267Structure of Syntax-directed Compilerscannerparsersemanticroutinesoptimizercodegenerator“target code”“source code”tokensASTSymbol Table/Intermediate Code2022-4-268Symbo

7、l Tablescannerparsersemanticroutinesoptimizercodegenerator“target code”“source code”symbol attributes x Symbol Table2022-4-269Symbol Table: attributes are many and variedscannerparsersemanticroutinesoptimizercodegenerator“target code”“source code”X int 3Y bool 987Z float 16SymbolAttributestype“defin

8、ed at source line”Ex:2022-4-2610Compilation in a NutshellSource code(character stream)ParsingSemantic Analysisif (b = 0) a = b;Token streamif(b)a=b;0=Lexical analysisif=int bint 0=int aint bbooleanDecorated ASTint;Abstract syntax tree(AST)if=b0=ab;2022-4-2611Compilation in a NutshellOptimizationCode

9、 generationif=int bint 0=int aint bbooleanint;Intermediate Code GenerationCJUMP =MEMfp8+CONSTMOVE0MEMMEMfp4fp8NOP+CJUMP =CONSTMOVE0DXCXNOPCXCMP CX, 0CMOVZ DX,CX2022-4-2612Questions to Answer:nIs x a scalar, an array, or a function?nIs x declared before it is used?nWhich declaration of x does this re

10、ference?nDoes the dimension of a reference match the declaration?nIs an array reference in bounds?nType errors (that can be caught statically)2022-4-261313Attribute GrammarsnGeneralization of context-free grammarsnEach grammar symbol has an associated set of attributesnAugment grammar with rules tha

11、t define valuesqNot allowed to refer to any variables or attributes outside the current production2022-4-2614Example:Consider the following grammar for simple integer arithmetic expressions:expr1 expr2 + term expr termterm1 term2 * factorterm factorfactor ( expr )factor numexpr1.val = expr2.val + te

12、rm.val expr.val = term.valterm1.val = term2.val * factor.valterm.val = factor.valfactor.val = expr.valfactor.val = num.valGrammar RuleSemantic Rulesexpr expr + term expr termterm term * factorterm factorfactor ( expr )factor num2022-4-261515Attribute TypesnValues are computed from constants and othe

13、r types:qSynthesized attribute value computed from childrenqInherited attribute value computed from siblings, parent, and own attributes2022-4-26166.1 Attributes and Attribute Grammars2022-4-2617AttributesnProperty of a programming language constructnExamplesqData type of a variableqValue of an expr

14、essionqLocation of a variable in memoryqObject code of a procedureqNumber of significant digits in a number2022-4-2618AttributesnAttributes are associated directly with the grammar symbols (terminals and nonterminals)nIf X is a grammar symbol ,and a is an attribute associated to X, then the value of

15、 a associated to X is written as X.a2022-4-2619Attribute Equation (or Semantic Rule)nGiven a collection of attributes a1 , . . . , aknFor each grammar rule X0X1 X2 . . . X n, the values of the attributes Xi.aj of each grammar symbol Xi are related to the values of the attributes of the other symbols

16、 in the rulenAttribute equation has the formXi .aj = fij (X0.a1 , . . . , X0.ak ,X1.a1 , . . . , X1.ak , . . . , Xn .a1 , . . . , Xn .ak ) where fij is a mathematical function of its arguments2022-4-2620Attribute GrammarnAn attribute grammar for the attributes a1,ak is the collection of all attribut

17、e equations, for all the grammar rules of the languagenTypically, attribute grammars are written in tabular formGrammar RuleSemantic RulesRule 1Associated attribute equationsRule nAssociated attribute equations2022-4-2621Attribute GrammarsnAttributes are given names (e.g. value)nGrammars are modifie

18、d to clarifyexpr expr + term|termbecomesexpr1 expr2 + termexpr termnAttributes are associated with symbols likeexpr1.valnEach grammar rule has associated rules to deal with the attributesexpr1.val = expr2.val + term.val2022-4-2622Rewriteexpr1 expr2 + term expr termterm1 term2 * factorterm factorfact

19、or ( expr )factor numexpr1.val = expr2.val + term.val expr.val = term.valterm1.val = term2.val * factor.valterm.val = factor.valfactor.val = expr.valfactor.val = num.valGrammar RuleSemantic Rules2022-4-2623Evaluate1 + 2 * 3expr1 expr2 + term expr termterm1 term2 * factorterm factorfactor ( expr )fac

20、tor num2022-4-2624exprtermexprtermfactortermfactorfactornumnumnum11111232223367expr1.val = expr2.val + term.val expr.val = term.valterm1.val = term2.val * factor.valterm.val = factor.valfactor.val = expr.valfactor.val = num.val2022-4-2625Consider a declaratione.g. float x,y;int i;char c;2022-4-2626G

21、rammar for Declarationdecl type dec_list;dec_list id | dec_list, idtype char | int | i, j, k2022-4-2627Grammar for Declarationdecl type dec_list;dec_list iddec_list1 dec_list2, idtype chartype inttype floatdecl.dtype = type.dtype;dec_list.dtype = decl.dtype;id.dtype = dec_list.dtype;id.

22、dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;Grammar RuleSemantic Rulese.g. int i, j, kLets parse: int i, j, k;decldecl type dec_list;dec_list iddec_list1 dec_list2, idtype chartype inttype floatdecltypedec_listLets parse: int i, j,

23、k;decl type dec_list;dec_list iddec_list1 dec_list2, idtype chartype inttype floatdec_listidLets parse: int i, j, k;decltypedec_listdecl type dec_list;dec_list iddec_list1 dec_list2, idtype chartype inttype floatdec_listidLets parse: int i, j, k;decltypedec_listdec_listiddecl type dec_list;dec_list

24、iddec_list1 dec_list2, idtype chartype inttype floatdec_listidLets parse: int i, j, k;decltypedec_listdec_listididdecl type dec_list;dec_list iddec_list1 dec_list2, idtype chartype inttype floatdec_listidLets parse: int i, j, k;decltypedec_listdec_listididdecl type dec_list;dec_list iddec_list1 dec_

25、list2, idtype chartype inttype floatdecltypedec_listdec_listiddec_listididdecldec_listtypeiddecl.dtype = type.dtype;dec_list.dtype = decl.dtype;id.dtype = dec_list.dtype;id.dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;decltypedec_lis

26、tdec_listiddec_listididdecl.dtype = type.dtype;dec_list.dtype = decl.dtype;id.dtype = dec_list.dtype;id.dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;decldec_listtypeiddecltypedec_listdec_listiddec_listididdecl.dtype = type.dtype;dec_

27、list.dtype = decl.dtype;id.dtype = dec_list.dtype;id.dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;decldec_listtypeiddecltypedec_listdec_listiddec_listididdecl.dtype = type.dtype;dec_list.dtype = decl.dtype;id.dtype = dec_list.dtype;i

28、d.dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;decldec_listtypeiddecltypedec_listdec_listiddec_listididdecl.dtype = type.dtype;dec_list.dtype = decl.dtype;id.dtype = dec_list.dtype;id.dtype = dec_list1.dtype;dec_list2.dtype = dec_lis

29、t1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;decldec_listtypeiddecltypedec_listdec_listiddec_listididdecl.dtype = type.dtype;dec_list.dtype = decl.dtype;id.dtype = dec_list.dtype;id.dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dt

30、ype = FLOAT;decldec_listtypeiddecltypedec_listdec_listiddec_listididdecl.dtype = type.dtype;dec_list.dtype = decl.dtype;id.dtype = dec_list.dtype;id.dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;decldec_listtypeiddecltypedec_listdec_l

31、istiddec_listididdecl.dtype = type.dtype;dec_list.dtype = decl.dtype;id.dtype = dec_list.dtype;id.dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;decldec_listtypeiddecltypedec_listdec_listiddec_listididdecl.dtype = type.dtype;dec_list.d

32、type = decl.dtype;id.dtype = dec_list.dtype;id.dtype = dec_list1.dtype;dec_list2.dtype = dec_list1.dtype;type.dtype = CHAR;type.dtype = INT;type.dtype = FLOAT;decldec_listtypeid2022-4-2643Textbook Examples2022-4-2644number1number2 digitnumber digit digit 0 digit 1 digit 2 digit 3 digit 4 digit 5 dig

33、it 6 digit 7 digit 8 digit 9 table 6.1Example 6.1 consider the following simple grammar for unsigned numbers:number number digit | digitdigit 0|1|2|3|4|5|6|7|8|9 The most significant attribute: numeric value (write as val)Grammar RuleSemantic Rulesnumber1.val = number2.val*10+digit.valnumber.val= di

34、git.valdigit.val = 0digit.val = 1digit.val = 2digit.val = 3digit.val = 4digit.val = 5digit.val = 6digit.val = 7digit.val = 8digit.val = 92022-4-2645The parse tree showing attribute computations for the number 345 is given as follows 3numbernumberdigitnumberdigitdigit45(val=3)(val=3)(val=4)(val=3*10+

35、4=34)(val=5)(val=34*10+5=345)Fig. 6.12022-4-2646Example 6.2 consider the following grammar for simple integer arithmetic expressions:exp exp + term | exp-term | termterm term*factor | factorfactor (exp)| number The principal attribute of an exp (or term or factor) is its numeric value (write as val)

36、 and the attribute equations for the val attribute are given as followsGrammar RuleSemantic Rulesexp1exp2+termexp1.val=exp2.val+term.valexp1exp2-termexp1.val=exp2.val-erm.valexp1 termexp1.val= term.valterm1term2*factorterm1.val=term2.val*factor.val termfactorterm.val=factor.val factor(exp)factor.val

37、=exp.val factornumberfactor.val=number.valTable 6.22022-4-2647Given the expression (34-3)*42 , the computations implied by this attribute grammar by attaching equations to nodes in a parse tree is as followsexp(val = 1302)term(val = 31*42=1302)term(val = 31)factor(val = 42)( exp ) (val = 34-3=31)exp

38、(val = 34)term(val = 3)factor(val = 31)number(val = 42)term(val = 34)factor(val =3)factor(val = 34)number(val = 3)number(val = 34)-*Fig. 6.2Grammar RuleSemantic Rulesexp1exp2+termexp1.val=exp2.val+term.valexp1exp2-termexp1.val=exp2.val-erm.valexp1 termexp1.val= term.valterm1term2*factorterm1.val=ter

39、m2.val*factor.val termfactorterm.val=factor.val factor(exp)factor.val=exp.val factornumberfactor.val=number.val2022-4-2648Example 6.3 consider the following simple grammar of variable declarations in a C-like syntax:decl type var-listtypeint | floatvar-listid, var-list |id Define a data type attribu

40、te for the variables given by the identifiers in a declaration and write equations expressing how the data type attribute is related to the type of the declaration as follows: (We use the name dtype to distinguish the attribute from the nonterminal type)2022-4-2649declType(dtype = real)Var-list(dtyp

41、e = real)Var-list(dtype = real)id(x)(dtype = real)id(y)(dtype = real)float,Note that there is no equation involving the dtype of the nonterminal decl. It is not necessary for the value of an attribute to be specified for all grammar symbols Parse tree for the string float x,y showing the dtype attri

42、bute as specified by the attribute grammar above is as follows:Attribute grammars may involve several interdependent attributes.Fig. 6.32022-4-2650Example 6.4 consider the following grammar, where numbers may be octal or decimal, suppose this is indicated by a one-character suffix o(for octal) or d(

43、for decimal):based-num num basecharbasechar o|dnum num digit | digitdigit 0|1|2|3|4|5|6|7|8|9In this case num and digit require a new attribute base, which is used to compute the val attribute. The attribute grammar for base and val is given as follows.2022-4-2651Table 6.4Grammar Rulebased-numnum ba

44、secharbasechar obasechar dnum1 num2 digitnum1 digitdigit 0digit 1 digit 7 digit 8digit 9Semantic Rulesbased-num.val = num.valnum.base = basechar.basebasechar.base = 8basechar.base = 10num1.val =if digit.val = error or num2.val = errorthen errorelse num2.val*num1.base+digit.valnum2.base = num1.basedi

45、git.base = num1.basenum.val = digit.valdigit.base = num.basedigit.val = 0digit.val = 1 digit.val = 7digit.val = if digit.base = 8 then error else 8digit.val = if digit.base = 8 then error else 92022-4-2652num(val = 3)(base = 8)digit(val = 3)(base = 8)3based-num(val = 229)num(val = 28*8+5=229)(base =

46、 8)basechar(base = 8)num (val = 3*8+4=28)(base=8)digit(val = 4)(base = 8)o4digit(val = 5)(base = 8)5Fig. 6.42022-4-26536.1.2 Simplifications and Extensions to Attribute GrammarsnThe collection of expressions allowable in an attribute equation is called metalanguage for the attribute grammar. qSuch a

47、s: if-then-else expression in example 6.4nUsually we use a metalanguage that is limited to arithmetic, logical, and a few other kinds of expression:qif-then-elseqswitch, case2022-4-2654nA further simplification that can be useful in specifying attribute grammars is to use an ambiguous, but simpler,

48、form of the original grammar.exp exp+exp| exp-exp| exp*exp| (exp)| numbernumberGrammar RuleSemantic Rulesexp1 exp2 + exp3 exp1.val=exp2.val+exp3.valexp1 exp2 - exp3 exp1.val=exp2.val-exp3.valexp1 exp2 * exp3 term1.val=term2.val*factor.val exp1 (exp2)factor.val=exp.val exp1 numbernumberfactor.val=num

49、bernumber.valTable 6.5 (compare this with Table 6.2)2022-4-2655nA simplification can also be made in displaying attribute values by using an abstract syntax tree instead of a parse tree.nAn abstract syntax tree must always have enough structure so that the semantic defined by an attribute grammar ca

50、n be expressed.* (val = 31*42=1302)-(val = 34-3=31)42(val = 42)34(val = 34)3(val = 3)Fig 6.52022-4-2656Example 6.5 Given the grammar for the simple integer arithmetic expression of Example 6.2, we can define an abstract syntax tree for expressions by the attribute grammar given in Table 6.6.Grammar

51、RuleSemantic Rulesexp1exp2+termexp1.tree = mkOpNode(+, exp2.tree, term.tree)exp1exp2-term exp1.tree = mkOpNode( -, exp2.tree, term.tree)exp1 termexp1.tree= term.treeterm1term2*factorterm1.tree = mkOpNode( *, term2.tree, factor.tree)termfactorterm.tree=factor.treefactor(exp)factor.tree=exp.treefactor

52、numberfactor.tree=mkNumNode(number.lexval)Table 6.62022-4-26576.2 Algorithm for Attribute Computation2022-4-26586.2.1 Dependency graphs and evaluation order2022-4-2659nDependency graph of the string: The union of the dependency graphs of the grammar rule choices representing each node (nonleaf) of t

53、he parse tree of the stringqXi.aj = fij(, Xm.ak, )qAn edge from each node Xm.ak to Xi.aj the node expressing the dependency of Xi.aj on Xm.ak.Xm.akXi.aj2022-4-2660Example 6.6 Consider the grammar of Example 6.1, with the attribute grammar as given in tab 6.1. for each symbol there is only one node i

54、n each dependency graph, corresponding to its val attributeGrammar rule attribute equationnumber1number2.digit number1.val = number2.val * 10 +digit.val num1.valnum2.valdigit.valThe dependency graph for this grammar rule choice is:2022-4-2661The subscripts for repeated symbols will be omittednumberd

55、igit number.val = digit.val The string 345 has the following dependency graph.num1.valdigit.valnum.valnumber.valdigit.valnumber.valdigit.valdigit.val2022-4-2662Example 6.7 consider the grammar of example 6.3var-list1 id, varlist2has two associated attribut equationsid.dtype = var-list1.dtypevar-list

56、2.dtype = var-list1.dtypeand the dependency graphsimilarly var-listid respond tovar-list.dtypeid.dtypevar-list.dtypevar-list.dtypeid.type2022-4-2663decltype varlistIt can also be drawn as:So, the first graph in this example can be drawn as :decltype dtypedtype var-listdtypedtypedtypevar-listidvar-li

57、st,type.dtypevar-list.dtype 2022-4-2664Finally, the dependency graph for the string float x, y isdtypeid(x)var-list,id(y)dtypedecltypefloatvar-listdtypedtypedtypeFig. 6.92022-4-2665For string 345o, the corresponding dependency graph is as follows:2022-4-2666nSuppose now that we wish to determine an

58、algorithm that computers the attributes of an attribute grammar using the attribute equations as computation rules.nIndeed, any algorithm must compute the attribute at each node in the dependency graph before it attempts to compute any successor attributes.qA traversal order of the dependency graph

59、that obeys this restriction is called a topological sortqand a well-known necessary and sufficient condition for a topological sort to exist is that the graph must be acyclic. qSuch graphs are called directed acyclic graphs, or DAGs.2022-4-2667Example 6.9 The dependency of Fig 6.6 is a DAG, which gi

60、ves as follows:Fig 6.7Another topological sort is given by the order12 6 9 1 2 11 3 8 4 5 7 10 13 14Base(4)Base(5)Val(14) Val(13)Val(10)Val(7)Val(6)Val(12)Val(9)Base(2)Base(3)Base(8)Base(1)Base(11)2022-4-2668Another topological sort is given by the order 12 6 9 1 2 11 3 8 4 5 7 10 13 14num(val = 3)(