抽象语法树.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,抽象语法树,语法分析树,S,S,+,E,(,S ),S +E,1,5,E,S +E,4,句子：,1+(2+(3+4)+5,文法：,S,E|S+E,E (S)|Number,S +E,E,2,(,S ),E,3,语法分析树,S,S,+,E,(,S ),S +E,1,5,E,S +E,4,为了表达这个表达式，是否真的需要如此复杂的树结构？,S +E,E,2,(,S ),E,3,抽象语法树(,ASTs,),+,+,5,1,+,2,+,3,4,S,S,+,E,5,S +E,1,(,S ),S +E,E,4,S +E,2,E,(,S ),3,E,为了表达这个表达式，是否真的需要如此复杂的树结构？,NO!,只需要使用,Abstract Syntax Trees,来替代.,如何来构建,AST？,构建抽象语法树的最佳途径是伴随句子的语法分析过程；,为每个“重要的”产生式规则构建内部的树结点，使用指针指向其叶子结点规则。,需要能够掠过那些不重要的规则（例如一个直接的转换）或者以后的分析中不要的部分（括号；变量声名等）,AST,的结构,AST,的叶子结点是什么？,变量,variable,数字,number,等,一般来说：,一个文法规则，如果右侧产生式仅仅含有终结符，其将会成为,AST,的叶子结点。,这些规则将会首先进行归约。,抽象语法树,画这颗语法分析树,1+2*(3+4)+5,S,E|S+E,E,T|E*T,T (S)|Number,S,S,+,E,S +E,1,5,E,S +E,T,E *T,T,2,(,S ),E,T,T,T,3,4,抽象语法树,画这颗语法树,1+2*(3+4)+5,S,E|S+E,E,T|E*T,T (S)|Number,在,AST,中，哪些规则应该被表示出来？,S,S,+,E,S +E,1,5,E,S +E,T,E *T,T,2,(,S ),E,T,T,T,3,4,抽象语法树,1+2*(3+4)+5,S,E|S+E,E,T|E*T,T (S)|,Number,只有,Nnumber,应该被看作一个叶子结点。,S,S,+,E,S +E,1,5,E,S +E,T,E *T,T,2,(,S ),E,T,T,T,3,4,抽象语法树,1+2*(3+4)+5,S,E|S+E,E,T|E*T,T (S)|,Number,只有,Nnumber,应该被看作一个叶子结点。,S,S,+,E,S +E,1,5,E,S +E,T,E *T,T,2,(,S ),E,T,T,T,3,4,抽象语法树,1+2*(3+4)+5,S,E|S+E,E,T|E*T,T (S)|,Number,不重要的运算符在,AST,中不出现。,S,S,+,E,S +E,1,5,E,S +E,T,E *T,T,2,(,S ),E,T,T,T,3,4,抽象语法树,1+2*(3+4)+5,S,E,|S+E,E,T,|E*T,T,(S),|,Number,不重要的运算符在,AST,中不出现。,S,S,+,E,S +E,1,5,E,S +E,T,E *T,T,2,(,S ),E,T,T,T,3,4,抽象语法树,1+2*(3+4)+5,S,E,|S+E,E,T,|E*T,T,(S),|,Number,不重要的运算符在,AST,中不出现。,.,S,S,+,E,S +E,1,5,E,S +E,T,E *T,T,2,(,S ),E,T,T,T,3,4,抽象语法树,1+2*(3+4)+5,S,E,|S+E,E,T,|E*T,T,(S),|,Number,从,AST,中可以移除这些内容，直接从子树连接到父亲结点。,S,S,+,E,S +E,1,5,E,S +E,T,E *T,T,2,(,S ),E,T,T,T,3,4,抽象语法树,Draw the tree for:,1+2*(3+4)+5,S,E,|S+E,E,T,|E*T,T,(S),|,Number,从,AST,中可以移除这些内容，直接从子树连接到父亲结点。,S,S,+,E,S +E,1,5,S +E,E *T,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|S+E,E,T,|E*T,T,(S),|,Number,产生式右部具有几个算符的规则可以归约为一个非终结符，使用一个结点表示。,S,S,+,E,S +E,1,5,S +E,E *T,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,产生式右部具有几个算符的规则可以归约为一个非终结符，使用一个结点表示。,S,S,+,E,S +E,1,5,S +E,E *T,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,S,S,+,E,S +E,1,5,S +E,E *T,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,S,S,+,E,1,5,S +E,E *,+,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,S,S,+,E,1,5,S +E,E *,+,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,S,S,+,E,1,5,S +,*,+,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,S,S,+,E,1,5,S +,*,+,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,S,+,+,E,1,5,*,+,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,S,+,+,E,1,5,*,+,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,+,+,1,5,*,+,2,3,4,抽象语法树,1+2*(3+4)+5,S,E,|,S+E,E,T,|,E*T,T,(S),|,Number,DONE!,+,+,1,5,*,+,2,3,4,从抽象语法树如何进行翻译,LocationEx,id=x,AddExpr,left,right,ValueExpr,val,=42,visit,visit(left),visit(right),TR,x+42,T,A,Load_,Mem,x,R1,Load_Const 42,R2,Add_,Reg,R2,R1,Load_,Mem,x,R1,Load_Const 42,R2,Add_,Reg,R2,R1,T=R1,A=R2,Rn,T=R1,A=R2,Rn,T=R2,A=R3,Rn,