PL/0语言及其实现
1.1PL/0语言简介
PL/0语言是Pascal语言的一个子集，是Pascal语言的设计者NiklausWirth在其专著
Algorithms+DataStructures=Programs一书（译著书名：算法＋数据结构＝程序）中给出的。
PL/0是一个小巧的高级语言。
虽然它只有整数类型，但它是相当完全的可嵌套的分程 序（block）的程序结构，分程序中可以有常量定义、变量声明和无参过程声明，过程体又 是分程序。
PL/0有赋值语句、条件语句、循环语句、过程调用语句、复合语句和空语句。
由于上面这些语言概念已为大家熟知，因此不再进行语义解释。
下面用习题3.7所介绍 的扩展方式来给出PL/0语言的文法。
Program →Block. Block →[ConstDecl][VarDecl][ProcDecl]Stmt ConstDecl→constConstDef{,ConstDef}; ConstDef→ident=number VarDecl →varident{,ident}; ProcDecl→procedureident;Block;{procedureident;Block;} Stmt →ident:=Exp|callident|beginStmt{;Stmt}end| ifCondthenStmt|whileConddoStmt|ε Cond →oddExp|ExpRelOpExp RelOp →=|<>|<|>|<=|>= Exp →[+|−]Term{+Term|−Term} Term →Factor{∗Factor|/Factor} Factor →ident|number|(Exp) 其中的标识符ident是字母开头的字母数字串，number是无符号整数，begin、call、const、 do、end、if、odd、procedure、then、var、while是保留字。
用PL/0语言写的一个程序如下，它有3个过程，分别计算两个整数相乘、相除和求最 大公约数。
constm=7,n=85; varx,y,z,q,r; proceduremultiply; vara,b; begin a:=x;b:=y;z:=0; whileb>0do begin ifoddbthenz:=z+a; a:=2*a;b:=b/2; end end; proceduredivide;
1 varw;begin r:=x;q:=0;w:=y;whilew<=rdow:=2*w;whilew>ydo beginq:=2*q;w:=w/2;ifw<=rthenbeginr:=r-w;q:=q+1;end endend; proceduregcd;varf,g;beginf:=x;g:=y;whilef<>gdobeginiff
中间语言是一种栈机器代码，其指令集是根据PL/0语言的需要来设计的。
它包括下列指令： （1）lit：将常数装入栈顶的指令；（2）lod：将变量的值装入栈顶的指令；（3）sto：对应于赋值语句的存储指令；（4）cal：对应于过程调用的指令；（5）int：增加栈顶寄存器的值，完成对局部变量的存储分配的指令；
2 （6）jmp，jpc：对应条件语句和循环语句的无条件转移和条件转移的控制转移指令；（7）opr：包括一组算术和关系运算的指令。
一条指令由三个域组成：
（1）操作码f：上面已经列出了所有8种操作码。
（2）层次差l：这里的层次差就是5.3.2节介绍嵌套深度时的np−na。
该域仅用于存取指令和调用指令。
（3）多用途a：在运算指令中，a的值用来区分不同的运算；在其他情况，a或是一个数（lit，int），或是一个程序地址（jmp，jpc，cal），或是一个数据地址（lod，sto）。
编译器对PL/0源程序进行一遍扫描，并逐行输出源程序。
在源程序无错的情况下，编译器每编译完一个分程序，就列出该分程序的代码，这由编译器的listcode过程完成。
每个分程序的第一条指令是jmp指令，其作用是绕过该分程序声明部分产生的代码（即绕过内嵌过程的代码）。
listcode过程没有列出这条代码。
解释器是编译器中的一个过程，若源程序无错，则编译结束时调用解释过程interpret。
由于PL/0语言没有输出语句，解释器按执行次序，每遇到对变量赋值时就输出该值。
由于PL/0语言是过程嵌套语言，因此程序运行时，活动记录栈中每个活动记录需要包含控制链和访问链，并按5.3.2节所讲的方法来建立访问链。
活动记录栈的栈顶以外的存储空间作为代码执行过程中所需要的计算栈，无需另外设立计算栈。
PL/0语言虽然简单，但它的编译器能够展示编译高级语言的许多基本概念，它提出的基本方法对设计复杂语言的编译器也是适用的。
NiklausWirth的这个编译器已经有30多年的历史，虽然30年来编译技术有了很大发展，但是对普通高校计算机专业的学生来说，通过阅读该编译器的源代码来融会贯通编译的理论和技术，并以此编译器为基础来进行课程实践，仍不失为一种好的选择。
1.3PL/0语言编译器的源代码NiklausWirth设计的编译器是用Pascal语言编写的，本书作者用C语言改写后的代码 在下面给出。
为尊重NiklausWirth的原意，也为了便于对照原来用Pascal语言写的代码，我们尽量不改动原来代码的流程和风格等，除非那些由于Pascal语言和C语言不共同支持的程序结构、数据类型和语句等引起的问题。
代码改写中碰到的问题整理如下，若有读者感兴趣同时了解两种不同语言写的版本，则需要关注下面这几点。
（1）Pascal语言允许过程嵌套，导致有非全局且非局部的变量，而C语言的非局部变量则一定是全局的。
（2）Pascal语言有集合类型，而C语言没有。
这是改写中碰到的最大问题，我们用位串来表示集合，用位运算来实现集合运算。
这样做使得改写的代码容易理解，但是由于字长的限制，给扩展语言的实现带来一点点麻烦。
（3）Pascal有子界类型，而C语言没有。
（4）Pascal语言用子界类型来规定数组下标的上下界，而C语言的下标从0开始。
（5）Pascal语言用紧缩字符数组类型作为字符串类型，由于长度相同的字符串才可能属于同一个类型，因此字符串无需‘\0’作为结束标记，而C语言的字符串一定以‘\0’结尾。
（6）Pascal语言的变体记录类型可以有标志域，它和C语言的共用体类型是有区别的。
（7）对于两种语言都有的整型，在C语言中统一使用long类型（统一使用int类型也是一样的）。
3
（8）两种语言的文件（包括标准输入和输出）操作有较大区别。
（9）两种语言的注释形式不同。
（10）由于int是C语言的关键字，因此中间语言指令的操作码int被改成Int。
（11）改写版本中增加了制表符作为单词的分隔符，因为现在大家已经习惯用制表符。
带来的问题是编译器报错的箭头所指位置可能不准确。
NiklausWirth设计的编译器中有一些不影响大局的小问题（也许是NiklausWirth有意为之），我们也没有修改。
例如：
（1）没有检查一个分程序中的名字是否重复声明，导致出现重复声明的名字时，默认的是最后出现的那一个。
（2）按附录1.1节的文法，常量定义和变量声明用逗号分隔，但实际情况是用分号分隔也被认可。
（3）无符号整数超过一定位数时，以报告编号为30而不是31的错误更为准确。
下面是编译器两个文件pl0.h和pl0.c的代码。
（1）文件pl0.h#include
#definenorw
11
#definetxmax
100
#definenmax
14
#defineal
10
#defineamax
2047
#definelevmax
3 #definecxmax 2000 //no.ofreservedwords//lengthofidentifiertable//max.no.ofdigitsinnumbers//lengthofidentifiers//maximumaddress//maximumdepthofblocknesting//sizeofcodearray #define#define#define#define#define#define#define#define#define#define#define#define#define#define#define#define#define#define#define nulidentnumberplusminustimesslashoddsymeqlneqlssleqgtrgeqlparenmasemicolonperiod 0x10x20x40x80x100x200x400x800x1000x2000x4000x8000x10000x20000x40000x80000x100000x200000x40000
4 #define#define#define#define#define#define#define#define#define#define#define esbeginsymendsymifsymthensymwhilesymdosymcallsymconstsymvarsymprocsym 0x800000x1000000x2000000x4000000x8000000x10000000x20000000x40000000x80000000x100000000x20000000 enumobject{constant,variable,proc }; enumfct{lit,opr,lod,sto,cal,Int,jmp,jpc }; typedefstruct{ enumfctf; //functioncode longl; //level longa; //displacementaddress }instruction; /*lit0,a:loadconstanta opr0,a:executeoperationa lodl,a:loadvariablel,a stol,a:storevariablel,a call,a:callprocedureaatlevell Int0,a:incrementt-registerbya jmp0,a:jumptoa jpc0,a:jumpconditionaltoa */ charch;unsignedlongsym;charid[al+1];longnum;;longll;longkk,err;longcx; //lastcharacterread//lastsymbolread//lastidentifierread//lastnumberread//charactercount//linelength //codeallocationindex charline[81]; //functions
5 chara[al+1];instructioncode[cxmax+1];charword[norw][al+1];unsignedlongwsym[norw];unsignedlongssym[256]; charmnemonic[8][3+1];unsignedlongdeclbegsys,statbegsys,facbegsys; struct{charname[al+1];enumobjectkind;longval;longlevel;longaddr; }table[txmax+1]; charinfilename[80];FILE*infile; //thefollowingvariablesforblock longdx; //dataallocationindex longlev; //currentdepthofblocknesting longtx; //currenttableindex //thefollowingarrayspaceforinterpreter#definestacksize50000longs[stacksize];//datastore
（2）文件pl0.c//pl/pilerwith#include#include#include"pl0.h"
code
generation
voiderror(longn){longi;
printf("****");for(i=1;i<-1;i++){
printf("");}printf("^%2d\n",n);err++;
6 } voidgetch(){ ==ll){ if(feof(infile)){ printf("************************************\n"); printf(" program
plete\n"); printf("************************************\n"); exit
(1); } ll=0;=0; printf("%5d
",cx); while((!
feof(infile))&&((ch=getc(infile))!
='\n')){ printf("%c",ch); ll=ll+1;line[ll]=ch; } printf("\n"); ll=ll+1;line[ll]=''; } +1;ch=]; } voidgetsym(){longi,j,k; while(ch==''||ch=='\t'){getch(); }if(isalpha(ch)){//identifiedorreserved k=0;do{ if(k=kk){kk=k;}else{do{
kk=kk-1;a[kk]='';}while(k7
do{k=(i+j)/2;if(strcmp(id,word[k])<=0){j=k-1;}if(strcmp(id,word[k])>=0){i=k+1;}
}while(i<=j);if(i-1>j){
sym=wsym[k];}else{
sym=ident;}}elseif(isdigit(ch)){//numberk=0;num=0;sym=number;do{
num=num*10+(ch-'0');k=k+1;getch();}while(isdigit(ch));if(k>nmax){error(31);}}elseif(ch==':'){getch();if(ch=='='){sym=es;getch();}else{sym=nul;}}elseif(ch=='<'){getch();if(ch=='='){sym=leq;getch();}elseif(ch=='>'){sym=neq;getch();}else{sym=lss;}}elseif(ch=='>'){getch();if(ch=='='){sym=geq;getch();}else{
8 sym=gtr;}}else{sym=ssym[(unsignedchar)ch];getch();}} voidgen(enumfctx,longy,longz){if(cx>cxmax){printf("programtoolong\n");exit
(1);}code[cx].f=x;code[cx].l=y;code[cx].a=z;cx=cx+1; } voidtest(unsignedlongs1,unsignedlongs2,longn){if(!
(sym&s1)){error(n);s1=s1|s2;while(!
(sym&s1)){getsym();}} } voidenter(enumobjectk){ //enterobjectintotable tx=tx+1; strcpy(table[tx].name,id); table[tx].kind=k; switch(k){ caseconstant: if(num>amax){ error(31); num=0; } table[tx].val=num; break; casevariable: table[tx].level=lev;table[tx].addr=dx;dx=dx+1; break; caseproc: table[tx].level=lev; break;
9 }} longposition(char*id){longi; //findidentifieridintable strcpy(table[0].name,id);i=tx;while(strcmp(table[i].name,id)!
=0){ i=i-1;}returni;} voidconstdeclaration(){if(sym==ident){getsym();if(sym==eql||sym==es){if(sym==es){error
(1);}getsym();if(sym==number){enter(constant);getsym();}else{error
(2);}}else{error
(3);}}else{error
(4);} } voidvardeclaration(){if(sym==ident){enter(variable);}else{error
(4);} } getsym(); voidlistcode(longcx0){//listcodegeneratedforthisblock 10 longi; for(i=cx0;i<=cx-1;i++){printf("%10d%5s%3d%5d\n",i,mnemonic[code[i].f],code[i].l,code[i].a); } } voidexpression(unsignedlong);voidfactor(unsignedlongfsys){ longi; test(facbegsys,fsys,24);while(sym&facbegsys){ if(sym==ident){i=position(id);if(i==0){error(11);}else{switch(table[i].kind){caseconstant:gen(lit,0,table[i].val);break;casevariable:gen(lod,lev-table[i].level,table[i].addr);break;caseproc:error(21);break;}}getsym(); }elseif(sym==number){if(num>amax){error(31);num=0;}gen(lit,0,num);getsym(); }elseif(sym==lparen){getsym();expression(rparen|fsys);if(sym==rparen){getsym();}else{ 11 error(22);}}test(fsys,lparen,23);}} voidterm(unsignedlongfsys){unsignedlongmulop; factor(fsys|times|slash);while(sym==times||sym==slash){ mulop=sym;getsym();factor(fsys|times|slash);if(mulop==times){ gen(opr,0,4);}else{ gen(opr,0,5);}}} voidexpression(unsignedlongfsys){unsignedlongaddop; if(sym==plus||sym==minus){addop=sym;getsym();term(fsys|plus|minus);if(addop==minus){gen(opr,0,1);} }else{term(fsys|plus|minus); }while(sym==plus||sym==minus){ addop=sym;getsym();term(fsys|plus|minus);if(addop==plus){ gen(opr,0,2);}else{ gen(opr,0,3);}}} 12 voidcondition(unsignedlongfsys){unsignedlongrelop; if(sym==oddsym){getsym();expression(fsys);gen(opr,0,6); }else{expression(fsys|eql|neq|lss|gtr|leq|geq);if(!
(sym&(eql|neq|lss|gtr|leq|geq))){error(20);}else{relop=sym;getsym();expression(fsys);switch(relop){caseeql:gen(opr,0,8);break;caseneq:gen(opr,0,9);break;caselss:gen(opr,0,10);break;casegeq:gen(opr,0,11);break;casegtr:gen(opr,0,12);break;caseleq:gen(opr,0,13);break;}} }} voidstatement(unsignedlongfsys){longi,cx1,cx2; if(sym==ident){i=position(id);if(i==0){ 13 error(11);}elseif(table[i].kind!
=variable){//assignmentto error(12);i=0;}getsym();if(sym==es){ getsym();}else{ error(13);}expression(fsys);if(i!
=0){ gen(sto,lev-table[i].level,table[i].addr);}}elseif(sym==callsym){getsym();if(sym!
=ident){ error(14);}else{ i=position(id);if(i==0){ error(11);}elseif(table[i].kind==proc){ gen(cal,lev-table[i].level,table[i].addr);}else{ error(15);}getsym();}}elseif(sym==ifsym){getsym();condition(fsys|thensym|dosym);if(sym==thensym){getsym();}else{error(16);}cx1=cx;gen(jpc,0,0);statement(fsys);code[cx1].a=cx;}elseif(sym==beginsym){getsym();statement(fsys|semicolon|endsym);while(sym==semicolon||(sym&statbegsys)){if(sym==semicolon){ getsym(); non-variable 14 }else{error(10); }statement(fsys|semicolon|endsym);}if(sym==endsym){getsym();}else{error(17);}}elseif(sym==whilesym){cx1=cx;getsym();condition(fsys|dosym);cx2=cx;gen(jpc,0,0);if(sym==dosym){getsym();}else{error(18);}statement(fsys);gen(jmp,0,cx1);code[cx2].a=cx;}test(fsys,0,19);} voidblock(unsignedlongtx0;longcx0;longtx1;longdx1; longfsys){//initialtableindex//initialcodeindex//savecurrenttableindexbeforeprocessingnestedprocedures//savedataallocationindex dx=3;tx0=tx;table[tx].addr=cx;gen(jmp,0,0);if(lev>levmax){ error(32);}do{ if(sym==constsym){getsym();do{constdeclaration();while(sym=ma){getsym();constdeclaration();}if(sym==semicolon){ 15 getsym();}else{ error
(5);}}while(sym==ident);}if(sym==varsym){getsym();do{vardeclaration();while(sym=ma){ getsym();vardeclaration();}if(sym==semicolon){ getsym();}else{ error
(5);}}while(sym==ident);}while(sym==procsym){getsym();if(sym==ident){enter(proc);getsym();}else{error
(4);}if(sym==semicolon){getsym();}else{error
(5);}lev=lev+1;tx1=tx;dx1=dx;block(fsys|semicolon);lev=lev-1;tx=tx1;dx=dx1;if(sym==semicolon){getsym();test(statbegsys|ident|procsym,fsys,6);}else{error
(5);}}test(statbegsys|ident,declbegsys,7);}while(sym&declbegsys); 16 code[table[tx0].addr].a=cx; table[tx0].addr=cx; //startaddrofcode cx0=cx;gen(Int,0,dx); statement(fsys|semicolon|endsym); gen(opr,0,0);//return test(fsys,0,8); listcode(cx0); } longbase(longb,longl){longb1; b1=b;while(l>0){//findbasellevelsdown b1=s[b1];l=l-1;}returnb1;} voidinterpret(){longp,b,t;instructioni; //program-,base-,stack-registers//instructionregister printf("startPL/0\n");t=0;b=1;p=0;s[1]=0;s[2]=0;s[3]=0;do{ i=code[p];p=p+1;switch(i.f){ caselit:t=t+1;s[t]=i.a;break; caseopr:switch(i.a){//operatorcase0://returnt=b-1;p=s[t+3];b=s[t+2];break;case1:s[t]=-s[t];break;case2:t=t-1;s[t]=s[t]+s[t+1];break;case3: 17 t=t-1;s[t]=s[t]-s[t+1]; break; case4: t=t-1;s[t]=s[t]*s[t+1]; break; case5: t=t-1;s[t]=s[t]/s[t+1]; break; case6: s[t]=s[t]%2; break; case8: t=t-1;s[t]=(s[t]==s[t+1]); break; case9: t=t-1;s[t]=(s[t]!
=s[t+1]); break; case10: t=t-1;s[t]=(s[t]=s[t+1]);
break;
case12:
t=t-1;s[t]=(s[t]>s[t+1]);
break;
case13:
t=t-1;s[t]=(s[t]<=s[t+1]);
}
break;
caselod:
t=t+1;s[t]=s[base(b,i.l)+i.a];
break;
casesto:
s[base(b,i.l)+i.a]=s[t];printf("%10d\n",
break;
casecal:
//generatenewblockmark
s[t+1]=base(b,i.l);s[t+2]=b;s[t+3]=p;
b=t+1;p=i.a;
break;
caseInt:
t=t+i.a;
break;
casejmp:
s[t]);
t=t-1;
18
p=i.a;break;casejpc:if(s[t]==0){
p=i.a;}t=t-1;}}while(p!
=0);printf("endPL/0\n");} main(){ longi; for(i=0;i<256;i++){ ssym[i]=nul; } strcpy(word[0],"begin "); strcpy(word[1],"call "); strcpy(word[2],"const "); strcpy(word[3],"do "); strcpy(word[4],"end "); strcpy(word[5],"if "); strcpy(word[6],"odd "); strcpy(word[7],"procedure"); strcpy(word[8],"then "); strcpy(word[9],"var "); strcpy(word[10],"while "); wsym[0]=beginsym; wsym[1]=callsym; wsym[2]=constsym; wsym[3]=dosym; wsym[4]=endsym; wsym[5]=ifsym; wsym[6]=oddsym; wsym[7]=procsym; wsym[8]=thensym; wsym[9]=varsym; wsym[10]=whilesym; ssym['+']=plus; ssym['-']=minus; ssym['*']=times; ssym['/']=slash; ssym['(']=lparen; 19 ssym[')']=rparen;
ssym['=']=eql;ssym[',']ma;ssym['.']=period;ssym[';']=semicolon;strcpy(mnemonic[lit],"lit");strcpy(mnemonic[opr],"opr");strcpy(mnemonic[lod],"lod");strcpy(mnemonic[sto],"sto");strcpy(mnemonic[cal],"cal");strcpy(mnemonic[Int],"int");strcpy(mnemonic[jmp],"jmp");strcpy(mnemonic[jpc],"jpc");declbegsys=constsym|varsym|procsym;statbegsys=beginsym|callsym|ifsym|whilesym;facbegsys=ident|number|lparen; printf("pleaseinputsourceprogramfilename:");scanf("%s",infilename);printf("\n");if((infile=fopen(infilename,"r"))==NULL){ printf("File%scan'tbeopened.\n",infilename);exit
(1);} err=0;=0;cx=0;ll=0;ch='';kk=al;getsym();lev=0;tx=0;block(declbegsys|statbegsys|period);if(sym!
=period){ error
(9);}if(err==0){ interpret();}else{ printf("errorsinPL/0program\n");}fclose(infile);} 下面是编译器报告错误的错误编号及含义。
错误编号含义
1 应为=而不是:=
2 =后应为数 20
3 标识符后应为=
4 const，var，procedure后应为标识符
5 遗漏逗号或分号
6 过程声明后的记号不正确
7 应为语句
8 分程序内的语句部分后的记号不正确
9 应为句号 10 语句之间漏分号 11 标识符未声明 12 不可向常量或过程赋值 13 应为赋值运算符:= 14 call
后应为标识符 15 不可调用常量或变量 16 应为then 17 应为分号或end 18 应为do 19 语句后的记号不正确 20 应为关系运算符 21 表达式内不可有过程标识符 22 遗漏右括号 23 因子后不可为此记号 24 表达式不能以此记号开始 30 这个数太大 31 这个常数或地址偏移太大 32 程序嵌套层次太多 下面是一个
PL/0源程序编译和解释执行时的输出。
pleaseinputsourceprogramfilename: 0constm=7,n=85; 1varx,y,z,q,r; 1proceduremultiply; 1vara,b; 2begin
3 a:=x;b:=y;z:=0;
9 whileb>0do 13 begin 13 ifoddbthenz:=z+a; 20 a:=2*a;b:=b/2; 28 end 28end; 2int05 3lod13 4sto03 5lod14 21 30313536 start 6sto047lit008sto159lod0410lit0011opr01212jpc02913lod0414opr0615jpc02016lod1517lod0318opr0219sto1520lit0221lod0322opr0423sto0324lod0425lit0226opr0527sto0428jmp0929opr00beginx:=m;y:=n;callmultiply;end.30int0831lit0732sto0333lit08534sto0435cal0236opr00PL/0785785071442 22 2821355610112 5147224 2448 1595896 0endPL/0 附录二基于PL/0语言的课程实践选题 基于附录一的PL/0语言及其编译器，可以提出很多课程实践的课题，下面列出一些比较简单的课题，可选择实现其中的一部分。
1、给PL/0语言增加像C语言那样的形式为/∗……∗/的注释。
2、给PL/0语言增加带else子句的条件语句和exit语句。
exit语句作为while语句的非正常出口语句。
若处于多层while语句中，则它只作为最内层while语句的非正常出口。
若它没有处于任何while语句中，则是一个错误。
3、给PL/0语言增加输入输出语句。
4、给PL/0语言增加带参数的过程，参数传递按值调用方式。
5、给PL/0语言增加布尔类型，并且布尔类型的表达式按短路方式计算。
6、给PL/0语言增加数组类型。
7、给PL/0语言增加函数类型。
8、给PL/0语言增加实数类型。
9、用或类似的生成器来生成PL/0语言的编译器。
10、为PL/0实现效果更好的语法错误恢复机制。
11、分离解释器和编译器。
把解释器从现在的编译器中分离出来，变成一个独立的C语言程序。
分离后，编译器和解释器的接口是二进制形式的中间代码文件。
23
PL/0是一个小巧的高级语言。
虽然它只有整数类型，但它是相当完全的可嵌套的分程 序（block）的程序结构，分程序中可以有常量定义、变量声明和无参过程声明，过程体又 是分程序。
PL/0有赋值语句、条件语句、循环语句、过程调用语句、复合语句和空语句。
由于上面这些语言概念已为大家熟知，因此不再进行语义解释。
下面用习题3.7所介绍 的扩展方式来给出PL/0语言的文法。
Program →Block. Block →[ConstDecl][VarDecl][ProcDecl]Stmt ConstDecl→constConstDef{,ConstDef}; ConstDef→ident=number VarDecl →varident{,ident}; ProcDecl→procedureident;Block;{procedureident;Block;} Stmt →ident:=Exp|callident|beginStmt{;Stmt}end| ifCondthenStmt|whileConddoStmt|ε Cond →oddExp|ExpRelOpExp RelOp →=|<>|<|>|<=|>= Exp →[+|−]Term{+Term|−Term} Term →Factor{∗Factor|/Factor} Factor →ident|number|(Exp) 其中的标识符ident是字母开头的字母数字串，number是无符号整数，begin、call、const、 do、end、if、odd、procedure、then、var、while是保留字。
用PL/0语言写的一个程序如下，它有3个过程，分别计算两个整数相乘、相除和求最 大公约数。
constm=7,n=85; varx,y,z,q,r; proceduremultiply; vara,b; begin a:=x;b:=y;z:=0; whileb>0do begin ifoddbthenz:=z+a; a:=2*a;b:=b/2; end end; proceduredivide;
1 varw;begin r:=x;q:=0;w:=y;whilew<=rdow:=2*w;whilew>ydo beginq:=2*q;w:=w/2;ifw<=rthenbeginr:=r-w;q:=q+1;end endend; proceduregcd;varf,g;beginf:=x;g:=y;whilef<>gdobeginiff
它包括下列指令： （1）lit：将常数装入栈顶的指令；（2）lod：将变量的值装入栈顶的指令；（3）sto：对应于赋值语句的存储指令；（4）cal：对应于过程调用的指令；（5）int：增加栈顶寄存器的值，完成对局部变量的存储分配的指令；
2 （6）jmp，jpc：对应条件语句和循环语句的无条件转移和条件转移的控制转移指令；（7）opr：包括一组算术和关系运算的指令。
一条指令由三个域组成：
（1）操作码f：上面已经列出了所有8种操作码。
（2）层次差l：这里的层次差就是5.3.2节介绍嵌套深度时的np−na。
该域仅用于存取指令和调用指令。
（3）多用途a：在运算指令中，a的值用来区分不同的运算；在其他情况，a或是一个数（lit，int），或是一个程序地址（jmp，jpc，cal），或是一个数据地址（lod，sto）。
编译器对PL/0源程序进行一遍扫描，并逐行输出源程序。
在源程序无错的情况下，编译器每编译完一个分程序，就列出该分程序的代码，这由编译器的listcode过程完成。
每个分程序的第一条指令是jmp指令，其作用是绕过该分程序声明部分产生的代码（即绕过内嵌过程的代码）。
listcode过程没有列出这条代码。
解释器是编译器中的一个过程，若源程序无错，则编译结束时调用解释过程interpret。
由于PL/0语言没有输出语句，解释器按执行次序，每遇到对变量赋值时就输出该值。
由于PL/0语言是过程嵌套语言，因此程序运行时，活动记录栈中每个活动记录需要包含控制链和访问链，并按5.3.2节所讲的方法来建立访问链。
活动记录栈的栈顶以外的存储空间作为代码执行过程中所需要的计算栈，无需另外设立计算栈。
PL/0语言虽然简单，但它的编译器能够展示编译高级语言的许多基本概念，它提出的基本方法对设计复杂语言的编译器也是适用的。
NiklausWirth的这个编译器已经有30多年的历史，虽然30年来编译技术有了很大发展，但是对普通高校计算机专业的学生来说，通过阅读该编译器的源代码来融会贯通编译的理论和技术，并以此编译器为基础来进行课程实践，仍不失为一种好的选择。
1.3PL/0语言编译器的源代码NiklausWirth设计的编译器是用Pascal语言编写的，本书作者用C语言改写后的代码 在下面给出。
为尊重NiklausWirth的原意，也为了便于对照原来用Pascal语言写的代码，我们尽量不改动原来代码的流程和风格等，除非那些由于Pascal语言和C语言不共同支持的程序结构、数据类型和语句等引起的问题。
代码改写中碰到的问题整理如下，若有读者感兴趣同时了解两种不同语言写的版本，则需要关注下面这几点。
（1）Pascal语言允许过程嵌套，导致有非全局且非局部的变量，而C语言的非局部变量则一定是全局的。
（2）Pascal语言有集合类型，而C语言没有。
这是改写中碰到的最大问题，我们用位串来表示集合，用位运算来实现集合运算。
这样做使得改写的代码容易理解，但是由于字长的限制，给扩展语言的实现带来一点点麻烦。
（3）Pascal有子界类型，而C语言没有。
（4）Pascal语言用子界类型来规定数组下标的上下界，而C语言的下标从0开始。
（5）Pascal语言用紧缩字符数组类型作为字符串类型，由于长度相同的字符串才可能属于同一个类型，因此字符串无需‘\0’作为结束标记，而C语言的字符串一定以‘\0’结尾。
（6）Pascal语言的变体记录类型可以有标志域，它和C语言的共用体类型是有区别的。
（7）对于两种语言都有的整型，在C语言中统一使用long类型（统一使用int类型也是一样的）。
3
（8）两种语言的文件（包括标准输入和输出）操作有较大区别。
（9）两种语言的注释形式不同。
（10）由于int是C语言的关键字，因此中间语言指令的操作码int被改成Int。
（11）改写版本中增加了制表符作为单词的分隔符，因为现在大家已经习惯用制表符。
带来的问题是编译器报错的箭头所指位置可能不准确。
NiklausWirth设计的编译器中有一些不影响大局的小问题（也许是NiklausWirth有意为之），我们也没有修改。
例如：
（1）没有检查一个分程序中的名字是否重复声明，导致出现重复声明的名字时，默认的是最后出现的那一个。
（2）按附录1.1节的文法，常量定义和变量声明用逗号分隔，但实际情况是用分号分隔也被认可。
（3）无符号整数超过一定位数时，以报告编号为30而不是31的错误更为准确。
下面是编译器两个文件pl0.h和pl0.c的代码。
（1）文件pl0.h#include
3 #definecxmax 2000 //no.ofreservedwords//lengthofidentifiertable//max.no.ofdigitsinnumbers//lengthofidentifiers//maximumaddress//maximumdepthofblocknesting//sizeofcodearray #define#define#define#define#define#define#define#define#define#define#define#define#define#define#define#define#define#define#define nulidentnumberplusminustimesslashoddsymeqlneqlssleqgtrgeqlparenmasemicolonperiod 0x10x20x40x80x100x200x400x800x1000x2000x4000x8000x10000x20000x40000x80000x100000x200000x40000
4 #define#define#define#define#define#define#define#define#define#define#define esbeginsymendsymifsymthensymwhilesymdosymcallsymconstsymvarsymprocsym 0x800000x1000000x2000000x4000000x8000000x10000000x20000000x40000000x80000000x100000000x20000000 enumobject{constant,variable,proc }; enumfct{lit,opr,lod,sto,cal,Int,jmp,jpc }; typedefstruct{ enumfctf; //functioncode longl; //level longa; //displacementaddress }instruction; /*lit0,a:loadconstanta opr0,a:executeoperationa lodl,a:loadvariablel,a stol,a:storevariablel,a call,a:callprocedureaatlevell Int0,a:incrementt-registerbya jmp0,a:jumptoa jpc0,a:jumpconditionaltoa */ charch;unsignedlongsym;charid[al+1];longnum;;longll;longkk,err;longcx; //lastcharacterread//lastsymbolread//lastidentifierread//lastnumberread//charactercount//linelength //codeallocationindex charline[81]; //functions
5 chara[al+1];instructioncode[cxmax+1];charword[norw][al+1];unsignedlongwsym[norw];unsignedlongssym[256]; charmnemonic[8][3+1];unsignedlongdeclbegsys,statbegsys,facbegsys; struct{charname[al+1];enumobjectkind;longval;longlevel;longaddr; }table[txmax+1]; charinfilename[80];FILE*infile; //thefollowingvariablesforblock longdx; //dataallocationindex longlev; //currentdepthofblocknesting longtx; //currenttableindex //thefollowingarrayspaceforinterpreter#definestacksize50000longs[stacksize];//datastore
（2）文件pl0.c//pl/pilerwith#include
6 } voidgetch(){ ==ll){ if(feof(infile)){ printf("************************************\n"); printf(" program
plete\n"); printf("************************************\n"); exit
(1); } ll=0;=0; printf("%5d
",cx); while((!
feof(infile))&&((ch=getc(infile))!
='\n')){ printf("%c",ch); ll=ll+1;line[ll]=ch; } printf("\n"); ll=ll+1;line[ll]=''; } +1;ch=]; } voidgetsym(){longi,j,k; while(ch==''||ch=='\t'){getch(); }if(isalpha(ch)){//identifiedorreserved k=0;do{ if(k
8 sym=gtr;}}else{sym=ssym[(unsignedchar)ch];getch();}} voidgen(enumfctx,longy,longz){if(cx>cxmax){printf("programtoolong\n");exit
(1);}code[cx].f=x;code[cx].l=y;code[cx].a=z;cx=cx+1; } voidtest(unsignedlongs1,unsignedlongs2,longn){if(!
(sym&s1)){error(n);s1=s1|s2;while(!
(sym&s1)){getsym();}} } voidenter(enumobjectk){ //enterobjectintotable tx=tx+1; strcpy(table[tx].name,id); table[tx].kind=k; switch(k){ caseconstant: if(num>amax){ error(31); num=0; } table[tx].val=num; break; casevariable: table[tx].level=lev;table[tx].addr=dx;dx=dx+1; break; caseproc: table[tx].level=lev; break;
9 }} longposition(char*id){longi; //findidentifieridintable strcpy(table[0].name,id);i=tx;while(strcmp(table[i].name,id)!
=0){ i=i-1;}returni;} voidconstdeclaration(){if(sym==ident){getsym();if(sym==eql||sym==es){if(sym==es){error
(1);}getsym();if(sym==number){enter(constant);getsym();}else{error
(2);}}else{error
(3);}}else{error
(4);} } voidvardeclaration(){if(sym==ident){enter(variable);}else{error
(4);} } getsym(); voidlistcode(longcx0){//listcodegeneratedforthisblock 10 longi; for(i=cx0;i<=cx-1;i++){printf("%10d%5s%3d%5d\n",i,mnemonic[code[i].f],code[i].l,code[i].a); } } voidexpression(unsignedlong);voidfactor(unsignedlongfsys){ longi; test(facbegsys,fsys,24);while(sym&facbegsys){ if(sym==ident){i=position(id);if(i==0){error(11);}else{switch(table[i].kind){caseconstant:gen(lit,0,table[i].val);break;casevariable:gen(lod,lev-table[i].level,table[i].addr);break;caseproc:error(21);break;}}getsym(); }elseif(sym==number){if(num>amax){error(31);num=0;}gen(lit,0,num);getsym(); }elseif(sym==lparen){getsym();expression(rparen|fsys);if(sym==rparen){getsym();}else{ 11 error(22);}}test(fsys,lparen,23);}} voidterm(unsignedlongfsys){unsignedlongmulop; factor(fsys|times|slash);while(sym==times||sym==slash){ mulop=sym;getsym();factor(fsys|times|slash);if(mulop==times){ gen(opr,0,4);}else{ gen(opr,0,5);}}} voidexpression(unsignedlongfsys){unsignedlongaddop; if(sym==plus||sym==minus){addop=sym;getsym();term(fsys|plus|minus);if(addop==minus){gen(opr,0,1);} }else{term(fsys|plus|minus); }while(sym==plus||sym==minus){ addop=sym;getsym();term(fsys|plus|minus);if(addop==plus){ gen(opr,0,2);}else{ gen(opr,0,3);}}} 12 voidcondition(unsignedlongfsys){unsignedlongrelop; if(sym==oddsym){getsym();expression(fsys);gen(opr,0,6); }else{expression(fsys|eql|neq|lss|gtr|leq|geq);if(!
(sym&(eql|neq|lss|gtr|leq|geq))){error(20);}else{relop=sym;getsym();expression(fsys);switch(relop){caseeql:gen(opr,0,8);break;caseneq:gen(opr,0,9);break;caselss:gen(opr,0,10);break;casegeq:gen(opr,0,11);break;casegtr:gen(opr,0,12);break;caseleq:gen(opr,0,13);break;}} }} voidstatement(unsignedlongfsys){longi,cx1,cx2; if(sym==ident){i=position(id);if(i==0){ 13 error(11);}elseif(table[i].kind!
=variable){//assignmentto error(12);i=0;}getsym();if(sym==es){ getsym();}else{ error(13);}expression(fsys);if(i!
=0){ gen(sto,lev-table[i].level,table[i].addr);}}elseif(sym==callsym){getsym();if(sym!
=ident){ error(14);}else{ i=position(id);if(i==0){ error(11);}elseif(table[i].kind==proc){ gen(cal,lev-table[i].level,table[i].addr);}else{ error(15);}getsym();}}elseif(sym==ifsym){getsym();condition(fsys|thensym|dosym);if(sym==thensym){getsym();}else{error(16);}cx1=cx;gen(jpc,0,0);statement(fsys);code[cx1].a=cx;}elseif(sym==beginsym){getsym();statement(fsys|semicolon|endsym);while(sym==semicolon||(sym&statbegsys)){if(sym==semicolon){ getsym(); non-variable 14 }else{error(10); }statement(fsys|semicolon|endsym);}if(sym==endsym){getsym();}else{error(17);}}elseif(sym==whilesym){cx1=cx;getsym();condition(fsys|dosym);cx2=cx;gen(jpc,0,0);if(sym==dosym){getsym();}else{error(18);}statement(fsys);gen(jmp,0,cx1);code[cx2].a=cx;}test(fsys,0,19);} voidblock(unsignedlongtx0;longcx0;longtx1;longdx1; longfsys){//initialtableindex//initialcodeindex//savecurrenttableindexbeforeprocessingnestedprocedures//savedataallocationindex dx=3;tx0=tx;table[tx].addr=cx;gen(jmp,0,0);if(lev>levmax){ error(32);}do{ if(sym==constsym){getsym();do{constdeclaration();while(sym=ma){getsym();constdeclaration();}if(sym==semicolon){ 15 getsym();}else{ error
(5);}}while(sym==ident);}if(sym==varsym){getsym();do{vardeclaration();while(sym=ma){ getsym();vardeclaration();}if(sym==semicolon){ getsym();}else{ error
(5);}}while(sym==ident);}while(sym==procsym){getsym();if(sym==ident){enter(proc);getsym();}else{error
(4);}if(sym==semicolon){getsym();}else{error
(5);}lev=lev+1;tx1=tx;dx1=dx;block(fsys|semicolon);lev=lev-1;tx=tx1;dx=dx1;if(sym==semicolon){getsym();test(statbegsys|ident|procsym,fsys,6);}else{error
(5);}}test(statbegsys|ident,declbegsys,7);}while(sym&declbegsys); 16 code[table[tx0].addr].a=cx; table[tx0].addr=cx; //startaddrofcode cx0=cx;gen(Int,0,dx); statement(fsys|semicolon|endsym); gen(opr,0,0);//return test(fsys,0,8); listcode(cx0); } longbase(longb,longl){longb1; b1=b;while(l>0){//findbasellevelsdown b1=s[b1];l=l-1;}returnb1;} voidinterpret(){longp,b,t;instructioni; //program-,base-,stack-registers//instructionregister printf("startPL/0\n");t=0;b=1;p=0;s[1]=0;s[2]=0;s[3]=0;do{ i=code[p];p=p+1;switch(i.f){ caselit:t=t+1;s[t]=i.a;break; caseopr:switch(i.a){//operatorcase0://returnt=b-1;p=s[t+3];b=s[t+2];break;case1:s[t]=-s[t];break;case2:t=t-1;s[t]=s[t]+s[t+1];break;case3: 17 t=t-1;s[t]=s[t]-s[t+1]; break; case4: t=t-1;s[t]=s[t]*s[t+1]; break; case5: t=t-1;s[t]=s[t]/s[t+1]; break; case6: s[t]=s[t]%2; break; case8: t=t-1;s[t]=(s[t]==s[t+1]); break; case9: t=t-1;s[t]=(s[t]!
=s[t+1]); break; case10: t=t-1;s[t]=(s[t]
=0);printf("endPL/0\n");} main(){ longi; for(i=0;i<256;i++){ ssym[i]=nul; } strcpy(word[0],"begin "); strcpy(word[1],"call "); strcpy(word[2],"const "); strcpy(word[3],"do "); strcpy(word[4],"end "); strcpy(word[5],"if "); strcpy(word[6],"odd "); strcpy(word[7],"procedure"); strcpy(word[8],"then "); strcpy(word[9],"var "); strcpy(word[10],"while "); wsym[0]=beginsym; wsym[1]=callsym; wsym[2]=constsym; wsym[3]=dosym; wsym[4]=endsym; wsym[5]=ifsym; wsym[6]=oddsym; wsym[7]=procsym; wsym[8]=thensym; wsym[9]=varsym; wsym[10]=whilesym; ssym['+']=plus; ssym['-']=minus; ssym['*']=times; ssym['/']=slash; ssym['(']=lparen; 19 ssym[')']=rparen;
ssym['=']=eql;ssym[',']ma;ssym['.']=period;ssym[';']=semicolon;strcpy(mnemonic[lit],"lit");strcpy(mnemonic[opr],"opr");strcpy(mnemonic[lod],"lod");strcpy(mnemonic[sto],"sto");strcpy(mnemonic[cal],"cal");strcpy(mnemonic[Int],"int");strcpy(mnemonic[jmp],"jmp");strcpy(mnemonic[jpc],"jpc");declbegsys=constsym|varsym|procsym;statbegsys=beginsym|callsym|ifsym|whilesym;facbegsys=ident|number|lparen; printf("pleaseinputsourceprogramfilename:");scanf("%s",infilename);printf("\n");if((infile=fopen(infilename,"r"))==NULL){ printf("File%scan'tbeopened.\n",infilename);exit
(1);} err=0;=0;cx=0;ll=0;ch='';kk=al;getsym();lev=0;tx=0;block(declbegsys|statbegsys|period);if(sym!
=period){ error
(9);}if(err==0){ interpret();}else{ printf("errorsinPL/0program\n");}fclose(infile);} 下面是编译器报告错误的错误编号及含义。
错误编号含义
1 应为=而不是:=
2 =后应为数 20
3 标识符后应为=
4 const，var，procedure后应为标识符
5 遗漏逗号或分号
6 过程声明后的记号不正确
7 应为语句
8 分程序内的语句部分后的记号不正确
9 应为句号 10 语句之间漏分号 11 标识符未声明 12 不可向常量或过程赋值 13 应为赋值运算符:= 14 call
后应为标识符 15 不可调用常量或变量 16 应为then 17 应为分号或end 18 应为do 19 语句后的记号不正确 20 应为关系运算符 21 表达式内不可有过程标识符 22 遗漏右括号 23 因子后不可为此记号 24 表达式不能以此记号开始 30 这个数太大 31 这个常数或地址偏移太大 32 程序嵌套层次太多 下面是一个
PL/0源程序编译和解释执行时的输出。
pleaseinputsourceprogramfilename: 0constm=7,n=85; 1varx,y,z,q,r; 1proceduremultiply; 1vara,b; 2begin
3 a:=x;b:=y;z:=0;
9 whileb>0do 13 begin 13 ifoddbthenz:=z+a; 20 a:=2*a;b:=b/2; 28 end 28end; 2int05 3lod13 4sto03 5lod14 21 30313536 start 6sto047lit008sto159lod0410lit0011opr01212jpc02913lod0414opr0615jpc02016lod1517lod0318opr0219sto1520lit0221lod0322opr0423sto0324lod0425lit0226opr0527sto0428jmp0929opr00beginx:=m;y:=n;callmultiply;end.30int0831lit0732sto0333lit08534sto0435cal0236opr00PL/0785785071442 22 2821355610112 5147224 2448 1595896 0endPL/0 附录二基于PL/0语言的课程实践选题 基于附录一的PL/0语言及其编译器，可以提出很多课程实践的课题，下面列出一些比较简单的课题，可选择实现其中的一部分。
1、给PL/0语言增加像C语言那样的形式为/∗……∗/的注释。
2、给PL/0语言增加带else子句的条件语句和exit语句。
exit语句作为while语句的非正常出口语句。
若处于多层while语句中，则它只作为最内层while语句的非正常出口。
若它没有处于任何while语句中，则是一个错误。
3、给PL/0语言增加输入输出语句。
4、给PL/0语言增加带参数的过程，参数传递按值调用方式。
5、给PL/0语言增加布尔类型，并且布尔类型的表达式按短路方式计算。
6、给PL/0语言增加数组类型。
7、给PL/0语言增加函数类型。
8、给PL/0语言增加实数类型。
9、用或类似的生成器来生成PL/0语言的编译器。
10、为PL/0实现效果更好的语法错误恢复机制。
11、分离解释器和编译器。
把解释器从现在的编译器中分离出来，变成一个独立的C语言程序。
分离后，编译器和解释器的接口是二进制形式的中间代码文件。
23
声明：
该资讯来自于互联网网友发布，如有侵犯您的权益请联系我们。