第講語(yǔ)法制導(dǎo)翻譯和中間代碼生成

布爾表達(dá)式的計(jì)值方法

方法一：逐步計(jì)算方法二：優(yōu)化計(jì)算例如：1∨（～0∧0）∨0=1∨（1∧0）∨0=1∨0∨0=1∨0=1①A∨B②A∧B③～A解釋為：ifAthenTRUEelseB解釋為：ifAthenBelseFALSE解釋為：ifAthenFALSEelseTRUE目前一頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)作為邏輯計(jì)值的布爾表達(dá)式的翻譯例如：將A∨B∧C=D翻譯成四元式的形式（=，C，D，T1）（∧，B，T1，T2）（∨，A，T2，T3）目前二頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)作為控制條件的布爾表達(dá)式的翻譯下面我們來(lái)觀察“if-語(yǔ)句”和“while-語(yǔ)句”中布爾表達(dá)式的作用：僅僅用于執(zhí)行流程的控制ifEthenS1elseS2whileEdoSE的四元式代碼S1的四元式代碼GOTOLE的四元式代碼S2的四元式代碼……S的四元式代碼GOTOL……TRUETRUEFALSEFALSE返回目前三頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)我們通過(guò)觀察“if-語(yǔ)句”和“while-語(yǔ)句”中布爾表達(dá)式的作用可以知道：E的四元式代碼TRUEFALSEE的真出口，用E.TC表示E的假出口，用E.FC表示目前四頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)

（jnz，A，，p）

若A為真，則轉(zhuǎn)到第p號(hào)四元式去執(zhí)行（jrop，A，B，p）

若AropB為真，則轉(zhuǎn)到第p號(hào)四元式去執(zhí)行（j，，，p）

無(wú)條件轉(zhuǎn)到第p號(hào)四元式去執(zhí)行為了翻譯布爾表達(dá)式，我們引入下面三種四元式：目前五頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)例如：將下面語(yǔ)句翻譯成四元式的形式（編號(hào)從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語(yǔ)句105（:=，T1，，x）

；S1語(yǔ)句106（j，，，109）

；跳過(guò)S2的代碼107（-，y，z，T2）

；S2語(yǔ)句108（:=，T2，，x）

；S2語(yǔ)句109…………目前六頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)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語(yǔ)句105（:=，T1，，x）

；S1語(yǔ)句106（j，，，109）

；跳過(guò)S2的代碼107（-，y，z，T2）

；S2語(yǔ)句108（:=，T2，，x）

；S2語(yǔ)句109…………如何確定一個(gè)布爾表達(dá)式的“真出口”和“假出口”呢？目前七頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)優(yōu)化計(jì)算②A∨B①A∧B③～A解釋為：ifAthenTRUEelseB解釋為：ifAthenBelseFALSE解釋為：ifAthenFALSEelseTRUEE→E1∧E2

E1的“真出口”就是E2的第一個(gè)四元式編號(hào)；E1的“假出口”就是E的“假出口”；E2的“真/假出口”就是E的“真/假出口”E→E1∨E2

E1的“真出口”就是E的“真出口”；E1的“假出口”就是E2的第一個(gè)四元式編號(hào)；E2的“真/假出口”就是E的“真/假出口”E→～E1

E1的“真出口”就是E的“假出口”；E1的“假出口”就是E的“真出口”；目前八頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)由于在分析過(guò)程中，一個(gè)布爾表達(dá)式的“真/假出口”往往不能在產(chǎn)生四元式的同時(shí)就填上。所以我們常采用“拉鏈——回填”的方式來(lái)處理。為此，對(duì)布爾表達(dá)式E我們賦予兩個(gè)屬性（語(yǔ)義值）：存放E的“真鏈”鏈頭，該鏈上的所有四元式均是需要回填“真出口”的四元式的地址（編號(hào)）E.TC存放E的“假鏈”鏈頭，該鏈上的所有四元式均是需要回填“假出口”的四元式的地址（編號(hào)）E.FC例如：E.TC=rr(～，～，～，p)…p(～，～，～，q)…q(～，～，～，0)0表示鏈尾目前九頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)r(～，～，～，0)p(～，～，～，0)q(～，～，～，0)…………………………………………r(～，～，～，p)p(～，～，～，q)

