第讲语法制导翻译和中间代码生成

布尔表达式的计值方法

方法一：逐步计算方法二：优化计算例如：1∨（～0∧0）∨0=1∨（1∧0）∨0=1∨0∨0=1∨0=1①A∨B②A∧B③～A解释为：ifAthenTRUEelseB解释为：ifAthenBelseFALSE解释为：ifAthenFALSEelseTRUE目前一页\总数八十三页\编于十八点作为逻辑计值的布尔表达式的翻译例如：将A∨B∧C=D翻译成四元式的形式（=，C，D，T1）（∧，B，T1，T2）（∨，A，T2，T3）目前二页\总数八十三页\编于十八点作为控制条件的布尔表达式的翻译下面我们来观察“if-语句”和“while-语句”中布尔表达式的作用：仅仅用于执行流程的控制ifEthenS1elseS2whileEdoSE的四元式代码S1的四元式代码GOTOLE的四元式代码S2的四元式代码……S的四元式代码GOTOL……TRUETRUEFALSEFALSE返回目前三页\总数八十三页\编于十八点我们通过观察“if-语句”和“while-语句”中布尔表达式的作用可以知道：E的四元式代码TRUEFALSEE的真出口，用E.TC表示E的假出口，用E.FC表示目前四页\总数八十三页\编于十八点

（jnz，A，，p）

若A为真，则转到第p号四元式去执行（jrop，A，B，p）

若AropB为真，则转到第p号四元式去执行（j，，，p）

无条件转到第p号四元式去执行为了翻译布尔表达式，我们引入下面三种四元式：目前五页\总数八十三页\编于十八点例如：将下面语句翻译成四元式的形式（编号从100开始）ifA∨B<Dthenx:=y+zelsex:=y-z100（jnz，A，，104）

；A的“真出口”101（j，，，102）

；A的“假出口”102（j<，B，D，104）

；B<D的“真出口”103（j，，，107）

；B<D的“假出口”104（+，y，z，T1）

；S1语句105（:=，T1，，x）

；S1语句106（j，，，109）

；跳过S2的代码107（-，y，z，T2）

；S2语句108（:=，T2，，x）

；S2语句109…………目前六页\总数八十三页\编于十八点ifA∨B<Dthenx:=y+zelsex:=y-z100（jnz，A，，104）

；A的“真出口”101（j，，，102）

；A的“假出口”102（j<，B，D，104）

；B<D的“真出口”103（j，，，107）

；B<D的“假出口”104（+，y，z，T1）

；S1语句105（:=，T1，，x）

；S1语句106（j，，，109）

；跳过S2的代码107（-，y，z，T2）

；S2语句108（:=，T2，，x）

；S2语句109…………如何确定一个布尔表达式的“真出口”和“假出口”呢？目前七页\总数八十三页\编于十八点优化计算②A∨B①A∧B③～A解释为：ifAthenTRUEelseB解释为：ifAthenBelseFALSE解释为：ifAthenFALSEelseTRUEE→E1∧E2

E1的“真出口”就是E2的第一个四元式编号；E1的“假出口”就是E的“假出口”；E2的“真/假出口”就是E的“真/假出口”E→E1∨E2

E1的“真出口”就是E的“真出口”；E1的“假出口”就是E2的第一个四元式编号；E2的“真/假出口”就是E的“真/假出口”E→～E1

E1的“真出口”就是E的“假出口”；E1的“假出口”就是E的“真出口”；目前八页\总数八十三页\编于十八点由于在分析过程中，一个布尔表达式的“真/假出口”往往不能在产生四元式的同时就填上。所以我们常采用“拉链——回填”的方式来处理。为此，对布尔表达式E我们赋予两个属性（语义值）：存放E的“真链”链头，该链上的所有四元式均是需要回填“真出口”的四元式的地址（编号）E.TC存放E的“假链”链头，该链上的所有四元式均是需要回填“假出口”的四元式的地址（编号）E.FC例如：E.TC=rr(～，～，～，p)…p(～，～，～，q)…q(～，～，～，0)0表示链尾目前九页\总数八十三页\编于十八点r(～，～，～，0)p(～，～，～，0)q(～，～，～，0)…………………………………………r(～，～，～，p)p(～，～，～，q)

