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

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