抽象语法树.ppt

1、抽象语法树,语法分析树,S,句子： 1 + (2 + (3 + 4) + 5 文法： S E | S + E E (S) | Number,语法分析树,S,为了表达这个表达式，是否真的需要如此复杂的树结构？,抽象语法树 (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？,构建抽象语法树的最佳途径是伴随句子的语法分析过程； 为每个“重要的”产生式规

2、则构建内部的树结点，使用指针指向其叶子结点规则。 需要能够掠过那些不重要的规则（例如一个直接的转换）或者以后的分析中不要的部分（括号；变量声名等）,AST的结构,AST的叶子结点是什么？ 变量variable 数字 number 等 一般来说： 一个文法规则，如果右侧产生式仅仅含有终结符，其将会成为AST的叶子结点。 这些规则将会首先进行归约。,抽象语法树,画这颗语法分析树 1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number,抽象语法树,画这颗语法树 1 + 2 * (3 + 4) + 5 S E | S + E E T | E

3、 * T T (S) | Number 在AST中，哪些规则应该被表示出来？,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number 只有Nnumber应该被看作一个叶子结点。,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number 只有Nnumber应该被看作一个叶子结点。,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number 不重要的运算符在AST中不出现。,抽象语法树

4、,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number 不重要的运算符在AST中不出现。,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number 不重要的运算符在AST中不出现。.,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number 从AST中可以移除这些内容，直接从子树连接到父亲结点。,抽象语法树,Draw the tree for: 1 + 2 * (3 + 4) + 5 S

5、E | S + E E T | E * T T (S) | Number 从AST中可以移除这些内容，直接从子树连接到父亲结点。,S,S + E,1,5,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number 产生式右部具有几个算符的规则可以归约为一个非终结符，使用一个结点表示。,S,S + E,1,5,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number 产生式右部具有几个算符的规则可以归约为一个非终结符，使用一个结点表

6、示。,S,S + E,1,5,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number,S,S + E,1,5,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number,S,1,5,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number,S,1,5,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T

7、| E * T T (S) | Number,S,1,5,+,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number,S,1,5,+,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number,S,1,5,*,+,2,3,4,抽象语法树,1 + 2 * (3 + 4) + 5 S E | S + E E T | E * T T (S) | Number,S,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,从抽象语法树如何进行翻译,visit,visit(left),visit(right),TRx + 42,T,A,Load_Mem x, R