“拉链”（并链）过程：Merge(p1，p2)功能：将p2链附加在p1链的后面，返回p1链的链首指针①E.TC=r②E.TC=Merge(E.TC，p)③E.TC=Merge(E.TC，q)目前十页\总数八十三页\编于十八点…………………………………………r(～，～，～，p)p(～，～，～，q)

“回填”过程：BackPatch(p，t)功能：用四元式编号t填入首指针为p的链中的全部四元式中的第四个元。E.TC执行回填过程：BackPatch(E.TC，t)r(～，～，～，t)p(～，～，～，t)q(～，～，～，0)q(～，～，～，t)目前十一页\总数八十三页\编于十八点引入以下属性和子程序：①E.TC（真链头）；E.FC（假链头）②NXQ：全局变量，其值等于即将产生而又没有产生的四元式编号，初始值为1，每调用一次四元式生成子程序，其值自动加1。③Merge（p1，p2）:将p1和p2两条链合并，返回合并后的链头。④BackPatch（p，t）:用四元式编号t去填p链中所有四元式的第四个元。将布尔表达式改写成如下形式：E→E∧E│E∨E│～E│(E)│iropi│iE∧→E∧E∨→E∨为什么要如此改写产生式？

目前十二页\总数八十三页\编于十八点布尔表达式的语义子程序如下：E→i{E.TC=NXQ;E.FC=NXQ+1;Gen(jnz,Lookup(),,0);Gen(j,,,0);}(2)E→i1ropi2{E.TC=NXQ;E.FC=NXQ+1;Gen(jrop,Lookup(),Lookup(),0);Gen(j,,,0);}(3)E→(E1){E.TC=E1.TC;E.FC=E1.FC;}(4)E→～E1{E.TC=E1.FC;E.FC=E1.TC;}(5)E∧→E1∧{BackPatch(E1.TC,NXQ);E∧.FC=E1.FC;}(6)E→E∧E2{E.TC=E2.TC;E.FC=Merge(E∧.FC,E2.FC)}(7)E∨→E1∨{BackPatch(E1.FC,NXQ);E∨.TC=E1.TC;}(8)E→E∨E2

{E.FC=E2.FC;E.TC=Merge(E∨.TC,E2.TC)}返回目前十三页\总数八十三页\编于十八点例1：把A∨B∧C>D翻译成四元式（从100号开始）100（jnz，A，，0）101（j，，，0）句型:A∨B∧C>D

=>

EA∨B∧C>D

执行：Sub1；NXQ=102属性：EA.TC=100;EA.FC=101;

102

查看语义子程序EA.TCEA.FCNXQE→i{E.TC=NXQ;E.FC=NXQ+1;Gen(jnz,Lookup(),,0);Gen(j,,,0);}目前十四页\总数八十三页\编于十八点100（jnz，A，，0）101（j，，，102）②句型:EA∨B∧C>D

=>

E∨B∧C>D

执行：Sub7；NXQ=102属性：E∨.TC=100;（EA.TC=100;EA.FC=101;）102查看语义子程序E∨.TCNXQ

(7)E∨→E1∨{BackPatch(E1.FC,NXQ);E∨.TC=E1.TC;}目前十五页\总数八十三页\编于十八点100（jnz，A，，0）101（j，，，102）③句型:E∨B∧C>D

=>

E∨EB∧C>D

执行：Sub1；NXQ=104属性：E∨.TC=100;EB.TC=102;EB.FC=103;

（E∨.TC=100;

）查看语义子程序E∨.TC

NXQE→i{E.TC=NXQ;E.FC=NXQ+1;Gen(jnz,Lookup(),,0);Gen(j,,,0);}102（jnz，B，，0）103（j，，，0）104

EB.TCEB.FC目前十六页\总数八十三页\编于十八点100（jnz，A，，0）101（j，，，102）④句型:E∨EB∧C>D

=>E∨E∧C>D

执行：Sub5；NXQ=104属性：E∨.TC=100;E∧.FC=103;

（E∨.TC=100;EB.TC=102;EB.FC=103;

