(5.2.1)--4.2.1Bottom-UpParsingofS-Attribu.pdf

Compilers TechniquesSyntax-DirectedTranslationAttributes understandingNon-terminal analysis procedures(functions)synthesized attributesThe return value of the procedureInherited attributesparameters of the procedureDeepen UnderstandingAttribute understandinge.g.int id,id,idProductionSemantic rulesD TLL.in:=T.typeT intT.type:=integerT realT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lid addtype(id.entry,L.in)ImproveReviewAttribute understandingvoid D()T_temp=T();L_in=T_temp;L(L_in);return;int T()switch lookahead case INT:return INTEGER;case REAL:return REAL;default:error;void L(int L_in)L(L_in);match(,);match(id);addtype(id.entry,L_in);Void L(int L_in)match(id);addtype(id.entry,L.in);ProductionSemantic rulesD TLL.in:=T.typeT intT.type:=integerT realT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lid addtype(id.entry,L.in)Syntax tree is a condensed representation of parse tree:operators and keywords are used as internal nodes Syntax-directed translation can based on parse trees or syntax tree.Examples of syntax trees：Syntax TreeS if B then S1 else S2if-then-elseBS1S2Syntax treeSBS1S2ifthenelseSyntax treeBottom-up Computation of Attribute Definitionmknode(op,left,right)An operator node is established,the label is op,and the two fields left and rightpoint to the left subtree and the right subtree respectively.mkleaf(id,entry)mkleaf(num,val)Establish an identifier node,labeled id,and a domain entry points to the entry of the identifier in the symbol table.A digit node is established,labeled num,and a field val is used to store the valueof the number.Create Syntax Trees for Operator ExpressionsProductionSemantic rulesE E1+TE.nptr:=mknode(+,E1.nptr,T.nptr)E TE.nptr:=T.nptrT T1*FT.nptr:=mknode(*,T1.nptr,F.nptr)T FT.nptr:=F.nptrF (E)F.nptr:=E.nptrF id F.nptr:=mkleaf(id,id.entry)F num F.nptr:=mkleaf(num,num.val)A Syntax-directed Definition Used to Construct Syntax TreesNote:It is also a production with semantic rules.Different semantic rules have different effects.For operator nodes,one domain holds the operator and serves as the marker of a node,while the other two domains hold pointers to the operand.The basic operand node,one field holds the operand class and the other field holds its value.(Also can save other attributes or pointers to the value of the attribute in other fields).A Syntax-directed Definition Used to Construct Syntax TreesConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionConstruct the syntax tree for a+5*b.Points to the entry of a in the symbol tablePoints to the entry of b in the symbol tableE E1+T|TT T1*F|FF (E)F id|numE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+Bottom-up Computation of Attribute DefinitionEstablishing Semantic Rules of Abstract Syntax TreeProductionSemantic RuleEE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptrT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val)To entry for aE nptrE-idnum4T nptrE nptr-+idTo entry for cT nptrididT nptrEstablishing Semantic Rules of Abstract Syntax Tree(1)p1:=mkleaf(id,entry a);(2)p2:=mkleaf(num,4);(3)p3:=mknode(-，p1,p2)(4)p4:=mkleaf(id,entry c)(5)p5:=mknode(+,p3,p4)p1,p2,.,p5 are pointers point to the nodesentry a and entry c are pointers to identifiers a and c in the symbol table,respectivelyidentry ato entry for ap1num 4p2-p3+p5identry cto entryfor cp4Construct the Syntax Tree of a-4+cCompilers TechniquesSyntax-DirectedTranslation