pl0v3.c

C语言写的PL0文法编译器

// This works. This supports write statement and parameters.
// sign != given by #
// sign <= given by $
// sign >= given by %
#include <string.h>
#include <stdio.h>
struct namerecord{
  int kind;
  char name[10];
  int val;
  int level;
  int adr;
  int indirect;
};
struct instruction {
  int f; int l; int a;
};
int i,ii,j,k,m, n,kind;
char line[81];
int  norw=12;     /* no. of reserved words */
int  txmax=100;   /* length of indentifier table */
int  nmax=14;     /* max. no. of digits in numbers */
int  al=10;       /* length of identifier */ 
int  amax=2047;   /* maximum address */
int  levmax=3;    /* maximum depth of block nesting */
int  cxmax=20000;   /* size of code array */
// The following is for symbol type
int nul=1; int ident=2; int number=3; int plus=4 ;
int minus=5; int mult=6; int slash=7; int oddsym=8;
int eql=9; int neq=10; int lss=11; int leq=12;
int gtr=13; int geq=14; int lparen=15; int rparen=16; 
int comma=17; int semicolon=18; int period=19; int becomes=20; 
int beginsym=21; int endsym=22; int ifsym=23; int thensym=24; 
int whilesym=25; int dosym=26; int callsym=27; int constsym=28; 
int varsym=29; int procsym=30; int writesym=31; int amper=32;
int constant=1; int variable=2; int procedure=3;
int null=0;