）查看语义子程序E∨.TC

NXQ

102（jnz，B，，104）103（j，，，0）104E∧.FC(5)E∧→E1∧{BackPatch(E1.TC,NXQ);E∧.FC=E1.FC;}目前十七页\总数八十三页\编于十八点100（jnz，A，，0）101（j，，，102）⑤句型:E∨E∧C>D

=>E∨E∧E2

执行：Sub2；NXQ=106属性：E∨.TC=100;E∧.FC=103;E2.TC=104;E2.FC=105;（E∨.TC=100;

E∧.FC=103;

）查看语义子程序E∨.TC

NXQ102（jnz，B，，104）103（j，，，0）E∧.FC

104（j>，C，D，0）105（j，，，0）106E2.TCE2.FC(2)E→i1ropi2{E.TC=NXQ;E.FC=NXQ+1;Gen(jnz,Lookup(),Lookup(),0);Gen(j,,,0);}目前十八页\总数八十三页\编于十八点100（jnz，A，，0）101（j，，，102）⑥句型:E∨E∧E2

=>

E∨E2’

执行：Sub6；NXQ=106属性：E∨.TC=100;E2’.FC=103;E2’.TC=104;（E∨.TC=100;

E∧.FC=103;

E2.TC=104;E2.FC=105;

）查看语义子程序E∨.TC

NXQ

102（jnz，B，，104）103（j，，，105）E2’.FC104（j>，C，D，0）105（j，，，0）106E2’.TC(6)E→E∧E2{E.TC=E2.TC;E.FC=Merge(E∧.FC,E2.FC)}目前十九页\总数八十三页\编于十八点100（jnz，A，，104）101（j，，，102）⑦句型:

E∨E2’

=>E执行：Sub8；NXQ=106属性：E.TC=100;E.FC=103;（E∨.TC=100;

E2’.FC=103;

E2’.TC=104;）查看语义子程序E.TCNXQ

102（jnz，B，，104）103（j，，，105）E.FC104（j>，C，D，0）105（j，，，0）106(8)E→E∨E2

{E.FC=E2.FC;E.TC=Merge(E∨.TC,E2.TC)}目前二十页\总数八十三页\编于十八点100（jnz，A，，104）101（j，，，102）E.TCNXQ

102（jnz，B，，104）103（j，，，105）E.FC104（j>，C，D，0）105（j，，，0）106100（jnz，A，，106）101（j，，，102）102（jnz，B，，104）103（j，，，108）104（j>，C，D，106）105（j，，，108）106（+，x，1，x）107（j，，，109）108（+，y，1，y）109………………ifA∨B∧C>Dthenx:=x+1elsey:=y+1A∨B∧C>D目前二十一页\总数八十三页\编于十八点例2：翻译布尔表达式A∧B∨C≤D，并把其值保存到一个临时变量中（用四元式表示，从100号开始）100（jnz，A，，102）101（j，，，104）E.TC

102（jnz，B，，104）103（j，，，104）E.FC104（j≤，C，D，0）105（j，，，0）106100（jnz，A，，102）101（j，，，104）102（jnz，B，，106）103（j，，，104）104（j≤，C，D，106）105（j，，，108）106（:=，1，，x）107（j，，，109）108（:=，0，，x）109………………表达式A∧B∨C≤D的四元式X:=A∧B∨C≤D的四元式(9)S’→E{T:=Newtemp;BackPatch(E.TC,NXQ);BackPatch(E.FC,NXQ+2);Gen(:=,1,,T);L=NXQ+2;Gen(j,,,L);

Gen(:=,0,,T);S’.Place:=T;}在前面文法的基础上增加如下一条四元式：目前二十二页\总数八十三页\编于十八点标号语句和GOTO语句到四元式的翻译标号语句和GOTO语句的文法(1)Sg→gotoLabel(2)S→LabelS(3)Label→i:符号表名字定义种属类型……地址……L0LAB……r……目前二十三页\总数八十三页\编于十八点gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定义种属类型……地址………………………………L11LAB……k源代码：四元式：k(～,～,～,～)…gotoL2符号表目前二十四页\总数八十三页\编于十八点gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定义种属类型……地址………………………………L11LAB……k源代码：四元式：…k(～,～,～,～)…m(j,,,k)…n(j,,,k)gotoL2符号表目前二十五页\总数八十三页\编于十八点gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定义种属类型……地址………………………………L11LAB……kL20LAB