“拉鏈”（并鏈）過(guò)程：Merge(p1，p2)功能：將p2鏈附加在p1鏈的后面，返回p1鏈的鏈?zhǔn)字羔槩貳.TC=r②E.TC=Merge(E.TC，p)③E.TC=Merge(E.TC，q)目前十頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)…………………………………………r(～，～，～，p)p(～，～，～，q)

“回填”過(guò)程：BackPatch(p，t)功能：用四元式編號(hào)t填入首指針為p的鏈中的全部四元式中的第四個(gè)元。E.TC執(zhí)行回填過(guò)程：BackPatch(E.TC，t)r(～，～，～，t)p(～，～，～，t)q(～，～，～，0)q(～，～，～，t)目前十一頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)引入以下屬性和子程序：①E.TC（真鏈頭）；E.FC（假鏈頭）②NXQ：全局變量，其值等于即將產(chǎn)生而又沒(méi)有產(chǎn)生的四元式編號(hào)，初始值為1，每調(diào)用一次四元式生成子程序，其值自動(dòng)加1。③Merge（p1，p2）:將p1和p2兩條鏈合并，返回合并后的鏈頭。④BackPatch（p，t）:用四元式編號(hào)t去填p鏈中所有四元式的第四個(gè)元。將布爾表達(dá)式改寫成如下形式：E→E∧E│E∨E│～E│(E)│iropi│iE∧→E∧E∨→E∨為什么要如此改寫產(chǎn)生式？

目前十二頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)布爾表達(dá)式的語(yǔ)義子程序如下：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)}返回目前十三頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)例1：把A∨B∧C>D翻譯成四元式（從100號(hào)開始）100（jnz，A，，0）101（j，，，0）句型:A∨B∧C>D

=>

EA∨B∧C>D

執(zhí)行：Sub1；NXQ=102屬性：EA.TC=100;EA.FC=101;

102

查看語(yǔ)義子程序EA.TCEA.FCNXQE→i{E.TC=NXQ;E.FC=NXQ+1;Gen(jnz,Lookup(),,0);Gen(j,,,0);}目前十四頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)100（jnz，A，，0）101（j，，，102）②句型:EA∨B∧C>D

=>

E∨B∧C>D

執(zhí)行：Sub7；NXQ=102屬性：E∨.TC=100;（EA.TC=100;EA.FC=101;）102查看語(yǔ)義子程序E∨.TCNXQ

(7)E∨→E1∨{BackPatch(E1.FC,NXQ);E∨.TC=E1.TC;}目前十五頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)100（jnz，A，，0）101（j，，，102）③句型:E∨B∧C>D

=>

E∨EB∧C>D

執(zhí)行：Sub1；NXQ=104屬性：E∨.TC=100;EB.TC=102;EB.FC=103;

（E∨.TC=100;

）查看語(yǔ)義子程序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目前十六頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)100（jnz，A，，0）101（j，，，102）④句型:E∨EB∧C>D

=>E∨E∧C>D

執(zhí)行：Sub5；NXQ=104屬性：E∨.TC=100;E∧.FC=103;

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

）查看語(yǔ)義子程序E∨.TC

NXQ

102（jnz，B，，104）103（j，，，0）104E∧.FC(5)E∧→E1∧{BackPatch(E1.TC,NXQ);E∧.FC=E1.FC;}目前十七頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)100（jnz，A，，0）101（j，，，102）⑤句型:E∨E∧C>D

=>E∨E∧E2

