pl-0編譯程序?qū)嵺`-原理教程

序 第一部分PL/0語(yǔ)言及其編譯 PL/0語(yǔ)言介 PL/0語(yǔ)言編譯 第二部分上機(jī)實(shí)踐要 第三部分PL/0語(yǔ)言編譯器源程 PL/0語(yǔ)言源程 PL/0語(yǔ)言編譯器源程 編譯原理實(shí)踐序適中的語(yǔ)言來(lái)設(shè)計(jì)一個(gè)相對(duì)完整、獨(dú)立編譯器。設(shè)計(jì)某一規(guī)模適中的語(yǔ)言的編譯器該編譯器不僅涉及編譯程序的各個(gè)階為了使學(xué)生能盡早動(dòng)手實(shí)踐建議把實(shí)踐分成三部分首先閱讀本第PL/0便對(duì)PL/0編譯程序有個(gè)初步的印象。其次要認(rèn)真閱讀理解第三部分所給出的PL/0編譯器源程序，使上一階段的初步印象得以加深、具體化。最后按照第二PL/0第一部分PL/0語(yǔ)言及其編譯PL/0語(yǔ)言PL/0程序設(shè)計(jì)語(yǔ)言是一個(gè)較簡(jiǎn)單的語(yǔ)言，它以賦值語(yǔ)句為基礎(chǔ)，構(gòu)造概念有順序、條件和重復(fù)（循環(huán)）三種。PL/0（可以嵌套）與調(diào)用且有局部變量說(shuō)明。PL/0該類型的常量和變量當(dāng)然PL/0也具有通常的算術(shù)運(yùn)算和關(guān)系運(yùn)算具體的PL/0PL/0語(yǔ)言的語(yǔ)法..==,;,;;;;;+-項(xiàng)=<>++-項(xiàng)項(xiàng)**/(()PL/0語(yǔ)言編譯PL/01-11-1PL/0詞法分PL/0跳過(guò)分隔符（如空格，回車，制表符begin，end，if，whilesymSYM_IDENTIFIER。NUM，symsym則分別被賦值為ES，SYM_LEQ，SYM_GEQ相關(guān)過(guò)程（函數(shù)）getsym()，getch()，getch()為獲取單個(gè)字符的語(yǔ)法分PL/0FOLLOW非終結(jié)符ifbegin.identcallbeginif.;odd+-(identthen+-(ident.;)Rendthen項(xiàng)identnumber.;)R+-endthenidentnumber.;)R+-*/endthenR不難證明，PL/0LL（1）（ST（S，則：將每一個(gè)圖按下面的規(guī)則（3）-（7）對(duì)應(yīng)：beginT(S1);T(S2);...;T(Sn)對(duì)應(yīng)：casecasechof ifchinL1thenT(S1)elseL1:T(S1); ifchinL2thenT(S2)elseL2: ifchinLnthenT(Sn)Ln: Li∈FIRST（Si，chSS對(duì)應(yīng)：whilechinLdoAAAAxx對(duì)應(yīng)：ifch==xthenread(ch)elseblock(),constdeclaration(),vardeclaration(),statement(),condition(),expression(),term(),factor()等。1-項(xiàng)項(xiàng)1-2語(yǔ)義分PL/0是否存在標(biāo)識(shí)符先未的情況是否存在己的標(biāo)識(shí)符的錯(cuò) 是否存在一般標(biāo)識(shí)符的多 代碼生PL/0編譯程序不僅完成通常的詞法分析、語(yǔ)法分析，而且還產(chǎn)生中間代碼和想有臺(tái)適合PL/0程序運(yùn)行的計(jì)算機(jī)，我們稱之為PL/0處理機(jī)。PL/0處理機(jī)順解釋程序就看成是PL/0機(jī)硬件，把解釋執(zhí)行看成是PL/0的硬件執(zhí)行，那么我們所做的工作：由PL/0源語(yǔ)言程序到PL/0機(jī)器指令的變換，就是一個(gè)完整的編譯PL/0PL/0 /* /*將變量值置于棧頂 /*將棧頂?shù)闹蒂x與某變量 /*用于過(guò)程調(diào)用的指令 /*在數(shù)據(jù)棧中分配存貯空間JMP, /*if,while /*一組算術(shù)或邏輯運(yùn)算指令FLA其中，f,l,aFLa—— —— ——————2-1PL/0上表中，層次差為變量名或過(guò)程名和之間的靜態(tài)層次差別，程序地codeXYopZ（op，將被翻譯成下面的目標(biāo)代碼（100）fLa—————ifwhilePL/0回ifCthenWhileCdoCJPC--SL1:L1:CJPC–S L2:...表2- if-while語(yǔ)句目標(biāo)代碼生成模相關(guān)過(guò)程（函數(shù)）有：gen()，其任務(wù)是把三個(gè)參數(shù)f、l、a組裝成一條目標(biāo)指令并存放于code數(shù)組中，增加CX的值，CX表示下一條即將生成的目標(biāo)指代碼執(zhí)PL/0PL/0PL/0址寄存器組成。程序（目標(biāo)代碼）存貯稱為ode，由編譯程序裝入，在目標(biāo)代S（元，并用結(jié)果值代替原來(lái)的運(yùn)算對(duì)象。棧頂元的地址（下標(biāo)）記在棧頂寄存器TIP一條將取出的指令。棧S內(nèi)順序疊起來(lái)，每個(gè)過(guò)程，除用戶定義的變量外，還應(yīng)當(dāng)有它自己的信止后，為了恢復(fù)原來(lái)程序的執(zhí)行，這兩個(gè)地址都是必須的。我們可將這兩個(gè)值作為位于該過(guò)程數(shù)據(jù)區(qū)的式隱式局部變量我們把它們分別稱為返回地址（returnaddress）RA和動(dòng)態(tài)鏈（dynamiclink）DL。動(dòng)態(tài)鏈的頭，即分B（解釋為了正確地存取數(shù)據(jù)，解釋程序需將某個(gè)修正量加到相應(yīng)的數(shù)據(jù)區(qū)的址上去。若變量是局部于當(dāng)前正在解釋的過(guò)程，則此址由寄存器B給出，否則，例如，假定有過(guò)程A，B，C，其中過(guò)程C的說(shuō)明局部于過(guò)程B，而過(guò)程B的說(shuō)明局部于過(guò)程A，程序運(yùn)行時(shí)，過(guò)程A調(diào)用過(guò)程B，過(guò)程B則調(diào)用過(guò)程C，過(guò)CB，如下圖所示：ABAAB C圖2- 過(guò)程說(shuō)明嵌套 過(guò)程調(diào)用 表示A調(diào)用從靜態(tài)的角度我們可以說(shuō)A是在第一層說(shuō)明的，B是在第二層說(shuō)明的，C則是在第三層說(shuō)明的。若在B中存取A中說(shuō)明的變量a，由于編譯程序只知道A，B間的靜態(tài)層差為1，如果這時(shí)沿著動(dòng)態(tài)鏈下降一步，將導(dǎo)致對(duì)C的局部變量的操各個(gè)數(shù)據(jù)區(qū)連接起來(lái)。我們稱之為靜態(tài)鏈（staticlink）SL。這樣，編譯程序A、BC ABCB有了以上認(rèn)識(shí)，我們就不難明白PL/0源程序的目標(biāo)代碼是如何被解釋執(zhí)行XYopZ（2.4PL/0stepS[++T]←S[base(level_diff_Y)+YstepS[++T]←S[base(level_diff_Z)+ZYstep3,stepS[T]←S[T]opS[T+YZ“op”stepS[base(level_diff_X)+addr_X]←Xstep6,interpret()錯(cuò)誤診斷處任何輸入序列都不會(huì)引起編譯程序的一切按語(yǔ)言定義為的結(jié)構(gòu)，都能被發(fā)現(xiàn)和標(biāo)志出來(lái)PL/0（稱為同步符號(hào)）的最好選擇就是關(guān)鍵字。PL/0的每一種構(gòu)造語(yǔ)句以begin、ifwhilevar、constprocedure輸入正文，直到下一個(gè)可以正確地跟隨當(dāng)前正在分析的句子結(jié)構(gòu)的符號(hào)為）testtestn，表示有關(guān)錯(cuò)誤的診斷號(hào)：voidtest(symsets1,symsets2,intn){symsetif(!inset(sym,{s=uniteset(s1,s2);while(!inset(sym,}}如“;”P(pán)L/0分析程序中復(fù)合語(yǔ)句分析的一小段。它的效果等于關(guān)鍵字前漏掉的分號(hào)。statbegsysif(sym=={set1=createset(SYM_SEMICOLON,SYM_END,SYM_NULL);set=uniteset(set1,fsys);while(sym==SYM_SEMICOLON||inset(sym,{if(sym=={}{}}//whileif(sym=={}{error(17);//';'or'end'}}相關(guān)過(guò)程：test(),inset(),createset,uniteset(),符號(hào)表管程的地址及層次。（PL/0dxdx3，含三個(gè)變量RA，DL和SL。其本所提供的PL/0編譯程序包括詞法分析、語(yǔ)法分析、錯(cuò)誤診碼listcode()完成。注意，每個(gè)分程序（過(guò)程）的第一PL/0第二部分機(jī)實(shí)踐要PL/0100（BNF有關(guān)修改后的PL/0編譯/解釋器的說(shuō)明。詳細(xì)說(shuō)明你的編譯器是如何編譯新的PL/0語(yǔ)言程序的。你的程序中最的部分，以及你（1（270注釋（5注釋由(*和*)BNFvar_option→ε|varvar_decl_list→var_decl|var_decl_listvar_declvar_decl→ident_list:data_typedata_type→integer|Pascal能夠使用布爾常量truefalsePL/0Pascal布爾表達(dá)式可以比較大?。篺alse布爾表達(dá)式的短路計(jì)算（5（2，除數(shù)組（10注意數(shù)組可以由其它的數(shù)組來(lái)構(gòu)造因而必須考慮數(shù)組的情況。data_type→integer|boolean|array[const..const]ofconst→ident|語(yǔ)言中允許有數(shù)組說(shuō)明對(duì)數(shù)組元素賦值在表達(dá)式中數(shù)組元素。為了便于解釋執(zhí)行，可能要增加新的PL/0器操作指令。參數(shù)（10）Pascal，采用值-結(jié)果方式傳遞（var函數(shù)（10）Pascalelserepeat（5forPascalC（5循環(huán)（5）記錄（結(jié)構(gòu)）,Pascal（10更有力的語(yǔ)法錯(cuò)誤恢復(fù)機(jī)制（20分離解釋和編譯器（5上面的這些要求有時(shí)會(huì)互相影響參數(shù)就應(yīng)該能處理其相互組合的情況，如布爾型數(shù)組（包括數(shù)組、布遞等。PL/0選做題：此題不計(jì)入總分，僅做為學(xué)生在有余力的情況下的進(jìn)一步練習(xí)。PL/0PascalPascal第三部分PL/0語(yǔ)言編譯器源程一個(gè)例PL/0語(yǔ)言源程PL/0constm=7,n=85;varx,y,z,q,r;proceduremultiply;vara,b;a:=x;b:=y;z:=0;whileb>0doifoddbthenz:=z+a;a:=2*a;b:=b/2;proceduredivide;varw;r:=x;q:=0;w:=y;whilew>ydoq:=2*q;w:=w/2;ifw<=rthenr:=r-w;q:=q+procedure;varf,g;f:=g:=whilef<>gdoiff<gtheng:=g–f;ifg<fthenf:=f–x:=m;y:=n;callmultiply;x:=25;y:=3;calldivide;x:=34;y:=36;call;生成的代碼（片段PL/0 --allocateLOD -- --LOD -- -- -- --LOD -- -- 12--

a:=b:=yz:=b> 29--ifb<=0thengotoLOD -- --

20--ifnot(odd(b))gotoLOD -- LOD -- -- -- --LOD -- -- --LOD --

z:=z+a:=2*0202-202-/04-b09-9

29 --PL/0語(yǔ)言編譯器源程PL/0語(yǔ)言編譯器源程序包括如下C程序文件，PL0.h、PL0.c、set.h和set.c PL0.h*************/#include<stdio.h>#define //numberoflengthofidentifierumnumberofdigitsinumnumberofsymbolsinlengthofumumdepthofnestingsizeofcodeumnumberofumenum{enum{ID_CONSTANT,ID_VARIABLE,enum{LIT,OPR,LOD,STO,CAL,INT,JMP,enum{OPR_RET,OPR_NEG,OPR_ADD,OPR_MIN,OPR_MUL,OPR_DIV,OPR_ODD,OPR_EQU,OPR_NEQ,OPR_LES,OPR_LEQ,OPR_GTR,typedef{intf;//functioncodeintl;//levelinta;//displacement}char*err_msg[]={01whenexpecting2beanumbertofollow3bean'='tofollowthe45"Missing','or6"Incorrectprocedure7"Statement8"Followthestatementisanincorrect9"'.'"';'"Undeclared"Illegal"':='"Theremustbeanidentifiertofollowthe"Aconstantorvariablecannotbe"'then'"';'or'end'"'do'"Incorrect"Relativeoperators"Procedureidentifiercannotbeinan"Missing"Thesymbolcannotbefollowedbya"Thesymbolcannotbeasthebeginningofan"Thenumberistoo"Therearetoomanycharch; //lastcharacterread //lastsymbolcharid[MAXIDLEN+1];//lastidentifierread //lastnumberread //character //linelength //indexofcurrentinstructiontobegenerated. level=0; tx=0;charline[80];instructionchar*word[NRW+1]{"",/*placeholder"begin","call","const","do","odd","procedure","then","var",intwsym[NRW+1]{SYM_NULL,SYM_BEGIN,SYM_CALL,SYM_CONST,SYM_DO,SYM_END,SYM_IF,SYM_ODD,SYM_PROCEDURE,SYM_THEN,SYM_VAR,SYM_WHILEintssym[NSYM+1]{SYM_NULL,SYM_PLUS,SYM_MINUS,SYM_TIMES,SYM_LPAREN,SYM_RPAREN, MA,SYM_PERIOD,charcsym[NSYM+1]{'','+','-','*','/','(',')','=',',','.',#define char*mnemonic[MAXINS]{"LIT","OPR","LOD","STO","CAL","INT","JMP",typedef{charname[MAXIDLEN+1]; }comtabtypedef{ name[MAXIDLEN+1]; shortlevel;shortaddress;}FILE*//EOF SET.h#ifndefSET_H#definetypedefstruct{instructsnode*}snode,symsetphi,declbegsys,statbegsys,facbegsys,relset;symsetcreateset(intdata,.../*SYM_NULL*/);voiddestroyset(symsetsymsetuniteset(symsets1,symsets2);intinset(inem,symsets);//EOF SET.c#include<stdlib.h>#include<stdio.h>#include<stdarg.h>#include"set.h"symsetuniteset(symsets1,symset{symsets;snode*s=p=(snode*)malloc(sizeof(snode));while(s1&&s2){p->next=(snode*)malloc(sizeof(snode));p=p->next;if(s1->elem<s2-{p->elem=s1->elem;s1=s1->next;}{p->elem=s2->elem;s2=s2->next;}}while{p->next=(snode*)malloc(sizeof(snode));p=p->next;p->elem=s1->elem;s1=s1->next;}while{p->next=(snode*)malloc(sizeof(snode));p=p->next;p->elem=s2->elem;s2=s2->next;}p->next=NULL;returns;}//voidsetinsert(symsets,in{snode*p=s;snode*q;while(p->next&&p->next->elem<{p=p-}q=(snode*)malloc(sizeof(snode));q->elem=elem;q->next=p->next;p->next=q;}//symsetcreateset(inem,.../*SYM_NULL{va_listlist;symsets;s=(snode*)malloc(sizeof(snode));s->next=NULL;va_start(list,elem);while(elem){setinsert(s,elem=va_arg(list,}returns;}//voiddestroyset(symset{snode*while{p=s=s->next;}}//intinset(inem,symset{s=s-while(s&&s->elem<elem)s=s->next;if(s&&s->elem==elem)return1;return}////EOF PL0.c//pl0compilersource#include<stdio.h>#include<stdlib.h>#include<string.h>#include<ctype.h>#include"set.h"#include"pl0.h"http://printerrormessage.voiderror(n){int for(i=1;i<=cc-1;i++)printf("");printf("Error%3d:%s\n",n,err_msg[n]);}//voidgetch(void){if(cc=={if{ }ll=cc=0; ",cx);while(!feof(infile)&&(ch={printf("%c",ch);line[++ll]=ch;}//whileline[++ll]='}ch=}////getsasymbolfrominputstream.voidgetsym(void){inti,chara[MAXIDLEN+while(ch=='if{//symbolisawordoranidentifier.k=0;{if(k<a[k++]=ch;}while(isalpha(ch)||isdigit(ch));a[k]=0;strcpy(id,a);word[0]=id;i=NRW;while(strcmp(id,word[i--]));if(++i)sym=wsym[i];//symbolisawordsym= //symbolisan}elseif{//symbolisanumber.k=num=0;sym={num=num*10+ch-'0';}while(isdigit(ch));if(k>MAXNUMLEN) //Thenumberistoo}elseif(ch=={if(ch=={sym= ES;//:=}{sym= //}}elseif(ch=={if(ch=={sym=SYM_GEQ; //>=}{sym= //}}elseif(ch=={if(ch=={sym=SYM_LEQ; //<=}elseif(ch=={sym=SYM_NEQ; //<>}{sym= //}}{//othertokensi=NSYM;csym[0]=while(csym[i--]!=ch);if(++i){sym=ssym[i];}{printf("FatalError:Unknowncharacter.\n");}}}////generates(assembles)aninstruction.voidgen(intx,inty,intz){if(cx>{printf("FatalError:Programtoolong.\n");}code[cx].f=code[cx].l=y;code[cx++].a=z;}////testsiferroroccursandskipsallsymbolsthatdonotbelongstos1ors2.voidtest(symsets1,symsets2,intn){symsetif(!inset(sym,{s=uniteset(s1,s2);while(!inset(sym,}}//intdx; //dataallocationindex//enterobject(constant,variableorprocedre)intotable.voidenter(intkind){mask*strcpy(table[tx].name,id);table[tx].kind=kind;switch(kind){caseif(num>{error(25);//Thenumberistoogreat.num=0;}table[tx].value=num;casemk=(mask*)&table[tx];mk->level=level;mk->address=dx++;casemk=(mask*)&table[tx];mk->level=level;}//}////position(char*id){inti;strcpy(table[0].name,id);i=tx+1;while(strcmp(table[--i].name,id)!=0);returni;}//voidconstdeclaration(){if(sym=={if(sym==SYM_EQU||sym {if(sym error(1);//Found':='whenexpecting'='.if(sym=={}{error(2);//Theremustbeanumbertofollow}}{error(3);//Theremustbean'='tofollowthe}}error(4);//Theremustbeanidentifiertofollow'const','var',or}//voidvardeclaration(void){if(sym=={}{error(4);//Theremustbeanidentifiertofollow'const','var',or}}//voidlistcode(intfrom,intto){intfor(i=from;i<to;{}}//voidfactor(symsetfsys){voidexpression();inti;symsettest(facbegsys,fsys,24);//Thesymbolcannotbeasthebeginningofanwhile(inset(sym,{if(sym=={if((i=position(id))=={error(11);//Undeclared}{switch{mask*mk;caseID_CONSTANT:gen(LIT,0,table[i].value);casemk=(mask*)gen(LOD,level-mk->level,mk->address);caseerror(21);//Procedureidentifiercannotbeinanexpression.}//}}elseif(sym=={if(num>{error(25);//Thenumberistoogreat.num=0;}gen(LIT,0,num);}elseif(sym=={set=uniteset(createset(SYM_RPAREN,SYM_NULL),fsys);if(sym=={}{error(22);//Missing}}test(fsys,createset(SYM_LPAREN,SYM_NULL),}//}//{{voidterm(symsetfsys){intmulop;symsetset=uniteset(fsys,createset(SYM_TIMES,SYM_SLASH,SYM_NULL));while(sym==SYM_TIMES||sym=={mulop=sym;if(mulop=={gen(OPR,0,}{gen(OPR,0,}}//while}//voidexpression(symsetfsys){intaddop;symsetset=uniteset(fsys,createset(SYM_PLUS,SYM_MINUS,SYM_NULL));if(sym==SYM_PLUS||sym==SYM_MINUS){addop=sym;if(addop=={gen(OPR,0,}}}while(sym==SYM_PLUS||sym=={addop=sym;if(addop=={gen(OPR,0,}{gen(OPR,0,}}//}//voidcondition(symsetfsys){intrelop;symsetif(sym=={gen(OPR,0,6);}{set=uniteset(relset,fsys);if(!inset(sym,{}relop=sym;switch(relop){casegen(OPR,0,caseSYM_NEQ:gen(OPR,0,caseSYM_LES:gen(OPR,0,caseSYM_GEQ:gen(OPR,0,caseSYM_GTR:gen(OPR,0,caseSYM_LEQ:gen(OPR,0,}//}//}//}//voidstatement(symsetfsys){inti,cx1,cx2;symsetset1,if(sym=={//variableassignmentmask*mk;if(!(i={error(11);//Undeclared}elseif(table[i].kind!={error(12);//Illegali=}if(sym {}{error(13);//':='}mk=(mask*)&table[i];if(i){gen(STO,level-mk->level,mk-}}elseif(sym=={//procedurecallif(sym!={error(14);//Theremustbeanidentifiertofollowthe}{if(!(i={error(11);//Undeclared}elseif(table[i].kind=={mask*mk=(mask*)gen(CAL,level-mk->level,mk-}{error(15);//Aconstantorvariablecannotbe}}}elseif(sym=={//ifstatementset1=createset(SYM_THEN,SYM_DO,SYM_NULL);set=uniteset(set1,fsys);if(sym=={}{error(16);//'then'}cx1=cx;gen(JPC,0,0);code[cx1].a=}elseif(sym=={//set1=createset(SYM_SEMICOLON,SYM_END,SYM_NULL);set=uniteset(set1,fsys);while(sym==SYM_SEMICOLON||inset(sym,{if(sym=={}{}}//whileif(sym=={}{error(17);//';'or'end'}}elseif(sym=={//whilestatementcx1=cx;set1=createset(SYM_DO,SYM_NULL);set=uniteset(set1,fsys);cx2=cx;gen(JPC,0,0);if(sym=={}{error(18);//'do'}gen(JMP,0,cx1);code[cx2].a=}test(fsys,phi,}//voidblock(symsetfsys){intcx0;//initialcodeindexmask*mk;intblock_dx;intsavedTx;symsetset1,dx=3;block_dx=dx;mk=(mask*)mk->address=cx;gen(JMP,0,0);if(level>{error(32);//Therearetoomany}{if(sym=={//constantdeclarations{while(sym== {}if(sym=={}{error(5);//Missing','or}}while(sym==}//if(sym=={//variabledeclarations{while(sym {}if(sym=={}{error(5);//Missing','or}}while(sym== block=}//while(sym=={//proceduredeclarationsif(sym=={}{error(4);//Theremustbeanidentifiertofollow'const',or}if(sym=={}{error(5);//Missing','or}savedTx=tx;set1=createset(SYM_SEMICOLON,SYM_NULL);set=uniteset(set1,fsys);tx=savedTx;if(sym=={set1=createset(SYM_IDENTIFIER,SYM_PROCEDURE,set=uniteset(statbegsys,set1);test(set,fsys,6);}{error(5);//Missing','or}}//set1=createset(SYM_IDENTIFIER,SYM_NULL);set=uniteset(statbegsys,set1);test(set,declbegsys,7);}while(inset(sym,code[mk->address].a=cx;mk->address=cx;cx0=gen(INT,0,set1=createset(SYM_SEMICOLON,SYM_END,SYM_NULL);set=uniteset(set1,fsys);gen(OPR,0,OPR_RET);//test(fsys,phi,8);//testforerror:Followthestatementisanincorrectlistcode(cx0,}//intbase(intstack[],intcurrentLevel,intlevelDiff){intb=currentLevel;while(levelDiff--)b=stack[b];returnb;}////interpretsandexecutescodes.voidinterpret(){intpc; //programcounterintstack[STACKSIZE];int //topofintb; //program,base,andtop-stackregisterinstructioni;//instructionregisterprintf("BeginexecutingPL/0program.\n");pc=0;b=top=stack[1]=stack[2]=stack[3]=0;{i=code[pc++];switch(i.f){casestack[++top]=i.a;caseswitch(i.a)//{casetop=b-pc=stack[top+3];b=stack[top+2];casestack[top]=-stack[top];caseOPR_ADD:stack[top]+=stack[top+1];casestack[top]-=stack[top+1];caseOPR_MUL:stack[top]*=stack[top+1];caseOPR_DIV:if(stack[top+1]=={fprintf(stderr,"Runtim