#define LIT 1
#define LOD 2
#define STO 3
#define CAL 4
#define INT 5
#define JMP 6
#define JPC 7
#define OPR 8
#define NUL ENDARRAY
/*假想栈式计算机目标指令集
指令格式: f l a
1。lit :将常量取到运行栈顶,a域为常数值
2。lod:将变量放到栈顶。a域为变量在所说明层的相对位置,l为调用层与说明层的层差值。
3。sto:将栈顶的内容送入某变量单元中。a,l域的含义同lod指令。
4。cal:调用过程的指令。a为被调用过程的目标程序入口地址,l为层差
5。int:为被调用的过程(或主程序)在运行栈中开辟数据区。a域为开辟的单元个数。
6。jmp:无条件转移指令,a为转向地址。
7。jpc:条件转移指令,当栈顶的布尔值为非真时,转向a域的地址,否则顺序执行。
8。 opr: 关系运算和算术运算指令。具体操作由a域值给出
0 return
1 - (求反)
2 +
3 -(减)
4 *
5 /
6 true
7
8 ==
9 <>
10 <
11 >=
12 >
13 <=
*//
/*
PL0语言的ENBF表示
<程序>::=<分程序>.
<分程序>::=[<变量说明>][<过程说明>]<语句>
<数字>::=<数字>{<数字>}
<变量说明>:=VAR〈标识符〉{,〈标识符};
〈标识符〉::=〈字母〉{〈字母〉|〈数字〉}
<过程说明>::=〈过程首部〉〈分程序〉{;〈过程说明〉};
〈过程首部〉::=FUNC〈标识符〉;
〈语句〉::=〈赋值语句〉|〈条件语句〉|〈循环语句〉|〈过程调用语句〉|〈读语句〉|〈写语句|〉〈复合语句〉|〈空〉
〈赋值语句〉::=〈标识符〉:=〈表达式〉
〈复合语句〉::=BEG〈语句〉{,〈语句〉}END
〈条件〉::=〈表达式〉〈关系运算符
〈表达式〉::=[+|-]<项>{〈加法运算符〉〈项〉};
〈项〉::=〈因子〉{〈乘法运算符〉〈因子〉}
〈因子〉::=〈标识符〉|〈数字〉‘(’表达式‘)
〈加法运算符〉:=+|-
〈乘法运算符〉:=*|/
〈关系运算符〉:==|#|〈|〈=|〉|〉=
〈条件语句〉::=IF〈条件〉THEN〈语句〉
〈当循环语句〉::WHILE〈条件〉DO〈语句〉
〈读语句〉:=READ‘(’〈标识符〉{,〈标识符〉}‘)’
〈写语句〉:=WRITE‘(’〈表达式〉{,〈表达式〉}‘)’
〈字母〉:=a|b...X|Y|Z
〈数〉::<-><数字><.数字><e><数字><数字>
〈数字〉::=1|2|3|4|5|6|7|8|9|0
*/''
//变量有三种类型 ,num,string,func
/*error:
99 块中的变量名过多
32 层数太深
5 函数名后要加分号
11 未定义的标识符
15 不是函数
16 函数参数没有用“,”分割
34 函数调用的括号不对
48 保留字太多
49 实数中的e后要跟数字
*/
#define sp 0
#define dot 1
#define eql 2
#define plus 3
#define
# define EOF .
# define maxidt 8
# define maxvar 100 // every block can have 100 variables
# define norw 16
# define txmax 100 //最多100个标识符
# define al 10
# define nmax 14
# define amax 2047
# define levmax 3
# define cxmax 2000//最多2000条指令
# define stacksize 5000
# define maxchar 5000
/*-----------------------type define-----------------------------*/
typedef struct { int level, size, foot;
int adr;
ldouble numval;
char * strval;
char name[maxidt];
char kind; // v(variable) or f(func) s(string) or n(num)
} tbl;
typedef struct { int f;//instruct 指令号
int l;//level 层次
int a;//addition
} instruction;
typedef struct {
int size; //how many syms in set now
char sym[maxvar][maxidt];// sym set
} symset;
int strcpy(char *,char *);
int strcmp(char *,char *);
/*------------------------------variable declaration------------------------*/
ldouble g_num;
char * g_str;
int ll,cc,err,num,kk,cx,line[81];
int s;
char id[maxidt];//当前标识符
char sym[maxidt];//当前标识符类型
char a[maxidt];
char ch;
char text[maxchar];
int ptext;
instruction code[cxmax+1];
tbl table[txmax+1]={0};
#define FUNC 3864
#define IF 43
#define THEN 8436
#define ELSE 3573
#define WHIL 9445
#define DO 36
#define BEG 234
#define END 343
#define SHIF 7447
#define WRIT 9748
#define READ 7323
#define AND 263
#define OR 67
#define NOT 668
#define USESYM 99
#define BEGINSYM 120
#define IFSYM 121
#define WHILESYM 122
#define READSYM 123
#define WRITESYM 124
#define DOSYM 127
char * word[]={0,"beg","else","end","if","func","read","then","var","whil","writ","do","*"};
int wsym[]={0,BEGSYM,ELSESYM,ENDSYM,IFSYM,FUNCSYM,READSYM,THENSYM,VARSYM,WHILESYM,WRITESYM,DOSYM,"*"};
#define PERIOD 100
#define LT 101
#define GT 102
#define LE 103
#define GE 104
#define LP 105
#define PLUS 106
#define TIMES 107
#define RP 108
#define SEMI 109
#define MINUS 110
#define SLASH 111
#define AND 112
#define OR 113
#define NOT 114
#define NE 115
#define EQ 116
#define COMMA 117
int ssym[]={PERIOD,LT,GT,LE,GE,LP,PLUS,TIMES,RP,SEMI,MINUS,SLASH,AND,OR,NOT,NE,EQ,COMMA};
#define VARSYM 118
#define FUNCSYM 119
#define ENDARRAY
int declbegsys[]={ VARSYM,FUNCSYM,ENDARRAY};
int statbegsys[]={ BEGINSYM,IFSYM,WHILESYM,READSYM,WRITESYM,ENDARRAY};
#define IDENT 125
#define NUM 126
#define LP 105
int facbegsys[]={IDENT,NUM,LP,ENDARRAY};
//after a block ,follow sym can appear
int fsysa[]={PERIOD,VARSYM,FUNCSYM,BEGINSYM,IFSYM,WHILESYM,ENDARRAY};
#define BECOME 127
int what_identify(char ch){
switch(ch){
case '.':return PERIOD;break;
case '<':return LT;break;
case '>':return GT;break;
case '(':return LP;break;
case '+':return PLUS;break;
case '*':return TIMES;break;
case ')':return RP;break;
case ';':return SEMI;break;
case '-':return MINUS;break;
case '/':return SLASH;break;
case '!':return NE;break;
case '=':return EQ;break;
default:return "";
}
}
void gen(int , int , int );
void error(int n);
void getsym();
void constdeclaration(int *dx,int *tx,int lev);
void vardeclaration(int * dx,int *tx,int lev);
void enter(char k,int *dx,int *tx,int lev);
void insert(int sym1,symset * fsys,symset *fsys1);
void test(symset * s1,symset * s2,int n);
int in(int sm,symset * fsys);
void statement(symset * fsys,int tx,int lev);
void listcode(int cx0);
int position(char * id,int tx);
void expression(symset * fsys,int tx,int lev);
void term(symset *fsys,int tx,int lev);
void condition(symset *fsys,int tx,int lev);
void factor(symset *fsys,int tx,int lev);
void getch();
/*------------------------------block (lev, tx, fsys)-----------------------------*/
void block(int lev,int tx,symset * fsys)
{
int tx0,tx1,cx0,dx;
symset fsys1={0};
dx=3;
tx0=tx;
table[tx].adr=cx;
gen(JMP,0,0);
if (lev>levmax)error(32);
do{
if (sym==USESYM){
getsym();
do{
usedeclaration(&dx,&tx,lev);
if (sym=SEMI) getsym();
else error(5);
} while (sym==IDENT);
}
if (sym==VARSYM){
getsym();
do{
vardeclaration(&dx,&tx,lev);
while (sym==COMMA){
getsym();
vardeclaration(&dx,&tx,lev);
}
if (sym==SEMI) getsym();
else error(5);
} while (sym==IDENT);
}
while (sym,FUNCSYM){//过程首部
getsym();
if (sym==IDENT){
enter('f',&dx,&tx,lev);
getsym( );
}
else error(4);
if (sym==SEMI) getsym( );//过程首部后加分号
else error(5);
insert(SEMI,fsys,&fsys1);
// "semicolon" and the fsys now and front the follow sym
block(lev+1,tx,&fsys1);//分程序
if (sym==SEMI)
{
getsym();
//ident and procsym can follow "declbegsys
//子程序说明之后可以跟变量说明,函数说明,语句开始符号
//
//〈语句〉::=〈赋值语句〉|〈条件语句〉|〈循环语句〉|〈过程调用语句〉|〈读语句〉|〈写语句|〉〈复合语句〉
// ident,if,while,reads,readn,writes,writen,beg,
//后面跟<语句> 或者继续是子程序说明
//
insert(IDENT,&statbegsys,&fsys1);
insert(FUNCSYM,&fsys1,&fsys1);
test( fsys,&fsys1,6);
}
else error(5);
}
//块中的最外层的函数说明之后 ident,if,while,reads,readn,writes,writen,beg,
//不能再声明分程序
insert(IDENT,&statbegsys,&fsys1);
test(&fsys1,&declbegsys,7);
} while (in(sym,declbegsys));
code[table[tx0].adr].a=cx;
table[tx0].adr=cx;
table[tx0].size=dx;
cx0=cx;
gen(INT,0,dx);
insert(SEMI,fsys,&fsys1);
insert(ENDSYM,&fsys1,&fsys1);
statement(fsys1,tx,lev);
gen(OPR,0,0);
test(fsys,fsys,8);
listcode(cx0);
}
/*-----------------------------------statement (fsys, tx, lev)---------------------*/
void statement(symset * fsys,int tx,int lev)
{
symset fsys1={0};
int i,cx1,cx2;
if (sym==IDENT){//可能是数字 字符串 函数
i=position(id,tx);
if (i==0){
error(11);
}
else
if (table[i].kind!='v'){
error(12);
i=0;
}
getsym( );
if (sym==BECOME)
getsym();
else
error(13);
expression(fsys,tx,lev);
if (i!=0)
gen(STO,lev-table[i].level,table[i].adr);
}
else
if (sym==READSYM)
{
getsym( );
if (sym==LP)error(34);//函数调用的括号不对
else
do
{
getsym ();
if ( sym==LP)
error (34);//
if (sym==IDENT)
i=position(id,tx);
else
i=0;
if (i==0)
error(35);
else
{
gen(OPR,0,16);
gen(STO,lev-table[i].level,table[i].adr);
}
getsym( );
} while (sym==COMMA);
if (sym!=RP)
{
error(33);
while (in(sym,fsys)==0)
getsym( );
}
else
getsym();
}
else
if (sym==WRITESYM)
{
getsym();
if (sym==LP)
{
do
{
getsym( );
insert(RP,fsys,&fsys1);
insert(COMMA,fsys1,&fsys1);
expression(fsys1,tx,lev);
gen(OPR,0,14);
} while (sym==COMMA);
if (sym!=RP)
error(33);
else
getsym( );
}
gen(OPR,0,15);
}
else
if (sym==CALLSYM)
{
getsym();
if (sym!=IDENT)
error(14);
else
{
i=position(id, tx);
if (i==0)
error(11);
else
if (table[i].kind!='p')
error(15);
else{
gen(CAL,lev-table[i].level,table[i].adr);
getsym( );
if(sym==LP){
while(sym!=RP){
getsym();
if (sym==IDENT){//可能是数字 字符串 函数
i=position(id,tx);
if (i==0){
error(11);
}
else
if (table[i].kind!='v'){
error(12);
i=0;
}
//参数出栈
gen(LOD,lev-table[i].level,table[i].adr);
getsym( );
if(sym!=COMMA){
error(16);
}
getsym();
}
}
}
getsym( );
}
}
else
if (sym==IFSYM)
{
getsym( );
insert(THENSYM,fsys,&fsys1);
condition(fsys1,tx,lev);
if (sym==THENSYM)
getsym( );
else
error(16);
cx1=cx;
gen(JPC,0,0);
statement(fsys,tx,lev);
code[cx1].a=cx;//跳出地址
}
else
if (sym==BEGINSYM)
{
getsym();
insert(SEMI,fsys,&fsys1);
insert(ENDSYM,fsys1,&fsys1);
statement(fsys1,tx,lev);
while (in(sym,statbegsys) || (sym==SEMI))
{
if (sym==SEMI)
getsym( );
else
error(10);
statement(fsys1,tx,lev);
}
if (sym==ENDSYM)
getsym( );
else
error(17);
}
else
if (sym==WHILESYM)
{
cx1=cx;
getsym( );
insert(DOSYM,fsys,&fsys1);
condition(fsys1,tx,lev);
cx2=cx;
gen(JPC,0,0);
if (sym==DOSYM)
getsym( );
else
error(18);
statement(fsys,tx,lev);
gen(JMP,0,cx1); /* has been changed */
code[cx2].a=cx;//跳出循环
}
}
/*----------------------condition (fsys, tx, lev)----------------------*/
void condition(symset fsys,int tx,int lev)
{
int relop;
symset fsys1={0};
insert(EQ,fsys,&fsys1);
insert(NE,fsys1,&fsys1);
insert(LS,fsys1,&fsys1);
insert(LE,fsys1,&fsys1);
insert(GT,fsys1,&fsys1);
insert(GE,fsys1,&fsys1);
expression(fsys1,tx,lev);
if ((sym!=EQ) && (sym!=NE)
&& (sym!=LS) && (sym!=LE)
&&(sym!=GT) && (sym!=GEge))
error(20);
else
{
relop=sym;
getsym( );
expression(fsys,tx,lev);
if (relop==EQ) gen(OPR,0,8);
if (relop==NE) gen(OPR,0,9);
if (relop==LS) gen(OPR,0,10);
if (relop==LE) gen(OPR,0,11);
if (relop==GT) gen(OPR,0,12);
if (relop==GE) gen(OPR,0,13);
}
}
/*-------------------expression (fsys, tx, lev)----------------------*/
void expression(symset fsys,int tx,int lev)
{
int addop;
symset fsys1;
insert(PLUS,fsys,&fsys1);
insert(MINUS,fsys1,&fsys1);
if ((sym==PLUS) || (sym==MINUS)){
addop=sym;
getsym( );
term(fsys1,tx,lev);
if (addop==MINUS)
gen(OPR,0,1);
}
else term(fsys1,tx,lev);
while ((sym==PLUS) || (sym==MINUS))
{
addop=sym;
getsym( );
term(fsys1,tx,lev);
if (addop==PLUS)
gen(OPR,0,2);
else
gen(OPR,0,3);
}
}
/*-----------------term (fsys, tx, lev)-----------------------*/
void term(symset * fsys,int tx,int lev){
int mulop;
symset fsys1={0};
insert(TIMES,fsys,&fsys1);
insert(SLASH,fsys1,&fsys1);
factor(fsys1,tx,lev);
while ((sym==TIMES) || (sym==SLASH)){
mulop=sym;
getsym( );
factor(fsys1,tx,lev);
if (mulop==TIMES)
gen(OPR,0,4);
else gen(OPR,0,5);
}
}
/*------------------factor (fsys, tx, lev)--------------------*/
void factor(symset fsys,int tx,int lev)
{
symset fsys1={0};
int i;
test(facbegsys,fsys,24);
while (in(sym,facbegsys)==1)
{
if (sym==IDENT)
{
i=position(id,tx);
if (i==0) error(11);
else
{
if (table[i].kind=='v'){
gen(LOD,lev-table[i].level,table[i].adr);
}
if (table[i].kind=='f')
error(21);
}
getsym();//
}
else if (sym==NUM){
if (num>amax){
error(31);
num =0;
}
gen(LIT,0,num);
getsym( );
}
else if (sym==LP){
getsym();
insert(RP,fsys,&fsys1);
expression(fsys1,tx,lev);
if (sym==RP) getsym();
else error(22);
}
test(fsys,facbegsys,23);
}
}
/*-------------------vardeclaration (&dx, &tx, lev)---------------------*/
void vardeclaration(int * dx,int *tx,int lev)
{
if (sym==IDENT){
enter('v',dx,tx,lev);
getsym();
}
else error(4);
}
/*-----------------------------enter (k)-----------------------------------*/
void enter(char k,int *dx,int *tx,int lev)
{
if(tx==txmax) {
error(99);
return;
}
(*tx)++;
table[(*tx)].kind=k;
strcpy(table[(*tx)].name,g_id);
if (k=='v'){
table[(*tx)].level=lev;
table[(*tx)].adr=(*dx);
(*dx)++;
}
if (k=='f') table[(*tx)].level=lev;
}
/*--------------------------test (s1,s2, n)-----------------------------*/
void test(symset s1,symset s2,int n)
{
if (in(sym,s1)==0)//不在可接受的sym集合中,出错
{
error(n);
//向后继续取sym直到遇到可接受的sym
//跳过不在s1中sym, 跳过不在s2中的sym
//s1是块本身的后继sym,s2是块所包含的语句段的后继sym
//不属于s1一定出错
//属于s1之后 也一定要属于s2
while ((in(sym,s1)==0)&&(in(sym,s2)==0)&&ch!='.')
getsym( );
}
}
/*---------------------------gen (x,y,z)-----------------------------*/
//void gen(char x[5],int y,int z)
void gen(int x, int y, int z)
{
if (cx>cxmax)
{
print("program too long !\n");
exit(0);
}
code[cx].f=x;
code[cx].l=y;
code[cx].a=z;
cx++;
}
/*-----------------------------getsym ( )------------------------------*/
void getsym()
{
int i,j,k;
bool isblank=(ch==' '||ch=='\n'||ch=='\t'||'\r');
while (isblank&&ch!='.'){
getch();
isblank=(ch==' '||ch=='\n'||ch=='\t'||ch=='\r');
}
if(ch==EOF||ch=='.')return;
bool find=false;
char tp[al];;
if ((ch>='a')&& (ch<='z'))
{
k=0-1;
id=string();
do
{ int p;
if (k<al){//标识符最大长度
k++;
id[k]=ch;
}
getch( );
} while ((ch>='a')&&(ch<='z')||(ch>='0')&&(ch<='9'));
id[k++]='\n';
ptext--;
i=1;
j=norw;
for(k=i;k<i+j;k++){
if (strcmp(id,word[k])==0){
sym=wsym[k];
find=true;
break;
}
}
if(!find){
sym=IDENT;
}
return;
}
if ((ch>='0')&&(ch<='9')){//combine a number
k=0;
num=0;
int e;
sym=NUM;
do {
num=10*num+ch-'0';
k++;
getch( );
} while ((ch>='0')&&(ch<='9'));
if(ch=='e' || ch=='E'){
e=0;
getch();
if((ch>='0')&&(ch<='9')) e=ch-'0'
else error(49);
getch();
if((ch>='0')&&(ch<='9')) e=ch-'0'
else error(49);;
e=10*e+ch-'0';
}
num=num+ipow(10,e);//拼上幂指数
ptext--;
if (k>nmax)
error(30);
return;
}
//not a-z and not 0-9
if (ch=='='){
sym=EQ;
return;
}
if (ch==':'){
getch();
if (ch=='='){
sym=BECOME;
}
else
sym=NUL;
return;
}
if (ch=='<'){
getch( );
if (ch=='='){
sym=LE;
}
else sym=LS;
return;
}
if (ch=='>'){
getch( );
if (ch=='='){
sym=GE;
}
else sym=GT;
return;
}
sym=what_identify(ch);
}
/*----------------------------getch ( )------------------------*/
void getch()
{
ch=text[ptext++];
}
/*-------------------error(n)------------*/
void error(int n)
{
int i=0;
printf("*****");
printf("%2d",n) ;
err++;
}
/*--------------------listcode (cx0)-----------------------*/
void listcode(int cx0)
{
int i;
if (listswitch==1)
for (i=cx0-1;i<cx;i++) /*has been changed */
printf("%4d%5s%3d%5d\n",i,code[i].f.c_str(),code[i].l,code[i].a);
}
/*-----------------------------insert (symi,fsys,&fsysi)--------------------*/
// add a new sym and a exising fsys to fsys1
void insert(int sym1,symset * fsys,symset *fsys1)
{
int i=0,j=0;
if (fsys1->size!=0) fsys1->size--;//ENDARRAY 出栈
while (fsys[i]!=ENDARRAY)
{
strcpy(fsys1->sym[i],fsys->sym[i]);
i++;
fsys1->size++;
if(i+1==maxvar){
error(98);
}
}
fsys1->sym[i]=ENDARRAY;
i=0;
while (
(sym1!=fsys1->sym[i]))
&&
(fsys1->sym[i]!=ENDARRAY)
{
i++;
}
if (
(sym1!=fsys1->sym[i])//没找到 等于sym的
&&
(i+1<maxvar)//has more info to put this sym1
)
{
if(i+1=maxvar) error(48);
fsys1->sym[i-1]=sym1;
fsys1->sym[i]=ENDARRAY;// insert the sym1 into it
}
}
/*--------------------------------int in (sm,fsys)--------------------*/
int in(char * sm,symset * fsys)//第一个sym是否在fsys中,不是的话,返回0
{
int i;
i=0;
while (sm!=fsys->sym[i] && fsys->sym[i]!=ENDARRAY)
i++;
if (sm==fsys->sym[i])
i=1;
else
i=0;
return(i);
}
/*------------------------------int position (id,tx)------------------*/
int position(char * id,int tx)//从tx开始反向找符号表中的位置,若到头,则失败
{
int i;
strcpy(table[0].name,id);
i=tx;
while (strcmp(table[i].name,id)!=0)
i--;
return(i);
}
/*-----------------------int base (l,b)------------------------*/
int base(int l,int b)
{
int b1;
b1=b;
while (l>0)
{
b1=s[b1];
l--;
}
return (b1);
}
/*-----------------------interpret() ------------------------*/
void interpret()
{
int p,b,t;
instruction i;
printf("start pl/0 :\n");
t=p=0;
b=1;
s[1]=s[2]=s[3]=0;
do
{
i.a=code[p].a;
i.l=code[p].l;
i.f=code[p].f;
p++;
if (i.f==LIT)
{
t++;
s[t]=i.a;
}
if (i.f==OPR)
switch(i.a)
{
case 0:
t=b-1;//栈顶指针置到基址寄存器前
p=s[t+3];//代码指针指向基址后两格的值
b=s[t+2];//基址指针指向基址后一 格的值
break;
case 1:
s[t]=0-s[t];
break;
case 2:
t--;
s[t]=s[t]+s[t+1];
break;
case 3:
t--;
s[t]=s[t]-s[t+1];
break;
case 4:
t--;
s[t]=s[t]*s[t+1];
break;
case 5:
t--;
s[t]=s[t]/s[t+1];
break;
case 6:
if (s[t]!=0)
s[t]=1;
else s[t]=0;
break;
case 8:
t--;
if (s[t]==s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 9:
t--;
if (s[t]!=s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 10:
t--;
if (s[t]<s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 11:
t--;
if (s[t]>=s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 12:
t--;
if (s[t]>s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 13:
t--;
if (s[t]<=s[t+1])
s[t]=1;
else
s[t]=0;
break;
case 14:
printf("%d",s[t]);
t--;
break;
case 15:
printf("\n");
break;
case 16:
t++;
printf("?");
sprintf("%d",s[t]);
print("%d",s[t])+;
break;
default:
exit(0);
}
if (i.f==LOD)
{
t++;
s[t]=s[base(i.l,b)+i.a];
}
if (i.f==STD)
{
s[base(i.l,b)+i.a]=s[t];
t--;
}
if (i.f==CAL)
{
s[t+1]=base(i.l,b);
s[t+2]=b;
s[t+3]=p;
b=t+1;
p=i.a;
}
if (i.f==INT)
t=t+i.a;
if (i.f==JMP)
p=i.a;
if (i.f==JPC)
if (s[t]==0)
p=i.a;
} while (p!=0);
printf("end pl/0 !\n");
}
/*---------------------------end--------------------*/
/*---------------------------result----------------*/
/*-----------------------------main( )-----------------------------------*/
void main()
{
err=cc=ll=cx=ptext=0;
kk=10;
ch=' ';
getsym();
block(0,0,fsysa);
if (err==0)
interpret();
else
printf("error in cacl program !\n");
}
本文地址:http://com.8s8s.com/it/it25082.htm