pl0.txt

ＰＬ／０的Ｃ语言版本

这是我编译原理课程的课程设计时写的，对PL0文法进行了扩充，主要增加了数组及结构体的功能，并用C语言实现了之。可能有人需要，就在这贴出来了。

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "ctype.h"

#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

typedef int BOOL;

#define cxmax 2000
#define amax 16383

#define imax 100 /* length of identifier table */
#define tmax 100 /* length of type table */
#define lmax 10  /* maximum level */
#define al 10  /* length of identifiers */
#define norw 27  /* number of reserverd words */

/* standard function */
#define fabs 0
#define fsqr 1
#define fodd 2
#define fchr 3
#define ford 4
#define fwrite 5
#define fwriteln 6
#define fread 7
#define freadln 8
#define feoln 9

/* standard types */
#define intip 1
#define booltip 2
#define chartip 3

/*指令码*/
typedef enum opcode{
 add, neg, mul, divd, remd, div2, rem2, eqli, neqi, lssi,
    leqi, gtri, geqi, dupl, swap, andb, orb,
 load, stor, hhalt, wri, wrc, wrl, rdi, rdc, rdl, eol,
    ldc, ldla, ldl, ldg, stl, stg, move, copy, addc, mulc,
    jump, jumpz, call, adjs, sets, pexit
}opcode;

/*指令结构体*/
typedef struct instr{
 opcode op;
 int a;
}instr;

/*词法类别*/
typedef enum symbol{
 ident, number, sstring, plus, minus, star, lbrack, rbrack,
 colon, eql, neq, lss, leq, gtr, geq, lparen, rparen, comma, 
 semicolon, period, becomes,
 beginsym, endsym, ifsym, thensym, elsesym, whilesym, dosym,
 casesym, repeatsym, untilsym, forsym, tosym, downtosym,
 notsym, divsym, modsym, andsym, orsym, constsym, varsym,
 typesym, arraysym, ofsym, recordsym, progsym, funcsym,
 procsym
}symbol;

/*变量类型*/
typedef enum idkind{
 konst, varbl, field, tipe, funkt
}idkind;

/*类型的种类，简单的，数组，记录类型*/
typedef enum tpkind{
 simple, arrays, records
}tpkind;

typedef char alfa[al+1];

instr code[cxmax + 1];
int m[amax + 1];

/*词法分析相关全局变量*/
char ch;
int cc = 0, ll = 0;
char line[129];
symbol sym;
alfa id;
int num;
char str[81];
int slen;
/*alfa word[norw + 1];*/
int cx;
int lev;
int dx;
BOOL labeled;
int nl; /* as namelist[-1] */
int namelist[lmax];
int ix, tx; /* indices in tables */

/* identifier table */
typedef struct ITAB{
 alfa name;
 int link;
 int tip;
 idkind kind;
 union{
  int val; /*常量类型的值*/
  struct{
   int vlevel;
   int vadr;
   BOOL refpar;
  };   /*变量类型的属性*/
  int offset; /*域类型的偏移地址*/
  struct{
   int flevel;
   int fadr;
   int lastpar;
   int resultadr;
   BOOL inside;
  };   /*函数类型的属性*/
 };
}ITAB;
ITAB itab[imax + 1];

/* type table */
typedef struct TTAB{
 int size;
 tpkind kind;
 union{
  struct{
   int low;
   int high;
   int elemtip;
  }; /*数组类型的属性*/
  int fields; /*记录类型最后一个域的地址*/
 };
}TTAB;
TTAB ttab[tmax + 1];

/*保留字*/
static struct{
 alfa name;
 symbol lex;
}word[] = {
 { "", -1 },
 { "begin", beginsym },
 { "end", endsym },
 { "if", ifsym },
 { "then", thensym },
 { "else", elsesym },
 { "while", whilesym },
 { "do", dosym },
 { "case", casesym },
 { "repeat", repeatsym },
 { "until", untilsym },
 { "for", forsym },
 { "to", tosym },
 { "downto", downtosym },
 { "not", notsym },
 { "div", divsym },
 { "mod", modsym },
 { "and", andsym },
 { "or", orsym },
 { "const", constsym },
 { "var", varsym },
 { "type", typesym },
 { "array", arraysym },
 { "of", ofsym },
 { "record", recordsym },
 { "program", progsym },
 { "function", funcsym },
 { "procedure", procsym }
};

FILE * source;
BOOL eof_flag = FALSE;

symbol search()
{
 int i;
 for(i = norw; i >= 1; i--)
 {
  if(strcmp(id, word[i].name) == 0)
   return word[i].lex;
 }
 return ident;
}

