编译原理编译原理编译原理 (41).ppt

CompilerS1Dependency GraphGiven an attribute grammar,each grammar rule choice has an associated dependency graph.The graph has a node labeled by each attribute of each symbol in the grammar rule.For each attribute equation Xi.aj=fij(Xm.ak)there is an edge from each node Xm.ak to the node Xi.ajCompilerS2Dependency Graph(cont)Given 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)node of the parse tree of the string.CompilerS3Example 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.valCompilerS4Example 6.6(cont)String:3 4 5number.valnumber.valnumber.valdigit.valdigit.valdigit.valnumber number digit|digitdigit 0|1|2|3|4|5|6|7|8|9(val=3)(val=4)(val=5)CompilerS5Example 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 CompilerS6Example 6.7(cont)The grammar rule var-list id has the attribute equation id.dtype=var-list.dtype and the dependency graph var-list.dtype id.dtypeThe rule decl type var-list with the equation var-list.dtype=type.dtype has the dependency graph type.dtype var-list.dtype CompilerS7Example 6.7(cont)decl 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.This makes clearer the grammar rule to which the dependency is associated decltype.dtype var-list.dtype CompilerS8Example 6.7(cont)We suppress 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-list2CompilerS9Example 6.7(cont)String:float x,ydecltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtypeCompilerS10Order ConstrainsGiven 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.Any algorithm must compute the attribute at each node in the dependency graph before it attempts to compute any successor attributes.The traversal order of the graph that obeys this restriction is called topological sort.A necessary and sufficient condition for a topological sort to exist is that the graph must be acyclic(DAG).CompilerS11RootA root of the graph is node that has no predecessors.Attribute values in such nodes do not depend on any other attribute.decltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtype。