编译原理课件 第五章 语法制导翻译.ppt

第五章 语法制导翻译 　　这是一种语法分析和语义动作交错的表示法， 　　翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。 　　他表达在按深度优先遍历分析树的过程中何时执行语义动作。 例2： 一个简单的翻译模式（中缀变后缀） E→TR R→addop T {print(addop.lexeme)}R1|ε T→num{print(num.val)} 3+5的语义翻译过程 E R T Pr’3’ 3 T + Pr’+’ 5 R Pr’5’ ε 结果：35+ 翻译方案不仅要考虑“做什么”，还要考虑“怎么做” 某种意义上说，语法制导定义类似于算法，而翻译方案更象程序 　带有继承属性L.in的翻译方案 D?T｛　L?in:=T ? type　｝L T ?int ｛　T ? type :=integer　｝ T ?real ｛ T ? type :=real　｝ L ?{L1 ?in :=L ?in} L1,id{addtype(id ?entry,L ?in) } L ?id { addtype(id ?entry,L ?in) } 例5 . 3 变量说明的类型定义 int a,b,c D L.in=t.type L real L1.in=L.in , id3 L1.in=L.in , id2 id1 句子real id1,id2,id3的带继承属性的分析树 T T.type=real L L Add(L.in) Add(L.in) Add(L.in) 例：文法G的产生式如下： S→（L） S →a L →L,S L →S 1.试写出一个语法制导定义，输出配对括号个数 2.写一个翻译方案，打印每个a的嵌套深度 解：1.为S，L引入属性h 产生式 语法制导定义 S→（L） S.h=L.h+1 S →a S.h=0 L →L1,S L.h=L1.h+S.h L →S L.h=s.h S’ →S print(S.h) ( a S S.h=0 L , ( a L.h=0 S S.h=0 L L.h=0 ) S S.h=1 L L.h=1 ) S S.h=2 (a,(a))的分析过程 2.为S，L引入属性d,翻译方案如下 S’ →{S.d=0} S S→（ {L.d=S.d+1} L） S →a {print(s.d)} L →{L1.d=L.d} L1, {S.d=L.d}S L →{S.d=L.d} S S’ S.h=0 S ( L.d=1 L ) L.d=1 L , S.d=1 S S.d=1 S Print(1) a ( L.d=2 L ) S.d=2 S Print(2) a (a,(a))的分析过程 5.3 S-属性定义及其自底向上的计算 state val top 在分析栈中使用一个附加的域来存放综 合属性值。 下图为一个带有综合属性值域的分析栈： Z Y Z …… Z.val Y.val Z.val …… ?A?? b:=f(c1,c2,…,ck) A ?b X ?x Y ?y Z ?z 例：A?XYZ A?b:=f(X ?x, Y ?y,Z ?z) 　　　　　　　　　　　ci(1? i?k)是 ?中符号的属性。 其中：b是A的综合属性， 　　　　　　　　综合属性的值在自底向上的分析过程中， 　　　　　　　　　　每步归约时，计算相应的属性值。 X　　Y　　 Z A state val ... ... A A .b top 定义式 A .b=f(X.x, Y.y, Z.z)(抽象) 变成 val[ntop]=f(val[top-2],val[top-1],val[top])（具体可执行代码）。 归约后,分析栈为： 在执行代码段之前执行： 　　　　 ntop:=top-r+1 执行代码段后执行： top:=ntop; 其中:r是句柄的长度, ntop为归约后栈顶 例5.10 用LR分析器实现台式计算器 产生式 代码段(和表5.1对比） L?En printf(val[ntop])