《编译原理》词法分析程序设计方案.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 Wordbuffer10=“”/单词缓冲区置空Nextchar=getchar（）；/读i=0；while（nextchar！=NULL）/NULL代表此类单词 if （nextchar！ALPHABET） ERROR（“非法字符”），return（“非法字符”）； S=MOVESnextchar /下一状态 if（S=NULL）return（“不接受”）；/下一状态为空，不能识别，单词错误 wordbufferi=nextchar ； /保存单词符号 i+； nextchar=getchar（）；Wordbufferi=0;If（SF）return（wordbuffer）； /接受 Else return（“不接受”）；该算法要求：实现DFA算法，给定一个DFA（初态、状态转换矩阵、终态集、字母表），调用DFA（），识别给定源程序中的单词，查看结果是否正确。三、实验要求1能对任何S语言源程序进行分析在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。2能检查并处理某些词法分析错误词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。本实验要求处理以下两种错误（编号分别为1，2）：1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。2：源程序文件结束而注释未结束。注释格式为：/* */四、保留字和特殊符号表单词代码123456789单词intcharfloatvoidconstforifelsethen单词助记符intcharfloatvoidconstforifelsethen内码值-单词代码101112131415161718单词whileswitchbreakbeginend标识符整数单词助记符whileswitchbreakbeginendid num内码值-在符号表中的位置在常数表中的位置单词代码192021222324252627单词+-*/%()单词助记符+-*/%()内码值-单词代码28303536单词=!=%;单词助记符rlop%;内码值=!=-单词代码373839404142434445单词/=+=-=*=%=|&!=单词助记符/=+=-=*=%=orandnot=内码值-单词的构词规则：字母=A-Za-z数字=0-9标识符=字母（字母|数字）*数字=数字(数字)*四、S语言表达式和语句说明1算术表达式:+、-、*、/、%2关系运算符：、=、=、=、！=3赋值运算符：=，+=、-=、*=、/=、%=4变量说明：类型标识符 变量名表；5类型标识符：int char float6If语句：if 表达式then 语句 else 语句7For语句：for（表达式1；表达式2；表达式3） 语句8While语句：while 表达式 do 语句9S语言程序：由函数构成，函数不能嵌套定义。函数格式为：返回值 函数名（参数）begin 数据说明 语句end10复合语句构成begin 语句序列end五、程序参考结构说明#include #include #include #include #define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OK 1#define ERROR 0#define Status inttypedef structchar key20;char num10;ElemType;typedef structchar num10;char sign10;char mnemonics10;char isn10;ElemType2;typedef structElemType *elem;int length;int listsize;SqList;SqList L;SqList L2;int n=1;/行数 FILE *in,*out;/ 指向文件的指针char tokenLISTINCREMENT;char order_numberLIST_INIT_SIZELISTINCREMENT=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_world14=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 symbol25=0,+,+,_,1,-,-,_,2,*,*,_,3,/,/,_,4,%,%,_,5,(,(,_,6,),),_,7,_,8,_,9,rlop,rlop,9,=,rlop,=,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_SqStatus ListInsert_Sq(SqList &L, int i,char a10,char n10) / 算法2.4 / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1char p10;int b;if (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.elemb+1.key,L.elemb.key);strcpy(L.elemb+1.num,L.elemb.num);/ 插入位置及之后的元素右移strcpy(L.elemi-1.key,a);strcpy(L.elemi-1.num,n);+L.length; / 表长增1return OK; / ListInsert_Sqvoid remove() /扫描指针回退一个字符fseek(in,-1,SEEK_CUR);void Output(char a10,char m10)fputs(,out);fputs(a,out);fputs(,out);/if(m=-1)/fputs(Keyn.keyValue,out);/elsefputs(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;i14;i+)/关键字if(strcmp(token,key_worldi.key)=0)Output(key_worldi.key,_);return 0;/标识符for(i=0;i=L.length;i+)if(L.elemi.key)&strcmp(token,L.elemi.key)=0)Output(id,L.elemi.num);return 0;/可识别100 ListInsert_Sq(L,i,token,order_numberi-1);Output(id,order_numberi-1);return 0;int Isnumber()/Isnumber函数:constsNUMMAXint i;for(i=0;i=L2.length;i+)if(strcmp(token,L2.elemi.key)=0)Output(num,L2.elemi.num);return 0;/可识别100 ListInsert_Sq(L2,i,token,order_numberi-1);Output(num,order_numberi-1);return 0;int Isanotation()char ch,pre;ch=getc(in);if(ch=)/ /=Output(symbol16.mnemonics,symbol16.isn);else if(ch=*)/ /*ch=getc(in);doif(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(symbol3.mnemonics,symbol3.isn);elseOutput(symbol3.mnemonics,symbol3.isn);else if(ch=/)/remove();printf(n第(%d)行 : 非法字符：/错误n,n);/Isother函数识别其他特殊字符int Isother() int i;int j;char ch;for(i=0;i25;i+) if(strcmp(token,symboli.sign)=0)if(token0=|token0=!|token0=+|token0=-|token0=*|token0=%|token0=)ch=getc(in);if(ch=)token1=ch;for(j=0;j25;j+)if(strcmp(token,symbolj.sign)=0)Output(symbolj.mnemonics,symbolj.isn);return OK;else if(!feof(in)remove();Output(symboli.mnemonics,symboli.isn);return OK;elseOutput(symboli.mnemonics,symboli.isn);return OK;elseOutput(symboli.mnemonics,symboli.isn);return OK;else if(token0=|token0=&)ch=getc(in);token1=ch;for(j=0;j=a)&(ch=A)&(ch=a)&(ch=0)&(ch=A)&(ch=0)&(ch=0)&(ch=9)/word numbertokeni+=ch;ch=getc(in);tokeni=0;Isnumber();else if(ch=/)/区分/，/*，/= memset(token,0,sizeof(token);token0=ch;Isanotation();ch=getc(in);else if(!feof(in) /特殊字符memset(token,0,sizeof(token);token0=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;iL.length;i+)printf(%s,%sn,L.elemi.num,L.elemi.key);if(L2.length!=0)printf(n-常数表-n); for(i=0;i）9Error函数：输出错误信息到屏幕10除此之外，还可以设置查符号表，填写符号表等函数，学生可自行设计。六、实验过程说明1每人单独完成。2完成后，由老师验收，并给出成绩。3实验完成后，写出实验报告（要求交打印稿）。报告内容要求如下：完成人：班级、学号、姓名一、实验名称：简化S语言词法分析器二、实验目的：通过手工编写简化C语言词法分析器，熟悉并深入理解编译程序词法分析器的工作原理。三、实验内容：1根据保留字和特殊符号表能区分出源文件中的保留字、普通标识符和特殊符号，并能进行简单的错误处理。2设计词法分析器模块调用结构图和各模块流程图。3程序源代码。4程序的执行结果：输入文件，输出结果文件及屏幕信息。四、实验中出现的问题及解决方法。五、体会、意见或建议。12