執(zhí)行：Sub2；NXQ=106屬性：E∨.TC=100;E∧.FC=103;E2.TC=104;E2.FC=105;（E∨.TC=100;

E∧.FC=103;

）查看語(yǔ)義子程序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);}目前十八頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)100（jnz，A，，0）101（j，，，102）⑥句型:E∨E∧E2

=>

E∨E2’

執(zhí)行：Sub6；NXQ=106屬性：E∨.TC=100;E2’.FC=103;E2’.TC=104;（E∨.TC=100;

E∧.FC=103;

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

）查看語(yǔ)義子程序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)}目前十九頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)100（jnz，A，，104）101（j，，，102）⑦句型:

E∨E2’

=>E執(zhí)行：Sub8；NXQ=106屬性：E.TC=100;E.FC=103;（E∨.TC=100;

E2’.FC=103;

E2’.TC=104;）查看語(yǔ)義子程序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)}目前二十頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)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目前二十一頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)例2：翻譯布爾表達(dá)式A∧B∨C≤D，并把其值保存到一個(gè)臨時(shí)變量中（用四元式表示，從100號(hào)開始）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………………表達(dá)式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;}在前面文法的基礎(chǔ)上增加如下一條四元式：目前二十二頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)標(biāo)號(hào)語(yǔ)句和GOTO語(yǔ)句到四元式的翻譯標(biāo)號(hào)語(yǔ)句和GOTO語(yǔ)句的文法(1)Sg→gotoLabel(2)S→LabelS(3)Label→i:符號(hào)表名字定義種屬類型……地址……L0LAB……r……目前二十三頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定義種屬類型……地址………………………………L11LAB……k源代碼：四元式：k(～,～,～,～)…gotoL2符號(hào)表目前二十四頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定義種屬類型……地址………………………………L11LAB……k源代碼：四元式：…k(～,～,～,～)…m(j,,,k)…n(j,,,k)gotoL2符號(hào)表目前二十五頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定義種屬類型……地址………………………………L11LAB……kL20LAB

p

源代碼：四元式：……k(～,～,～,～)…m(j,,,k)…n(j,,,k)gotoL2p(j,,,0)符號(hào)表目前二十六頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定義種屬類型……地址………………………………L11LAB……kL20LAB

q

源代碼：四元式：………k(～,～,～,～)…m(j,,,k)…n(j,,,k)gotoL2p(j,,,0)符號(hào)表q(j,,,p)目前二十七頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定義種屬類型……地址………………………………L11LAB……kL20LAB

r

源代碼：四元式：………k(～,～,～,～)…m(j,,,k)……n(j,,,k)gotoL2p(j,,,0)符號(hào)表q(j,,,p)r(j,,,q)目前二十八頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)gotoL1…gotoL2…gotoL2…L1:S1…gotoL1……L2:S2……名字定義種屬類型……地址………………………………L11LAB……kL2

1LAB

t

源代碼：四元式：………k(～,～,～,～)…m(j,,,k)………n(j,,,k)gotoL2p(j,,,t)符號(hào)表q(j,,,t)r(j,,,t)t(～,～,～,～)目前二十九頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)標(biāo)號(hào)語(yǔ)句和GOTO語(yǔ)句的語(yǔ)義子程序(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}目前三十頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)條件語(yǔ)句、while語(yǔ)句和復(fù)合語(yǔ)句到四元式的翻譯條件語(yǔ)句、while語(yǔ)句和復(fù)合語(yǔ)句的語(yǔ)法（1）S→ifEthenS│ifEthenSelseS│whileEdoS│beginLend│A（2）L→L;S│S說(shuō)明：S表示語(yǔ)句；E表示布爾表達(dá)式；A表示賦值語(yǔ)句；L表示語(yǔ)句串。引入二個(gè)新的符號(hào)屬性①S.Chain:轉(zhuǎn)出內(nèi)層語(yǔ)句S的各四元式所形成的鏈的鏈頭。②X.Quad:相應(yīng)于X符號(hào)的四元式串的第一個(gè)四元式編號(hào)。目前三十一頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)

