院 系： 计算机科学学院 专业、年级： 07计科2大班 课程名称： 编译原理 学号姓名： 指导教师：
2010 年11月17 日
组员 学号 姓名 实验实验一：词法分析 名称 通过设计一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 具体要求：输入为某语言源代码，达到以下功能： 程序输入/输出示例：如源程序为C语言。输入如下一段： main() { int a,b; a=10; 实验室 9205 实 验 目 的 或 要 求 b=a+20; } 要求输出如下（并以文件形式输出或以界面的形式输出以下结果）。 （2，”main”） （5，”（“） （5，”）“） （5，”{“} （1，”int”） （2，”a”） （5，”,”） （2，”b”） （5，”;”） （2，”a”） （4，”=”） （3，”10”） （5，”;”） （2，”b”） （4，”=”） （2，”a”） （4，”+”） （3，”20”） （5，”;”） （5，”}“） 要求： 识别保留字：if、int、for、while、do、return、break、continue等等，单词种别码为1。 其他的标识符，单词种别码为2。常数为无符号数，单词种别码为3。 运算符包括：+、-、*、/、=、>、<等；可以考虑更复杂情况>=、<=、!= ；单词种别码为4。分隔符包括： “，”“；”“（”“）”“{”“}”等等， 单词种别码为5。 1. 程序思路： 2. 定义部分：定义常量、变量、数据结构。 3. 初始化：从文件将源程序输入到字符缓冲区中。 4. 取单词前：去掉多余空白。调用过程GETNB(); 5. 提取字符组成单词，构造单词扫描过程SCAN()。 6. 判断单词的种别码，调用过程LOOKUP(); 7. 显示（导出）结果。 a) 实验的具体流程图如下： 实 验 原 理 （ 算 法 流 程 ） 词法分析器主窗口： 程 序 界 面 （ 效 果 图 ） 点击“分析”，显示实验结果： 输入源程序： 单击“另存为”，保存分析结果： 单击“清空”，清空对话框中的内容，进行下一分析： 以上就是程序执行时的窗口效果 #include #include //#include\"pl0.h\" #define al 10/*符号的最大长度*/ #define nmax 14/*number的最大位数*/ #define norw 8/*关键字个数*/ char ch;/*获取字符的缓冲区,getch使用*/ int cc,ll;/*cc表示当前字符(ch)的位置*/ char line[81];/*读取行缓冲区*/ char a[al+1];/*临时符号,多处的字节用于存放0*/ char anum[nmax+1];/*临时符号,存放number*/ char inum[nmax+1];/*存放常数*/ char word[norw][al];/*保留字*/ char fname[al];/*文件名*/ char id[al+1];/*存放标识符或保留字*/ int num;/*常数*/ int err;//错误计数器 FILE * fin; FILE * fout; FILE * fas;/*词法分析结果文件*/ /*函数执行出错,退出程序*/ #define getchdo if(-1==getch()) return -1 #define getsymdo if(-1==getsym()) return -1 int getch();/*读取一行字符*/ int getsym();/*读取一个分词*/ /*从文件fin中读取一行字符,保存到字符缓冲区line中*/ int getch() { if(cc==ll) { if(feof(fin))//“feof()”函数返回的是最后一次“读操作的内容”。 { printf(\"program incomplete\"); return -1; } ll=0; cc=0; ch=' '; while(ch!=10) { 源 程 序 代 码 if(EOF==fscanf(fin,\"%c\是文件结束标志的文件 { line[ll]=0; break; } line[ll]=ch; ll++; } } ch=line[cc]; cc++; return 0; } /*读取一个分词*/ int getsym() { int i,j,k; while(ch==' '||ch==10||ch==9)//忽略空格,换行和TAB { getchdo; } if(ch>='a'&&ch<='z')//判断是否为关键字或标识符 { k=0; do{ if(k='a'&&ch<='z'||ch>='0'&&ch<='9'); a[k]=0; if(k>al)printf(\"error\"); 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) { fprintf(fas,\"(1,\\\"%s\\\")\\n\分词为关键字*/ } else { fprintf(fas,\"(2,\\\"%s\\\")\\n\标识符*/ } } else if(ch>='0'&&ch<='9')/*判断分词是否为常数*/ { k=0; num=0; do{ num=10*num+ch-'0'; anum[k]=ch; k++; getchdo; }while(ch>='0'&&ch<='9'); fprintf(fas,\"(3,\\\"%d\\\") \常数*/ anum[k]=0; if(k>nmax)/*常数位数超过规定的最大位数,报错*/ { strcpy(inum,anum); fprintf(fas,\"常数%s超出范围!\ } fprintf(fas,\"\\n\"); } else if(ch=='+')/*运算符*/ { fprintf(fas,\"(4,\\\"%c\\\")\\n\ getchdo; } else if(ch=='-') { fprintf(fas,\"(4,\\\"%c\\\")\\n\ getchdo; } else if(ch=='*') { fprintf(fas,\"(4,\\\"%c\\\")\\n\ getchdo; } else if(ch=='/') { fprintf(fas,\"(4,\\\"%c\\\")\\n\ getchdo; } else if(ch=='=') { fprintf(fas,\"(4,\\\"%c\\\")\\n\ getchdo; } else if(ch==',')/*界符*/ { fprintf(fas,\"(5,\\\"%c\\\")\\n\ getchdo; } else if(ch==';') { fprintf(fas,\"(5,\\\"%c\\\")\\n\ getchdo; } else if(ch=='{') { fprintf(fas,\"(5,\\\"%c\\\")\\n\ getchdo; } else if(ch=='}') { fprintf(fas,\"(5,\\\"%c\\\")\\n\ getchdo; } else if(ch=='(') { fprintf(fas,\"(5,\\\"%c\\\")\\n\ getchdo; } else if(ch==')') { fprintf(fas,\"(5,\\\"%c\\\")\\n\ getchdo; } else{/*其他字符*/ getchdo; } return 0; } void init()/*初始化*/ { /*设置保留字名字,按照字母顺序,便于折半查找*/ strcpy(&(word[0][0]),\"break\");//把字符串\"break\"赋值给关键字数组 strcpy(&(word[1][0]),\"continue\"); strcpy(&(word[2][0]),\"do\"); strcpy(&(word[3][0]),\"for\"); strcpy(&(word[4][0]),\"if\"); strcpy(&(word[5][0]),\"int\"); strcpy(&(word[6][0]),\"return\"); strcpy(&(word[7][0]),\"while\"); } int main() { printf(\"请输入源文件名:\"); scanf(\"%s\fin=fopen(fname,\"r\"); if(fin) { fas=fopen(\"fas.txt\ init(); err=0; cc=ll=0; ch=' '; do{ getsymdo; }while(!feof(fin)); fclose(fas); fclose(fin); } else{ printf(\"can't open file!\"); } printf(\"词法分析结果已保存到文件fas.txt\\n\"); return 0; } 实验结果如下： 输入程序段： main() 实 验 结 果 分 析 及 心 得 体 会 { int a,b,c; c=a+b; c=c+20; d=(a-b)*c/a; } 分析结果为： (2,\"main\") (5,\"(\") (5,\")\") (5,\"{\") (1,\"int\") (2,\"a\") (5,\(2,\"b\") (5,\(2,\"c\") (5,\";\") (2,\"c\") (4,\"=\") (2,\"a\") (4,\"+\") (2,\"b\") (5,\";\") (2,\"c\") (4,\"=\") (2,\"c\") (4,\"+\") (3,\"20\") (5,\";\") (2,\"d\") (4,\"=\") (5,\"(\") (2,\"a\") (4,\"-\") (2,\"b\") (5,\")\") (4,\"*\") (2,\"c\") (4,\"/\") (2,\"a\") (5,\";\") (5,\ 经检查发现实验结果正确。 心得体会： 通过此次实验，让我了解到如何设计、编制并调试词法分析程序，加深对词法分析原理的理解；熟悉了构造词法分析程序的手工方式的相关原理，使用某种高级语言（例如C++语言）直接编写此法分析程序。另外，也让我重新熟悉了C++语言的相关内容，加深了对C++语言的用途的理解。通过相应的学习，对可视化编程工具vc++ 6.0有了进一步的了解，同时，也深深的感觉到团队合作的重要性，当你遇到一个问题时，一个人无法解决，有几个 人来和你一起探讨时，也许问题会变得豁然开朗。同时，也让我们意识到，遇到问题时， 要学会去充分的利用各种资源，查阅资料，来解决我们所遇到的问题。 成 绩 评 定 教师签名： 2010年11月 日学号 组员 姓名 实验实验二：语法分析器 名称 实 验 目 的 或 要 求 实验室 9205 实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 注：也可以采用预测分析方法、算符优先分析方法来进行分析。具体参照课本上的说明，以下是递归下降分析法的介绍。 实验要求： 对算术表达式文法，用递归下降分析法（或预测分析方法、算符优先分析方法等）对任意输入的符号串进行分析，如合法给出相应信息，如果不合法，最好能给出在哪个产生式出现的问题。 算术表达式至少包含+、-、*、/、（）。例如：i1 + i2 * ( 34 - i3 / 2 ) 1、 递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、 递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法。 实 验 原 理 3、 递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构： (1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现, 具体为：（1）对于每个非终结符号U->u1|u2|…|un处理的方法如下 U( ) { ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分； else if(ch可能是u2字的开头)处理u2的程序部分； ….. else error(); } （2）对于每个右部u1->x1x2…xn的处理架构如下： 处理x1的程序； 处理x2的程序； …… 处理xn的程序； （3）如果非终结符U有空产生式：Uε ，则还需考虑ch属于Follow(U)的情况 实验流程图： 实 验 原 理 主窗口： 程 序 界 面 输入规约串： 单击“分析”，显示分析结果： 单击“清空”： //#include \"stdafx.h\" // 以上所表示的T',E'在此程序中分别用 T':t E':e 表示. #include #include #include #include typedef char datatype; #define maxsize 100 int BCi=0; int BCj=0; int l=0; int w; char a[10]; typedef struct { datatype data[maxsize]; int topstack; }seqstack; seqstack g; void SETNULL(seqstack *s) { s->topstack=-1; } int EMPTY(seqstack *s) { if(s->topstack>=0) return 0; else return 1; } int PUSH(seqstack *s,datatype x) //进栈函数 { if(s->topstack==maxsize-1){printf(\"overflow\");} else { s->topstack++; s->data[s->topstack]=x; l=s->topstack; } return l; } int POP(seqstack *s) //出栈函数 程 序 源 代 码 { if(EMPTY(s)) {printf(\"underflow\"); return NULL;} else{ s->topstack--; l=s->topstack; } return l; } void Input() //程序输出函数 { int i=-1; char c; c=getchar(); while(c!='#') { a[++i]=c; c=getchar(); } a[++i]='#'; BCi=i; } datatype topstack(seqstack *s) //栈状态判断函数 { if(EMPTY(s)) {printf(\"stack is empty \"); return NULL;} else return (s->data[s->topstack]); } void st() //分析函数 { //SETNULL(&g); if(EMPTY(&g)) {PUSH(&g,'#'); PUSH(&g,'E'); } } int LL1analyse() { char c; if(g.data[g.topstack]==a[BCj]) {BCj++; POP(&g); return BCj;} else if(a[BCj]=='i') { c=topstack(&g); if(c=='E') { POP(&g); PUSH(&g,'e'); PUSH(&g,'T'); } if(c=='T') {POP(&g); PUSH(&g,'t'); PUSH(&g,'F'); } if(c=='F') {POP(&g); PUSH(&g,'i'); } } else if(a[BCj]=='+') { c=topstack(&g); if(c=='e') { POP(&g); PUSH(&g,'e'); PUSH(&g,'T'); PUSH(&g,'+'); } if(c=='t') { POP(&g); } } else if(a[BCj]=='-') { c=topstack(&g); if(c=='e') { POP(&g); PUSH(&g,'e'); PUSH(&g,'T'); PUSH(&g,'-'); } if(c=='t') { POP(&g); } } else if(a[BCj]=='*') { c=topstack(&g); if(c=='t') { POP(&g); PUSH(&g,'t'); PUSH(&g,'F'); PUSH(&g,'*'); } } else if(a[BCj]=='/') { c=topstack(&g); if(c=='t') { POP(&g); PUSH(&g,'t'); PUSH(&g,'F'); PUSH(&g,'/'); } } else if(a[BCj]=='(') { c=topstack(&g); if(c=='E') {POP(&g); PUSH(&g,'e'); PUSH(&g,'T'); } if(c=='T') { POP(&g); PUSH(&g,'t'); PUSH(&g,'F'); /// PUSH(&g,'*'); } if(c=='F') { POP(&g); PUSH(&g,')'); PUSH(&g,'E'); PUSH(&g,'('); } } else if(a[BCj]==')') { c=topstack(&g); if(c=='e') { POP(&g); } if(c=='t') { POP(&g); } } else if(a[BCj]=='#') { c=topstack(&g); if(c=='e') { POP(&g); } if(c=='t') { POP(&g); } } else cout<<\"此语法错误\"<教师签名： 2010年11月 日