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

《(5.2.1)--4.2.1Bottom-UpParsingofS-Attribu.pdf》由会员分享，可在线阅读，更多相关《(5.2.1)--4.2.1Bottom-UpParsingofS-Attribu.pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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

2、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)

3、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:o

4、perators 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 o

5、perator 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 i

6、s 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(i

7、d,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

8、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 sy

9、ntax 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

10、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 tablePoin

11、ts 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

12、 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|nu

13、mE.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

14、.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*

15、+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 Attribut

16、e 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

17、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 nptrEstab

18、lishing 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