void error(int n)
{
 int i;
 for(i = 0; i < ll; i++)
  putchar(line[i]);
 for(i = 0; i <= cc - 1; i++)
  putchar(' ');
 printf("^\n");
 printf("error %d detected\n", n);
 exit(1);
}

void getch()
{
 if (cc == ll)
 {
  memset(line, 0, 129);
  if(feof(source))
  {
   fprintf(stderr, "program incomplete\n");
   exit(0);
  }
  ll = 0;
  cc = 0;
  while(!feof(source) && (ch = getc(source)) != '\n')
  {
   line[ll] = ch;
   ll++;
  }
  if(ch == '\n')
  {
   line[ll] = ch;
   ll++;
  }
 }
 ch = line[cc];
 cc++;
}

void getsym()
{
 int k;
 int strend;
 while(ch == ' ' || ch == '\t' || ch == '\n')
  getch();
 if(isalpha(ch))
 {
  memset(id, 0, al+1);
  k = 0;
  do{
   if(k != al)
   {
    id[k] = ch;
    k++;
   }
   getch();
  }while(isalnum(ch));
  sym = search();
 }
 else if(isdigit(ch))
 {
  num = 0;
  sym = number;
  do{
   num = 10 * num + (ch - '0');
   getch();
  }while(isdigit(ch));
 }
 else if(ch == ':')
 {
  getch();
  if(ch == '=')
  {
   getch();
   sym = becomes;
  }
  else
   sym = colon;
 }
 else if(ch == '>')
 {
  getch();
  if(ch == '=')
  {
   getch();
   sym = geq;
  }
  else
   sym = gtr;
 }
 else if(ch == '<')
 {
  getch();
  if(ch == '=')
  {
   getch();
   sym = leq;
  }
  else if(ch == '>')
  {
   getch();
   sym = neq;
  }
  else
   sym = lss;
 }
 else if(ch == '.')
 {
  getch();
  if(ch == '.')
  {
   getch();
   sym = colon;
  }
  else
   sym = period;
 }
 else if(ch == '\'')
 {
  slen = 0;
  strend = FALSE;
  sym = sstring;
  do{
   if(cc == ll)
    error(101);
   getch();
   if(ch == '\'')
   {
    getch();
    if(ch == '\'')
    {
     str[slen] = ch;
     slen++;
    }
    else
     strend = TRUE;
   }
   else
   {
    str[slen] = ch;
    slen++;
   }
  }while(strend == FALSE);
  if(slen == 0)
   error(102); /*不允许空字符串*/
  str[slen++] = '\0';
 }
 else if(ch == '+')
 {
  getch();
  sym = plus;
 }
 else if(ch == '-')
 {
  getch();
  sym = minus;
 }
 else if(ch == '*')
 {
  getch();
  sym = star;
 }
 else if(ch == '(')
 {
  getch();
  sym = lparen;
 }
 else if(ch == ')')
 {
  getch();
  sym = rparen;
 }
 else if(ch == '[')
 {
  getch();
  sym = lbrack;
 }
 else if(ch == ']')
 {
  getch();
  sym = rbrack;
 }
 else if(ch == '=')
 {
  getch();
  sym = eql;
 }
 else if(ch == ',')
 {
  getch();
  sym = comma;
 }
 else if(ch == ';')
 {
  getch();
  sym = semicolon;
 }
 else if(ch == '{')
 {
  do{
   getch();
  }while(ch != '}');
  getch();
  getsym();
 }
 else
  error(104);
}

void check(symbol s)
{
 if(sym != s)
  error(s);
}

void skip(symbol s)
{
 check(s);
 getsym();
}

/*将符号串登记入符号表*/
void enter(alfa id, idkind k, int t)
{
 int j;
 if(ix == imax)
  error(104);
 else
 {
  ix++;
  strcpy(itab[0].name, id);
  if(lev == -1)
   j = nl;
  else
   j = namelist[lev];
  while(strcmp(itab[j].name, id) != 0)
   j = itab[j].link;
  if(j != 0)
   error(105);
  else
  {
   strcpy(itab[ix].name, id);
   if(lev == -1)
    itab[ix].link = nl;
   else
    itab[ix].link = namelist[lev];
   itab[ix].tip = t;
   itab[ix].kind = k;
   
   if(lev == -1)
    nl = ix;
   else
    namelist[lev] = ix;
  }
 }
}

/*在符号表中查找符号，返回位置*/
int position()
{
 int i , j;
 strcpy(itab[0].name, id);
 i = lev;
 do{
  if(i == -1)
   j = nl;
  else
   j = namelist[i];
  while(strcmp(itab[j].name, id) != 0)
   j = itab[j].link;
  i = i - 1;
 }while(i >= -1 && j == 0);
 if(j == 0)
  error(106);
 return j;
}

