《(8.1)--Samuel's Ch6_1编译原理与实践英文版.ppt》由会员分享，可在线阅读，更多相关《(8.1)--Samuel's Ch6_1编译原理与实践英文版.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 6Semantic AnalysisAttributesCompilerS2Translation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode GeneratorTarget Code OptimizerSource CodeTokensLiteral TableSymbol TableError Handler2CompilerS3Translation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode Generato
2、rTarget Code OptimizerSource CodeTokensSyntax TreeLiteral TableSymbol TableError Handler3CompilerS4Translation ProcessScannerParserSemantic AnalyzerSource Code OptimizerCode GeneratorTarget Code OptimizerSource CodeTokensSyntax TreeAnnotated TreeLiteral TableSymbol TableError Handler4CompilerS5Attri
3、butesoAttribute is any property of a programming language construct.oAttributes can vary widely in the information they contain,their complexity,and the time during the translation/execution process when they can be determined.oExamples of attributes:nThe data type of a variablenThe value of an expr
4、essionnThe location of a variable in memorynThe object code of a procedurenThe number of significant digits in a numberCompilerS6BindingoThe process of computing an attribute and associating its computed value with the language construct is referred to as the binding of the attribute.oThe time durin
5、g the compilation/execution process when the binding occur is called its binding time.oAttributes that can be bound prior to execution are called static.oAttributes that can only be bound during execution are dynamic.CompilerS7Attribute GrammarsoIn syntax-directed semantics,attributes are associated
6、 directly with the grammar symbols of the language.oIf X is a grammar symbol,and a is an attribute associated to X,then we write X.a for the value of a associated to X.oFor each grammar rule X0X1 X2Xn,the values of attributes Xi.aj of each grammar symbol Xi are related.oAttribute equation or semanti
7、c rule:Xi.aj=fij(X0.a1,X0.ak,X1.a1,X1.ak,Xn.a1,Xn.ak)oAttribute grammar for the attributes a1,a2,ak is the collection of such equations for all grammar rules of the language.CompilerS8Example 6.1number number digit|digitdigit 0|1|2|3|4|5|6|7|8|9 The most significant attribute of a number is its valu
8、e.Each digit has a value computable from the digit it represents.digit 0 implies that digit has value 0 digit.val=0 If a number is derived using the rule number digit,then number.val=digit.val If a number contains more digits number number digit,then number1.val=number2.val*10+digit.valnumber1 numbe
9、r2 digitCompilerS9Example 6.2exp exp+term|exp term|termterm term*factor|factorfactor (exp)|number factor.val=number.val factor number factor.val=exp.val factor (exp)term.val=factor.val term factor term1.val=term2.val*factor.val term1 term2*factor exp.val=term.val exp term exp1.val=exp2.val -term.val
10、 exp1 exp2 term exp1.val=exp2.val +term.val exp1 exp2+termSemantic RulesGrammar RuleCompilerS10Example 6.3decl type var-listtype int|floatvar-list id,var-list|id id.type=var-list.dtype var-list id id.type=var-list1.dtype var-list2.dtype=var-list1.dtype var-list1 id,var-list2 type.dtype=float type fl
11、oat type.dtype=integer type int var-list.dtype=type.dtype decl type var-listSemantic RulesGrammar RuleCompilerS11Dependency GraphoGiven an attribute grammar,each grammar rule choice has an associated dependency graph.oThe graph has a node labeled by each attribute of each symbol in the grammar rule.
12、oFor each attribute equation Xi.aj=fij(Xm.ak)there is an edge from each node Xm.ak to the node Xi.ajCompilerS12Dependency Graph(cont)oGiven a legal string in the language,the dependency graph of the string is the union of the dependency graphs of the grammar rule choices representing each(nonleaf)no
13、de of the parse tree of the string.CompilerS13Example 6.6number number digit|digitdigit 0|1|2|3|4|5|6|7|8|9number1.val=number2.val*10+digit.valnumber1.valnumber2.valdigit.valnumber.val=digit.valnumber.valdigit.valCompilerS14Example 6.6(cont)String:3 4 5number.valnumber.valnumber.valdigit.valdigit.va
14、ldigit.valnumber number digit|digitdigit 0|1|2|3|4|5|6|7|8|9(val=3)(val=4)(val=5)CompilerS15Example 6.7var-list1 id,var-list2has two associated attribute equations id.dtype=var-list1.dtype var-list2.dtype=var-list1.dtypeand the dependency graph var-list1.dtype id.dtype var-list2.dtype CompilerS16Exa
15、mple 6.7(cont)oThe grammar rule var-list id has the attribute equation id.dtype=var-list.dtype and the dependency graph var-list.dtype id.dtypeoThe rule decl type var-list with the equation var-list.dtype=type.dtype has the dependency graph type.dtype var-list.dtype CompilerS17Example 6.7(cont)odecl
16、 is not directly involved in the dependency graph.We often draw the dependency graph superposed over a parse tree segment corresponding to the grammar rule.oThis makes clearer the grammar rule to which the dependency is associated decltype.dtype var-list.dtype CompilerS18Example 6.7(cont)oWe suppres
17、s the dot notation and write the attributes next to associated node.var-list1.dtype id.dtype var-list2.dtype var-list id ,var-listdtypedtypedtypevar-list1 id,var-list2CompilerS19Example 6.7(cont)String:float x,ydecltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtypeCompilerS20Order Constra
18、insoGiven a particular string of tokens to be translated,the dependency graph of the parse tree of the string gives a set of order constrains under which the algorithm must operate to compute the attributes for the string.oAny algorithm must compute the attribute at each node in the dependency graph
19、 before it attempts to compute any successor attributes.oThe traversal order of the graph that obeys this restriction is called topological sort.oA necessary and sufficient condition for a topological sort to exist is that the graph must be acyclic(DAG).CompilerS21RootoA root of the graph is node th
20、at has no predecessors.oAttribute values in such nodes do not depend on any other attribute.decltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtypeCompilerS22Synthesized AttributesoAn attribute is synthesized if all its dependencies point from child to parent in the parse tree.oEquivalentl
21、y,an attribute a is synthesized if,given a grammar rule A X1 X2,Xn the only associated attribute equation with an a on the left-hand side is of the form A.a=f(X1.a1,X1.ak,Xn.a1,Xn.ak)oAn attribute grammar in which all the attributes are synthesized is called an S-attributed grammar.CompilerS23Attrib
22、ute Values of S-Attributed GrammaroGiven a parse tree or a syntax tree constructed by a parser,the attribute values of S-attributed grammar can be computed by a single bottom-up,or postorder,traversal of the tree.procedure PostEval(T:treenode);for each child C of T do PostEval(C);compute all synthes
23、ized attributes of TCompilerS24Examplenumber1.valnumber2.valdigit.valnumber.valdigit.valCompilerS25Inherited AttributeoAn attribute that is not synthesized is called an inherited attribute.oExample:decltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtypeCompilerS26Inherited Attribute(cont)o
24、Dependencies flow either from parent to children or from sibling to sibling.oInherited attributes can be computed by a preorder traversal,or combined preorder/inorder traversal of the syntax tree.a Aa Ba Ca Aa Ba Cprocedure PreEval(T:treenode);for each child C of T do compute all inherited attribute
25、s of C PreEval(C);CompilerS27Example 6.12decl type var-listtype int|floatvar-list id,var-list|iddecltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtype12345CompilerS28Attribute Computation and SyntaxoProperties of attributes depend on the structure of the grammar.oModifications to the gram
26、mar that do not change the legal strings of the language can make the computation of attributes simpler or more complex.Theorem:Given an attribute grammar,all inherited attributes can be changed into synthesized attributes by suitable modification of the grammar,without changing the language of the
27、grammar.KnuthCompilerS29Example 6.18decl type var-listtype int|floatvar-list id,var-list|idGrammar RuleSemantic Rules decl type var-list var-list.dtype=type.dtype type int type.dtype=integer type float type.dtype=float var-list1 id,var-list2 id.dtype=var-list1.dtype var-list2.dtype=var-list1.dtype v
28、ar-list1 id id.dtype=var-list1.dtypedtype attribute is inherited.CompilerS30Example 6.7(cont)String:float x,ydecltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtypedtype attribute is inherited.CompilerS31Example 6.18(cont)decl type var-listtype int|floatvar-list id,var-list|iddecl var-list
29、 idvar-list var-list id,|typetype int|floatGrammar RuleSemantic Rules decl var-list id id.dtype=var-list.dtype var-list1 var-list2 id,var-list1.dtype=var-list2.dtype id.dtype=var-list1.dtype var-list type var-list.dtype=type.dtype type int type.dtype=integer type float type.dtype=floatCompilerS32Exa
30、mple 6.18(cont)float x,ydeclvar-list dtype=realid dtype=real(y)var-list dtype=realid dtype=real(x),type dtype=realfloat The two dependencies that are drawn as dashed lines appear to be inherited attributes.These dependencies are always to the leaves(not recursive)and not viewed as inherited.CompilerS33Homework o6.1,6.2,6.4,6.7,6.11,6.12