為了在翻譯過(guò)程中能及時(shí)地進(jìn)行“拉鏈”和“回填”處理，我們將其文法改寫成如下形式：（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改寫前的四元式：查看語(yǔ)句翻譯模式目前三十二頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)

語(yǔ)義子程序如下：(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;}返回查看翻譯框架目前三十三頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)例3：將下列語(yǔ)句翻譯成四元式的形式（假設(shè)編號(hào)從100開始）while(A<B)doif(C>D)thenx:=y+z;查看語(yǔ)義子程序句型:while(A<B)doif(C>D)thenx:=y+z;=>

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

NXQ

100(5)W→while{W.Quad:=NXQ;}目前三十四頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序②句型:W(A<B)doif(C>D)thenx:=y+z;=>

WEdoif(C>D)thenx:=y+z;執(zhí)行：歸約布爾表達(dá)式；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

目前三十五頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序③句型:WEdoif(C>D)thenx:=y+z;=>

Wdif(C>D)thenx:=y+z;執(zhí)行：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;}目前三十六頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序④句型:Wdif(C>D)thenx:=y+z;=>

WdifEthenx:=y+z;執(zhí)行：歸約布爾表達(dá)式；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目前三十七頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序⑤句型:Wd

ifEthenx:=y+z;=>

Wd

Cx:=y+z;執(zhí)行：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;}目前三十八頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)⑥句型:WdCx:=y+z;=>

WdCA;執(zhí)行：歸約賦值語(yǔ)句；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目前三十九頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序⑦句型:WdCA;=>

WdCS1;執(zhí)行：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目前四十頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序⑧句型:Wd

CS1;=>

Wd

S2;執(zhí)行：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);}目前四十一頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序⑨句型:WdS2;=>

S;執(zhí)行：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目前四十二頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序⑩句型:S;=>

L;執(zhí)行：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;}目前四十三頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序⑾句型:L;=>

LS執(zhí)行：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);}目前四十四頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)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上面語(yǔ)句翻譯成四元式的形式為：思考題：上面語(yǔ)句后面少分號(hào)，結(jié)果有是如何呢？目前四十五頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)例4：將下列語(yǔ)句翻譯成四元式的形式（假設(shè)編號(hào)從100開始）while(A∧B∨C)dobegink:=k+1;if(m>n)thenx:=x+y;elsex:=x-y;y:=y*2;end思考題目：給出詳細(xì)的翻譯步驟？目前四十六頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)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目前四十七頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)總結(jié)如何分割一個(gè)產(chǎn)生式如何為一個(gè)產(chǎn)生式編寫語(yǔ)義子程序理解語(yǔ)句的執(zhí)行流程。自左向右掃描，理解語(yǔ)句的翻譯框架。對(duì)后面四元式的轉(zhuǎn)移目標(biāo)（四元式編號(hào)）設(shè)置屬性保存。拉（并）鏈的時(shí)機(jī)?；靥畹臅r(shí)機(jī)。設(shè)置文法符號(hào)的屬性值以便保存：①后面四元式的轉(zhuǎn)移目標(biāo)；②待回填的四元式編號(hào)；③需要繼承的屬性。如果需要并鏈，則用Merge函數(shù)。如果需要回填，則用BackPatch過(guò)程。如果需要產(chǎn)生四元式，則用Gen過(guò)程。返回目前四十八頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)For循環(huán)語(yǔ)句到四元式的翻譯三種for循環(huán)語(yǔ)句的文法：S→fori:=E1stepE2untilE3doS1S→fori:=E1untilE2stepE3doS1S→for(E1;E2;E3)S1目前四十九頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)語(yǔ)句

fori:=E1stepE2untilE3doS1的翻譯執(zhí)行流程如下：語(yǔ)義解釋如下：i:=E1Si:=i+E2i≤E3