void gen(instr i)
{
 switch(i.op)
 {
 case dupl:
 case eol:
 case ldc:
 case ldla:
 case ldl:
 case ldg:
  dx = dx - 1;
  break;
 case add:
 case mul:
 case divd:
 case remd:
 case eqli:
 case neqi:
 case lssi:
 case leqi:
 case gtri:
 case geqi:
 case andb:
 case orb:
 case wrc:
 case rdi:
 case rdc:
 case stl:
 case stg:
 case jumpz:
  dx = dx + 1;
  break;
 case stor:
 case wri:
 case move:
  dx = dx + 2;
  break;
 case copy:
  dx = dx - i.a + 1;
  break;
 case adjs:
  dx = dx + i.a;
  break;
 }
 if(!(((i.op == addc || i.op == adjs) && (i.a == 0)) || ((i.op == mulc) && (i.a == 1))))
 {
  if(labeled)
  {
   code[cx] = i;
   cx = cx +1;
   labeled = FALSE;
  }
  else if(code[cx - 1].op == ldc && i.op == add)
  {
   code[cx - 1].op = addc;
  }
  else if(code[cx - 1].op == ldc && i.op == mul)
  {
   code[cx - 1].op = mulc;
  }
  else if(code[cx - 1].op == ldc &&  i.op == neg)
  {
   code[cx - 1].a = -code[cx - 1].a;
  }
  else if(code[cx - 1].op == ldc && code[cx - 1].a == 2 && i.op == divd)
  {
   code[cx - 1].op = div2;
  }
  else if(code[cx - 1].op == ldc && code[cx - 1].a == 2 && i.op == remd)
  {
   code[cx - 1].op = rem2;
  }
  else if(code[cx - 1].op == ldc && i.op == stor)
  {
   code[cx - 1].op = stg;
  }
  else if(code[cx - 1].op == ldc && i.op == load)
  {
   code[cx - 1].op = ldg;
  }
  else if(code[cx - 1].op == ldla && i.op == stor)
  {
   code[cx - 1].op = stl;
  }
  else if(code[cx - 1].op == ldla && i.op == load)
  {
   code[cx - 1].op = ldl;
  }
  else
  {
   code[cx] = i;
   cx = cx + 1;
  }
 }
}

void gen0(opcode op)
{
 instr i;
 i.op = op;
 gen(i);
}

void gen1(opcode op, int a)
{
 instr i;
 i.op = op;
 i.a = a;
 gen(i);
}

int codelabel()
{
 labeled = TRUE;
 return cx;
}

void address(int lv, int ad)
{
 if(lv == 0)
  gen1(ldc, ad);
 else if(lv == lev)
  gen1(ldla, ad - dx);
 else
 {
  gen1(ldl, -dx);
  while(lv + 1 != lev)
  {
   gen0(load);
   lv = lv + 1;
  }
  gen1(addc, ad);
 }
}

void addressvar(int ref)
{
 address(itab[ref].vlevel, itab[ref].vadr);
 if(itab[ref].refpar)
  gen0(load);
}

void mustbe(int x, int y)
{
 if(x != y)
 {
  if((ttab[x].kind == arrays) && (ttab[y].kind == arrays) && 
   (ttab[x].low == ttab[y].low) && (ttab[x].high == ttab[y].high))
   mustbe(ttab[x].elemtip, ttab[y].elemtip);
  else
   error(107);/*类型不匹配*/
 }
}

void expression(int * x);

void selector(int * t, int * ref)
{
 int j, x;
 *t = itab[*ref].tip;
 getsym();
 if(sym == period ||sym == lbrack)
 {
  addressvar(*ref);
  *ref = 0;
  while(sym == period || sym == lbrack)
  {
   switch(sym)
   {
   case period:
    if(ttab[*t].kind != records)
     error(108);
    else
    {
     getsym();
     check(ident);
     j = ttab[*t].fields;
     strcpy(itab[0].name, id);
     while(strcmp(itab[0].name, id) != 0)
      j = itab[j].link;
     if(j == 0)
      error(109);
     else
     {
      gen1(addc, itab[j].offset);
      *t = itab[j].tip;
      getsym();
     }
    }
    break;
   case lbrack:
    do{
     if(ttab[*t].kind != arrays)
      error(110);
     else
     {
      getsym();
      expression(&x);
      mustbe(intip, x);
      gen1(addc, -(ttab[*t].low));
      *t = ttab[*t].elemtip;
      gen1(mulc, ttab[*t].size);
      gen0(add);