编译原理总复习chap8

1、第 1 页u没有标准的方法来说明语言的静态语义没有标准的方法来说明语言的静态语义u对于各种语言，静态语义分析的种类和总量的变对于各种语言，静态语义分析的种类和总量的变化范围很大。化范围很大。属性文法属性文法u确定语言实体的属性，写成属性等式进行计算，确定语言实体的属性，写成属性等式进行计算，并描述属性的计算如何与语言的文法规则相关。并描述属性的计算如何与语言的文法规则相关。u应用比较广的应用比较广的：语法制导翻译语法制导翻译u编译的语义分析编译的语义分析第 2 页静态语义分析的环境静态语义分析的环境符号表符号表第 3 页8.1 属性及属性文法属性及属性文法8.2 语法制导翻译概论语法制导翻译概

2、论8.3 中间代码的形式中间代码的形式第 4 页8.1 属性及属性文法属性及属性文法第 5 页定义定义 属性文法属性文法(Attribute Grammar) 既描述程序设计语言的语法既描述程序设计语言的语法, ,又描述语义。又描述语义。1968年由年由D.E.Knuth 提出提出第 6 页例例 关于表达式的文法关于表达式的文法 ：ET+T| T or T Tnum|true|false规定：规定：参加参加”运算的：运算的：int型；参加型；参加 “or”运算的运算的: bool型型写出写出表达式类型的属性文法表达式类型的属性文法P P156属性文法的思想：属性文法的思想：n对每个文法符号引进

3、相关的属性符号；对每个文法符号引进相关的属性符号；n对每个产生式写出属性值计算的规则。对每个产生式写出属性值计算的规则。第 7 页例例 8.1 简单算术表达式求值的属性文法。简单算术表达式求值的属性文法。值属性值属性val ：每个非终结符有一个。：每个非终结符有一个。数字数字digit的值：由词法分析程序提供。的值：由词法分析程序提供。P P156语语 义义 规规 则则 L E E E1+TE T T T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.v

4、alF.val:=E.valF.val:=digit.lexval产产 生生 式式打印打印E的值的值第 8 页属性分类属性分类第 9 页属性计算属性计算n将属性等式转化为计算规则。将属性等式转化为计算规则。n为赋值和属性分配寻找一个顺序为赋值和属性分配寻找一个顺序，确保每次计算时，确保每次计算时要使用的所有属性值都是有效的。要使用的所有属性值都是有效的。n属性等式属性等式本身指示了属性计算时的约束顺序本身指示了属性计算时的约束顺序A的综合属性的综合属性Xj的继承属性的继承属性 产生式左边的继承属性和右边的综合属性产生式左边的继承属性和右边的综合属性 不由该产生式计算，不由该产生式计算，由其它产

5、生式的属性规则计算由其它产生式的属性规则计算n相关依赖图相关依赖图 (associated dependency graph)。n描述分析树中的属性之间的相互依赖关系描述分析树中的属性之间的相互依赖关系n明确约束的顺序。明确约束的顺序。第 10 页 从祖先到子孙的继承从祖先到子孙的继承属性值经过父结点属性值经过父结点在兄弟中传递在兄弟中传递继承属性的相关依赖图继承属性的相关依赖图属性值直接沿着属性值直接沿着兄弟链传递兄弟链传递重叠在相应语法树中的相关图重叠在相应语法树中的相关图第 11 页属性计算方式属性计算方式第 12 页综合属性的计算综合属性的计算对语法树进行简单的对语法树进行简单的自底向

6、上自底向上或或后序遍历后序遍历。属性赋值程序属性赋值程序第 13 页例例 定义表达式值的属性文法定义表达式值的属性文法EE1+E2 E.val := E1.val +E2.valE(E1) E.val := E1.val En E.val := n.lexE.Val：综合属性综合属性句子句子2（31）带注释的语法树带注释的语法树第 14 页继承属性的计算继承属性的计算语法树的语法树的前序遍历前序遍历或或前序前序/中序遍历中序遍历的组合。的组合。属性赋值程序属性赋值程序计算的顺序计算的顺序在子孙的属性中继承属性可能有依赖关系。在子孙的属性中继承属性可能有依赖关系。T T的每个子孙的每个子孙C C

