E (Ltrue, Lfalse)
E (Ltrue, Lfalse)
(Ltrue, L1) E or (L2, Lfalse) E and E (Ltrue, Lfalse)
a< b
c< d e< f
6
产生式
语义规则
考虑如下表达式： E→id1 relop id2
E.code:=gerenl(o‘ipfg.’oeipdn1(i.‘dpg2lo.aptcolae’cEe.‘fgaolsteo)’ E.true) ||
(2) E→E1 and M E2
{ backpatch(E1.truelist, M.quad);
E.truelist:=E2.truelist;
E.falselist:=merge(E1.falselist,E2.falselist) }
21
a<b or c<d and e<f
(5) E→id1 relop id2 { E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(‘j’ relop.op ‘,’ id 1.place ‘,’ id 2.place‘,’ ‘0’); emit(‘j, －, －, 0’) }
作为整个布尔表达式的“真”“假”出口 (转移目标)仍待回填.
20
a<b or c<d and e<f
(5) E→id1 relop id2 { E.truelist:=makelist(nextquad);
E.falselist:=makelist(nextquad+1);
emit(‘j’ relop.op ‘,’ id 1.place ‘,’ id 2.place‘,’ ‘0’); emit(‘j, －, －, 0’) }
E→E1 or E2
E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code || gen(E1.false ‘:’) || E2.code
E→E1 and E2
EEEEE1122.c....tfftorraauudllsseeeee:::===::==nEEEEe.1t..w.rffcuaaloaelssdb;leeee;;l|;| gen(E1.true ‘:’) || E2.code5
To E.true To E.false
{ backpatch(E1.falselist, M.quad);
E.truelist:=merge(E1.truelist, E2.truelist);
E.falselist:=E2.falselist }
(2) E→E1 and M E2 { backpatch(E1.truelist, M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) }
goto Lfalse
L2:if e<f goto Ltrue goto Lfalse
E(Ltrue, Lfalse)
E(Ltrue, Lfalse)
(Ltrue, L1) E or (L2, Lfalse) E and E (Ltrue, Lfalse)
a< b
c< d e< f
7
布尔表达式的翻译
例如:假定E的四元式中需要回填"真"出口的p，q， r三个四元式，则E.truelist为下列链:
(p) (x， x，x，0) …
链尾
(q) (x，x，x，p)
…
(r) (x，x，x，q)
E. truelist =r
12
为了处理E.truelist和E.falselist ，引入下列语 义变量和过程
过程backpatch(p, t)，其功能是完成“回填”，把 p所链接的每个四元式的第四区段都填为t。
13
过程backpatch(p, t)，其功能是完成“回 填”，把p所链接的每个四元式的第四区 段都填为t。
(r) (x， x，x，0t )
…
(q) (x，x，x，tr )
…
(p) (x，x，x，tq )
E→E1 or E2
a<b E1.true:=E.true;
E1.false:=newlabel;
or
c<d
and
e<f
假 和定Lfa整ls个eEEE，22.表..ctfraou则ldse达ee:=::按==E式EE.t.r1f定au.的cleso;义ed真;e将||假g生e出n(成E口1.f如a已ls下e分‘:的’)别||代E置2.码c为od：eLtrue
链尾 p
14
布尔表达式的文法
(1) E→ E1 or M E2
(2)
| E1 and M E2
(3)
| not E1
(4)
| (E1)
(5)
| id1 relop id2
(6)
| id
(7) M→
15
布尔表达式的翻译模式
(7) M→
{ M.quad:=nextquad }
(1) E→ E1 orΒιβλιοθήκη M E2产生式语义规则
E→E1 or E2
E1.true:=E.true;
考虑如下表达式： E1.false:=newlabel; E2.true:=E.true;
E→E1假 和an定Ld fEa整2 ls个eEEEEEEE，表.....fftftooaararuudd按lllsssee达eeeee::::==:::==定===EnEE式EEEe.11t.....wrfff义ccaaau的oolllsaessddlb;写eeeeeae真;;;l||<;|| 出ggb假eenn将o((出EEr11.生f.ct口arlu<s成ee已d‘‘::’的’)a)分||||n代EEd别码oeo置dd<eef为Ltrue
17
布尔表达式的翻译模式
(3) E→not E1 { E.truelist:=E1.falselist; E.falselist:=E1.truelist}
(4) E→(E1) { E.truelist:=E1.truelist; E.falselist:=E1. falselist}
18
布尔表达式的翻译模式
编译原理
第七章 语义分析和中间代码产生
1
第七章 语义分析和中间代码产生
中间语言 赋值语句的翻译 布尔表达式的翻译 控制语句的翻译 过程调用的处理
2
第七章 语义分析和中间代码产生
中间语言 赋值语句的翻译 布尔表达式的翻译 控制语句的翻译 过程调用的处理
3
布尔表达式的翻译
两(多)遍扫描
变量nextquad，它指向下一条将要产生但尚未形 成的四元式的地址(标号)。nextquad的初值为1， 每当执行一次emit之后，nextquad将自动增1。
函数makelist(i)，它将创建一个仅含i的新链表，其 中i是四元式数组的一个下标(标号)；函数返回指向 这个链的指针。
并函为数一m，erg作e为(p1函,p数2)，值，把回以送p1合和并p2为后链的首链的首两。条链合
9
一遍扫描实现布尔表达式的翻译
过程emit将四元式代码送到输出文件中
100 ( j<, a, b, 104) 101 ( j, -, -, 102) 102 ( j<, c, d, 104) 103 ( j, -, -, 110) 104 ...
... 110 ...
a<b or c<d
10
最大的困难?
为给定的输入串构造一棵语法树 遍历语法树，进行语义规则中规定的翻译
4
考虑如下表达式：
a<b or c<d and e<f 假产生定式整个表达式的真语假义出规口则已分别置为Ltrue E→和idL1fraellospe，id2则按E.定cod义ree:lo将=pg.e生onp(成‘iidfg2’如e.ipndl1(a下‘.gcpoel的atoc‘ge’代oEto码.’faEl：s.teru)e) ||
a< b
c< d
ε
e< f
22
(1) E→E1 or M E2 { backpatch(E1.falselist, M.quad);
a<b or c<d and e<f E.truelist:=merge(E1.truelist, E2.truelist);
E.falselist:=E2.falselist } (2) E→E1 and M E2
E→E1 and E2
EEEEE1122.....ctftfraraouulldsseeeee::==:::===nEEEEe.t..wr1ffaau.lclsaesolb;eede;;le; || gen(E1.true ‘:’) || E2.code
if a<b goto Ltrue
goto L1 L1:if c<d goto L2
两(多)遍扫描
为给定的输入串构造一棵语法树 遍历语法树，进行语义规则中规定的翻译
一遍扫描
8
一遍扫描实现布尔表达式的翻译
采用四元式形式 把四元式存入一个数组中，数组下标就代表四元
式的标号 约定
四元式(jnz, a, -, p) 表示 if a goto p 四元式(jrop, x, y, p) 表示 if x rop y goto p 四元式(j, -, -, p) 表示 goto p