YNi:=E1gotooveragain:i:=i+E2over:ifi≤E3thenbeginS1;gotoagainend總結(jié)目前五十頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)i:=E1gotooveragain:i:=i+E2over:ifi≤E3thenbeginS1;gotoagainend語(yǔ)句

fori:=E1stepE2untilE3doS1的翻譯框架E1的四元式代碼i:=E1(j,,,over)i:=i+E2(j≤,i,E3,L)(j,,,again)(j,,,0)E2的四元式代碼againE3的四元式代碼overS1的四元式代碼L總結(jié)目前五十一頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)E1的四元式代碼i:=E1(j,,,over)i:=i+E2E2的四元式代碼(j≤,i,E3,L)E3的四元式代碼(j,,,again)(j,,,0)S1的四元式代碼overagainL總結(jié)(4)A→fori:=E1step(3)B→AE2until(2)C→BE3do(1)S→CS1S.Chain產(chǎn)生式S→fori:=E1stepE2untilE3doS1的分割返回目前五十二頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)E1的四元式代碼i:=E1(j,,,0)i:=i+E2E2的四元式代碼(j≤,i,E3,L)E3的四元式代碼(j,,,again)(j,,,0)S1的四元式代碼總結(jié)返回(4)A→fori:=E1step語(yǔ)句

fori:=E1stepE2untilE3doS1的語(yǔ)義子程序｛A.Place:=LookUp(i.Name);Gen(:=,E1.Place,,A.Place);A.Chain:=NXQ;Gen(j,,,0);A.Quad:=NXQ;｝A.ChainA.QuadNXQ目前五十三頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)總結(jié)返回語(yǔ)句

fori:=E1stepE2untilE3doS1的語(yǔ)義子程序(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目前五十四頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)總結(jié)返回語(yǔ)句

fori:=E1stepE2untilE3doS1的語(yǔ)義子程序(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目前五十五頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)總結(jié)返回語(yǔ)句

fori:=E1stepE2untilE3doS1的語(yǔ)義子程序(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目前五十六頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)(4)A→fori:=E1step(3)B→AE2until(2)C→BE3do(1)S→CS1語(yǔ)句

fori:=E1stepE2untilE3doS1的語(yǔ)義子程序｛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);｝返回目前五十七頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)例５：將下列語(yǔ)句翻譯成四元式的形式（編號(hào)從１００開始）forI:=a+2*bstepc+duntiln+mdox:=y+z查看語(yǔ)義子程序①句型:forI:=a+2*bstepc+duntiln+mdox:=y+z=>forI:=E1stepc+duntiln+mdox:=y+z執(zhí)行：歸約算術(shù)表達(dá)式；NXQ=102屬性：NXQ

100（*，２，b，T1）101（+，a，T1，T2）102目前五十八頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)②句型:forI:=E1stepc+duntiln+mdox:=y+z=>Astepc+duntiln+mdox:=y+z執(zhí)行：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

查看語(yǔ)義子程序目前五十九頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序③句型:Astepc+duntiln+mdox:=y+z=>AstepE2untiln+mdox:=y+z執(zhí)行：歸約算術(shù)表達(dá)式；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目前六十頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)④句型:AstepE2untiln+mdox:=y+z=>Buntiln+mdox:=y+z執(zhí)行：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查看語(yǔ)義子程序目前六十一頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序⑤句型:Buntiln+mdox:=y+z=>BuntilE3dox:=y+z執(zhí)行：歸約算術(shù)表達(dá)式；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目前六十二頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序句型:BuntilE3dox:=y+z=>Cdox:=y+z執(zhí)行：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目前六十三頁(yè)\總數(shù)八十三頁(yè)\編于十八點(diǎn)查看語(yǔ)義子程序⑦句型:Cdox:=y+z=>CdoS1執(zhí)行：歸約賦值語(yǔ)句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