p

源代码：四元式：……k(～,～,～,～)…m(j,,,k)…n(j,,,k)gotoL2p(j,,,0)符号表目前二十六页\总数八十三页\编于十八点gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定义种属类型……地址………………………………L11LAB……kL20LAB

q

源代码：四元式：………k(～,～,～,～)…m(j,,,k)…n(j,,,k)gotoL2p(j,,,0)符号表q(j,,,p)目前二十七页\总数八十三页\编于十八点gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定义种属类型……地址………………………………L11LAB……kL20LAB

r

源代码：四元式：………k(～,～,～,～)…m(j,,,k)……n(j,,,k)gotoL2p(j,,,0)符号表q(j,,,p)r(j,,,q)目前二十八页\总数八十三页\编于十八点gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定义种属类型……地址………………………………L11LAB……kL2

1LAB

t

源代码：四元式：………k(～,～,～,～)…m(j,,,k)………n(j,,,k)gotoL2p(j,,,t)符号表q(j,,,t)r(j,,,t)t(～,～,～,～)目前二十九页\总数八十三页\编于十八点标号语句和GOTO语句的语义子程序(1)Sg→gotoLabel{Enter:=Lookup(Label.Name);ifEnter==NullthenBeginEnter.Name:=Label.Name;Enter.Cat:=LAB;Enter.Def:=0;Enter.Addr:=NXQ;Gen(j,,,0);EndelseifEnter.Def==1thenGen(j,,,Enter.Addr);elseBeginN:=NXQ;Gen(j,,,Enter.Addr);Enter.Addr:=N;End}(2)

S→LabelS{}(3)Label→i:{Enter:=Lookup(i.Name);ifEnter==NullthenBeginEnter.Name:=i.Name;Enter.Cat:=LAB;Enter.Def:=1;Enter.Addr:=NXQ;EndelseifEnter.Def==1thenError;elseBeginEnter.Def:=1;BackPatch(Enter.Addr,NXQ);Enter.Addr:=NXQ;End}目前三十页\总数八十三页\编于十八点条件语句、while语句和复合语句到四元式的翻译条件语句、while语句和复合语句的语法（1）S→ifEthenS│ifEthenSelseS│whileEdoS│beginLend│A（2）L→L;S│S说明：S表示语句；E表示布尔表达式；A表示赋值语句；L表示语句串。引入二个新的符号属性①S.Chain:转出内层语句S的各四元式所形成的链的链头。②X.Quad:相应于X符号的四元式串的第一个四元式编号。目前三十一页\总数八十三页\编于十八点

为了在翻译过程中能及时地进行“拉链”和“回填”处理，我们将其文法改写成如下形式：（1）S→ifEthenS│ifEthenSelseS│whileEdoS│beginLend│A（2）L→L;S│S(1)C→ifEthen(2)S→CS1(3)TP→CS1else(4)S→TPS2(5)W→while(6)Wd→WEdo(7)S→WdS1(8)S→A(9)L→S(10)LS→L;(11)L→LSS1(12)S→beginLend改写前的四元式：查看语句翻译模式目前三十二页\总数八十三页\编于十八点

语义子程序如下：(1)C→ifEthen(2)S→CS1(3)TP→CS1else(4)S→TPS2(5)W→while(6)Wd→WEdo(7)S→WdS1(8)S→A(9)L→S(10)LS→L;(11)L→LSS1(12)S→beginLend{BackPatch(E.TC,NXQ);C.Chain:=E.FC;}{S.Chain:=Merge(C.Chain,S1.Chain);}{q:=NXQ;Gen(j,,,0);BackPatch(C.Chain,NXQ);TP.Chain:=Merge(S1.Chain,q);}{S.Chain:=Merge(TP.Chain,S2.Chain);}{W.Quad:=NXQ;}{BackPatch(E.TC,NXQ);Wd.Chain:=E.FC;Wd.Quad:=W.Quad;}{BackPatch(S1.Chain,Wd.Quad);Gen(j,,,Wd.Quad);S.Chain:=Wd.Chain;}{S.Chain:=0;}{L.Chain:=S.Chain;}{BackPatch(L.Chain,NXQ);}{L.Chain:=S1.Chain;}{S.Chain:=L.Chain;}返回查看翻译框架目前三十三页\总数八十三页\编于十八点例3：将下列语句翻译成四元式的形式（假设编号从100开始）while(A<B)doif(C>D)thenx:=y+z;查看语义子程序句型:while(A<B)doif(C>D)thenx:=y+z;=>

