布尔表达式的翻译.ppt

布尔表达式的翻译
第1页，本讲稿共17页
1. 概述
布尔表达式是布尔运算量和逻辑运算符按一定语法规则组成的式子。
逻辑运算符通常有∧、∨、﹃三种（在某些语言中，还有≡（等价）及→（蕴含）等等）；
逻辑运算对象可以是逻辑值（T else S2
经翻译后，可得四元式序列：
(1) (jnz, A, -, 5)
(2) (j, - ,- , 3)
(3) (j<, B, C, 5)
(4) (j, -, -, p+1)
(5) S1相应的四元式序列
(p) (j, -, -, q)
(p+1) S2相应的四元式序列
(q) …
其中，表达式A的真出口为5（也是整个表达式的真出口），假出口为3（即表达式B<C的第一四元式）；B<C的真、假出口也分别是整个表达式的真、假出口。
第11页，本讲稿共17页
8. 拉链与回填
在自底向上的语法制导翻译时（或者说，在S-属性翻译文法中), 在产生一个(无)条件转移四元式时, 它所要转向的那个四元式有时尚未产生，故无法立即产生一个完全的控制转移四元式。
例如，在上例中，在产生第一个四元式时，由于语句S1的中间代码尚未产生，即A的真出口确切位置并不知道，故此时只能产生一个空缺转移目标的四元式 (jnz,A,-,0),
并将此四元式的序号(即1)作为语义信息存起来，待开始翻译S1时，再将S1的第一四元式的序号(即5)回填这个不完全的四元式。
另外，在翻译过程中，常常会出现若干转移四元式转向同一目标，但此目标的具体位置又尚未确定的情况，此时我们可将这些四元式用拉链的办法将它们链接起来，用一指针指向链头，在确定了目标四元式的位置之后，再回填这个链。
第12页，本讲稿共17页
对于一个布尔表达式E来说，它应有两条链：真出口链(称为T链，记作TC)和假出口链(称为F链，记作FC)。。
例如，对于上述if语句中的布尔式E=A∨B<C，在翻译过程中形成的T链和F链如右图所示。
其中，每条链都是利用四元式中的Result域连接的， Result >0时,它给出本链的后继四元式的序号， Result =0时表示本四元式是链尾结点。
第13页，本讲稿共17页
(1) (jnz,A,-,0)
(2) (j,-,-,3) →(3)(j<,B,C,1) → (4)(j, -,-,0)
A∧B∨C的四元式序列及其TC链和FC链
第14页，本讲稿共17页
9. 文法的“拆分”
为便于实现布尔表达式的语法制导翻译，我们先改写文法，以便能在翻译过程中的适当时机获得所需的语义属性值。例如，可将文法()改写为：
ExprExpr^ Expr | Expr∨ Expr | ﹃ Expr|
iden |iden Rop iden | ( Expr )
Expr^  Expr ∧
Expr∨  Expr ∨ ()
将文法进行“拆分”的目的:
∧（∨）左侧的表达式后，能够及时获取其语义属性TC及FC
（即运算符右侧表达式的第一四元式之序号）回填前一表达式的相应真（假）链TC（FC），
（TC）作为产生式左部符号的综合属性FC（TC）传播之。
第15页，本讲稿共17页
10. 语义变量及辅助语义函数
全局变量，用于指示所要产生的下一四元式的序号；
（…）其意义同前,每次调用,NXQ++；
Merge(int p1,int p2)将链首“指针”分别为p1和p2的两条链合并为一条，并返回新链的链首“指针”（此处的“指针”实际上是四元式的序号，应为整型值）我们假定四元式是以一结构形式表示（存储）的：
struct _Quadruple{
int Op, arg1, arg2, Result;
} QuadrupleList[];
BackPatch(int p,int t)用四元式序号t回填以p为首的链，将链中每个四元式的Result域改写为t的值。
函数Merge( )及BackPatch( )的程序见书
第16页，本讲稿共17页
11. 翻译布尔表达式的属性文法
→iden { $$.TC= NXQ; $$.FC= NXQ+1; GEN(jnz, Entry($1), 0, 0); GEN(j,0,0,0); }
| iden rop iden { $$.TC= NXQ; $$.FC= NXQ+1;