词法分析器(共25页).doc

精选优质文档-倾情为你奉上课 程 设 计 说 明 书设计题目： 词法分析器的实现 专业： 班级： 设计人： 山 东 科 技 大 学2014年 6 月 24日课 程 设 计 任 务 书学院：信息科学与工程学院 专业： 班级： 姓名： 一、 课程设计题目： 词法分析器的实现 二、 课程设计主要参考资料（1） 编译原理 韩太鲁、孙忠林著 （2） 三、课程设计应解决的主要问题（1） 词法分析器的实现 （2） （3） 四、任务发出日期： 2014-4-21 课程设计完成日期： 2014-6-24 指导教师签字： 系主任签字 ： 指导教师对课程设计的评语成绩： 指导教师签字： 年 月 日词法分析器的实现一、 设计目的1熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。2复习高级语言，进一步加强用高级语言来解决实际问题的能力。3通过完成词法分析程序，了解词法分析的过程。二、 设计要求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：源程序文件结束而注释未结束。注释格式为：/* */三、 设计说明（一）、需求分析1、设计要求：（1）、对给定的程序通过词法分析器能够识别一个个单词符号，并以二元式(单词类型，单词符号)显示；（2）、可以将要分析的程序保存到文件中进行读取；（3）、删除无用的空白字符、回车符、及其它非实质性符号。2、词法分析的任务从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器或称扫描器 。3、词法分析程序功能：（1）读入源程序字符串，识别开具有独立含义的最小语法单位单词（符号）；（2）把单词变换成长度统一的且为定长的属性字；（3）滤掉空格，跳过注释、换行符（4）某些预加工处理4、单词的分类（1） 基本字，也称关键词。如PASCAL语言中的begin，end，if，while和var等。（2）标识符。用来表示各种名字，如常量名、变量名、过程名和函数名等。（3）常数。各种类型的常数，如25，2.71828，'a'，'hello'和TRUE等。（4）算符。如+，-，*，<=等。（5）界符。如逗号，分号，括号等。 （二）、概要设计词法分析器主要特点是不依靠语法，而只依靠词法，即处理一个单词时不依赖于外部单词的信息，因此词法分析器一般都很简单。当然，对某些语言在作词法分析时，在有些情况下不得不往前查看多个字符，有时还要做一些特殊处理，还有一些在词法分析中处理不了的，要留到语法分析中进行处理。本算法主要利用状态转换图生成一个词法分析器，对输入的程序进行词法分析，并将分析得到的单词造表。其中关键字表和界限符表的大小是由高级语言的子集决定的，可以用数组装载；而标识符表和常数表的大小取决于输入的待分析程序中的变量、过程名、常数的个数，所以要用指针组成动态链表来装载。当然为了方便，我们也把它定义成数组处理。本程序规定：(1)关键字"begin","end","if","then","else","while","write","read","do", "call","const","char","until","procedure","repeat"(2)运算符："+","-","*","/","="(3)界符："","","","","",",",".","(",")",":"(4)其他标记 如字符串，表示以字母开头的标识符。(5)空格、回车、换行符跳过。对于一段可能的输入代码，其结果在屏幕上显示如下：( 1 , 无符号整数)( begin , 关键字 )( if , 关键字 )( +, 运算符 )( ； , 界符 )( a , 普通标识符 )关键字或标识符的判断：读入一串字符，将ASCII码在字母范围的字符存入数组中，将该数组与设置好的关键字比较，如果相等则输出是关键字，否则继续读入直至下一字符既非数字也非字母，输出为标识符；数字的判断：若跟在字母后面则一起输出为标识符，否则输出为数字；界符、运算符的判断：直接判断其ASCII码运行过程为：1预处理：把源文件一个字符一个字符的读入词法分析程序设置的输入字符结构体数组中（输入缓冲区），读入过程要删除多余的空格；2源程序字符数组中获得单词, 编码为二元式.：二元式采用结构体数组存储, 把单词类型和词元记录下来。 为了方便和适用起见，首先建立一个文本，进而在文本中进行pascal语言输入。输入完毕之后，就可以进行从文本中取字符，进而把它放在一个数组中。之后再数组中进行取字符，之前要定义一个数组，定义一个指针指向数组，为first。之后就用一个循环依次从数组中取字符，假如是字符就放在buf中，first+；一次进行下去，期间要时刻与关键字指针数组进行比较如果相等就立马输出，并显示是关键字此时将buf置为初值，first重新指向首地址。算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 （三）、详细设计1 主程序示意图：主程序示意图如图3-1所示。图3-1 主程序示意图其中初始包括以下两个方面： 关键字表的初值关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：KeyWord key14="void",1,"main",2,"int",3,"float",4,"const",5,"for",6,"if",7,"else",8,"then",9,"while",10,"switch",11,"break",12,"begin",13,"end",14;（2）程序中需要用到的主要变量为syn,token和sum token用来存放构成单词符号的字符串； sum用来存放整型单词； syn用来存放单词符号的种别码。2 扫描子程序的算法思想：下图描述了扫描子程序主要流程，具体内容如下图所示。图 3-2 扫描子程序主要流程3、设计词法分析器模块调用结构图图3-3 模块调用结构图模块结构：（1）main函数：程序主函数：输入并打开源程序文件，初始化保留字表调用其他判断标示符的子函数，输出分析结果。（2）IsAlp函数：识别保留字和标识符（3）IsNum函数：识别整数，如有精力，可加入识别实数部分工功能（4）IsAno函数：处理除号/和注释（5）IsOther函数：识别其他特殊字符（6）Output函数：输出单词的二元式到目标文件，输出格式（单词助记符，单词内码值），如（int，-）（rlop，>）（7）Error函数：输出错误信息到屏幕（8）Flag_Num函数：查填常量表（9）Flag_Sign函数：查填符号表4、程序流程图下图为程序执行的主要流程，具体内容如下：图3-4 程序执行的主要流程源代码：#include<stdio.h>#include<string.h>#include<stdlib.h>#defineLENGTH 46#define N 100typedef struct tokenchar name30;int code;int addr;token;typedef struct KeyWord/关键字char name30;/关键字名字int code;KeyWord;typedef struct symble/字符char name30;/字符名字int number;/字符编码int type;/字符类型symble;char ch;int error_count; /错误出现的个数int var_count; /字符个数int num_count; /数字个数int label_count;int code_count; /代码数量int addr_count; /内码编址int LineOfPro; /错误出现的行号char filename30;FILE *Source; /源文件KeyWord key14="void",1,"main",2,"int",3,"float",4,"const",5,"for",6,"if",7,"else",8,"then",9,"while",10,"switch",11,"break",12,"begin",13,"end",14;token CurrentToken;token zancun;symble CurrentSimble;symble SymbleListN;symble NumListN;/错误类型void Error(int a)error_count+;switch(a)case 1:printf("error %2d 非法字符 %3d行.n",error_count,LineOfPro+1);break;case 2:printf("error %2d 没有匹配的注释符 %3d行.n",error_count,LineOfPro+1);break;return;/输出void OutPut() int i=0;if(CurrentToken.code=17) / 标志符输出CurrentSimble.number=CurrentToken.addr; CurrentSimble.type=CurrentToken.code;strcpy(CurrentSimble.name,CurrentToken.name);Flag_Sign(); printf("<id,%d>",addr_count);elseif(CurrentToken.code=18) / 数字输出 CurrentSimble.number=CurrentToken.addr; CurrentSimble.type=CurrentToken.code; strcpy(CurrentSimble.name,CurrentToken.name); Flag_Num(); printf("<num , %d>",num_count); else if(CurrentToken.code>=1)&&(CurrentToken.code<=14)/关键字的输出 printf("<%s ,_>",zancun.name);else/符号的输出printf("<%s ,_>",CurrentToken.name);/判断是否是数字void IsNum()int k=0;while(ch>='0')&&(ch<='9')CurrentToken.namek+=ch;/将数字放入单词缓冲区ch=fgetc(Source); CurrentToken.code=18;/数字的机内码是18 OutPut();/判断是否是关键字void IsAlp()int i,h,j;h=0;i=0;j=0;while(ch>='a')&&(ch<='z')|(ch>='A')&&(ch<='Z')|ch='_')/将完整的单词放入单词缓冲区CurrentToken.namei+=ch;ch=fgetc(Source);zancun=CurrentToken;for(i=0;i<14;i+)/将单词缓冲区中的词和关键字数组中的词比较，看是不是关键字for(j=0;j<30;j+)if(CurrentToken.namej=keyi.namej)h=0;elseh=1;break;if(h=0) break; if(h=0)CurrentToken.code=keyi.code;/将第i个关键字的机内码给单词缓冲区中现有单词的机内码CurrentToken.addr=-1;/关键字地址为-1OutPut();else CurrentToken.code=17;CurrentToken.addr=addr_count+;/如果不是关键字就是普通标识符，地址加OutPut();/判断是否是注释void IsAno()char ch1;ch1=ch;ch=fgetc(Source);if(ch='*')for(;) ch=fgetc(Source);if(ch=EOF)Error(2);break;/到最后没有*说明注释不完全，有错误 if(ch='*')ch1=ch;ch=fgetc(Source);if(ch='/')/如果最后有*/说明注释完整ch=fgetc(Source);break;else error_count+;Error(2);CurrentToken.name0='/'/如果注释不完整，将第一个字母看成/CurrentToken.code=22;CurrentToken.addr=-1;/符号的地址是-1OutPut();/判断是否是其它void IsOther()char ch1;int i;for(i=0;i<30;i+)CurrentToken.namei='0'/将缓冲区初始化switch(ch)case'+':ch1=fgetc(Source);if(ch1='=') CurrentToken.name0='+'CurrentToken.name1='=' CurrentToken.code=38; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;elseCurrentToken.name0='+'CurrentToken.code=19;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case'-':ch1=fgetc(Source);if(ch1='=') CurrentToken.name0='-'CurrentToken.name1='=' CurrentToken.code=39; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;elseCurrentToken.name0='-'CurrentToken.code=20;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case'*':ch1=fgetc(Source);if(ch1='=') CurrentToken.name0='*'CurrentToken.name1='=' CurrentToken.code=40; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;elseCurrentToken.name0='*'CurrentToken.code=21;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case'%':if(ch1='=') CurrentToken.name0='%'CurrentToken.name1='=' CurrentToken.code=41; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;elseCurrentToken.name0='%'CurrentToken.code=23;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case'(':CurrentToken.name0='('CurrentToken.code=24;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case')':CurrentToken.name0=')'CurrentToken.code=25;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case'':CurrentToken.name0=''CurrentToken.code=26;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case'':CurrentToken.name0=''CurrentToken.code=27;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case'<':ch1=fgetc(Source);if(ch1='=') CurrentToken.name0='<'CurrentToken.name1='=' CurrentToken.code=31; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;else CurrentToken.name0='<' CurrentToken.code=29; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;case'>':ch1=fgetc(Source);if(ch1='=') CurrentToken.name0='>'CurrentToken.name1='=' CurrentToken.code=32; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;else CurrentToken.name0='>' CurrentToken.code=30; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;case'=':CurrentToken.name0='='CurrentToken.code=33;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break;case'!':ch1=fgetc(Source);if(ch1='=') CurrentToken.name0='!'CurrentToken.name1='=' CurrentToken.code=34; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;else CurrentToken.name0='n' CurrentToken.name1='o' CurrentToken.name2='t' CurrentToken.code=44; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;case'':CurrentToken.name0=''CurrentToken.code=35;CurrentToken.addr=-1;OutPut();ch=fgetc(Source); break; case'|':ch1=fgetc(Source);if(ch1='|') CurrentToken.name0='O'CurrentToken.name1='R' CurrentToken.code=42; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;case'&':ch1=fgetc(Source);if(ch1='&') CurrentToken.name0='A'CurrentToken.name1='N' CurrentToken.name2='D' CurrentToken.code=43; CurrentToken.addr=-1; OutPut(); ch=fgetc(Source); break;case 10: / /n换行LineOfPro+;ch=fgetc(Source);break;case 13: / 回车换行LineOfPro+;ch=fgetc(Source);break;case' ': / 空格CurrentToken.code=60;ch=fgetc(Source);break;default:Error(1);ch=fgetc(Source); break;/查添符号int Flag_Sign()int flag,i=0;/用缓冲符号表中的符号和符号数组中的比较for(i=0;i<(var_count-1);i+)flag=strcmp(CurrentSimble.name,SymbleListi.name);if(flag=0)CurrentToken.addr=var_count;/如果存在，将符号数组的地址返回return 0;SymbleListvar_count-1.number=CurrentToken.addr; SymbleListvar_count-1.type=CurrentToken.code;strcpy(SymbleListvar_count-1.name,CurrentToken.name);/不存在写入printf("<%s ,%3d >",SymbleListvar_count-1.name,var_count);var_count=var_count+1;return 1;/常量int Flag_Num()int flag,i=0;/用缓冲常量表中的常量和常量数组中的比较for(i=0;i<(num_count-1);i+)flag=strcmp(CurrentSimble.name,NumListi.name);if(flag=0)CurrentToken.addr=num_count;/如果存在，将符号数组的地址返回return 0;NumListnum_count-1.number=CurrentToken.addr; NumListnum_count-1.type=CurrentToken.code;strcpy(NumListnum_count-1.name,CurrentToken.name);/不存在写入num_count=num_count+1;return 1;int main()int i=0,j=0;code_count=0; /代码数量var_count=1; /字符个数 label_count=1; addr_count=0; /地址计数num_count=0; /数字计数 LineOfPro=0; /行号 printf("词法分析开始：n");if(Source=fopen("D:a.txt","r")=NULL)printf("无法打开文件%s!n",filename);exit(1);ch=fgetc(Source);while(ch!=EOF)