《编译原理》词法分析程序设计方案.doc

资源描述

实验1-4 词法分析器实验实验1-4 《编译原理》S语言词法分析程序设计方案一、实验目的了解词法分析程序的两种设计方法：1.根据状态转换图直接编程的方式；2.利用DFA编写通用的词法分析程序。二、实验内容 1．根据状态转换图直接编程编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。具体任务有：（1）组织源程序的输入（2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件（3）删除注释、空格和无用符号（4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。（5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。常量表结构：常量名，常量值 2．编写DFA模拟程序算法如下： DFA（S=S0,MOVE[][],F[],ALPHABET[]） /*S为状态，初值为DFA的初态，MOVE[][]为状态转换矩阵，F[] 为终态集，ALPHABET[] 为字母表，其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar（）；//读 i=0； while（nextchar！=NULL）//NULL代表此类单词 { if （nextchar！∈ALPHABET[]） {ERROR（“非法字符”），return（“非法字符”）；} S=MOVE[S][nextchar] //下一状态 if（S=NULL）return（“不接受”）；//下一状态为空，不能识别，单词错误 wordbuffer[i]=nextchar ； //保存单词符号 i++； nextchar=getchar（）； } Wordbuffer[i]=‘\0’; If（S∈F）return（wordbuffer）； //接受 Else return（“不接受”）； } 该算法要求：实现DFA算法，给定一个DFA（初态、状态转换矩阵、终态集、字母表），调用DFA（），识别给定源程序中的单词，查看结果是否正确。三、实验要求 1．能对任何S语言源程序进行分析在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表单词代码 1 2 3 4 5 6 7 8 9 单词 int char float void const for if else then 单词助记符 int char float void const for if else then 内码值 - - - - - - - - - 单词代码 10 11 12 13 14 15 16 17 18 单词 while switch break begin end 标识符整数单词助记符 while switch break begin end id num 内码值 - - - - - 在符号表中的位置在常数表中的位置单词代码 19 20 21 22 23 24 25 26 27 单词 + - * / % ( ) [ ] 单词助记符 + - * / % ( ) [ ] 内码值 - - - - - - - - - 单词代码 28 30 35 36 单词 < > <= >= == != % ; 单词助记符 rlop % ; 内码值 < > <= >= == != - - 单词代码 37 38 39 40 41 42 43 44 45 单词 /= += -= *= %= || && ! = 单词助记符 /= += -= *= %= or and not = 内码值 - - - - - - - - - 单词的构词规则：字母=[A-Za-z] 数字=[0-9] 标识符=字母（字母|数字）* 数字=数字(数字)* 四、S语言表达式和语句说明 1．算术表达式:+、-、*、/、% 2．关系运算符：>、>=、<、<=、==、！= 3．赋值运算符：=，+=、-=、*=、/=、%= 4．变量说明：类型标识符变量名表； 5．类型标识符：int char float 6．If语句：if 表达式then 语句 [else 语句] 7．For语句：for（表达式1；表达式2；表达式3）语句 8．While语句：while 表达式 do 语句 9．S语言程序：由函数构成，函数不能嵌套定义。函数格式为：返回值函数名（参数） begin 数据说明语句 end 10．复合语句构成 begin 语句序列 end 五、程序参考结构说明 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 1 #define ERROR 0 #define Status int typedef struct{ char key[20]; char num[10]; }ElemType; typedef struct{ char num[10]; char sign[10]; char mnemonics[10]; char isn[10]; }ElemType2; typedef struct{ ElemType *elem; int length; int listsize; }SqList; SqList L; SqList L2; int n=1;//行数 FILE *in,*out;// 指向文件的指针 char token[LISTINCREMENT]; char order_number[LIST_INIT_SIZE][LISTINCREMENT]= { "0","1","2","3","4","5","6","7","8","9","10", "11","12","13","14","15","16","17","18","19","20", "21","22","23","24","25","26","27","28","29","30", "31","32","33","34","35","36","37","38","39","40", "41","42","43","44","45","46","47","48","49","50", }; ElemType key_world[14]= { {"int","0"},{"char","1"},{"float","2"}, {"void","3"},{"const","4"},{"for","5"}, {"if","6"},{"else","7"},{"then","8"}, {"while","8"},{"switch","9"},{"break","10"}, {"begin","11"},{"end","12"} }; ElemType2 symbol[25]= { {"0","+","+","_"},{"1","-","-","_"},{"2","*","*","_"}, {"3","/","/","_"},{"4","%","%","_"},{"5","(","(","_"}, {"6",")",")","_"},{"7","[","[","_"},{"8","]","]","_"}, {"9","<","rlop","<"},{"9",">","rlop",">"},{"9","<=","rlop","<="}, {"9",">=","rlop",">="},{"9","==","rlop","=="},{"9","!=","rlop","!="}, {"10",";",";","_"},{"11","/=","/=","_"}, {"12","+=","+=","_"},{"13","-=","-=","_"},{"14","*=","*=","_"}, {"15","%=","%=","_"},{"16","||","or","_"},{"17","&&","and","_"}, {"18","!","not","_"},{"19","=","=","_"} }; Status InitList_Sq(SqList *L) { // 算法2.3 // 构造一个空的线性表L。 L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); memset(L->elem, 0, sizeof(ElemType *)); if (!L->elem) return OK; // 存储分配失败 L->length = 0; // 空表长度为0 L->listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq Status ListInsert_Sq(SqList &L, int i,char a[10],char n[10]) { // 算法2.4 // 在顺序线性表L的第i个元素之前插入新的元素e， // i的合法值为1≤i≤ListLength_Sq(L)+1 char p[10]; int b; if (i < 1 || i > L.length+1) return ERROR; // i值不合法 if (L.length >= L.listsize) { // 当前存储空间已满，增加容量 ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) return ERROR; // 存储分配失败 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存储容量 } for (b=L.length-1; b>=(i-1); --b) { strcpy(L.elem[b+1].key,L.elem[b].key); strcpy(L.elem[b+1].num,L.elem[b].num); } // 插入位置及之后的元素右移 strcpy(L.elem[i-1].key,a); strcpy(L.elem[i-1].num,n); ++L.length; // 表长增1 return OK; } // ListInsert_Sq void remove() //扫描指针回退一个字符 { fseek(in,-1,SEEK_CUR); } void Output(char a[10],char m[10]) { fputs("(",out); fputs(a,out); fputs(",",out); //if(m==-1) //fputs(Key[n].keyValue,out); //else fputs(m,out);//下标 fputs(")",out); } int Initscanner() { InitList_Sq(&L); InitList_Sq(&L2); if((in=fopen("s.txt","r"))==NULL) { printf("cannot open infile!\n"); return 0; } if((out=fopen("word.txt","w+"))==NULL) { printf("cannot open outfile!\n"); return 0; } return 0; } int Isalpha() { int i; for(i=0;i<14;i++)//关键字 { if(strcmp(token,key_world[i].key)==0) { Output(key_world[i].key,"_"); return 0; } } //标识符 for(i=0;i<=L.length;i++) { if((L.elem[i].key)&&strcmp(token,L.elem[i].key)==0) { Output("id",L.elem[i].num); return 0; } } //可识别100 ListInsert_Sq(L,i,token,order_number[i-1]); Output("id",order_number[i-1]); return 0; } int Isnumber()//Isnumber函数:consts[NUM][MAX] { int i; for(i=0;i<=L2.length;i++) { if(strcmp(token,L2.elem[i].key)==0) { Output("num",L2.elem[i].num); return 0; } } //可识别100 ListInsert_Sq(L2,i,token,order_number[i-1]); Output("num",order_number[i-1]); return 0; } int Isanotation() { char ch,pre; ch=getc(in); if(ch=='=')// "/=" Output(symbol[16].mnemonics,symbol[16].isn); else if(ch=='*')// "/*" { ch=getc(in); do{ if(feof(in)) { //num++; printf("\n第(%d)行 : 注释错误: /*后面的字符全部当做注释，缺少结束注释*/\n",n); break; } pre=ch; ch=getc(in); }while(pre!='*'||ch!='/'); } else if(ch!='/')// "/" { if(!feof(in)) { remove(); //指针回退一个字符 Output(symbol[3].mnemonics,symbol[3].isn); } else { Output(symbol[3].mnemonics,symbol[3].isn); } } else if(ch=='/') { //remove(); printf("\n第(%d)行 : 非法字符：//错误\n",n); } } //Isother函数识别其他特殊字符 int Isother() { int i; int j; char ch; for(i=0;i<25;i++) { if(strcmp(token,symbol[i].sign)==0) { if(token[0]=='<'||token[0]=='>'||token[0]=='!'|| token[0]=='+'||token[0]=='-'||token[0]=='*'||token[0]=='%'||token[0]=='=') { ch=getc(in); if(ch=='=') { token[1]=ch; for(j=0;j<25;j++) { if(strcmp(token,symbol[j].sign)==0) { Output(symbol[j].mnemonics,symbol[j].isn); return OK; } } } else if(!feof(in)) { remove(); Output(symbol[i].mnemonics,symbol[i].isn); return OK; } else { Output(symbol[i].mnemonics,symbol[i].isn); return OK; } } else { Output(symbol[i].mnemonics,symbol[i].isn); return OK; } } else if(token[0]=='|'||token[0]=='&') { ch=getc(in); token[1]=ch; for(j=0;j<25;j++) { if(strcmp(token,symbol[j].sign)==0) { Output(symbol[j].mnemonics,symbol[j].isn); return OK; } } remove(); printf("\n第(%d)行 : 非法字符：%c错误\n",n,token[0]); return ERROR; } } printf("\n第(%d)行 : 非法字符：%s错误\n",n,token); return ERROR; } void Scanner() { char ch; int i; ch=getc(in); while(!feof(in)) { while(ch==' '||ch=='\t'||ch=='\n') //先统计行数 { if(ch=='\n') ++n; ch=getc(in); } if(((ch>='a')&&(ch<='z'))||(ch=='_')||((ch>='A')&&(ch<='Z')))//标识符 isalpha(ch)单词 { i=1; memset(token,0,sizeof(token)); token[0]=ch; ch=getc(in); while(((ch>='a')&&(ch<='z'))||((ch>='0')&&(ch<='9'))||((ch>='A')&&(ch<='Z'))||(ch=='_'))//word number { token[i++]=ch; ch=getc(in); } token[i]='\0'; Isalpha(); } else if((ch>='0')&&(ch<='9'))//整数 { i=1; memset(token,0,sizeof(token)); token[0]=ch; ch=getc(in); while((ch>='0')&&(ch<='9'))//word number { token[i++]=ch; ch=getc(in); } token[i]='\0'; Isnumber(); } else if(ch=='/')//区分//，/*，/= { memset(token,0,sizeof(token)); token[0]=ch; Isanotation(); ch=getc(in); } else if(!feof(in)) //特殊字符 { memset(token,0,sizeof(token)); token[0]=ch; Isother(); ch=getc(in); } } } int show() { int i; char ch; printf("\n二元式:\n"); rewind(out); while(!feof(out)) { printf("%c",getc(out)); } if(L.length!=0) printf("\n--------------标识符表--------------\n"); for(i=0;i<L.length;i++) { printf("%s,%s\n",L.elem[i].num,L.elem[i].key); } if(L2.length!=0) printf("\n--------------常数表---------------\n"); for(i=0;i<L2.length;i++) { printf("%s,%s\n",L2.elem[i].num,L2.elem[i].key); } return OK; } int main() { Initscanner(); Scanner(); show(); fclose(in); fclose(out); return 0; } 1．Initscanner函数：程序初始化：输入并打开源程序文件和目标程序文件，初始化保留字表 2．Scanner函数：若文件未结束，反复调用lexscan函数识别单词。 3．Lexscan函数：根据读入的单词的第一个字符确定调用不同的单词识别函数 4．Isalpha函数：识别保留字和标识符 5．Isnumber函数：识别整数，如有精力，可加入识别实数部分工功能 6．Isanotation函数：处理除号/和注释 7．Isother函数识别其他特殊字符 8．Output函数：输出单词的二元式到目标文件，输出格式（单词助记符，单词内码值），如（int，-）（rlop，>）…… 9．Error函数：输出错误信息到屏幕 10．除此之外，还可以设置查符号表，填写符号表等函数，学生可自行设计。六、实验过程说明 1．每人单独完成。 2．完成后，由老师验收，并给出成绩。 3．实验完成后，写出实验报告（要求交打印稿）。报告内容要求如下：完成人：班级、学号、姓名一、实验名称：简化S语言词法分析器二、实验目的：通过手工编写简化C语言词法分析器，熟悉并深入理解编译程序词法分析器的工作原理。三、实验内容： 1．根据保留字和特殊符号表能区分出源文件中的保留字、普通标识符和特殊符号，并能进行简单的错误处理。 2．设计词法分析器模块调用结构图和各模块流程图。 3．程序源代码。 4．程序的执行结果：输入文件，输出结果文件及屏幕信息。四、实验中出现的问题及解决方法。五、体会、意见或建议。 12

展开阅读全文