7、的访问顺序必须满足这些依赖的要求。的访问顺序必须满足这些依赖的要求。第 15 页产生式语 义 规 则D TL T int T real L L1,idL idL. in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)例例8.2 描述说明语句中变量的类型属性描述说明语句中变量的类型属性(type)的文法的文法in：继承属性：继承属性int id1,id2的语法树的语法树P P157把标志符的类型信息把标志符的类型信息记录在符号表中记录在符号表中DLTintid2

8、id1,Ltype：综合属性：综合属性第 16 页语法制导翻译语法制导翻译(syntax-directed semantics)n以属性文法为基础，以属性文法为基础，分析属性的依赖关系；分析属性的依赖关系； n遍历语法树，在各结点按语义规则进行计算遍历语法树，在各结点按语义规则进行计算。8.2 语法制导翻译概论语法制导翻译概论综合属性综合属性继承属性继承属性自底向上自底向上传递信息传递信息自顶向下（自左自顶向下（自左向右）向右）传递信息传递信息第 17 页S S属性文法的自下而上计算属性文法的自下而上计算第 18 页例例 8.1_2 算术表达式求值的属算术表达式求值的属性文法，性文法，对对2+

9、3*5进行语法制导翻译。进行语法制导翻译。P P174产产 生生 式式 语语 义义 规规 则则（0）L E Print(E.val)（1）E E1+T E.val:=E1.val+T.val（2）E T E.val:=T.val（3）T T1* F T.val:=T1.val F.val（4）T F T.val:=F.val（5）F (E) F.val:=E.val（6）F digit F.val:=digit.lexvalSLR(1)SLR(1)分析表见分析表见P142 表表7.8第 19 页 中间代码中间代码( Intermediate code/ representation/ lang

10、uage) 源程序的一种内部表示源程序的一种内部表示, 复杂性介于源语言和目复杂性介于源语言和目标机语言之间标机语言之间从语法树生成的更接近目标代码的中间表示形式，从语法树生成的更接近目标代码的中间表示形式，代表了语法树的某种线性化代表了语法树的某种线性化 ( linearization )形式，将语形式，将语法树用顺序形式表示。法树用顺序形式表示。8.3 中间代码的形式中间代码的形式第 20 页中间代码的形式中间代码的形式n逆波兰式、四元式、三元式、间接三元式、逆波兰式、四元式、三元式、间接三元式、树树P-机器机器( P - machine )的假想栈机器的代码。的假想栈机器的代码。Pasc

11、al编译器产生的标准目标汇编代码编译器产生的标准目标汇编代码PL/0伪代码伪代码第 21 页逆波兰表示逆波兰表示运算对象在前，运算符号在后。运算对象在前，运算符号在后。ab+abc*+a-b+ac*bd*+a+ba+b*c-a+b a*c+b*d特点特点1、运算对象出现的顺序和原有顺序（从左到右）相同、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值优点：简明、便于计值第 22 页三元式表示三元式表示(算符算符o

12、p，第一运算对象，第一运算对象arg1，第二运算对象，第二运算对象arg2)a:=a*c+b*d第 23 页四元式表示四元式表示(算符算符op，第一运算对象，第一运算对象arg1，第二运算对象，第二运算对象arg2，运算结果运算结果result)a:=a*c+b*d第 24 页例例 A + B * ( C - D ) + E / ( C - D ) NA B C D - * + E C D N / +逆波兰逆波兰(1) ( - C D T1 ) (2) ( * B T1 T2) (3) ( + A T2 T3) (4) ( - C D T4) (5) ( T4 N T5) (6) ( / E

13、T5 T6) (7) ( + T3 T6 T7) 四元式四元式第 25 页 (1) ( - C D ) (2) ( * B (1) ) (3) ( + A (2) ) (4) ( - C D ) (5) ( (4) N ) (6) ( / E (5) ) (7) ( + (3) (6) ) 三元式三元式例例 A + B * ( C - D ) + E / ( C - D ) N第 26 页if E then s1 else s2ES1S2NYE的代码的代码S1的代码的代码goto outS2的代码的代码out:E.trueE.falseE.trueE.falseout:布尔表达式布尔表达式 E