W(A<B)doif(C>D)thenx:=y+z;执行：Sub5；NXQ=100属性：W.Quad=100;W.Quad

NXQ

100(5)W→while{W.Quad:=NXQ;}目前三十四页\总数八十三页\编于十八点查看语义子程序②句型:W(A<B)doif(C>D)thenx:=y+z;=>

WEdoif(C>D)thenx:=y+z;执行：归约布尔表达式；NXQ=102属性：W.Quad=100;E.TC=100;E.FC=101

(W.Quad=100;)NXQ

100（j<，A，B，0）101（j，，，0）102E.TCE.FC

W.Quad

目前三十五页\总数八十三页\编于十八点查看语义子程序③句型:WEdoif(C>D)thenx:=y+z;=>

Wdif(C>D)thenx:=y+z;执行：Sub6；NXQ=102属性：Wd.Quad=100;Wd.Chain=101

(W.Quad=100;E.TC=100;E.FC=101)Wd.Quad

NXQ100（j<，A，B，102）101（j，，，0）102Wd.Chain（6)Wd→WEdo{BackPatch(E.TC,NXQ);Wd.Chain:=E.FC;Wd.Quad:=W.Quad;}目前三十六页\总数八十三页\编于十八点查看语义子程序④句型:Wdif(C>D)thenx:=y+z;=>

WdifEthenx:=y+z;执行：归约布尔表达式；NXQ=104属性：Wd.Quad=100;Wd.Chain=101;E.TC=102;E.FC=103

(Wd.Quad=100;Wd.Chain=101)Wd.Quad

NXQ100（j<，A，B，102）101（j，，，0）Wd.Chain102（j>，C，D，0）103（j，，，0）104E.TCE.FC目前三十七页\总数八十三页\编于十八点查看语义子程序⑤句型:Wd

ifEthenx:=y+z;=>

Wd

Cx:=y+z;执行：Sub1；NXQ=104属性：Wd.Quad=100;Wd.Chain=101;C.Chain=103

(Wd.Quad=100;Wd.Chain=101;E.TC=102;E.FC=103)Wd.Quad

NXQ

100（j<，A，B，102）101（j，，，0）Wd.Chain102（j>，C，D，104）103（j，，，0）104C.Chain(1)C→ifEthen{BackPatch(E.TC,NXQ);C.Chain:=E.FC;}目前三十八页\总数八十三页\编于十八点⑥句型:WdCx:=y+z;=>

WdCA;执行：归约赋值语句；NXQ=106属性：Wd.Quad=100;Wd.Chain=101;C.Chain=103

(Wd.Quad=100;Wd.Chain=101;C.Chain=103)Wd.Quad

NXQ

100（j<，A，B，102）101（j，，，0）Wd.Chain102（j>，C，D，104）103（j，，，0）C.Chain104（+，y，z，T1）105（:=，T1，，x）106目前三十九页\总数八十三页\编于十八点查看语义子程序⑦句型:WdCA;=>

WdCS1;执行：Sub8；NXQ=106属性：Wd.Quad=100;Wd.Chain=101;C.Chain=103;S1.Chain=0

(Wd.Quad=100;Wd.Chain:=101;C.Chain=103)Wd.Quad

NXQ

100（j<，A，B，102）101（j，，，0）Wd.Chain102（j>，C，D，104）103（j，，，0）C.Chain104（+，y，z，T1）105（:=，T1，，x）106(8)S→A{S.Chain:=0;}S1.Chain=0目前四十页\总数八十三页\编于十八点查看语义子程序⑧句型:Wd

