词法分析器的设计与实现.doc

目录一设计题目2二设计要求21. 词法分析器的定义22. 设计要求23. 本程序自行规定：3三设计作用与目的41. 设计作用42. 设计目的4四运行环境及工具软件4五系统设计51. 系统总体设计5（1）词法分析器的设计5（2）总体设计框图6（3） 总程序流程图62. 各子模块设计8（1） 字符的识别8（2）关键字的识别8（3） 数字的识别8（4）界符的识别10（5） 运算处理103.相关函数分析114. 源程序设计12六实验调试结果291. 调试工具292. 调试步骤293. 调试结果29七设计中的问题及解决方法31八设计心得32九参考文献34词法分析器的设计与实现一设计题目词法分析器的设计与实现二设计要求1. 词法分析器的定义词法分析顾名思义就是分词。它以程序设计语言编制的源程序作为输入，以单词序列作为输出。分词过程可以通过编制程序自动完成，我们通常称这个分词程序为词法分析器。词法分析器分析的源程序可以是现有的各类程序设计语言源程序也可以是人为给定的模型语言的源程序。本文中的源程序为后者。从词的角度来看，它涉及的内容较为简单，只包括几个较为常用的词类，词类的构成上也适当的作了一些简化。对词进行分析时，我们是按类型进行分析的 。不同类型的词在后续的分析中所起的作用不同，相应的操作也各有不同，但同种类型中的 词虽然单词的构成不同但从宏观上看它们的操作大体一致。模型语言中的单词可以分为“关 键字”、“标识符”、“常数”、“分隔符”、“运算符”几类。一般，关键字在程序设计语言中人为给定2. 设计要求对给定的程序通过词法分析器能够识别一个个单词符号，并以二元式(单词种别码，单词符号的属性值)显示。而本程序则是通过对给定路径的文件的分析后以单词符号和文字提示显示。另外，如果是算术表达式，则需要通过栈、运算符的优先级比较处理等从而计算出最终结果并显示。通过此次课程设计要求掌握从源程序文件中读取有效字符的方法，掌握词法分析的实现方法并上机调试编出的词法分析程序。在处理表达式前，首先设置两个栈：一是运算符栈，用于在表达式处理过程中存放运算符。在开始时，运算符栈中先压入一个表达式结束符“#”。二是操作数栈，用于在表达式处理过程中存放操作数。然后从左到右依次读出表达式中的各个符号（运算符或操作数），每读出一个符号按以下原则进行处理：(1) 若读出的是操作数，则将该操作数压入操作数栈，并依次读入下一个符号。(2) 若读出的是运算符，则作进一步判断。若读出运算符的优先级大于运算符栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。若读出的是表达式结束符“#”，且运算符栈栈顶的运算符也是表达式结束符“#”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。若读出运算符的优先级不大于运算符栈栈顶运算任的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算（运算符为刚从运算符栈退出的运算符，运算对象为刚从操作数栈退出的两个操作数），并将运算结果压入操作栈。3. 本程序自行规定： 关键字：auto，break，case，char，const，continue， default，do，double，else，enum，extern， float，for，goto，if，int，long，return， short，signed，sizeof，static，struct，switch 运算符：+，-，*，/，= 界符：，;，,，.，(，)，: 数字：09 其他标记 如字符串，表示以字母开头的标识符。 空格、回车、换行符跳过。在屏幕上显示如下：( +, 运算符 )( ； , 界符 )(auto , 关键字 )( 1 , 无符号整数)( a , 普通标识符 )(continue , 关键字 )三设计作用与目的 1. 设计作用用高级语言编写一个词法分析器，使之能识别输入串,并把分析结果(单词符号，标识符，关键字等等)输出。输入源程序，输入单词符号，本词法分析器可以辨别关键字、标识符、常数、运算符号和某些界符，运用了文件读入来获取源程序代码，再对该源程序代码进行词法分析，这就是词法分析器的基本功能。当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后，分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理子程序来处理新串。 2. 设计目的1）熟悉词法分析的基本原理，词法分析的过程，以及词法分析中要注意的一些问题；2）通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；3）复习高级语言，进一步加强用高级语言来解决实际问题的能力；4）提高词法分析方法的实践能力；5）理解如何理论联系实际以及明白理论与实际的差别。四运行环境及工具软件Windows XP环境，Microsoft visual C+ 6.0版，512M内存，80G硬盘容量。VC+是微软公司开发的一个IDE(集成开发环境),换句话说,就是使 C+的一个开发平台.有些软件就是这个编出来的vc+是Windows平台上的C+编程环境，学习VC要了解很多Windows平台的特性并且还要掌握MFC、ATL、COM等的知识，难度比较大。五系统设计 1. 系统总体设计 （1）词法分析器的设计词法分析在教学上的主要应用是对源程序进行分词同时验证词的合性，词法分析的输入是给定的模型语言，输出为单词序列。输入的源程序可以看成是一个字符串序列，通过把源程序看作字符串序列就可以采用形式语言的一些现有理论处理相关的编译题。分词的输出为单词序列，单词是一个有共同含义的字符集。由于程序设计语言中通常使用空格来分割不同的词，因此初学者在理解这一概念时可以简单的把空格分隔开的字符串认为是一个单词。词法分析器设计时，输入的源程序以文件的形式存储在外部。主控程序通过打开文件调用待分析的源程序。程序设计时采用一字一码的形式处理，标志符为一类，不同的标志符通过值区别。常数只给出具体的值即可。根据以上的分析可以相应的设计如下的存储结构。关键字可以设计为一个预先存储好的表格。其设计的主要思路为：先让用户输入单词或字符串，而且是一个字一个字的读取，直到#束，且要全部打印出代码。着便开始进行分析，先是依次判断每一个字符，空白就跳到下一个，次往下类推，道不是空白为止。后再读入一个字符，如果是字母，就继续读入下一个，只要遇到是字母或者是数字的时候，都继续往下读，而且读入的字符都依次地保存在一个字符串当中，直到不是字母或者是数字为止。这时侯来查找关键字表，如果有关键字的话，则作为关键字输出，如果没有，就作为字符串输出。的话，如果是数字，也继续读入，如果是数字或者是小数点，依然继续往下读，也依次保存在字符串中，直到不是数字或小数点为止，最终这里得到就是常数。要注意的是，在这里如果中途遇到运算符和界符，也依然要做和前面关键字、字符串或者是常数类似的分析，如果输入是一个正确的算术表达式则按照如下操作进行：(1) 若读出的是操作数，则将该操作数压入操作数栈，并依次读入下一个符号。(2) 若读出的是运算符，则作进一步判断。若读出运算符的优先级大于运算符栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。若读出的是表达式结束符“#”，且运算符栈栈顶的运算符也是表达式结束符“#”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。若读出运算符的优先级不大于运算符栈栈顶运算任的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算（运算符为刚从运算符栈退出的运算符，运算对象为刚从操作数栈退出的两个操作数），并将运算结果压入操作栈。这就是整个词法分析器的设计思想。 （2）总体设计框图总体设计框图如下：出错处理常数表 界 符 源文件运算符 数 字字 符关键字 字符表词法分析器图1.总体设计框图（3） 总程序流程图总程序流程图如下： 将其依次输入到*c读入一个字符放在ch变量中调用count()函数计算判断能否计算?输出分析结果若可计算则输出表达式的值！ 结束！将字符拼接成一字符串strToken输入一个被识别字符串开始图2.总体流程图 Ch是字符？ Y N Ch是数字？ N Ch是运算符？strToken是关键字? Y N N Y Y Y Ch是界符？输出字符串输出关键字 Y Y NRetract()Error2. 各子模块设计（1） 字符的识别 判断输入的字符是否为字符，若为字符则将其拼凑成一个单词在往下进行判断，若不为字符则则判断其是否为数字，其子模块程序流程图1如下：读入一个字符放在ch变量中Ch是字符?NCh是数字？Y将字符拼接成一个字符串strToken 图3. 字符的识别（2）关键字的识别 判断输入的单词是否为关键字，若为关键字则返回它的编码，若不为关键字则判断其是否为运算符，其子模块程序流程图如图2所示：（3） 数字的识别 判断输入的字符是否为数字，若为数字则返回它的编码，若不为数字则判断其是否为运算符，其子模块程序流程图如图3所示：将字符拼接成一个字符串strTokenstrToken是关键字?NY输出关键字Return q输出字符串Return -1图4. 关键字的识别Ch是数字？NY Ch是运算符？将其依次输入到*c Y图5.数字的识别（4）界符的识别 判断输入的字符是否为界符，若为数字则break，若不为数字则将搜索指示器回调一个字符位置,将ch置为空白字符，其子模块程序流程图如下所示：Ch是界符？NYErrorRetract()图6.界符的识别（5） 运算处理数字和运算符依次输入*c判断能否运算？N Y输出字符串90调用函数count()90图7.运算的判别3.相关函数分析n int i=0,j=0,k=0,t=0; /搜索指示器n char ch; /存放最新读入的原程序字符n void GetChar(); /将下一个字符读入ch中,搜索指示器前移一字符位n void GetBC(); /检查ch中的字符是否为空白,若是则调用Getchar直至ch中进入一个非空白字符n void Concat(); /将ch中的字符连接到strToken之后n bool IsLetter(); /判断ch中的字符是否为字符 bool IsDigit(); /判断ch中的字符是否为数字int Reserve(); /对strToken中的字符串查找保留字表,若它是一个保留字 l 则返回它的编码,否则返回-1值。n void Retract(); /将搜索指示器回调一个字符位置,将ch置为空白字符n char*InsertId(); /将strToken中的标识符插入符号表,返回符号表的指针n char * InsertConst(); /将strToken中的常数插入常数表,返回常数表指针n int check(char *c); / 检查字符串中有否除了 0-9, +,-,*,/,(,),之外的其他字符，l 如果有，则返回0, 表示出现错误l 若没有，则返回1,表式字符串符合规定n void move(char *f, double *s,int p); / 将当前已经完成运算的运算符消去，同时将数值数组的位置调整以进行下一次运算n double convnum(char *c); / 将输入的字符串先将其小数点以前的部分复制到temp数组中，若有小数点，则将小数点之后的数值，也就是小数部分先进行计算,值存入num中，计算完成后，再对整数部分进行计算，值加上小数部分的值，存入num中。n double good(char *c); / 将输入的字符串中的数字分别调用convnum(char *c)函数进行数值变换，再将其依 次存入doulbe si中，将加减乘除运算符依次存入字符串符号数组 char fi中， 然后如果遇到括号，则将括号内的字符串存入另一字符数组中，然后用此 good(char *c) 递归函数进行递归运算。 然后根据先乘除，后加减的顺序对已存入数组的数值根 据存入字符串符号数组的运算符进行运算结果存入s0中返回最终结果。n void count(); /调用函数 计算正确算术式的值n void main(); /主函数4. 源程序设计#include #include /*库文件包含*/#include /*用于字符串操作*/#include /*用于exit函数*/ char * KeyWord45=auto,break,case,char,const,continue, default,do,double,else,enum,extern, float,for,goto,if,int,long,return, short,signed,sizeof,static,struct,switch, typedef,unsigned,void,while,catch,class, const_cast,delete,friend,inline,new,operator, private,protected,public,template,this, throw,try,virtual; int i=0,j=0,k=0,t=0;/搜索指示器 char ch;/存放最新读入的原程序字符 char strToken20;/存放构成单词符号的字符串 char * chr_form100;/字符表 char * int_form100;/常数表 char form1000; int q=0; int temp; void GetChar()/将下一个字符读入ch中,搜索指示器前移一字符位 ch=formk; k+; void GetBC() /检查ch中的字符是否为空白,若是则调用Getchar直至ch中进入 /一个非空白字符 while(ch= ) /k-; GetChar(); void Concat()/将ch中的字符连接到strToken之后, strTokeni=ch; i+; bool IsLetter()/判断ch中的字符是否为字符 if(ch=a)|(ch=A) return (1); else return(0); bool IsDigit()/判断ch中的字符是否为数字 /k-; if(ch)=0) return (1); else return (0); int Reserve()/对strToken中的字符串查找保留字表,若它是一个保留字 /则返回它的编码,否则返回-1值 for(int q=0;q45;q+) if (strcmp(KeyWordq,strToken)=0) return q; if(q=44) return -1; void Retract()/将搜索指示器回调一个字符位置,将ch置为空白字符 k-; ch=NULL; char*InsertId()/将strToken中的标识符插入符号表,返回符号表的指针 chr_formj=strToken; j+; return chr_form0; char * InsertConst()/将strToken中的常数插入常数表,返回常数表指针 int_formt=strToken; t+; return int_form0; int code; / void analyze() GetChar(); GetBC(); if(IsLetter() while(IsLetter()|IsDigit() Concat(); GetChar(); Retract(); code=Reserve(); switch(code) case -1:cout字符串, strTokenendl;break; default:cout关键字, strTokenendl; else if(IsDigit() while(IsDigit()|ch=.) Concat(); GetChar(); Retract(); cout常数,strTokenendl; else switch (ch) case =: case /: case %: case *: cout运算符，chendl;break; case -: GetChar(); if(ch=-) cout运算符，-endl;break; else Retract(); cout运算符，-endl;break; case +: GetChar(); if(ch=+) cout运算符，+endl;break; else Retract(); cout运算符，+endl;break; case |: GetChar(); if(ch=|) cout运算符，|endl;break; else Retract(); cout非法符号，|endl;break; case &: GetChar(); if(ch=&) cout运算符，&endl;break; case (: case ;: case ): case : case: case: case : case: case : case ,: case : cout界符， chendl;break; case : GetChar(); if(ch=) cout运算符，endl;break; else cout界符， : GetChar(); if(ch=) cout运算符，endl;break; else Retract(); cout界符， endl;break; while(kq) for(int p=0;p=0 & *c=9) | *c=+ | *c=- | *c=* | *c=/ | *c=. | *c=( | *c=) ) return 1; else printf(输入错误，不是合法的算术表达式!n); return 0; if(*c=() k+; else if(*c=) k-; c+; if(k!=0) printf(输入错误没有正确使用 ()!n); return 0; return 1;/*void move(char *f, double *s,int p) 输入参数： char *f : 运算符数组 double *s: 数值数组 int p: 当前运算符数组位置。返回参数: 无功能： 将当前已经完成运算的运算符消去，同时将数值数组的位置调整以进行下一次运算。 传入值p若为3 则当前符号的数组位置为3. f3=f3+1.flen-2=flen-1 flen-1=0; si=si+1.slen-1=slen 因为数值比运算符多一个。*/void move(char *f, double *s,int p) int i=0,len=strlen(f); for(i=p; ilen; i+) /*将已经运算过的符号，空出来的位置用后面的符号来填充，*/ /*即把乘和除号的位置用后面的加和减号填充*/ fi=fi+1; si=si+1; si=si+1; flen-1=0;/*double convnum(char *c)输入参数： char *c :由数字和小数点组成的字符，用以转换成double型的数值。返回参数： num:返回转换好的值。功能： 将输入的字符串先将其小数点以前的部分复制到temp数组中， 若有小数点，则将小数点之后的数值，也就是小数部分先进行计算,值存入num中 计算完成后，再对整数部分进行计算，值加上小数部分的值，存入num中。*/double convnum(char *c) double num=0.0; double a=1.0; int i=0,p=0,len=0; char temp100; int tempi=0; int start=0; int f=1; /*正负符号指示器，若为1则为正数，为1，此数为负数*/ len=strlen(temp); if(c0=-) start=1; f=-1; for(i=start; ilen; i+) if(ci=.) p=i; break; temptempi+=ci; /*将整数部分复制到temp中*/ temptempi=0; if(p!=0) for(i=p+1;i=0; i-) num=num+(a*(tempi-48); a*=10; num=num*f; return num;/*double good(char *c)输入参数： char *c :即将进行运算的字符串型数学表达式。如3.5+(2*3/5)返回参数： s0:计算结果将放入s0中功能： 将输入的字符串中的数字分别调用convnum(char *c)函数进行数值变换，再将其依次存入doulbe si中，将加减乘除运算符依次存入字符串符号数组 char fi中， 然后如果遇到括号，则将括号内的字符串存入另一字符数组中，然后用此 good(char *c) 递归函数进行递归运算。 然后根据先乘除，后加减的顺序对已 存入数组的数值根 据存入字符串符号数组的运算符进行运算。结果存入s0中。 返回最终结果。*/double good(char *c) /*可递归函数*/ /*取得数值字符串，并调用convnum转换成double*/ char g100,number30; /*g,保存当前的表达式串,number保存一个数的所有字符*/ char f80; /*保存所有的符号的堆栈*/ int fi=0; /*保存符号的位置指针*/ double s80; /*保存当前所有的数的一个堆栈*/ int si=0; /*保存数字位置指针*/ int k=0; /* 若k=1则表示有一对括号*/ int num=0,i=0; /*num保存新括号内的字符数,i 保存number里的字符位置*/ int cc=0; /*乘除符号数量*/ int jj=0; /*加减符号数量*/ while(*c!=0)/*当p=1 和k=0时，表示已经把括号里的内容全部复制到g100中了*/ k=0; num=0; switch(*c) case +: /*当前字符为+-乘除时则表示*/ case -: case *: case/: ffi+=*c; if(*c=* | *c=/) cc+; else jj+; if(*(c-1)!=) numberi=0; i=0;/*完成一个数字的复制，其位置指针i=0*/ ssi+=convnum(number); break; case(: /*有括号，则将当前括号作用范围内的全部字符保存，作为*/ k+; /*一个新的字符表达式进行递归调用good函数计算。*/ while(k0) c+; gnum=*c; num+; if(*c=) k-; else if(*c=() k+; gnum-1=0; num=0;/*完成一个括号内容的复制，其位置指针num=0*/ ssi+=good(g); break; default: numberi+=*c; if(*(c+1)=0) numberi=0; ssi+=convnum(number); break; c+; ffi=0; i=0; while(cc0) switch(fi) case *: cc-; si+1=si*si+1; move(f,s,i); break; case /: cc-; si+1=si/(float)si+1; move(f,s,i); break; default: i+; break; i=0; while(jj0) switch(fi) case +: si+1=si+si+1; jj-; move(f,s,i); break; case -: si+1=si-si+1; jj-; move(f,s,i); break; default: printf(operator error!); break; return s0;/void count() char str1000; double sum=0; int p=1; while(1) scanf(%s,str); p=strcmp(str,exit); if(p=0) break; p=check(str); if(p=0) continue; sum=good(str); printf(%s=%f,str,sum); printf(n); strcpy(form,str); analyze(); printf(赋值符,=n); cout结果,sumendl; printf(n); / void main() int p=1; cout请输入一段程序，以#号结束：endl; printf(输入 exit 退出程序!)nn); form0=cin.get(); for(q=1;formq-1!=#;q+) formq=cin.get(); if(formq=#) cout你输入的程序段为:t; cout.write(form,q); coutendl; analyze(); break; for(q=1;formq-1!=#;q+) formq=cin.get(); if(formq=0 & formq=9) |formq=+ | formq=- | formq=* | formq=/ | formq=. | formq=( | formq=) ) count(); coutendl; analyze(); break; printf(thank you,good bye!nnn); 六实验调试结果1. 调试工具Microsoft visual C+ 6.0软件2. 调试步骤（1）先打开Microsoft visual C+ 6.0软件新建一个工程，再新建一个c+文件。（2）打开新建的c+文件，将编写的程序写入。（3）写好程序之后先编译再组建。（4）最后查看结果，并且应用。3. 调试结果（1）验证#的结束功能（2） 输入一个算术式 （3）输入关键字 （4）输入字符串（5）有关界符的输入七设计中的问题及解决方法 在此次课程设计的实验中遇到了许多问题，但经过自己的查阅资料，并向指导老师请教后，知道了相关问题的解决方法，如：1. 经过自己努力查阅相关资料，发现找到的相关词法分析器只能实现字符串的分析功能而对算术式不能计算最终结果，后通过老师指导自己修改编写实现计算功能相关函数，具体通过调用count函数实现计算器与词法分析器之间的统一，完成了分析和计算功能。2. 由于对Microsoft visual C+ 6.0应用软件以及C+语言的不熟练，导致自己在调试过程中出现了一系列的错误，不过通过向同学请教和讨论以及查看相关书籍后，自己很快掌握了C+的基本语法规则以及熟练使用c+ 6.0的使用。3. 程序完成后，在最终调试运行的过程中发现有些功能还无法实现，比如， count函数无法调用，程序无法正确退出等，通过自己思考，发现main函数里无法正确的判断字符串是否为正确的算术表达式，加入if条件判断语句后解决此问题，对于程序无法退出的问题上加入对字符串 “exit”判断语句后，调用“break；“跳出，成功解决程序无法正确退出的问题。八设计心得通过此次进两周的计算机软件技术课程设计，不仅让我了解了什么是词法分析器以及它的一些具体功能，也让我通过查阅各种资料以及询问指导老师了解到如何设计、编制并调试词法分析程序，经过反复几次对程序的修改和调试，是我从中学习到了很多以前不知道的新知识，加深对词法分析原理的理解；熟悉了构造词法分析程序的手工方式的相关原理，使用某种高级语言直接编写此法分析程序。另外，也让我重新熟悉了VC6.0的相关内容，加深了对VC6.0语言的用途的理解。总的来说通过此次课程设计，主要有以下几个方面的收获：一、对实验原理有更深的理解；二、对词法分析在实践中的应用有深刻的理解，在实践的基础上，把所学过的知识应用于实际应用，更深刻的理解了词法分析以及编译原理的实际应用。三、通过本次的课程设计，激发了我学习的积极性，培养了我独立发现问题，分析问题，解决问题的能力，更增强了我与同学之间的交流沟通和共同解决问题的合作能力。四、理解了词法分析器的编译原理，懂得了设计的程序的构架不仅要合理，并要有一定的可扩展性，而具体功能的实现要灵活。此外，还将以前不怎么熟悉的VC+的基本知识应用于软件设计，加深了对VC+界面程序设计的理解，达到了学以致用的目的。现在回顾两个星期以前，当1个星期前的现在，当