14、：B rop C无条件转无条件转 (jmp , -, -, L)条件真转条件真转 (jrop, B, C, L)四元式四元式goto Lif B rop C goto L第 27 页例例 8.5 布尔表达式布尔表达式ab or cf的翻译的翻译 P183E E的的“真真”出口转移目出口转移目标标E E的的“假假”出口转移目标出口转移目标第 28 页(7)(p-1) u goto (p+1) (q-1)(q)语句语句if ab or cf then S1 else S2 的四元式的四元式S1的四元式的四元式S2的四元式的四元式转移地址在产生四元式时无法确定，需要转移地址在产生四元式时无法确定，需

15、要回填回填。E.trueE.false(7)(7)(p+1)(p+1)(q)ES1S2NYqE.trueE.false第 29 页（10） goto L （20） goto L （30） goto L （40）L：拉链返填拉链返填（10）goto 0（20）goto 10（30） goto 20链尾链尾链首链首链尾标志链尾标志第 30 页(E.true )： (1)和和( (5 ) )拉链拉链(E.false)：(4) 和和(6)拉链拉链语句语句if ab or cf then S1 else S2 的四元式的四元式(7)(p-1) u goto (p+1) (q-1)(q)S1的四元式的四元

16、式S2的四元式的四元式(7)(7)(p+1)(p+1)(q)第 31 页语义描述使用的变量语义描述使用的变量 P P184E.true ： “真真”链链 E.false ： “假假”链链 E.Codebegin：E的第一个四元式序号的第一个四元式序号 nextstat：输出序列中下一四元式的序号：输出序列中下一四元式的序号emit( ) ：输出一条四元式，而后：输出一条四元式，而后nextstat+1backpach(p,t)：把所链接的每个四元式的第四字段都填为：把所链接的每个四元式的第四字段都填为tE.place: : 存放存放E值的变量名在符号表中的登录项值的变量名在符号表中的登录项,或

17、一整数码或一整数码merge(p1,p2) ：把：把p1和和p2为链首的两条链合并为一条，返回合并为链首的两条链合并为一条，返回合并 后的链首值后的链首值(p1)第 32 页第 33 页(5)Eid E.true:=nextstat; E.codebegin:=nextstat; E.false:=nextstat+1; emit(if id.place goto); emit(goto-)(4)E(E1) E.true:= E1.true; E.Codebegin:= E1.codebegin; E.false:= E1.false(5)Eid1 rop id2 E.true:=nextst

18、at; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emit(goto-)第 34 页EEEaborEcf(100) if ab goto _ (101) goto _ 例例 8.5 ab or cf的自底向上翻译的自底向上翻译 P185(5)Eid1 rop id2 E.true:=nextstat; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emi

19、t(goto-)E.true=100E.false=101E.codebegin=100第 35 页EEEorEcf(100) if ab goto _ (101) goto _ E.true=100E.false=101E.codebegin=100例例 8.5 ab or cf的自底向上翻译的自底向上翻译 P185(5)Eid1 rop id2 E.true:=nextstat; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emit(goto-)(102) if cfE

20、.true=100E.false=101E.codebegin=100E.true=102E.false=103E.codebegin=102例例 8.5 ab or cf的自底向上翻译的自底向上翻译 P185(5)Eid1 rop id2 E.true:=nextstat; E.Codebegin:=nextstat; E.false:=nextstat+1; emit(if id1.place rop id2.place goto); emit(goto-)(100) if ab goto _ (101) goto _ (102) if cf goto _ (105) goto _E.true=104E.false=105E.codebegin=104第 37 页EEEorEandEE.true=100E.false=101E.codebegin=100E.true=102E.false=103E.codebegin=102例例 8.5 ab or cf的自底向上翻译的自底向上翻译 P185(100) if ab goto _ (101) goto _ (102) if cf goto _ (1