CS1;=>

Wd

S2;执行：Sub2；NXQ=106属性：Wd.Quad=100;Wd.Chain=101;S2.Chain=103;

(Wd.Quad=100;Wd.Chain:=101;C.Chain=103;S1.Chain=0)Wd.Quad

NXQ

100（j<，A，B，102）101（j，，，0）Wd.Chain102（j>，C，D，104）103（j，，，0）S2.Chain104（+，y，z，T1）105（:=，T1，，x）106(2)S→CS1{S.Chain:=Merge(C.Chain,S1.Chain);}目前四十一页\总数八十三页\编于十八点查看语义子程序⑨句型:WdS2;=>

S;执行：Sub7；NXQ=107属性：S.Chain=101;

(Wd.Quad=100;Wd.Chain:=101;C.Chain=103)NXQ

100（j<，A，B，102）101（j，，，0）S.Chain102（j>，C，D，104）103（j，，，100）104（+，y，z，T1）105（:=，T1，，x）(7)S→WdS1{BackPatch(S1.Chain,Wd.Quad);Gen(j,,,Wd.Quad);S.Chain:=Wd.Chain;}106（j，，，100）

107目前四十二页\总数八十三页\编于十八点查看语义子程序⑩句型:S;=>

L;执行：Sub9；NXQ=107属性：L.Chain=101;

(S.Chain:=101)NXQ

100（j<，A，B，102）101（j，，，0）L.Chain102（j>，C，D，104）103（j，，，100）104（+，y，z，T1）105（:=，T1，，x）(9)L→S106（j，，，100）107{L.Chain:=S.Chain;}目前四十三页\总数八十三页\编于十八点查看语义子程序⑾句型:L;=>

LS执行：Sub10；NXQ=107属性：(L.Chain:=101)NXQ

100（j<，A，B，102）101（j，，，107）102（j>，C，D，104）103（j，，，100）104（+，y，z，T1）105（:=，T1，，x）(10)LS→L;106（j，，，100）107{BackPatch(L.Chain,NXQ);}目前四十四页\总数八十三页\编于十八点while(A<B)doif(C>D)thenx:=y+z;100（j<，A，B，102）101（j，，，107）102（j>，C，D，104）103（j，，，100）104（+，y，z，T1）105（:=，T1，，x）106（j，，，100）107上面语句翻译成四元式的形式为：思考题：上面语句后面少分号，结果有是如何呢？目前四十五页\总数八十三页\编于十八点例4：将下列语句翻译成四元式的形式（假设编号从100开始）while(A∧B∨C)dobegink:=k+1;if(m>n)thenx:=x+y;elsex:=x-y;y:=y*2;end思考题目：给出详细的翻译步骤？目前四十六页\总数八十三页\编于十八点while(A∧B∨C)dobegink:=k+1;if(m>n)thenx:=x+y;elsex:=x-y;y:=y*2;end100(jnz,A,,102)101(j,,,104)102(jnz,B,,106)103(j,,,104)104(jnz,C,,106)105(j,,,0)106(+,k,1,T1)107(:=,T1,,k)108(j>,m,n,110)109(j,,,113)110(+,x,y,T2)111(:=,T2,,x)112(j,,,115)113(-,x,y,T3)114(:=,T3,,x)115(*,y,2,T4)116(:=,T4,,y)117(j,,,100)118S.Chain=105目前四十七页\总数八十三页\编于十八点总结如何分割一个产生式如何为一个产生式编写语义子程序理解语句的执行流程。自左向右扫描，理解语句的翻译框架。对后面四元式的转移目标（四元式编号）设置属性保存。拉（并）链的时机。回填的时机。设置文法符号的属性值以便保存：①后面四元式的转移目标；②待回填的四元式编号；③需要继承的属性。如果需要并链，则用Merge函数。如果需要回填，则用BackPatch过程。如果需要产生四元式，则用Gen过程。返回目前四十八页\总数八十三页\编于十八点For循环语句到四元式的翻译三种for循环语句的文法：S→fori:=E1stepE2untilE3doS1S→fori:=E1untilE2stepE3doS1S→for(E1;E2;E3)S1目前四十九页\总数八十三页\编于十八点语句

