北京科技大学编译原理实验报告

编译原理实验报告学院:计算机与通信工程学院专业:计算机科学与技术班级:学号:姓名:实验成绩：词法分析实验目的设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。实验要求2.1待分析的简单的词法（1）关键字：beginifthenwhiledoend所有的关键字都是小写。（2）运算符和界符：=+-*/<<=<>>>==;()#（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义：ID=letter(letter|digit)*NUM=digitdigit*（4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。2.2各种单词符号对应的种别码：表2.1各种单词符号对应的种别码单词符号种别码单词符号种别码bgin1：17If2：=18Then3<20wile4<>21do5<=22end6>23lettet（letter|digit）*10>=24dightdight*11=25+13；26—14(27*15)28/16#02.3词法分析程序的功能：输入：所给文法的源程序字符串。输出：二元组（syn,token或sum）构成的序列。其中：syn为单词种别码；token为存放的单词自身字符串；sum为整型常数。例如：对源程序beginx:=9:ifx>9thenx:=2*x+1/3;end#的源文件，经过词法分析后输出如下序列：(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)……三、词法分析程序的算法思想：算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。3.1主程序示意图：3.2词法分析程序流程图：开始开始变量初始化是否文件结束？返回拼数Syn=11返回拼字符串是否是关键字？Syn为对应关键字的单词种别码Syn=10给不同的符号相同的Syn值报错是否数字字母是否、运算符,界符等其他四、词法分析程序的C++语言程序源代码：#include"stdio.h"#include"stdlib.h"#include"string.h"#define_KEY_WORD_END"waitingforyourexpanding"typedefstruct{ inttypenum; char*word;}WORD;charinput[255];chartoken[255]="";intp_input;intp_token;charch;char*rwtab[]={"begin","if","then","while","do","end",_KEY_WORD_END};WORD*scaner();intmain(){ intover=1; WORD*oneword=newWORD; printf("输入源程序(以#结束):"); scanf("%[^#]s",input); p_input=0; printf("Yourwords:\n%s\n",input); while(over<1000&&over!=-1) { oneword=scaner(); if(oneword->typenum<1000) printf("(%d,%s)\n",oneword->typenum,oneword->word); over=oneword->typenum; } printf("\npress#toexit:"); scanf("%[^#]s",input); return0;}charm_getch(){ ch=input[p_input]; p_input=p_input+1; return(ch);}voidgetbc(){ while(ch==''||ch==10) { ch=input[p_input]; p_input=p_input+1; }}voidconcat(){ token[p_token]=ch; p_token=p_token+1; token[p_token]='\0';}intletter(){ if(ch>='a'&&ch<='z'||ch>='A'&&ch<='Z') return1; else return0;}intdigit(){ if(ch>='0'&&ch<='9') return1; else return0;}intreserve(){ inti=0; while(strcmp(rwtab[i],_KEY_WORD_END)) { if(!strcmp(rwtab[i],token)) { returni+1; } i=i+1; } return10;}voidretract(){ p_input=p_input-1;}char*dtp(){ returnNULL;}WORD*scaner(){ WORD*myword=newWORD; myword->typenum=10; myword->word=""; p_token=0; m_getch(); getbc(); if(letter()) { while(letter()||digit()) { concat(); m_getch(); } retract(); myword->typenum=reserve(); myword->word=token; return(myword); } elseif(digit()) { while(digit()) { concat(); m_getch(); } retract(); myword->typenum=20; myword->word=token; return(myword); } elseswitch(ch) { case'=':m_getch(); if(ch=='=') { myword->typenum=39; myword->word="=="; return(myword); } retract(); myword->typenum=21; myword->word="="; return(myword); break; case'+':myword->typenum=22; myword->word="+"; return(myword); break; case'-':myword->typenum=23; myword->word="-"; return(myword); break; case'*':myword->typenum=24; myword->word="*"; return(myword); break; case'/':myword->typenum=25; myword->word="/"; return(myword); break; case'(':myword->typenum=26; myword->word="("; return(myword); break; case')':myword->typenum=27; myword->word=")"; return(myword); break; case'[':myword->typenum=28; myword->word="["; return(myword); break; case']':myword->typenum=29; myword->word="]"; return(myword); break; case'{':myword->typenum=30; myword->word="{"; return(myword); break; case'}':myword->typenum=31; myword->word="}"; return(myword); break; case',':myword->typenum=32; myword->word=","; return(myword); break; case':':myword->typenum=33; myword->word=":"; return(myword); break; case';':myword->typenum=34; myword->word=";"; return(myword); break; case'>':m_getch(); if(ch=='=') { myword->typenum=37; myword->word=">="; return(myword); } retract(); myword->typenum=35; myword->word=">"; return(myword); break; case'<':m_getch(); if(ch=='=') { myword->typenum=38; myword->word="<="; return(myword); } retract(); myword->typenum=36; myword->word="<"; return(myword); break; case'!':m_getch(); if(ch=='=') { myword->typenum=40; myword->word="!="; return(myword); } retract(); myword->typenum=-1; myword->word="ERROR"; return(myword); break; case'\0':myword->typenum=1000; myword->word="OVER"; return(myword); break; default:myword->typenum=-1; myword->word="ERROR"; return(myword);}}五、结果分析：输入beginx:=9:ifx>9thenx:=2*x+1/3;end#后如图所示：六、总结：词法分析的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。通过本试验的完成，更加加深了对词法分析原理的理解。语法分析实验目的编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。实验要求利用C语言编制递归下降分析程序，并对简单语言进行语法分析。2.1待分析的简单语言的语法用扩充的BNF表示如下：⑴<程序>：：=begin<语句串>end⑵<语句串>：：=<语句>{；<语句>}⑶<语句>：：=<赋值语句>⑷<赋值语句>：：=ID：=<表达式>⑸<表达式>：：=<项>{+<项>|-<项>}⑹<项>：：=<因子>{*<因子>|/<因子>⑺<因子>：：=ID|NUM|（<表达式>）2.2实验要求说明输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。例如：输入begina:=9;x:=2*3;b:=a+xend#输出success！输入x:=a+b*cend#输出error2.3语法分析程序的酸法思想（1）主程序示意图如图2-1所示。置初值置初值调用scaner读下一个单词符号调用scaner读下一个单词符号调用lrparser调用lrparser结束结束图2-1语法分析主程序示意图（2）递归下降分析程序示意图如图2-2所示。（3）语句串分析过程示意图如图2-3所示。是否begin?是否begin?调用statement函数 否调用statement函数 是是否；?调用scaner是否；?调用scaner否调用语句串分析程序调用语句串分析程序 是调用scaner调用scaner是否end?否是否end? 调用statement函数调用statement函数 是调用scaner调用scaner出错处理出错处理syn=0&&kk=0? 否syn=0&&kk=0? 图2-3语句串分析示意图是打印分析成功出错处理 打印分析成功出错处理 图2-2递归下降分析程序示意图（4）statement语句分析程序流程如图2-4、2-5、2-6、2-7所示。调用term函数是否标识符?调用term函数是否标识符? 否调用expression函数调用scaner是否：=?调用scaner调用expression函数调用scaner是否：=?调用scaner是否+,-? 否是否+,-? 否 是调用scaner调用scaner调用term函数调用term函数出错处理出错处理出错处理出错处理图2-4statement语句分析函数示意图图2-5expression表达式分析函数示意图调用scaner调用factor函数出错处理是否*,/?调用factor函数调用scaner调用factor函数出错处理是否*,/?调用factor函数是否标识符? 是是否标识符? 否 否是否整常数? 是是否整常数? 是 否是否（? 否是否（? 是调用scaner调用scaner是否）?调用expression函数图2-6term分析函数示意图是否）?调用expression函数 否出错处理调用scaner调用scaner 是出错处理调用scaner调用scaner 图2-7factor分析过程示意图语法分析程序的C语言程序源代码：#include<stdio.h>#include<string.h>#include<ctype.h>#include<stdlib.h>charGetChar(char*input,int*index,intlength);intClearBlank(char*input,int(*index),intlength);intreserve(char*s);voidlrparser(char*input,intinputLength,int*index);voidyucu(char*input,intinputLength,int*index);voidfactor(char*input,intinputLength,int*index);voidstatement(char*input,intinputLength,int*index);voidexpression(char*input,intinputLength,int*index);voidterm(char*input,intinputLength,int*index);char*retab[6]={"begin","if","then","while","do","end"};//关键字intsyn=0;intmyIsAlpha(charch){ if(islower(ch)==2||isupper(ch)==1) { return1; } else { return0; }}voidscaner(char*input,intinputLength,int*index){ chars[256]="";//保存当前的字符 charch=GetChar(input,index,inputLength); intnowPosition=0; intj=0; if(myIsAlpha(ch)==1)//如果是字母 { while(((ch>='0'&&ch<='9')||(myIsAlpha(ch)==1))&&*index<=inputLength) { s[nowPosition]=ch;//添加到当前字符串中 nowPosition++; ch=GetChar(input,index,inputLength); } if((ch<'0'||ch>'9')&&(myIsAlpha(ch)==0))//进行回退操作，并输出结果 { s[nowPosition]='\0';//添加结束标志 j=reserve(s); if(j==0) { syn=10; } else { syn=j; } (*index)--; return; } else//超过范围 { s[nowPosition++]=ch; s[nowPosition]='\0';//添加结束标志 j=reserve(s); if(j==0) { syn=10; } else { syn=j; } getchar(); exit(0);*/ return; } } else if(ch>='0'&&ch<='9')//如果是数字 { while(ch>='0'&&ch<='9'&&*index<=inputLength) { s[nowPosition]=ch;//添加到当前字符串中 nowPosition++; ch=GetChar(input,index,inputLength); } if(ch<'0'||ch>'9')//进行回退操作 { (*index)--; syn=11; return; } else//超过范围时 { s[nowPosition]=ch; syn=11; return; } } else { switch(ch) { case'+': { syn=13; return; } case'-': { syn=14; return; } case'*': { syn=15; return; } case'/': { syn=16; return; } case'<': { ch=GetChar(input,index,inputLength); if(ch=='=') { syn=22; return; } else if(ch=='>') { syn=21; return; } else { syn=20; if(*index>inputLength) { return; } else { (*index)--; return; } } } case'>': { ch=GetChar(input,index,inputLength); if(ch=='=') { syn=24; return; } else { syn=23; if(*index>inputLength) { return; } else { (*index)--; return; } } } case':': { ch=GetChar(input,index,inputLength); if(ch=='=') { syn=18; return; } else { if(*index>inputLength) { return; } else { (*index)--; return; } } } case'=': { syn=25; return; } case';': {/* syn=26; return; } case'(': { syn=27; return; } case')': { Syn=28; return; } case'#': { syn=0; return; } case'': { syn=-1; return; } default: { printf("(非法符号)"); } } }}intreserve(char*s){ if(strcmp(s,retab[0])==0) { return1; } else if(strcmp(s,retab[1])==0) { return2; } else if(strcmp(s,retab[2])==0) { return3; } else if(strcmp(s,retab[3])==0) { return4; } else if(strcmp(s,retab[4])==0) { return5; } else if(strcmp(s,retab[5])==0) { return6; } else { return0; }}charGetChar(char*input,int*index,intlength){ if(*index<=length) { (*index)++; returninput[(*index)-1]; } else return0;}intClearBlank(char*input,int(*index),intlength){ while((*index)!=length) { if(input[(*index)]==32&&(*index)!=length) { ((*index))++; } else if(input[(*index)]==32&&(*index)==length) { printf("\n谢谢使用！\n"); getchar(); exit(0); } else { return1; } }return0;}voidlrparser(char*input,intinputLength,int*index){ if (syn==1) { scaner(input,inputLength,index); while(syn==-1) { scaner(input,inputLength,index); } yucu(input,inputLength,index); if(syn==6) {scaner(input,inputLength,index); while(syn==-1) { scaner(input,inputLength,index); } if(syn==0) { printf("success\n"); getchar(); return; } } } else { printf("error!"); return; }}voidyucu(char*input,intinputLength,int*index){ statement(input,inputLength,index); while (syn==26) { scaner(input,inputLength,index); while(syn==-1) { scaner(input,inputLength,index); }statement(input,inputLength,index); } return;}voidstatement(char*input,intinputLength,int*index){ if(syn==10) { scaner(input,inputLength,index); while(syn==-1) { scaner(input,inputLength,index); } if(syn==18) { scaner(input,inputLength,index); while(syn==-1) { scaner(input,inputLength,index); } expression(input,inputLength,index); } else { printf("输出赋值号错误！\n"); getchar(); exit(0); } } else { printf("输出语句错误！%d\n",syn); getchar(); exit(0); } return;}voidexpression(char*input,intinputLength,int*index){ term(input,inputLength,index); while(syn==13||syn==14) { scaner(input,inputLength,index); while(syn==-1) { scaner(input,inputLength,index); }term(input,inputLength,index); } return;}voidterm(char*input,intinputLength,int*index){ factor(input,inputLength,index); while(syn==15||syn==16) { scaner(input,inputLength,index); whi