pl0v1.c

C语言写的PL0文法编译器

/* Further modified, 16 Feb 2001
 This works
 This compiler supports only lower-case chracters
 sign != given by #
 sign <= given by $
 sign >= given by %
*/
#include <stdio.h>
struct namerecord{ /*** This records properties of a user defined name ***/
  int kind;
  char name[10];
  int val;
  int level;
  int adr;
};
struct instruction {  /*** This defines a machine instruction ***/
  int f;
  int l;
  int a;
};
int i,ii,j,k,m, n,kind;
char line[81];    /* container of one line of user program */
int  norw=11;     /* 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=200;   /* 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 constant=1; int variable=2; int procedure=3;
int null=0;

/* The following is the list of machine instructions */
int lit=1; int opr=2; int lod=3; int sto=4; int cal=5; 
int inc=6; int jmp=7; int jpc=8;

char ch,ch1,dummy; /*last character read */
int  sym ;    /* last symbol read */
char *id;  /* 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]; /* container of user defined names */
struct instruction code[1000];
char *word[100];
int wsym[1000]; /* container of word symbols */
int ssym[1000]; /* container of special symbols */
char *mnemonic[100];
int declbegsys, statbegsys, facbegsys;
FILE *f;
char c;
error(i) /* error handling */
 int i;
{
  printf("error %d\n",i);
}
getline() /* get one line */
{
 cc=0; ll=0; n=0;
 while (((c=getc(f))!=10)) /*** while character is not "return" key ***/
 {
  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() /* get one character */
{
  if (cc==ll){
   if (ch==-1) {printf("PROGRAM INCOMPLETE"); getchar(); return 0;}
   getline();
  }
  cc=cc+1;
  ch=line[cc];
}
search() /* serch for a reserved word */
{ 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() /* gets one symbol */
{
  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;}
  else
  {
    sym=ssym[ch]; getch();
  } 
}
gen(x,y,z) /* This generates one instruction */
  int x,y,z;
{
  if (cx>cxmax) error(99); else
  {
    code[cx].f=x;
    code[cx].l=y;
    code[cx].a=z;
  }
  cx++;
}
enter(k,ptx,pdx,lev) /* This enters a symbol into the table */
int k; int *ptx; int *pdx;  /* *ptx: pointer to the table */
int lev;                    /* *pdx: data allocation index */
{
  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; (*pdx)++; }
  else /* procedure */ { table[*ptx].level=lev;}
}
mismatch(a,b)  /* if a and b mismatch, return true */
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++; /* a++; */
    }
  return 0;
  }
}
int position(id,ptx) /* This finds the position of id */
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)); 
  return i+1;
}
constdeclaration(lev,ptx,pdx)
int *ptx, *pdx, lev;
{
  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); 
}
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); /* generates load literal */
        else if (kind==variable) gen(lod,lev-level,adr); /* generates load */
        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);  /* multiplication */
                else gen(opr,0,5);  /* division */
  }
}
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); /* addition */
                else gen(opr,0,3); /* subtraction */ 
  }
}
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;   /* equal */
          case 10: gen(opr,0,9); break;  /* not equal */
          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) 
      gen(sto, lev-table[i].level, table[i].adr);
  } else
  if (sym==callsym) { /* procedure call */
    getsym();
    if (sym!=ident) error(14); else
    { i=position(id, ptx); 
      if(i==0) error(11); else
      if (table[i].kind==procedure) 
        gen(cal,lev-table[i].level, table[i].adr);
      else error(15); 
      getsym();
    }
  } else
  if (sym==ifsym) { /* if statement */
     getsym(); condition(lev,ptx);
     if (sym==thensym) getsym(); else error(16);
     cx1=cx; gen(jpc,0,0); /* c1 memorizes code index of jpc */
     statement(lev, ptx); code[cx1].a=cx; /* fix-up for jump address */
  } else
  if (sym==beginsym) {  /* begin ... end */
    getsym();
    statement(lev,ptx);
    while((sym==semicolon)||(sym==whilesym)||
          (sym==ifsym)|| (sym==callsym)||(sym==beginsym))
    {
      if(sym==semicolon) getsym(); else error(10);
      statement(lev,ptx);
    }
    if (sym==endsym) getsym(); else error(17); 
  } else
  if (sym==whilesym) { /* while statement */
    cx1=cx; getsym(); condition(lev,ptx);
    cx2=cx; gen(jpc,0,0); /* c2 memorizes code index of jpc */
    if (sym==dosym) getsym(); else error(18);
    statement(lev,ptx); gen(jmp,0,cx1);  /* jump to beginning of condition */
    code[cx2].a=cx; /* fix-up */
  }
}
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();
        constdeclaration(lev,&tx,&dx);
        while(sym==comma) {
          getsym(); constdeclaration(lev,&tx,&dx);
        }
        if(sym==semicolon)getsym(); else error(5);
    }
    if (sym==varsym) {
      getsym();
        vardeclaration(lev,&tx,&dx);
        while (sym==comma) {
          getsym(); vardeclaration(lev,&tx,&dx);
        }
      if(sym==semicolon) getsym(); else error(5);
    }
    while(sym==procsym) {
      getsym();
      if(sym==ident){
        enter(procedure,&tx,&dx,lev); getsym();
      } else error(4);
      if (sym==semicolon) getsym(); 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++; printf("%d\n", s[t]); 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;
    }
  } while (p!=0);
  printf(" END PL/0\n");
}
main(argc, argv)
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";
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;
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;

f=fopen(*++argv,"r");
kk=al;
cc=0; ll=0; ch=' '; cx=0;
getsym();
block(0,0);
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;
  }
  printf("%d ", code[i].l);
  printf("%d ", code[i].a);
  printf("\n");
}
if (sym!=period) error(9);
getchar();
interpret();
exit:;
}