fori:=E1stepE2untilE3doS1的翻译执行流程如下：语义解释如下：i:=E1Si:=i+E2i≤E3

YNi:=E1gotooveragain:i:=i+E2over:ifi≤E3thenbeginS1;gotoagainend总结目前五十页\总数八十三页\编于十八点i:=E1gotooveragain:i:=i+E2over:ifi≤E3thenbeginS1;gotoagainend语句

fori:=E1stepE2untilE3doS1的翻译框架E1的四元式代码i:=E1(j,,,over)i:=i+E2(j≤,i,E3,L)(j,,,again)(j,,,0)E2的四元式代码againE3的四元式代码overS1的四元式代码L总结目前五十一页\总数八十三页\编于十八点E1的四元式代码i:=E1(j,,,over)i:=i+E2E2的四元式代码(j≤,i,E3,L)E3的四元式代码(j,,,again)(j,,,0)S1的四元式代码overagainL总结(4)A→fori:=E1step(3)B→AE2until(2)C→BE3do(1)S→CS1S.Chain产生式S→fori:=E1stepE2untilE3doS1的分割返回目前五十二页\总数八十三页\编于十八点E1的四元式代码i:=E1(j,,,0)i:=i+E2E2的四元式代码(j≤,i,E3,L)E3的四元式代码(j,,,again)(j,,,0)S1的四元式代码总结返回(4)A→fori:=E1step语句

fori:=E1stepE2untilE3doS1的语义子程序｛A.Place:=LookUp(i.Name);Gen(:=,E1.Place,,A.Place);A.Chain:=NXQ;Gen(j,,,0);A.Quad:=NXQ;｝A.ChainA.QuadNXQ目前五十三页\总数八十三页\编于十八点总结返回语句

fori:=E1stepE2untilE3doS1的语义子程序(3)B→AE2until｛B.Quad:=A.Quad;B.Place:=A.Place;Gen(+,A.Place,E2.Place,A.Place);BackPatch(A.Chain,NXQ);｝E1的四元式代码i:=E1(j,,,over)i:=i+E2E2的四元式代码(j≤,i,E3,L)E3的四元式代码(j,,,again)(j,,,0)S1的四元式代码B.QuadA.QuadA.ChainNXQ目前五十四页\总数八十三页\编于十八点总结返回语句

fori:=E1stepE2untilE3doS1的语义子程序(2)C→BE3do｛C.Quad:=B.Quad;q:=NXQ;Gen(j≤,B.Place,E3.Place,q+2);C.Chain:=NXQ;Gen(j,,,0);｝E1的四元式代码i:=E1(j,,,over)i:=i+E2E2的四元式代码(j≤,i,E3,L)E3的四元式代码(j,,,again)(j,,,0)S1的四元式代码C.QuadB.QuadC.ChainNXQ目前五十五页\总数八十三页\编于十八点总结返回语句

fori:=E1stepE2untilE3doS1的语义子程序(1)S→CS1｛Gen(j,,,C.Quad);S.Chain:=C.Chain;BackPatch(S1.Chain,C.Quad);｝E1的四元式代码i:=E1(j,,,over)i:=i+E2E2的四元式代码(j≤,i,E3,L)E3的四元式代码(j,,,again)(j,,,0)S1的四元式代码S.ChainC.ChainNXQC.Quad目前五十六页\总数八十三页\编于十八点(4)A→fori:=E1step(3)B→AE2until(2)C→BE3do(1)S→CS1语句

