一个简单的语法制导翻译器课件

单击编辑母版标题样式,#,/34,第,3,4,次课 一个简单的语法制导翻译器,2.32.5,中缀表达式转后缀表达式,本次课主要内容都是基于如何将中缀表达式转换为后缀表达式,9 5+2-95-2+,2.3,语法制导翻译的定义,第二章 一个简单的语法制导翻译器,语法制导翻译：对语法树进行,语义分析,例如：将中缀表达式转化成为后缀,9 -5 +2 9 5 2+,？,list,list,list,digit,9,digit,digit,-,5,+,2,第二章 一个简单的语法制导翻译器,语法制导翻译：对语法树进行,语义分析,语法制导定义,语法制导翻译方案,第二章 一个简单的语法制导翻译器,语法制导翻译,语法制导定义,(syntax-directed definition),每个文法符号和一个属性集合相关联,例树中,”.t”,是属性,每个产生式和一组语义规则相关联,expr.t,=95-2+,expr.t,=95-,expr.t,=9,term.t,=9,9,term.t,=5,5,-,+,term.t,=2,2,产生式,语义规则,expr,expr,1,+,term,expr.t,=,expr,1,.t,|,term.t,|+,expr,expr,1,-,term,expr.t,=,expr,1,.t,|,term.t,|-,expr,term,expr.t,=,term.t,term,0,term.t,=0,term,1,term.t,=1,term,9,term.t,=9,例子：,9-5+2,第二章 一个简单的语法制导翻译器,语法制导翻译,属性,综合属性,如果某个属性在语法分析树节点,N,上的值由,N,的子节点和,N,本身的属性值确定，则该属性为综合属性,继承属性,如果某个属性由语法分析树中该节点本身、父节点以及兄弟节点上的属性值决定，则该属性为继承属性,第二章 一个简单的语法制导翻译器,后缀表达式（,postfix notation,）：,E,如何,E,是一个变量或常量，则,E,的后缀是本身,如果,E,是一个形如,E,1,op,E,2,的表达式，,op,是二目运算符，那么,E,的后缀表示是：,E,1,E,2,op,，这里,E,1,和,E,2,分别是,E,1,和,E,2,的后缀表示,如果,E,是一个形如（,E,1,）的表达式，则,E,的后缀表示就是,E,1,的后缀表示,第二章 一个简单的语法制导翻译器,语法制导翻译,语法制导定义,(syntax-directed definition),每个文法符号和一个属性集合相关联,例树中,”.t”,是属性,每个产生式和一组语义规则相关联,expr.t,=95-2+,expr.t,=95-,expr.t,=9,term.t,=9,9,term.t,=5,5,-,+,term.t,=2,2,产生式,语义规则,expr,expr,1,+,term,expr.t,=,expr,1,.t,|,term.t,|+,expr,expr,1,-,term,expr.t,=,expr,1,.t,|,term.t,|-,expr,term,expr.t,=,term.t,term,0,term.t,=0,term,1,term.t,=1,term,9,term.t,=9,后缀表达式,第二章 一个简单的语法制导翻译器,语法制导翻译,语法制导定义,(syntax-directed definition),每个文法符号和一个属性集合相关联,例树中,”.t”,是属性,每个产生式和一组语义规则相关联,expr.t,=95-2+,expr.t,=95-,expr.t,=9,term.t,=9,9,term.t,=5,5,-,+,term.t,=2,2,产生式,语义规则,expr,expr,1,+,term,expr.t,=,expr,1,.t,|,term.t,|+,expr,expr,1,-,term,expr.t,=,expr,1,.t,|,term.t,|-,expr,term,expr.t,=,term.t,term,0,term.t,=0,term,1,term.t,=1,term,9,term.t,=9,简单语法制导定义,第二章 一个简单的语法制导翻译器,语法制导翻译,语法制导定义,(syntax-directed definition),深度优先遍历,procedure,visit,(node,N,),for(,从左到右遍历,N,的每个子节点,C,),visit,(,C,);,按照节点,N,上的语义规则求值,;,expr.t,=95-2+,expr.t,=95-,expr.t,=9,term.t,=9,9,term.t,=5,5,-,+,term.t,=2,2,产生式,语义规则,expr,expr,1,+,term,expr.t,=,expr,1,.t,|,term.t,|+,expr,expr,1,-,term,expr.t,=,expr,1,.t,|,term.t,|-,expr,term,expr.t,=,term.t,term,0,term.t,=0,term,1,term.t,=1,term,9,term.t,=9,第二章 一个简单的语法制导翻译器,语法制导翻译：对语法树进行语义分析,语法制导定义,语法制导翻译方案,将程序片段附加到一个文法的各个产生式上的表示法,rest,+,term,print(+),rest,1,第二章 一个简单的语法制导翻译器,语法制导翻译：对语法树进行,语义分析,语法制导定义,语法制导翻译方案,将程序片段附加到一个文法的各个产生式上的表示法,被嵌入到产生式体中的程序片段成为语义动作（,semantic action,）。语义动作用花括号括起来。,rest,+,term,print(+),rest,1,rest,+,term,print(+),rest,1,第二章 一个简单的语法制导翻译器,语法制导翻译：对语法树进行,语义分析,语法制导定义,语法制导翻译方案,将程序片段附加到一个文法的各个产生式上的表示法,如何,E,是一个变量或常量，则,E,的后缀是本身,如果,E,是一个形如,E,1,op,E,2,的表达式，,op,是二目运算符，那么,E,的后缀表示是：,E,1,E,2,op,，这里,E,1,和,E,2,分别是,E,1,和,E,2,的后缀表示,如果,E,是一个形如（,E,1,）的表达式，则,E,的后缀表示就是,E1,的后缀表示,(9 5)+2 9 5 2 +,?,9 5 2 +-3,*,第二章 一个简单的语法制导翻译器,语法制导翻译：对语法树进行,语义分析,语法制导定义,语法制导,翻译方案,expr,expr,+,term,print(+),expr,-,term,print(-),term,9,print(9),5,print(5),2,print(2),翻译方案,expr,expr,1,+,term,print(+),expr,expr,1,term,print(-),expr,term,term,0,print(0),term,1,print(1),term,9,print(9),总结,语法制导的定义,后缀表达式,语法制导的翻译方案,2.4,语法分析,第二章 一个简单的语法制导翻译器,语法分析,决定如何使用一个文法生成一个终结符号串的过程,给定输入：,终结符号串：,9,5,+,2,文法：,list,list,+,digit,list,list,-,digit,list,digit,digit,0|1|2|3|4|5|6|7|8|9,输出：？,第二章 一个简单的语法制导翻译器,语法分析,决定如何使用一个文法生成一个终结符号串的过程,给定输入：,终结符号串：,9,5,+,2,文法：,list,list,+,digit,list,list,-,digit,list,digit,digit,0|1|2|3|4|5|6|7|8|9,输出：？,list,list,list,digit,9,digit,digit,-,5,+,2,第二章 一个简单的语法制导翻译器,语法分析,决定如何使用一个文法生成一个终结符号串的过程,上下文无关文法,通常,Parsing,的时间复杂度是,O,(,n,3,),对于程序设计语言，时间复杂度是,O,(,n,),自顶向下方法,自底向上方法,第二章 一个简单的语法制导翻译器,语法分析,自顶向下分析方法,例：给定文法：,stmt,expr,|,if,(,expr,),stmt,|,for,(,optexpr,;,optexpr,;,optexpr,),stmt,|,other,optexpr,|,expr,第二章 一个简单的语法制导翻译器,语法分析,自顶向下分析方法,stmt,expr,|,if,(,expr,),stmt,|,for,(,optexpr,;,optexpr,;,optexpr,),stmt,|,other,optexpr,|,expr,输入是：,for(;expr;expr)other,第二章 一个简单的语法制导翻译器,语法分析,自顶向下分析方法,stmt,expr,;,|,if,(,expr,),stmt,|,for,(,optexpr,;,optexpr,;,optexpr,),stmt,|,other,optexpr,|,expr,输入是：,for(;expr;expr)other,stmt,for,(,optexpr,;,optexpr,;,optexpr,),stmt,expr,expr,other,语法,分析树,stmt,输入,for,(,;,exp,r,;,exp,r,),other,语法,分析树,stmt,输入,for,(,;,exp,r,;,exp,r,),other,stmt,for,(,optexpr,;,optexpr,;,optexpr,),stmt,语法,分析树,输入,for,(,;,exp,r,;,exp,r,),other,stmt,语法,分析树,stmt,输入,for,(,;,exp,r,;,exp,r,),other,stmt,for,(,optexpr,;,optexpr,;,optexpr,),stmt,语法,分析树,输入,for,(,;,exp,r,;,exp,r,),other,stmt,for,(,optexpr,;,optexpr,;,optexpr,),stmt,语法,分析树,输入,for,(,;,exp,r,;,exp,r,),other,第二章 一个简单的语法制导翻译器,语法分析,自顶向下分析方法,一般来说，为一个非终结符号选择产生式是一个“尝试并犯错”的过程,回溯,预测语法分析法：不需要回溯,要求设计的文法满足：当考虑到一个输入符号（终结符）的时候，只有一种非终结符可以生成这个输入符号，是确定性的。,FIRST,集合,令,是一个文法符号（终结符号或非终结符号）串，,FIRST(),是由,生成的一个或多个终结符号串的第一个符号的集合。,如果,是,或者可以生成,，那么,也在,FIRST(),中,第二章 一个简单的语法制导翻译器,语法分析,自顶向下分析方法,一般来说，为一个非终结符号选择产生式是一个“尝试并犯错”的过程,回溯,预测语法分析法：不需要回溯,要求设计的文法满足：当考虑到一个输入符号（终结符）的时候，只有一种非终结符可以生成这个输入符号，是确定性的。,有两个产生式,A ,和,A,，预测分析法要求,FIRST(),和,FIRST(),不相交,如果输入符号在,FIRST(),中，就用,A ,，如果输入符号在,FIRST(),中，就用,A ,第二章 一个简单的语法制导翻译器,语法分析,自顶向下分析方法,预测分析法,stmt,expr ;,|,if,(,expr,),stmt,|,for,(,optexpr,;,optexpr,;,optexpr,),stmt,|,other,optexpr,|,expr,FIRST(,stmt,)=,expr,if,for,other,FIR