int lit=1; int opr=2; int lod=3; int sto=4; int cal=5; 
int inc=6; int jmp=7; int jpc=8; int wrt=9; //int dec=10;
int stp=10; int lid=11; int lda=12; int sid=13;
char ch,ch1,dummy; /*last character read */
int  sym ;    /* last symbol read */
char *id;  // *s       last identifier read}
int num;   // last number read}
int cc;   // character count}
int ll;   // line length}
int kk,ii;
int cx;   //code allocation index}
int err;
char a[10];
int s[500]; //datastore
struct namerecord table[1000];
struct instruction code[10000];
char *word[100];
int wsym[1000];
int ssym[1000];
char *mnemonic[100];
int declbegsys, statbegsys, facbegsys;
int flag;
int param[100]; //parameter buffer;
char fname[10];
FILE *f;
char c;
error(i)
 int i;
{
  printf("error %d\n",i);
}
getline()
{
 cc=0; ll=0; n=0;
 while (((c=getc(f))!=10))
 {
  if (c==EOF){ch=-1; return 0;}
  n++; ll++;
  line[n]=c;
 }
  n++; ll++; line[n]=' ';
 for (i=1; i<=n; i++)printf("%c", line[i]);
 printf("\n");
 return 1;
}
getch()
{
  if (cc==ll){
   if (ch==-1) {printf("PROGRAM INCOMPLETE"); getchar(); return 0;}
   getline();
  }
   cc=cc+1;
   ch=line[cc];
}
search()
{ int i, j, len;
  char *s;
  for (i=norw; i>=1; i--) {
    s=word[i];
    len=strlen(s);
    for (j=1; j<=len; j++){
      if(a[j]!=*s) break; 
      s++;
    }
    if (j>len){ return i;}
  }
  return 0;
}
getsym()
{
  while (ch==' ') getch();
  if ((ch >= 'A') && (ch <= 'z')) {
    k=0;
    do{  
      if (k<al){k++; a[k]=ch;};
      getch(); 
    } while(((ch>='0') && (ch<='9')) || ((ch>='A') && (ch<='z')));
   a[k+1]=0;
   id=a+1;  
   if ((i=search())!=0)sym=wsym[i]; else sym=ident; 
  } else
  if ((ch>='0') && (ch <= '9')) {
    k=0; num=0; sym=number;
      do { num=10*num + (ch - '0');
           k++; getch();
      }
      while ((ch >= '0') && (ch <= '9'));
      if (k > nmax) error(30);
  } else
  if (ch==':') {
    getch();
    if (ch=='='){
      sym=becomes; getch();
    } else sym=null;
  } else if (ch==-1) {return 0;}
  else
  {
    sym=ssym[ch]; getch();
  } 
}
gen(x,y,z)
  int x,y,z;
{
  if (cx>cxmax) printf("program too long\n"); else
  {
    code[cx].f=x;
    code[cx].l=y;
    code[cx].a=z;
  }
  cx++;
}
enter(k,ptx,pdx,lev)
int k; int *ptx; int *pdx;
int lev;
{
  char *id1;
  int ii,len;
  (*ptx)++; 
  id1=id;
  len=strlen(id);
  for (ii=0;ii<=len;ii++) {table[*ptx].name[ii]=*id1; id1++;}
  table[*ptx].kind=k;
  if (k==constant) table[*ptx].val=num;
  else if (k==variable) 
  { 
     table[*ptx].level=lev; table[*ptx].adr=*pdx; 
     table[*ptx].indirect=flag; (*pdx)++;
    }
  else /* procedure */ { table[*ptx].level=lev;}
}
mismatch(a,b)
char *a; char *b;
{
  int i; int len1; int len2;
  len1=strlen(a); len2=strlen(b);
    i=0;
  if (len1!=len2) return 1; else
  {
    while(i<=len2-1) { 
      if (a[i]!=b[i]) return 1;
      i++; 
    }
  return 0;
  }
}
int position(id,ptx)
char *id;
int *ptx;
{
 char buf[10];
 char *id1;
 int i,ii,len;
 id1=id;
 len=strlen(id);
  for (i=0;i<=len;i++) {table[0].name[i]=*id1; id1++;} 
  i=*ptx;
  do {
    len=strlen(table[i].name);
    for (ii=0;ii<=len-1;ii++) {
      buf[ii]=table[i].name[ii]; 
    }
    buf[ii]=0;
    i--;}
  while (mismatch(buf, id)); 
//  while (mismatch(&(table[i].name), id)); 
  return i+1;
}
constdeclaration(lev,ptx,pdx)
int lev,*ptx,*pdx;
{
  if (sym==ident) {
    getsym();
    if ((sym==eql) || (sym==becomes)) {
      if (sym==becomes) error(1);
      getsym();
      if (sym==number) {enter(constant,ptx,pdx,lev); getsym();}
    }
  }
}
vardeclaration(lev,ptx,pdx)
int *ptx,*pdx,lev;
{
  if (sym==ident) {enter(variable, ptx,pdx,lev); getsym();}
  else error(4); 
}
expression(int, int*); 
factor(lev, ptx)
int lev, *ptx;
{
  int i, level, adr, val;
  while ((sym==ident)||(sym==number)||(sym==lparen)) 
  {
    if (sym==ident) 
    {
      i=position(id,ptx);
      if (i==0) error(11); else
      {
        kind=table[i].kind;
        level=table[i].level;
        adr=table[i].adr;
        val=table[i].val;
        if (kind==constant) gen(lit,0,val);
        else if (kind==variable) 
			if (table[i].indirect==0) gen(lod,lev-level,adr);
            else gen(lid,lev-level,adr);
			else error(21);
      }
      getsym(); 
    } else if(sym==number) {
      if (num>amax) {error(31); num=0;}
      gen(lit,0,num); getsym();
    } else if(sym==lparen) {
      getsym(); expression(lev,ptx);
      if (sym==rparen)getsym(); else error(22);
    }
  }
}
term(lev,ptx)
int lev, *ptx;
{
  int mulop;
  factor(lev,ptx);
  while((sym==mult)||(sym==slash)) {
    mulop=sym; getsym(); factor(lev,ptx);
    if (mulop==mult) gen(opr,0,4); else gen(opr,0,5);
  }
}
expression(lev,ptx)
int lev, *ptx;
{
  int addop;
  if ((sym==plus) ||(sym==minus)){
    addop=sym; getsym(); term(lev,ptx);
    if (addop==minus) gen(opr,0,1);}
    else term(lev,ptx);
  while ((sym==plus)||(sym==minus)) {
    addop=sym; getsym(); term(lev,ptx);
    if (addop==plus) gen(opr,0,2); else gen(opr,0,3);
  }
}
condition(lev,ptx)
int lev, *ptx;
{
  int relop;
  if(sym==oddsym) {
    getsym(); expression(lev,ptx); gen(opr,0,6);}
    else {
      expression(lev,ptx);
      if ((sym!=eql)&&(sym!=neq)&&(sym!=lss)&&
         (sym!=leq)&&(sym!=gtr)&&(sym!=geq)) error(20);
      else {
        relop=sym; getsym(); expression(lev,ptx);
        switch (relop) {
          case 9: gen(opr,0,8); break;
          case 10: gen(opr,0,9); break;
          case 11: gen(opr,0,10); break;
          case 12: gen(opr,0,11); break;
          case 13: gen(opr,0,12); break;
          case 14: gen(opr,0,13);
        }
      }
    }
}
statement(lev,ptx)
int lev, *ptx;
{
  int i, cx1,cx2;
  if (sym==ident){
    i=position(id,ptx);
    if(i==0) error(11); else
    if (table[i].kind!=variable) {
      error(12); i=0;
    };
    getsym(); 
    if (sym==becomes) getsym(); else error(13);
    expression(lev,ptx);
    if (i!=0)
	  if (table[i].indirect==0)
        gen(sto, lev-table[i].level, table[i].adr);
	  else gen(sid, lev-table[i].level, table[i].adr);
  } else
  if (sym==callsym) {
    getsym();
    if (sym!=ident) error(14); else
    { i=position(id, ptx); 
      if(i==0) error(11); else
      {
      getsym();
      if (sym==lparen) {getsym(); aparam(lev,ptx); 
        if (sym==rparen) getsym(); else error(89);
      }
      if (table[i].kind==procedure) gen(cal,lev-table[i].level, table[i].adr);
      else error(15); 
      }
    }
  } else
  if (sym==ifsym) {
     getsym(); condition(lev,ptx);
     if (sym==thensym) getsym(); else error(16);
     cx1=cx; gen(jpc,0,0);
     statement(lev, ptx); code[cx1].a=cx; 
  } else
  if (sym==beginsym) {
    getsym();
    statement(lev,ptx);
    while((sym==semicolon)||(sym==beginsym)||
          (sym==ifsym)||(sym==whilesym)||
          (sym==callsym)||(sym==writesym)) {
      if(sym==semicolon) getsym(); else error(10);
      statement(lev,ptx);
    }
    if (sym==endsym) getsym(); else error(17);
  } else
  if (sym==whilesym) {
    cx1=cx; getsym(); condition(lev,ptx);
    cx2=cx; gen(jpc,0,0);
    if (sym==dosym) getsym(); else error(18);
    statement(lev,ptx); gen(jmp,0,cx1); code[cx2].a=cx;
  } else
  if (sym==writesym) {
    getsym(); 
    if (sym!=lparen) error(98); else {
      getsym(); expression(lev, ptx); gen(wrt,0,0);
      if (sym!=rparen) error(99); else getsym(); 
    }
  }
}
fparam(lev,ptx,pdx)
  int lev, *ptx,*pdx; 
{   
	if (sym==varsym) {flag=1; getsym();} else flag=0;
	if(sym==ident)vardeclaration(lev,ptx,pdx); else error(81);
    flag=0;
	while (sym==comma){
   getsym();if (sym==varsym) {flag=1; getsym();} else flag=0;
   vardeclaration(lev,ptx,pdx); flag=0;
   }  
   if(sym!=rparen) error(82);
}
aparam(lev,ptx)
  int lev, *ptx;
{
 int pnum=0; int adr,level;
 if(sym==amper) {
	 getsym(); if(sym!=ident) error(70);
	 i=position(id,ptx); adr=table[i].adr; level=table[i].level;
	 gen(lda,lev-level,adr); getsym();} 
     else expression(lev,ptx);
	 pnum++;
 while (sym==comma){ 
	 getsym(); 
	 if(sym==amper){
		 getsym(); if (sym!=ident) error(70);
		 i=position(id,ptx); adr=table[i].adr; level=table[i].level;
		 gen(lda,lev-level,adr); getsym();}
	     else expression(lev,ptx);
		 pnum++;  
 }
 while(pnum>0){gen(stp,0,0); pnum--;}
}
block(lev, tx)
int lev;
int tx;
{
  int dx, tx0, cx0;
  dx=3; tx0=tx; table[tx].adr=cx; gen(jmp,0,0);
  if (lev>levmax) error(32);
  do {
    if (sym==constsym) {
      getsym();
      do {
        constdeclaration(lev,&tx,&dx);
        while(sym==comma) {
          getsym(); constdeclaration(lev,&tx,&dx);
        }
        if(sym==semicolon)getsym(); else error(5);
      } while (sym==ident);
    }
    if (sym==varsym) {
      getsym();
      do { vardeclaration(lev,&tx,&dx);
        while (sym==comma) {
          getsym(); vardeclaration(lev,&tx,&dx);
        }
      if(sym==semicolon) getsym(); else error(5);
      } while(sym==ident);
    }
    if (sym==lparen) {
      getsym(); fparam(lev,&tx,&dx);
      if (sym==rparen) getsym(); else error(88);
    }
    while(sym==procsym) {
      getsym();
      if(sym==ident){
        enter(procedure,&tx,&dx,lev); getsym();
	  } else error(4);
      if (sym==semicolon) getsym(); else if 
        (sym==lparen); else error(5);
      block(lev+1, tx);
      if(sym==semicolon) {
        getsym();
      } else error(5);
    }
  }while ((sym==constsym)||(sym==varsym)||(sym==procsym));
  code[table[tx0].adr].a=cx;
  table[tx0].adr=cx;
  cx0=cx; gen(inc,0,dx);
  statement(lev,&tx);
  gen(opr,0,0);
}
int base(l,b)
  int l,b;
{  
  int b1; //find base l levels down
  b1=b; 
   while (l>0) {
    b1=s[b1]; l--;
   }
  return b1;
}
interpret()
{
  int stacksize=500;
  int p,b,t; //program-, base-, topstack-registers
  int i; // instruction register
  printf("start PL/0\n");
  t=0; b=1; p=0;
  s[1]=0; s[2]=0; s[3]=0;
  do {
    i=code[p].f; 
    switch (i) {
      case 1: t++; s[t]=code[p].a; p++; break; //lit
      case 2:
      switch (code[p].a) {
        case 0: { /* return */ t=b-1; p=s[t+3]; b=s[t+2];
                 break;}
        case 1: s[t]=-s[t]; p++; break;
        case 2: t--; s[t]=s[t]+s[t+1]; p++; break;
        case 3: t--; s[t]=s[t]-s[t+1]; p++; break;
        case 4: t--; s[t]=s[t]*s[t+1]; p++; break;
        case 5: t--; s[t]=s[t]/s[t+1]; p++; break;
        case 6: if ((s[t]%2)==1) s[t]=1; else s[t]=0; p++; break; 
        case 7: p++; break;
        case 8: t--; s[t]=(s[t]==s[t+1]); p++; break;
        case 9: t--; s[t]=(s[t]!=s[t+1]); p++; break;
        case 10: t--; s[t]=(s[t]<s[t+1]); p++; break;
        case 11: t--; s[t]=(s[t]<=s[t+1]); p++; break;
        case 12: t--; s[t]=(s[t]>s[t+1]); p++; break;
        case 13: t--; s[t]=(s[t]>=s[t+1]); p++; break;
      } break;
      case 3: t++; s[t]=s[base(code[p].l,b)+code[p].a]; p++; break;
      case 4: s[base(code[p].l,b)+code[p].a]=s[t];   
              p++; t--; break;
      case 5: /* generate new block mark */
         s[t+1]=base(code[p].l,b); s[t+2]=b; s[t+3]=p+1;
         b=t+1; p=code[p].a; break;
      case 6: t=t+code[p].a; p++; break;
      case 7: p=code[p].a; break;
      case 8: if (s[t]==0) p=code[p].a; else p++;
              t--; break;
      case 9: printf("%d\n",s[t]); t--; p++; break;
 	  case 10: s[t+3]=s[t]; t--; p++; break;
	  case 11: t++; s[t]=s[s[base(code[p].l,b)+code[p].a]];p++; break;
	  case 12: t++; s[t]=base(code[p].l,b)+code[p].a;p++;break;
	  case 13: s[s[base(code[p].l,b)+code[p].a]]=s[t]; p++; t--; break;
	}
//	printf("%d  ",p);
//	for(ii=1;ii<=t;ii++)printf("%d ", s[ii]);
//	getchar();
  } while (p!=0);
  printf(" END PL/0\n");
}
main()
//int argc;
//char *argv[];
{
word[1]="begin"; word[2]="call"; word[3]="const"; word[4]="do";
word[5]="end"; word[6]="if"; word[7]="odd"; word[8]="procedure";
word[9]="then"; word[10]="var"; word[11]="while"; word[12]="write";
wsym[1]=beginsym; wsym[2]=callsym; wsym[3]=constsym; wsym[4]=dosym;
wsym[5]=endsym; wsym[6]=ifsym; wsym[7]=oddsym; wsym[8]=procsym;
wsym[9]=thensym; wsym[10]=varsym; wsym[11]=whilesym; wsym[12]=writesym;
ssym['+']=plus; ssym['-']=minus; ssym['*']=mult; ssym['/']=slash;
ssym['(']=lparen; ssym[')']=rparen; ssym['=']=eql; ssym[',']=comma;
ssym['.']=period; ssym['#']=neq; ssym['<']=lss; ssym['>']=gtr;
ssym['$']=leq; ssym['%']=geq; ssym[';']=semicolon; ssym['&']=amper;
printf("input source file name ");
scanf("%s",fname);
//f=fopen("t3.txt","r");
f=fopen(fname,"r");
kk=al;
cc=0; ll=0; ch=' '; cx=0;
getsym();
block(0,0);
getchar();
getchar();
for (i=0;i<=cx-1;i++) {
  if (i<10) printf(" ");
  printf("%d ",i);
  switch (code[i].f) {
    case 1: printf("lit "); break;
    case 2: printf("opr "); break;
    case 3: printf("lod "); break;
    case 4: printf("sto "); break;
    case 5: printf("cal "); break;
    case 6: printf("inc "); break;
    case 7: printf("jmp "); break;
    case 8: printf("jpc "); break;
    case 9: printf("wrt "); break;
    case 10: printf("stp "); break;
	case 11: printf("lid "); break;
	case 12: printf("lda "); break;
	case 13: printf("sid "); break;
  }
  printf("%d ", code[i].l);
  printf("%d ", code[i].a);
  printf("\n");
}
if (sym!=period) error(9);
getchar();
interpret();
getchar();
}