fori:=E1stepE2untilE3doS1的语义子程序｛A.Place:=LookUp(i.Name);Gen(:=,E1.Place,,A.Place);A.Chain:=NXQ;Gen(j,,,0);A.Quad:=NXQ;｝｛B.Quad:=A.Quad;B.Place:=A.Place;Gen(+,A.Place,E2.Place,A.Place);BackPatch(A.Chain,NXQ);｝｛C.Quad:=B.Quad;q:=NXQ;Gen(j≤,B.Place,E3.Place,q+2);C.Chain:=NXQ;Gen(j,,,0);｝｛Gen(j,,,C.Quad);S.Chain:=C.Chain;BackPatch(S1.Chain,C.Quad);｝返回目前五十七页\总数八十三页\编于十八点例５：将下列语句翻译成四元式的形式（编号从１００开始）forI:=a+2*bstepc+duntiln+mdox:=y+z查看语义子程序①句型:forI:=a+2*bstepc+duntiln+mdox:=y+z=>forI:=E1stepc+duntiln+mdox:=y+z执行：归约算术表达式；NXQ=102属性：NXQ

100（*，２，b，T1）101（+，a，T1，T2）102目前五十八页\总数八十三页\编于十八点②句型:forI:=E1stepc+duntiln+mdox:=y+z=>Astepc+duntiln+mdox:=y+z执行：Sub4；NXQ=104属性：A.Place→I;A.Chain=103;A.Quad=104NXQ100（*，２，b，T1）101（+，a，T1，T2）102（:=，T2，，i）(4)A→fori:=E1Gen(:=,E1.Place,,A.Place);A.Chain:=NXQ;Gen(j,,,0);A.Quad:=NXQ;｝｛A.Place:=LookUp(i.Name);103（j，，，0）104A.Chain

A.Quad

查看语义子程序目前五十九页\总数八十三页\编于十八点查看语义子程序③句型:Astepc+duntiln+mdox:=y+z=>AstepE2untiln+mdox:=y+z执行：归约算术表达式；NXQ=105属性：(A.Place→I;A.Chain=103;A.Quad=104)NXQ

100（*，２，b，T1）101（+，a，T1，T2）102（:=，T2，，i）103（j，，，0）104(+，c，d，T3)A.Chain

A.Quad

105目前六十页\总数八十三页\编于十八点④句型:AstepE2untiln+mdox:=y+z=>Buntiln+mdox:=y+z执行：Sub3；NXQ=105属性：B.Quad=104;B.Place→I;

(A.Place→I;A.Chain=103;A.Quad=104)NXQ

100（*，２，b，T1）101（+，a，T1，T2）102（:=，T2，，I）103（j，，，106）104(+，c，d，T3)

B.Quad

105(+，I，T3，I)(3)B→AstepE2B.Place:=A.Place;Gen(+,A.Place,E2.Place,A.Place);BackPatch(A.Chain,NXQ);｝｛B.Quad:=A.Quad;106查看语义子程序目前六十一页\总数八十三页\编于十八点查看语义子程序⑤句型:Buntiln+mdox:=y+z=>BuntilE3dox:=y+z执行：归约算术表达式；NXQ=107属性：(B.Place→I;B.Quad=104)NXQ

100（*，２，b，T1）101（+，a，T1，T2）102（:=，T2，，I）103（j，，，106）104(+，c，d，T3)

B.Quad

105(+，I，T3，I)

106(+，n，m，T4)107目前六十二页\总数八十三页\编于十八点查看语义子程序句型:BuntilE3dox:=y+z=>Cdox:=y+z执行：Sub2；NXQ=109属性：NXQ

100（*，２，b，T1）101（+，a，T1，T2）102（:=，T2，，I）103（j，，，106）104(+，c，d，T3)

C.Quad

105(+，I，T3，I)

106(+，n，m，T4)

107(j≤，I，T4，109)(2)C→BuntilE3Gen(j≤,B.Place,E3.Place,q+2);C.Chain:=NXQ;Gen(j,,,0);｝｛C.Quad:=B.Quad;q:=NXQ;(B.Place→I;B.Quad=104)108(j，，，0)109C.Chain

C.Quad=104;C.Chain=108目前六十三页\总数八十三页\编于十八点查看语义子程序⑦句型:Cdox:=y+z=>CdoS1执行：归约赋值语句NXQ=111属性：NXQ

100（*，２，b，T1）101（+，a，T1，T2）102（:=，T2，，I）103（j，，，106）104(+，c，d，T3)

C.Quad

105(+，I，T3，I)

106(+，n，m，T4)

107(j≤，I，T4，109)

(C.Quad=104;C.Cha