/*PL/0编译程序（C语言版）
*编译和运行环境：
*Visual C++6.0
*WinXP/7
*使用方法：
*运行后输入PL/0源程序文件名
*回答是否将虚拟机代码写入文件
*回答是否将符号表写入文件
*执行成功会产生四个文件（词法分析结果.txt符号表.txt虚拟代码.txt源程序和地址.txt）*/
#include
#include"pl0.h"
#include"string"
#define stacksize 500//解释执行时使用的栈
int main(){
bool nxtlev[symnum];
printf("请输入源程序文件名:");
scanf("%s",fname);
fin=fopen(fname,"r");//以只读方式打开pl0源程序文件
cifa=fopen("词法分析结果.txt","w");
fa1=fopen("源程序和地址.txt","w");//输出源文件及各行对应的首地址
fprintf(fa1,"输入pl0源程序文件名：");
fprintf(fa1,"%s\n",fname);
if(fin){
printf("是否将虚拟机代码写入文件?(Y/N)");//是否输出虚拟机代码
scanf("%s",fname);
listswitch=(fname[0]=='y'||fname[0]=='Y');
printf("是否将符号表写入文件?(Y/N)");//是否输出符号表
scanf("%s",fname);
tableswitch=(fname[0]=='y'||fname[0]=='Y');
init();//初始化
err=0;
cc=cx=ll=0;
ch=' ';
if(-1!=getsym()){
fa=fopen("虚拟代码.txt","w");
fas=fopen("符号表.txt","w");
addset(nxtlev,declbegsys,statbegsys,symnum);
nxtlev[period]=true;
if(-1==block(0,0,nxtlev)){//调用编译程序
fclose(fa);
fclose(fa1);
fclose(fas);
fclose(fin);
return 0;
}
if(sym!=period){
error(9);//结尾丢失了句号
}
if(err!=0){
printf("pl0源程序出现错误，退出编译!!!请从第一个错误处开始修改.\n\n");
fprintf(cifa,"源程序出现错误，请检查!!!");
fprintf(fa1,"源程序出现错误，请检查!!!");
fprintf(fa,"源程序出现错误，请检查!!!");
fprintf(fas,"源程序出现错误，请检查!!!");
}fclose(fa);
fclose(fa1);
fclose(fas);
}fclose(fin);
}else{
printf("Can't open file!\n");
}
fclose(cifa);//printf("\n");
return 0;
}
void init(){//初始化
int i;
for(i=0;i<=255;i++)
ssym[i]=nul;//设置单字符符号
ssym['+']=plus;
ssym['-']=minus;
ssym['*']=times;
ssym['/']=slash;
ssym['(']=lparen;
ssym[')']=rparen;
ssym['=']=eql;
ssym[',']=comma;
ssym['.']=period;
ssym['#']=neq;
ssym[';']=semicolon;
strcpy(&(word[0][0]),"begin");//保留字设置，以字母顺序排列便于折半查找
strcpy(&(word[1][0]),"call");
strcpy(&(word[2][0]),"const");
strcpy(&(word[3][0]),"do");
strcpy(&(word[4][0]),"end");
strcpy(&(word[5][0]),"if");
strcpy(&(word[6][0]),"odd");
strcpy(&(word[7][0]),"procedure");
strcpy(&(word[8][0]),"read");
strcpy(&(word[9][0]),"then");
strcpy(&(word[10][0]),"var");
strcpy(&(word[11][0]),"while");
strcpy(&(word[12][0]),"write");
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]=readsym;
wsym[9]=thensym;
wsym[10]=varsym;
wsym[11]=whilesym;
wsym[12]=writesym;
strcpy(&(mnemonic[lit][0]),"lit");//设置指令名称
strcpy(&(mnemonic[opr][0]),"opr");
strcpy(&(mnemonic[lod][0]),"lod");
strcpy(&(mnemonic[sto][0]),"sto");
strcpy(&(mnemonic[cal][0]),"cal");
strcpy(&(mnemonic[inte][0]),"int");
strcpy(&(mnemonic[jmp][0]),"jmp");
strcpy(&(mnemonic[jpc][0]),"jpc");
for(i=0;i declbegsys[i]=false; statbegsys[i]=false; facbegsys[i]=false; } declbegsys[constsym]=true;//设置声明开始符号集 declbegsys[varsym]=true; declbegsys[procsym]=true; statbegsys[beginsym]=true;//设置语句开始符号集 statbegsys[callsym]=true; statbegsys[ifsym]=true; statbegsys[whilesym]=true; facbegsys[ident]=true;//设置因子开始符号集 facbegsys[number]=true; facbegsys[lparen]=true; }//用数组实现集合的集合运算 int inset(int e,bool* s){ return s[e]; } int addset(bool*sr,bool* s1,bool* s2,int n){ int i; for(i=0;i sr[i]=s1[i]||s2[i]; return 0; } void error(int n){//出错处理，打印出错位置和错误编码char space[81]; memset(space, 32,81); space[cc-1]=0; printf("error(%d)",n); fprintf(fa1,"error(%d)",n); switch(n){ case 1: printf("\t\t常量说明中的“=”写成“:=”\n"); fprintf(fa1,"\t\t常量说明中的“=”写成“:=”\n"); break; case 2: printf("\t\t常量说明中的=后应该是数字\n"); fprintf(fa1,"\t\t常量说明中的=后应该是数字\n"); break; case 3: printf("\t\t常量说明符中的表示符应该是=\n" ); fprintf(fa1,"\t\t常量说明符中的表示符应该是=\n"); break; case 4: printf("\t\tconst,var,procedure后应为标识符\n" ); fprintf(fa1,"\t\tconst,var,procedure后应为标识符\n"); break; case 5: printf("\t\t漏掉了“,”或“;”\n" ); fprintf(fa1,"\t\t漏掉了“,”或“;”\n" ); break; case 6: printf("\t\t过程说明后的符号不正确\n" ); fprintf(fa1,"\t\t过程说明后的符号不正确\n"); break; case 7: printf("\t\t应是语句开始符\n" ); fprintf(fa1,"\t\t应是语句开始符\n" ); break; case 8: printf("\t\t程序体内语句部分的后跟符不正确\n" ); fprintf(fa1,"\t\t程序体内语句部分的后跟符不正确\n" ); break; case 9: printf("\t\t程序结尾丢了句号“.”\n\n" ); fprintf(fa1,"\t\t程序结尾丢了句号“.”\n"); break; case 10: printf("\t\t语句之间漏了“;”\n" ); fprintf(fa1,"\t\t语句之间漏了“;”\n"); break; case 11: printf("\t\t标识符拼写错误或未说明\n" ); fprintf(fa1,"\t\t标识符拼写错误或未说明\n"); break; case 12: printf("\t\t赋值语句中，赋值号左部标识符属性应是变量\n" ); fprintf(fa1,"\t\t赋值语句中，赋值号左部标识符属性应是变量\n"); break; case 13: printf("\t\t赋值语句左部标识符后应是复制号“:=”\n" ); fprintf(fa1,"\t\t赋值语句左部标识符后应是复制号“:=”\n"); break; case 14: printf("\t\tcall后应为标识符\n" ); fprintf(fa1,"\t\tcall后应为标识符\n"); break; case 15: printf("\t\tcall后标识符属性应为过程\n" ); fprintf(fa1,"\t\tcall后标识符属性应为过程\n"); break; case 16: printf("\t\t条件语句中丢了then\n" ); fprintf(fa1,"\t\t条件语句中丢了then\n"); break; case 17: printf("\t\t丢了“end”或“;”\n" ); fprintf(fa1,"\t\t丢了“end”或“;”\n"); break; case 18: printf("\t\twhile型循环语句中丢了“do”\n" ); fprintf(fa1,"\t\twhile型循环语句中丢了“do”\n"); break; case 19: printf("\t\t语句后的符号不正确\n" ); fprintf(fa1,"\t\t语句后的符号不正确\n" ); break; case 20: printf("\t\t应为关系运算符\n" ); fprintf(fa1,"\t\t应为关系运算符\n"); break; case 21: printf("\t\t表达式内标示符属性不能是过程\n" ); fprintf(fa1,"\t\t表达式内标示符属性不能是过程\n"); break; case 22: printf("\t\t表达式漏掉了右括号\n" ); fprintf(fa1,"\t\t表达式漏掉了右括号\n"); break; case 23: printf("\t\t因子后的非法符号\n" ); fprintf(fa1,"\t\t因子后的非法符号\n"); break; case 24: printf("\t\t表达式的开始符不能是此符号\n" ); fprintf(fa1,"\t\t表达式的开始符不能是此符号\n"); break; case 25: printf("\t\t标识符越界\n" ); fprintf(fa1,"\t\t标识符越界\n"); break; case 26: printf("\t\t非法字符\n" ); fprintf(fa1,"\t\t非法字符\n"); break; case 31: printf("\t\t数越界\n"); fprintf(fa1,"\t\t数越界\n"); break; case 32: printf("\t\tread语句括号中的标识符不是变量\n" ); fprintf(fa1,"\t\tread语句括号中的标识符不是变量\n"); break; case 33: printf("\t\twrite()或read()中应为完整表达式\n" ); fprintf(fa1,"\t\twrite()或read()中应为完整表达式\n"); break; default: printf("\t\t出现未知错误\n" ); fprintf(fa1,"\t\t出现未知错误\n"); }err++; } //漏掉空格，读取一个字符，每次读一行，存入line缓冲区，line被getsym取空后再读一//行，被函数getsym调用 int getch(){ if(cc==ll){ if(feof(fin)){ printf("program incomplete"); return-1; } ll=0; cc=0; printf("\n%d ",cx); fprintf(fa1,"\n%d ",cx); ch=' '; while(ch!=10){ if(EOF==fscanf(fin,"%c",&ch)){ line[ll]=0; break; }printf("%c",ch); fprintf(fa1,"%c",ch); line[ll]=ch; ll++; }fprintf(cifa,"\n"); } ch=line[cc]; cc++; return 0; } int getsym(){//词法分析 int i,j,k,l; while(ch==' '||ch==10||ch==9)//忽略空格换行 TAB getchdo; if(ch>='a'&&ch<='z'){//以字母开头的为保留字或者标识符 k=0,l=1; do{ if(k a[k]=ch; k++; } if(k==al&&l==1){ error(25); l=0; }getchdo; } while(ch>='a'&&ch<='z'||ch>='0'&&ch<='9'); a[k]=0;//末尾存零 strcpy(id,a); i=0; j=norw-1; 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]; fprintf(cifa,"%s\t\t%ssym\n",id,id);//printf("%s\t\t%ssym\n",id,id); } else{//否则为标识符或数字 sym=ident; fprintf(cifa,"%s\t\tident\n",id);//printf("%s\t\tident\n",id); } }else { if(ch>='0'&&ch<='9'){ k=0; num=0; sym=number; do{ num=10*num+ch-'0';//数字的数位处理 k++; getchdo; }while(ch>='0'&&ch<='9'); k--; if(k>nmax){//数字的长度限制 fprintf(cifa,"0\t\tnumber\n"); num=0; error(31); }else fprintf(cifa,"%d\t\tnumber\n",num);//printf("%d\t\tnumber\n",num); }else{ if(ch==':'){//检测赋值符号，:只能和=匹配，否则不能识别 getchdo; if(ch=='='){ sym=becomes; fprintf(cifa,":=\t\tbecomes\n"); getchdo; } else{ sym=nul; } }else{ if(ch=='<'){ getchdo; if(ch=='='){ sym=leq;//小于等于 fprintf(cifa,"<=\t\tleq\n"); getchdo; }else{ sym=lss;//小于 fprintf(cifa,"<\t\tlss\n"); } }else{ if(ch=='>'){ getchdo; if(ch=='='){ sym=geq;//大于等于 fprintf(cifa,">=\t\tgeq\n"); getchdo; }else{ sym=gtr;//大于 fprintf(cifa,">\t\tgtr\n"); } }else{ sym=ssym[ch];//不满足上述条件时按单字 //符处理 switch(ch){ case'+': fprintf(cifa,"%c\t\tplus\n",ch); break; case '-': fprintf(cifa,"%c\t\tminus\n",ch); break; case '*': fprintf(cifa,"%c\t\ttimes\n",ch); break; case '/': fprintf(cifa,"%c\t\tslash\n",ch); break; case '(': fprintf(cifa,"%c\t\tlparen\n",ch); break; case ')': fprintf(cifa,"%c\t\trparen\n",ch); break; case '=': fprintf(cifa,"%c\t\teql\n",ch); break; case ',': fprintf(cifa,"%c\t\tcomma\n",ch); break; case '#': fprintf(cifa,"%c\t\tneq\n",ch); break; case ';': fprintf(cifa,"%c\t\tsemicolon\n",ch); break; case '.':break; default :error(26); } if(sym!=period){//判断是否结束 getchdo; }else{ printf("\n"); fprintf(cifa,".\t\tperiod\n"); } } } } } }return 0; } //生成目标代码//目标代码的功能码，层差和位移量 int gen(enum fct x,int y,int z){ if(cx>=cxmax){//如果目标代码索引过大，报错 printf("Program too long"); return -1; } code[cx].f=x; code[cx].l=y; code[cx].a=z; cx++; return 0; } //测试字符串 int test(bool* s1,bool* s2,int n){ if(!inset(sym,s1)){//测试sym是否属于s1，不属于则报错n error(n); while((!inset(sym,s1))&&(!inset(sym,s2))){//检测不通过时，不停获得符号，直到它属于需要或补救的集合 getsymdo; } }return 0; } //编译程序主体 //lev：当前分程序所在层，tx:名字表当前尾指针fsys：当前模块后跟符号集合 int block(int lev,int tx,bool* fsys){ int i; int dx;//名字分配到的相对地址 int tx0;//保留初始tx int cx0;//保留初始cx bool nxtlev[symnum]; dx=3;//相对地址从3开始，前3个单元即0、1、2单元分别为 SL:静态链； //DL：动态链；RA：返回地址 tx0=tx;//记录本层的初始位置 table[tx].adr=cx; gendo(jmp,0,0); if(lev>levmax){//层数超过3 error(32); } do{ if(sym==constsym){//收到常量声明 printf("该语句为常量定义语句\n"); getsymdo; do{ constdeclarationdo(&tx,lev,&dx);//常量声明处理，dx会改//变所以使用指针 while(sym==comma){//处理一次多常量定义 getsymdo; constdeclarationdo(&tx,lev,&dx); } if(sym==semicolon){//常量声明处理结束 getsymdo; }else{ error(5);//漏掉了逗号或者分号（一般是分号）} }while(sym==ident); } if(sym==varsym){//收到变量声明 printf("该语句为变量声明语句\n"); getsymdo; do{ vardeclarationdo(&tx,lev,&dx);//变量声明处理 while(sym==comma){//处理一次多变量定义 getsymdo; vardeclarationdo(&tx,lev,&dx); } if(sym==semicolon){//变量声明处理结束 getsymdo; }else{ error(5);//漏掉逗号或者分号 } }while(sym==ident); } while(sym==procsym){//收到过程声明 printf("该语句为过程声明语句\n"); getsymdo; if(sym==ident){ enter(procedur,&tx,lev,&dx);//记录过程名 getsymdo; }else{ error(4);//过程声明后应为标识符 } if(sym==semicolon){ getsymdo; }else{ error(5);//漏掉了分号 } memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[semicolon]=true; if(-1==block(lev+1,tx,nxtlev)){ return -1; } if(sym==semicolon){ getsymdo; memcpy(nxtlev,statbegsys,sizeof(bool)*symnum); nxtlev[ident]=true; nxtlev[procsym]=true; testdo(nxtlev,fsys,6); }else{ error(5); } } memcpy(nxtlev,statbegsys,sizeof(bool)*symnum); nxtlev[ident]=true; nxtlev[period]=true; testdo(nxtlev,declbegsys,7); }while(inset(sym,declbegsys));//直到没有声明符号 code[table[tx0].adr].a=cx;//开始生成当前过程代码 table[tx0].adr=cx;//当前过程代码地址 table[tx0].size=dx; cx0=cx; gendo(inte,0,dx);//生成分配内存代码 if(tableswitch){//输出符号表 if(tx0+1 fprintf(fas,"TABLE:\n");//printf("NULL\n"); } for(i=tx0+1;i<=tx;i++){ switch(table[i].kind){ case constant: fprintf(fas,"%d const %s ",i,table[i].name); fprintf(fas,"val=%d\n",table[i].val); break; case variable: fprintf(fas,"%d var %s ",i,table[i].name); fprintf(fas,"lev=%daddr=%d\n",table[i].level,table[i].adr); break; case procedur: fprintf(fas,"%d proc %s ",i,table[i].name); fprintf(fas,"lev=%daddr=%dsize=%d\n", table[i].level,table[i].adr,table[i].size); break; } } } memcpy(nxtlev,fsys,sizeof(bool)*symnum);//每个后跟符号集和都包含上层后跟符//号集和，以便补救 nxtlev[semicolon]=true; nxtlev[endsym]=true; statementdo(nxtlev,&tx,lev); gendo(opr,0,0);//每个过程出口都要使用的释放数据指令 memset(nxtlev,0,sizeof(bool)*symnum);//分程序没有补救集合 testdo(fsys,nxtlev,8);//检测后跟符号集的正确性 listcode(cx0);//输出代码 return 0; } //k:const var procedure //ptx:符号表尾的指针 //pdx:dx为当前应分配变量的相对地址 //lev:符号名字所在的层次//往符号表中添加 void enter(enum object k,int* ptx,int lev,int* pdx){ (* ptx)++; strcpy(table[(*ptx)].name,id); table[(* ptx)].kind=k; switch(k){ case constant: if(num>amax){ error(31); num=0; } table[(*ptx)].val=num; break; case variable: table[(*ptx)].level=lev; table[(*ptx)].adr=(*pdx); (*pdx)++; break; case procedur: table[(*ptx)].level=lev; break; } } //寻找符号在符号表中的地址 int position(char*idt,int tx){ int i; strcpy(table[0].name,idt); i=tx;//符号表尾 while(strcmp(table[i].name,idt)!=0){ i--; }return i; } //常量声明处理 int constdeclaration(int* ptx,int lev,int* pdx){ if(sym==ident){ getsymdo; if(sym==eql||sym==becomes){ if(sym==becomes){ error(1); } getsymdo; if(sym==number){ enter(constant,ptx,lev,pdx); getsymdo; }else{ error(2); } }else{ error(3); } }else{ error(4); }return 0; } //变量声明处理 int vardeclaration (int* ptx,int lev,int* pdx){ if(sym==ident){ enter(variable,ptx,lev,pdx); getsymdo; }else{ error(4); } return 0; } //输出目标代码清单 void listcode(int cx0){ int i; if(listswitch){ for(i=cx0;i fprintf(fa,"%d %s %d %d\n",i, mnemonic[code[i].f],code[i].l,code[i],a); } } } //语句处理 int statement(bool* fsys,int* ptx,int lev){ int i,cx1,cx2; bool nxtlev[symnum]; if(sym==ident){ i=position(id,*ptx); if(i==0){ error(11); }else{ if(table[i].kind!=variable){ error(12); i=0; }else{ getsymdo; if(sym==becomes){ getsymdo; printf("该语句为赋值语句。\n"); }else{ error(13); } memcpy(nxtlev,fsys,sizeof(bool)* symnum); expressiondo(nxtlev,ptx,lev); if(i!=0){ gendo(sto,lev-table[i].level,table[i].adr); } } }//if(i==0) }else{//保留字匹配 if(sym==readsym){ printf("该语句为读语句\n"); getsymdo; if(sym!=lparen){ error(34); }else{ do{ getsymdo; if(sym==ident){ i=position(id,*ptx); } else{ i=0; } if(i==0){ error(35); }else{ gendo(opr,0,16); gendo(sto,lev-table[i].level,table[i].adr); } getsymdo; }while(sym==comma); } if(sym!=rparen){ error(33); while(!inset(sym,fsys)){ getsymdo; } }else{ getsymdo; } }else{ if(sym==writesym){ printf("该语句为写语句\n"); getsymdo; if(sym==lparen){ do{ getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[rparen]=true; nxtlev[comma]=true; expressiondo(nxtlev,ptx,lev); gendo(opr,0,14); }while(sym==comma); if(sym!=rparen){ error(33); }else{ getsymdo; } }gendo(opr,0,15); }else{ if(sym==callsym){ printf("该语句为调用语句\n"); getsymdo; if(sym!=ident){ error(14); }else{ i=position(id,*ptx); if(i==0){ error(11); }else{ if(table[i].kind==procedur){ gendo(cal,lev-table[i].level,table[i].adr); }else{ error(15); } }getsymdo; } }else{ if(sym==ifsym){ printf("该语句为if条件语句\n"); getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[rparen]=true; nxtlev[comma]=true; conditiondo(nxtlev,ptx,lev); if(sym==thensym){ getsymdo; }else{ error(16); } cx1=cx; gendo(jpc,0,0); statementdo(fsys,ptx,lev); code[cx1].a=cx; }else{ if(sym==beginsym){ getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[rparen]=true; nxtlev[comma]=true; statementdo(nxtlev,ptx,lev); while(inset(sym,statbegsys)||sym==semicolon){ if(sym==semicolon){ getsymdo; }else{ error(10); } statementdo(nxtlev,ptx,lev); } if(sym==endsym){ getsymdo; }else{ error(17); } }else{ if(sym==whilesym){ printf("该语句为while循环语句\n"); cx1=cx; getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[dosym]=true; conditiondo(nxtlev,ptx,lev); cx2=cx; gendo(jpc,0,0); if(sym==dosym){ getsymdo; }else{ error(18); } statementdo(fsys,ptx,lev); gendo(jmp,0,cx1); code[cx2].a=cx; }else{ memset(nxtlev,0,sizeof(bool)*symnum); testdo(fsys,nxtlev,19); } } } } } } }return 0; } int expression(bool* fsys,int * ptx,int lev){ enum symbol addop; bool nxtlev[symnum]; if(sym==plus||sym==minus){ addop=sym; getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[plus]=true; nxtlev[minus]=true; termdo(fsys,ptx,lev); if(addop==minus) gendo(opr,0,1); }else{ memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[plus]=true; nxtlev[minus]=true; termdo(fsys,ptx,lev); } while(sym==plus||sym==minus){ addop=sym; getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[plus]=true; nxtlev[minus]=true; termdo(nxtlev,ptx,lev); if(addop==plus){ gendo(opr,0,2); }else{ gendo(opr,0,3); } } return 0; } int term(bool* fsys, int* ptx,int lev){ enum symbol mulop; bool nxtlev[symnum]; memcpy(nxtlev,fsys,sizeof(bool)* symnum); nxtlev[times]=true; nxtlev[slash]=true; factordo(nxtlev,ptx,lev); while(sym==times||sym==slash){ mulop=sym; getsymdo; factordo(nxtlev,ptx,lev); if(mulop==times){ gendo(opr,0,4); }else{ gendo(opr,0,5); } }return 0; } int factor(bool* fsys,int* ptx,int lev){ int i; bool nxtlev[symnum]; testdo(facbegsys,fsys,24); while(inset(sym,facbegsys)){ if(sym==ident){ i=position(id,*ptx); if(i==0){ error(11); }else{ switch(table[i].kind){ case constant: gendo(lit,0,table[i].val); break; case variable: gendo(lod,lev-table[i].level,table[i].adr); break; case procedur: error(21); break; } }getsymdo; }else{ if(sym==number){ if(num>amax){ error(31); num=0; }gendo(lit,0,num); getsymdo; }else{ if(sym==lparen){ getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[rparen]=true; expressiondo(nxtlev,ptx,lev); if(sym==rparen){ getsymdo; }else{ error(22); } }testdo(fsys,facbegsys,23); } } }return 0; } int condition(bool* fsys,int* ptx,int lev){ enum symbol relop; bool nxtlev[symnum]; if(sym==oddsym){ getsymdo; expressiondo(fsys,ptx,lev); gendo(opr,0,6); }else{ memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[eql]=true; nxtlev[neq]=true; nxtlev[lss]=true; nxtlev[leq]=true; nxtlev[gtr]=true; nxtlev[geq]=true; expressiondo(nxtlev,ptx,lev); if(sym!=eql&&sym!=neq&&sym!=lss&&sym!=leq&&sym!=gtr&&sym!=geq){ error(20); }else{ relop=sym; getsymdo; expressiondo(fsys,ptx,lev); switch(relop){ case eql: gendo(opr,0,8); break; case neq: gendo(opr,0,9); break; case lss: gendo(opr,0,10); break; case geq: gendo(opr,0,11); break; case gtr: gendo(opr,0,12); break; case leq: gendo(opr,0,13); break; } } }return 0; } //pl0头文件 #define norw 13 #define txmax 100 #define nmax 14 #define al 10 #define amax 2047 #define levmax 3 #define cxmax 200 enum symbol{ nul, ident, number, plus, minus, times, slash, oddsym, eql, neq, lss, leq, gtr, geq, lparen, rparen, comma, semicolon, period, becomes, beginsym, endsym, ifsym, thensym, whilesym, writesym, readsym, dosym, callsym, constsym, varsym, procsym, }; #define symnum 32 enum object{ constant, variable, procedur, }; enum fct{ lit, opr, lod, sto, cal, inte, jmp, jpc, }; #define fctnum 8 struct instruction{ enum fct f; int l; int a; }; FILE* fas;//符号表文件 FILE* fa;//存放虚拟代码 FILE* fa1;//存放源程序及其首地址 FILE* cifa;//存放词法分析结果 bool listswitch; bool tableswitch; char ch; enum symbol sym; char id[al+1]; int num; int cc,ll; int cx; int realine; 一、填空题（每空2分，共30分） 1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段，另外还有两个重要的工作是表格管理和出错处理 2、规范规约中的可归约串是句柄，算符优先分析中的可归约串是最左素短语。 3、语法分析方法主要可分为自顶向下和自底向上两大类。 4、LR（0）文法的项目集中不会出现移进-归约冲突和归约-归约冲突。 5、数据空间的动存态储分配方式可分为栈式和堆式两种。 6、编译程序是指能将源语言程序翻译成目标语言程序的程序。 7、确定有穷自动机DFA是NFA 的一个特例。 8、表达式(a+b)*c 的逆波兰表示为ab+c* 。 二、选择题（每题2分，共20分） 1、L R语法分析栈中存放的状态是识别 B 的DFA状态。 A、前缀 B、可归前缀 C、项目 D、句柄 2、 D 不可能是目标代码。 A、汇编指令代码 B、可重定位指令代码 C、绝对机器指令代码 D、中间代码 3、一个控制流程图就是具有 C 的有向图 A、唯一入口结点 B、唯一出口结点 C、唯一首结点 D、唯一尾结点 4、设有文法G[S]：S→b|bB B→bS ，则该文法所描述的语言是 C 。 A、L（G）={b i|i≥0} B、L（G）={b2i|i≥0} C、L（G）={b2i+1|i≥0} D、L（G）={b2i+1|i≥1} 5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。 A、编译器 B、汇编器 C、解释器 D、预处理器 6、在目标代码生成阶段，符号表用于 D 。 A、目标代码生成 B、语义检查 C、语法检查 D、预处理器地址分配0 7、规范归约是指 B 。 A、最左推导的逆过程 B、最右推导的逆过程 C、规范推导 D、最左归约逆过程 内蒙古工业大学信息工程学院实验报告 课程名称：编译原理 实验名称：语法制导把表达式翻译成逆波兰式 实验类型：验证性□ 综合性□ 设计性□ 实验室名称： 班级：学号 姓名：组别： 同组人：成绩： 实验日期： 一、实验目的 通过上机实习加深对语法指导翻译原理的理解，掌握运算符优先权的算法，将语法分析所识别的表达式变换成中间代码的翻译方法。 二、实验题目 语法制导把表达式翻译成逆波兰式 三、要求及提示 1、从左到右扫描中缀表达式，经语法分析找出中缀表达式出现的错误并给出错误的具体位置和类型。 2、设一个运算符栈存放暂时不能出现的运算符，逆波兰区存放逆波兰表达式。 3、测试所编程序，给出正确和错误的结果。 4、工具：C语言或其它高级语言 5、实验时间：4学时 实验二语法制导把表达式翻译成逆波兰式 一、实验名称 语法制导把表达式翻译成逆波兰式 二、实验目的 通过上机实习加深对语法指导翻译原理的理解，进一步掌握语法制导翻译的概念，掌握运算符优先权的算法，将语法分析所识别的表达式变换成中间代码的翻译方法。 三、表达式生成逆波兰式的算法 1、初始化△送到运算符栈。 2、扫描左括号“（”，把△送到运算符栈。 3、扫描到变量，把它送到逆波兰区。 4、扫描到运算符 （1）栈内运算符比较 a.栈内运算符>=栈外运算符，把栈内运算符送到逆波兰区。 b.栈内运算符<栈外运算符，把栈外运算符入栈。 ( 2 ) 栈内是△把运算符入栈。 5、扫描右括号“)”。 ( 1 )栈内是运算符，把栈内运算符送到逆波兰区。 ( 2 )栈内是△则△退栈，读入下一个字符。 6、扫描到#（结束符） ( 1 )栈内是运算符，把栈内运算符送到逆波兰区。 ( 2 )栈内是△结束，否则继续分析。 四、程序清单 #include 第1章引言 1、解释下列各词 源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 （结果程序）一般可由计算机直接执行。 低级语言：机器语言和汇编语言。 高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言）， 然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。 2、什么叫“遍”？ 指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。 3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。 词法分析：输入源程序，进行词法分析，输出单词符号。 语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。 中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。 优化：对中间代码进行优化处理。 目标代码生成：把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别？ 编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。 5、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？ 编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。 6、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。 编译原理综合性实验报告-分析中间代码生成程序分析XXXXXX计算机系综合性实验 实验报告 课程名称编译原理实验学期 XXXX 至 XXXX 学年第 X 学期学生所在系部计算机系年级 X 专业班级 XXXXXX 学生姓名 XXX 学号 XXXXXXXXXXXX 任课教师XXX 实验成绩 计算机系制 《编译原理》课程综合性实验报告 开课实验室: 年月日实验题目分析中间代码生成程序 一、实验目的 分析PL/0编译程序的总体结构、代码生成的方法和过程;具体写出一条语句的中间代码生成过程。 二、设备与环境 PC兼容机、Windows操作系统、Turbo Pascal软件等。 三、实验内容 1. 分析PL/0程序的Block子程序，理清PL/0程序结构和语句格式。画出Block 子程序的流程图，写出至少两条PL/0程序语句的语法格式。 2. 分析PL/0程序的Block子程序和Gen子程序，了解代码生成的方法和过程。 使用概要算法来描述语句的代码生成过程。 3. 自己编写一个简单的PL/0程序，能够正确通过编译，得到中间代码。列出自 己编写的源程序和编译后得到的中间代码。 4. 从中选择一个语句或表达式，写出代码生成的过程。要求从自己的源程序中 选择一条语句，结合这条语句写出语义分析和代码生成过程。在描述这个过程中，要说清楚每个功能有哪个子程序的哪条语句来完成，说清楚语句和参数的含义和功能。 四、实验结果及分析 (一)Block子程序分析 1.常量声明的分析: 常量声明部分的语法结构定义为如下形式: 实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中得单词包括五个关键字begｉｎ、end、if、then、elsｅ；标识符；无符号常数；六种关系运算符；一个赋值符与四个算术运算符，试构造能识别这些单词得词法分析程序（各类单词得分类码参见表Ｉ）。 表Ｉ语言中得各类单词符号及其分类码表 输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。 输出：把所识别出得每一单词均按形如(CLASS，VＡLUE）得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数，CＬASS字段为相应得类别码得助记符;V AL ＵＥ字段则就是该标识符、常数得具体值；对于关键字与运算符,采用一词一类得编码形式，仅需在二元式得CLASS字段上放置相应单词得类别码得助记符，V ALUE字段则为“空". 三、实现方法与环境 词法分析就是编译程序得第一个处理阶段，可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BＮF)，用手工得方式（例如可用Ｃ语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成，即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程 第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？ 答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。 第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？ 答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。 答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 （1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答： （1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab 编译原理实验指导 书 《编译原理》实验指导书 太原科技大学计算机学院 -3-1 序 《编译原理》是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计和算法，因此，一直是一门比较难学的课程。为了使学生更好地理解和掌握编译原理和技术的基本概念、基本原理和实现方法，实践环节非常重要，只有经过上机进行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识，增强学生综合分析问题、解决问题的能力，并对提高学生软件设计水平大有益处。 为了配合《编译原理》课程的教学，考虑到本课程的内容和特点，本指导书设置了七个综合性实验，分别侧重于词法分析、NFA的确定化、非递归预测分析、算符优先分析器的构造、LR分析、语义分析和中间代码的生成、基于DAG的基本块优化，以支持编译程序的各个阶段，基本涵盖了《编译原理》课程的主要内容。 本指导书可作为《编译原理》课程的实验或课程设计内容，在课程教学的同时，安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境，使用C/C++的任何版本作为开发工具。学生在做完试验后，应认真撰写实验报告，内容应 包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。 目录 实验一词法分析 ........................................................... 错误!未定义书签。实验二 NFA的确定化.................................................... 错误!未定义书签。实验三非递归预测分析 ............................................... 错误!未定义书签。实验四算符优先分析器的构造................................... 错误!未定义书签。实验五 LR分析 .............................................................. 错误!未定义书签。实验六语义分析和中间代码生成................................ 错误!未定义书签。实验七基于DAG的基本块优化................................... 错误!未定义书签。 5. 目标代码生成 本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C 源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIM Simulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。 选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。 需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。 5.1 实验内容 5.1.1 实验要求 为了完成实验四，我们建议你首先下载并安装SPIM Simulator用于对生成的目标代码进行检查和调试，SPIM Simulator的官方下载地址为：https://www.doczj.com/doc/8813560112.html,/~larus/spim.html。这是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍有关SPIM Simulator的使用方法。 你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。因此，以下几个方面不属于检查范围： 1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的 正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。 2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使 用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即MIPS32汇编代码）能运行正确。 学生学号实验课成绩 武汉理工大学 学生实验报告书 实验课程名称编译原理 开课学院计算机科学与技术学院 指导老师姓名饶文碧 学生姓名 学生专业班级 —学年第学期 实验课程名称：编译原理 实验项目名称单词的词法分析实验成绩 实验者专业班级组别 同组者实验日期 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 完成对某一种常用高级语言（如Pascal、C语言、PL/0语言）的各类单词进行词法分析，即对源程序从左到右进行扫描，对组成源程序的字符串拼接成为单词；并把其转换成属性字输出。 实验要求： （1）选择常用高级程序设计语言（如 Pascal、C语言、PL/0语言）的源程序作为词法分析对象。 （2）根据教学要求和学生具体情况，从上列语言之一中选取它的一个适当大小的子集，可以选取一类典型单词，也可以尽可能使各种类型的单词都能兼顾到。其基本要求是：对源程序从左到右进行扫描，对组成源程序的字符串拼接成为单词，并把其转换成属性字输出。 二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） #include 一、选择 1．将编译程序分成若干个“遍”是为了_使程序的结构更加清晰__。 2．正规式 MI 和 M2 等价是指__.M1 和 M2 所识别的语言集相等_。 3．中间代码生成时所依据的是 _语义规则_。 4．后缀式 ab+cd+/可用表达式__(a+b)/(c+d)_来表示。 6．一个编译程序中，不仅包含词法分析，_语法分析 ____，中间代码生成，代码优化，目标代码生成等五个部分。 7．词法分析器用于识别__单词___。 8．语法分析器则可以发现源程序中的___语法错误__。 9．下面关于解释程序的描述正确的是__解释程序的特点是处理程序时不产生目标代码 ___。 10．解释程序处理语言时 , 大多数采用的是__先将源程序转化为中间代码 , 再解释执行___方法。 11．编译过程中 , 语法分析器的任务就是__(2)(3)(4)___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 12．编译程序是一种__解释程序__。 13．文法 G 所描述的语言是_由文法的开始符号推出的所有终极符串___的集合。 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___正则文法__。 15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _产生式__。 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_表格处理和出错处理__。 17．文法 G[N]= （ {b} ， {N ， B} ， N ， {N→b│ bB ， B→bN} ），该文法所描述的语言是L(G[N])={b2i+1│ i ≥0} 18．一个句型中的最左_简单短语___称为该句型的句柄。 19．设 G 是一个给定的文法，S 是文法的开始符号，如果 S->x( 其中 x∈V*), 则称 x 是 文法 G 的一个__句型__。 21．若一个文法是递归的，则它所产生的语言的句子_是无穷多个___。 22．词法分析器用于识别_单词_。 23．在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_终极符集 ___。 24．在自底向上的语法分析方法中，分析的关键是_寻找句柄 ___。 25．在 LR 分析法中，分析栈中存放的状态是识别规范句型__活前缀__的 DFA 状态。 26．文法 G 产生的__句子___的全体是该文法描述的语言。 27．若文法 G 定义的语言是无限集，则文法必然是 __递归的_ 28．四种形式语言文法中，1 型文法又称为 _短语结构文法__文法。 29．一个文法所描述的语言是_唯一的__。 30． _中间代码生成___和代码优化部分不是每个编译程序都必需的。 31．_解释程序和编译程序___是两类程序语言处理程序。 32．数组的内情向量中肯定不含有数组的_维数___的信息。 33. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组__D___。 34．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 2 型文法是__上下文无关文法__。 35．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __产生式___。 36．__ BASIC ___是一种典型的解释型语言。 37．与编译系统相比，解释系统___比较简单 , 可移植性好 , 执行速度慢__。 38．用高级语言编写的程序经编译后产生的程序叫__目标程序___。 39．编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过__(1)(2)(3)__这几步: (1) 编辑 (2) 编译 (3) 连接 (4) 运行 40．把汇编语言程序翻译成机器可执行的目标程序的工作是由__编译器__完成的。 41．词法分析器的输出结果是__单词的种别编码和自身值__。 42．文法 G ：S→xSx|y 所识别的语言是_ xnyxn(n≥0)___。 43．如果文法 G 是无二义的，则它的任何句子α__最左推导和最右推导对应的语法树必定相同_。 44．构造编译程序应掌握___源程序目标语言编译方法___。 45．四元式之间的联系是通过__临时变量___实现的。 46．表达式( ┐ A ∨B)∧(C∨D)的逆波兰表示为___ A ┐ B∨CD∨∧__。 47. 优化可生成__运行时间短且占用存储空间小___的目标代码。 48．下列__删除多余运算 ____优化方法不是针对循环优化进行的。 49．编译程序使用__说明标识符的过程或函数的静态层次___区别标识符的作用域。 50．编译程序绝大多数时间花在___表格管理__ 上。 51．编译程序是对__高级语言的翻译___。 编译原理综合实验指导书 一、实验任务 设计、编制并调试一个中缀表达转换为后缀表达的实验程序，加深对词法分析、语法分析、语义分析及代码生成的理解。 二、实验内容 1、词法 输入：扩展ASCII码字符集字符。除大小写26英文字母（letter）和数字0-9（digit）以及+ - * / ^ = ; , ( )以外，所有其他字符一律按等同于空格处理，一般用来分隔单词。 输出：识别单词，单词包括关键字、运算符、界符、标识符和整型常数。 （1）关键字：var （2）运算符和界符：+ - * / ^ = ; , ( ) 其中：乘除运算符（*， /）返回具有不同属性值的单词mulop， 加减运算符（+， -）返回具有不同属性值的单词addop。 （3）标识符（id）和整型常数（num）： 标识符（id）和整型常数（num）最大长度为8个字符，定义如下。 id = letter (letter | digit)* num = digit digit* 2、语法 根据输入的单词序列，分析是否符合语法规则，如果不符合，应指明位置与理由；如果符合，则执行相应的语义子程序完成语义分析及中缀表达转换为后缀表达的过程。需注意的是，这里给出的是二义文法，从语义上考虑，表达式的计算按先幂次运算（^），再乘除运算（*， /）的最后加减运算（+， - ）的优先顺序；括号（(， )）用于调整运算先后顺序，既括号内部分先计算；赋值运算（=）最后进行。本实验系统的语法规则是： program → compound compound → declaration assignstatement compound | ε declaration → var identifier_list ; | ε dentifier_list →id, dentifier_list | id assignstatement →id= expression ; | ε expression → expression addop expression | expression mulop expression | expression ^ expression | ( expression ) | id | num 3、语义分析及代码生成 语义分析的主要任务是判断变量是否先定义后使用。代码生成的的主要任务是将赋值语句从中缀表达转换为后缀表达。 ( 编译原理实验报告 , 实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：（ 13软件四 姓名：丁越 学号： 实验地点：) 秋白楼B720 实验成绩： 日期：2016年 3 月 18 日 一、实验目的 通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标：[ 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 > （1）主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中（编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 ￥ outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图 1-1。 … 编译原理 实 验 指 导 书 前言 编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。 本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。 实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。 通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。 第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 1. 源语言：书写源程序所使用的语言 2. 源程序：用程序设计语言书写的程序 3. 目标语言：计算机的机器指令。目标语言可以是机器语言，也可以是汇编语言， 或者是其他中间语言，但最终结果必是机器语言。 4. 目标程序：由机器指令构成的程序。目标程序是经过翻译程序加工后用目标语言 表示的程序。 5. 翻译程序：能够把某一种语言程序(源程序)改造成另一种语言程序(目标程序)将 源程序译成逻辑上等价的目标程序的程序。翻译程序有两种工作方式：编译和解释。 6. 编译程序：也称翻译程序 7. 解释程序：有些翻译程序在翻译过程中并不产生完整的目标程序，而是翻译一句， 解释执行一句，这样的称为解释程序。 8. 汇编程序：由汇编语言写成的程序 9. 词法分析：执行词法分析的程序成为词法分析器，词法分析依据的是语言构词规 则。词法分析器从文件读入源程序，由字符拼接单词。每当识别出一个单词，词法分析器就输出这个单词的内部码。 10. 语法分析：执行语法分析的程序叫做语法分析器。语法分析的任务就是根据语言 的规则，将词法分析器所提供的单词种别分成各类语法范畴。 11. 中间代码生成：中间代码产生有时称为语义分析，执行中间代码产生的程序称为 中间代码生成器。他的任务时按照语法分析器所识别出的语法范畴产生相应的中间代码，并建立符号表、常数表，等各种表格。 12. 目标代码生成：执行目标代码生成的程序称为目标代码生成器。他的任务是根据 中间代码和表格信息，确定各类数据在内存中的位置，选择合适的指令代码，将中间代码翻译成汇编语言或机器指令，这部分工作与计算机硬件有关。 13. 符号表：用于记录源程序中出现的标识符，一个标识符往往具有一系列的语义 值，她包括标识符的名称、种属、类型、值存放的地址等等。 14. 常数表：用于记录在源程序中出现的常数。 15. 编译程序前端：是由词法分析器、语法分析器和中间代码产生器组成的。她的特 点是依赖于被编译的源程序，输出结果用中间代码描述，和目标机器无关。16. 编译程序后端：是由目标代码生成器组成，他的特点是和源程序无关，以中间代 码形式的源程序为输入进行处理，输出结果依赖于目标机器。 17. 文本文件：文本文件的内容由94个图形字符‘！‘-' ~ '(33-126)和4个 控制字符换行(10)、回车(13)、空格(32)、TAB( 9)构成，文本文件又称为 ASCII码文件，扩展名通常为TXT,文件尾用控制字符EOF( 26)指示。 18. 二进制文件：由机器指令即二进制数构成，因二进制数可能是26 (文件结束控制 符)，故文件尾用文件长度(文件的字节数)指示，扩展名通常为EX E。 19. 源代码(source code)—预处理器(preprocessor) —编译器(compiler) —汇编程序 (assembler)—目标代码(object code)—链接器(Linker) —可执行程序 (executables) 20. 编译程序的流程是： 源程序―》词法分析―》语法分析―》语义分析(中间代码产生)―》目标 代码生成-》目标程序 实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符流形式的源程序转化为一个由各类单词符号组成的流的词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中的单词包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序（各类单词的分类码参见表I）。 表I 语言中的各类单词符号及其分类码表 输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。 输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE 字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。 三、实现方法与环境 词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵连同控制程序一起便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。 处理过程简述：在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后添加当进行状态转移时所需执行的语义动作，就可以据此构造词法分析程序了。 为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、无符号常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。 实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: "; 作业题: 2.1(a,c,d), 2.8(a,c,d), 2.12, 3.3, 3.4, 4.8, 4.12 5.8(a,b,c), 5.12, 6.7, 6.8, 6.13 7.4, 7.15 第二章作业： 2．1(a) a | a[a-z]*a (c)[1-9][0-9]* (d)[0-9]*[02468] 2.8（a） 正则表达式中丢了单独a的情况的比较多，另外有些同学在有NFA到DFA的转化过程中，不能够正确的确定最终的状态，造成有两个终结状态的情况。 （c） （d） 问题比较多，建议同学画出DFA图生成的全部过程。 2.12 3．4 （c ）.rewrite this grammar to establish the correct precedences for the operator. rexp -> rexp “|” rexp1 | rexp1 rexp1 -> rexp1 rexp2 | rexp2 rexp2 -> rexp3 * | rexp3 rexp3 -> (rexp) | letter 左结合 4．8 （a ） 消除左递归 lexp -> atom | list atom -> number | identifier list -> (lexp-seq) lexp-seq -> lexp lexp-seq’ lexp-seq’ -> lexp lexp-seq’ | ε first (lexp)= { number ,identifier,( } first (atom)= { number, identifier } first (list) = { ( } first (lexp-seq)= { number ,identifier,( } first (lexp-seq’)= { number ,identifier,( , ε}编译原理考试试卷
编译原理实验报告二
编译原理作业参考答案
编译原理综合性实验报告-分析中间代码生成程序分析
编译原理实验报告一
(完整版)编译原理课后习题答案
编译原理实验指导书
编译原理实验：目标代码的生成
编译原理实验报告2
编译原理
编译原理综合实验题
编译原理实验报告：实验一编写词法分析程序
编译原理实验指导书(图)
编译原理课后习题答案+清华大学出版社第二版
完整版编译原理名词解释
编译原理实验报告一
编译原理实验 中间代码生成
编译原理与实践作业答案
相关主题
文本预览