递归下降分析 (42).ppt

《递归下降分析 (42).ppt》由会员分享，可在线阅读，更多相关《递归下降分析 (42).ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、CompilerS1Synthesized AttributesAn attribute is synthesized if all its dependencies point from child to parent in the parse tree.Equivalently,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(X

2、1.a1,X1.ak,Xn.a1,Xn.ak)An attribute grammar in which all the attributes are synthesized is called an S-attributed grammar.CompilerS2Attribute Values of S-Attributed GrammarGiven a parse tree or a syntax tree constructed by a parser,the attribute values of S-attributed grammar can be computed by a si

3、ngle bottom-up,or postorder,traversal of the tree.procedure PostEval(T:treenode);for each child C of T do PostEval(C);compute all synthesized attributes of TCompilerS3Examplenumber1.valnumber2.valdigit.valnumber.valdigit.valCompilerS4Inherited AttributeAn attribute that is not synthesized is called

4、an inherited attribute.Example:decltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtypeCompilerS5Inherited Attribute(cont)Dependencies flow either from parent to children or from sibling to sibling.Inherited attributes can be computed by a preorder traversal,or combined preorder/inorder tra

5、versal of the syntax tree.a Aa Ba Ca Aa Ba Cprocedure PreEval(T:treenode);for each child C of T do compute all inherited attributes of C PreEval(C);CompilerS6Example 6.12decl type var-listtype int|floatvar-list id,var-list|iddecltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtype12345Compi

6、lerS7Attribute Computation and SyntaxProperties of attributes depend on the structure of the grammar.Modifications to the grammar 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 attri

7、butes can be changed into synthesized attributes by suitable modification of the grammar,without changing the language of the grammar.KnuthCompilerS8Example 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 typ

8、e.dtype=integer type float type.dtype=float var-list1 id,var-list2 id.dtype=var-list1.dtype var-list2.dtype=var-list1.dtype var-list1 id id.dtype=var-list1.dtypedtype attribute is inherited.CompilerS9Example 6.7(cont)String:float x,ydecltypevar-listid(x),var-listid(y)floatdtypedtypedtypedtypedtypedt

9、ype attribute is inherited.CompilerS10Example 6.18(cont)decl type var-listtype int|floatvar-list id,var-list|iddecl var-list 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=v

10、ar-list1.dtype var-list type var-list.dtype=type.dtype type int type.dtype=integer type float type.dtype=floatCompilerS11Example 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.