pl-0编译程序实践-原理教程

序 第一部分PL/0语言及其编译 PL/0语言介 PL/0语言编译 第二部分上机实践要 第三部分PL/0语言编译器源程 PL/0语言源程 PL/0语言编译器源程 编译原理实践序适中的语言来设计一个相对完整、独立编译器。设计某一规模适中的语言的编译器该编译器不仅涉及编译程序的各个阶为了使学生能尽早动手实践建议把实践分成三部分首先阅读本第PL/0便对PL/0编译程序有个初步的印象。其次要认真阅读理解第三部分所给出的PL/0编译器源程序，使上一阶段的初步印象得以加深、具体化。最后按照第二PL/0第一部分PL/0语言及其编译PL/0语言PL/0程序设计语言是一个较简单的语言，它以赋值语句为基础，构造概念有顺序、条件和重复（循环）三种。PL/0（可以嵌套）与调用且有局部变量说明。PL/0该类型的常量和变量当然PL/0也具有通常的算术运算和关系运算具体的PL/0PL/0语言的语法..==,;,;;;;;+-项=<>++-项项**/(()PL/0语言编译PL/01-11-1PL/0词法分PL/0跳过分隔符（如空格，回车，制表符begin，end，if，whilesymSYM_IDENTIFIER。NUM，symsym则分别被赋值为ES，SYM_LEQ，SYM_GEQ相关过程（函数）getsym()，getch()，getch()为获取单个字符的语法分PL/0FOLLOW非终结符ifbegin.identcallbeginif.;odd+-(identthen+-(ident.;)Rendthen项identnumber.;)R+-endthenidentnumber.;)R+-*/endthenR不难证明，PL/0LL（1）（ST（S，则：将每一个图按下面的规则（3）-（7）对应：beginT(S1);T(S2);...;T(Sn)对应：casecasechof ifchinL1thenT(S1)elseL1:T(S1); ifchinL2thenT(S2)elseL2: ifchinLnthenT(Sn)Ln: Li∈FIRST（Si，chSS对应：whilechinLdoAAAAxx对应：ifch==xthenread(ch)elseblock(),constdeclaration(),vardeclaration(),statement(),condition(),expression(),term(),factor()等。1-项项1-2语义分PL/0是否存在标识符先未的情况是否存在己的标识符的错 是否存在一般标识符的多 代码生PL/0编译程序不仅完成通常的词法分析、语法分析，而且还产生中间代码和想有台适合PL/0程序运行的计算机，我们称之为PL/0处理机。PL/0处理机顺解释程序就看成是PL/0机硬件，把解释执行看成是PL/0的硬件执行，那么我们所做的工作：由PL/0源语言程序到PL/0机器指令的变换，就是一个完整的编译PL/0PL/0 /* /*将变量值置于栈顶 /*将栈顶的值赋与某变量 /*用于过程调用的指令 /*在数据栈中分配存贮空间JMP, /*if,while /*一组算术或逻辑运算指令FLA其中，f,l,aFLa—— —— ——————2-1PL/0上表中，层次差为变量名或过程名和之间的静态层次差别，程序地codeXYopZ（op，将被翻译成下面的目标代码（100）fLa—————ifwhilePL/0回ifCthenWhileCdoCJPC--SL1:L1:CJPC–S L2:...表2- if-while语句目标代码生成模相关过程（函数）有：gen()，其任务是把三个参数f、l、a组装成一条目标指令并存放于code数组中，增加CX的值，CX表示下一条即将生成的目标指代码执PL/0PL/0PL/0址寄存器组成。程序（目标代码）存贮称为ode，由编译程序装入，在目标代S（元，并用结果值代替原来的运算对象。栈顶元的地址（下标）记在栈顶寄存器TIP一条将取出的指令。栈S内顺序叠起来，每个过程，除用户定义的变量外，还应当有它自己的信止后，为了恢复原来程序的执行，这两个地址都是必须的。我们可将这两个值作为位于该过程数据区的式隐式局部变量我们把它们分别称为返回地址（returnaddress）RA和动态链（dynamiclink）DL。动态链的头，即分B（解释为了正确地存取数据，解释程序需将某个修正量加到相应的数据区的址上去。若变量是局部于当前正在解释的过程，则此址由寄存器B给出，否则，例如，假定有过程A，B，C，其中过程C的说明局部于过程B，而过程B的说明局部于过程A，程序运行时，过程A调用过程B，过程B则调用过程C，过CB，如下图所示：ABAAB C图2- 过程说明嵌套 过程调用 表示A调用从静态的角度我们可以说A是在第一层说明的，B是在第二层说明的，C则是在第三层说明的。若在B中存取A中说明的变量a，由于编译程序只知道A，B间的静态层差为1，如果这时沿着动态链下降一步，将导致对C的局部变量的操各个数据区连接起来。我们称之为静态链（staticlink）SL。这样，编译程序A、BC ABCB有了以上认识，我们就不难明白PL/0源程序的目标代码是如何被解释执行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()错误诊断处任何输入序列都不会引起编译程序的一切按语言定义为的结构，都能被发现和标志出来PL/0（称为同步符号）的最好选择就是关键字。PL/0的每一种构造语句以begin、ifwhilevar、constprocedure输入正文，直到下一个可以正确地跟随当前正在分析的句子结构的符号为）testtestn，表示有关错误的诊断号：voidtest(symsets1,symsets2,intn){symsetif(!inset(sym,{s=uniteset(s1,s2);while(!inset(sym,}}如“;”PL/0分析程序中复合语句分析的一小段。它的效果等于关键字前漏掉的分号。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'}}相关过程：test(),inset(),createset,uniteset(),符号表管程的地址及层次。（PL/0dxdx3，含三个变量RA，DL和SL。其本所提供的PL/0编译程序包括词法分析、语法分析、错误诊码listcode()完成。注意，每个分程序（过程）的第一PL/0第二部分机实践要PL/0100（BNF有关修改后的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布尔表达式可以比较大小：false布尔表达式的短路计算（5（2，除数组（10注意数组可以由其它的数组来构造因而必须考虑数组的情况。data_type→integer|boolean|array[const..const]ofconst→ident|语言中允许有数组说明对数组元素赋值在表达式中数组元素。为了便于解释执行，可能要增加新的PL/0器操作指令。参数（10）Pascal，采用值-结果方式传递（var函数（10）Pascalelserepeat（5forPascalC（5循环（5）记录（结构）,Pascal（10更有力的语法错误恢复机制（20分离解释和编译器（5上面的这些要求有时会互相影响参数就应该能处理其相互组合的情况，如布尔型数组（包括数组、布递等。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"//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