实验一词法分析器的设计

实验一词法分析器的设计.............................................................................................................21.1词法分析器的结构和主要任务........................................................................................21.1.1输入输出接口.........................................................................................................21.1.2条件限制.................................................................................................................21.2词法分析程序的总体设计................................................................................................31.3词法分析程序的详细设计................................................................................................41.4实验步骤.............................................................................................................................51.5输入数据...........................................................................................................................151.6结果输出...........................................................................................................................15

实验一词法分析器的设计实验目的：掌握词法分析的概念，设计方法，熟悉高级语言中词法的定义，词法分析程序的编写。实验要求：在8学时内实现SAMPLE语言的词法分析器，要求用VC窗口界面实现。图1-1词法分析器的输入输出界面词法分析程序的主要任务是从左到右扫描每行源程序，拼成单词，换成统一的内部表示(token)输出，送给语法分析器。具体包括：1.组织源程序的输入；2.按规则拼单词，并转换成二元形式；3.滤掉空白符，跳过注释4.进行行列计数，用于指出出错的行列号，并复制出错部分；5.列表打印源程序；6.发现并定7.生成符token文件和符号表用语作法分析的输入部分。、换行符及一些无用的符号(如字符常数的引号)位词法错误；号表。1.1.2条件限制本实验(1)假定SAMPLE语言采用自由格式书写；(2)可以使用注解，用/*……*/或者{……}标识，但注解不能插结束，若一行结束，没有遇到注释后面的结束标记，自动认为注释也结束；(3)一行可以有多个语句，一个语句也可以分布在多行中，单词之间和语意空格，单词中间也不能有回车换行符，即单词不能跨行书写；(4)关键字都是保留字。可以作如下假定：在单词内部，注解要在一行内句之间可以插入任间不能有空白符号，单词中图1-2词法分析程序的顶层数据流图图1-3词法分析程序的详细数据流图在上面的数据流图中，各个加工处理完成的功能如下：加工1.1(读一行并打印)：收到读下一行命令后，从源程序读入一行，装入缓冲区，行计数，并打印。在这里需要注意的是，回车换行在源程序（文本文件）中用两个字符0D0AH来表示，而用高级语言（C语言）读入内存后，就用一个字符0AH来表示，这是在用高级语言编写词法分析器时常被忽略导致错误的原因加工1.2(读一非空字符)：收到读一字符命令后，从缓冲区读入一非空字符，列计数。若缓冲区已空，则再读—行，列计数置0。加工1.3(分类)：根据单词的首字符以决定对不同加工1.4(识别标识符)；当输入字母时，开始识别标识符或关键宇，边拼写读入下一符号，当读入一非字母数字符号时，标识符识别完成，但已多读入一个符号，所以列记数回退。然后查关键字表，判断拼出的符号串是否为关键字。若是关键字，输出其种别码。否则识别的单词就是标识符，同时输出标识符及其种别码。加工1.5(识别常数)：当输入数字时，开始识别整数或实数。边拼写。类单词的处理。边从缓冲区边读入下一符号，当遇到“.”时，还要继续拼写该常数(实数情况)。如果遇到E，要识别带指数的常数，当遇到其它非数字符号时，数字常数拼写完毕，列计数也要退1。输出常数及其种别码。加工1.6(处理注解)；当输入“／”时，开始识别注解或除号，若是注解时，最后两个连续读出的符号是“*／”，不需再读下一符号，列计数不变。当判定是除号“／”时，已多读入一字符，列计数-1，输出“／”的种别码。加工1.7(识别分界符)：识别其它界符，对于<、>、：、|、·等符号，还需要再读入下一符号，判别是否为双界符。若不是，列计数-1，输出单词的种别码。加工1.8(识别文字常数)：当输入引号时，引号忽略，开始拼写字符常数，不断拼读下一符号，搜索下一个引号，当读入第二个引号时，字符常数拼写结束。最后列计数不减1，然后输出该常数。以上加工1.4～1.8都需要从缓冲区A每次读出一个字符，进行列计数。由于假定每个单词不跨行，所以不用考虑从源程序中读出下一行到缓冲区的功能。加工1.9(输出TOKEN)：对各种界符与关键字输出其相应的二元式(TOKEN)，对常数与标识符则让它流入下一个加工。加工2(查填符号表)：如果是的类型栏中填有“字符标识符栏的类型栏空白)判断有无同名和同类型的入口。如果有同名入口P1，则把P1作为TOKEN的自身值同名，则将字符中存入字符串表中，把它的长度和在字符串表中的开始位置及其类型(标识符为空白)填入符号表的新入口P中，并把P作为TOKEN的自身值如下：先查符号表VAL栏，若发现相同的常数则直接输出其二元式。若表内无相同的常数，则将数字常数填入符号表内，在TYPE栏内填入整型或实型，然后输标识符或字符常数，首先查看名字栏和类型栏(字符常数常数”，填入它的二元式中；填入的二元式中。对数字常数的处理出其二元式。二元式中包含该常数在符号表中的入口。1.3词法分析程序的详细设计图1-3的数据流图属于输入-变换-输出形式的变换型数据流图，但加工1.3-1.9构成了典型的事务处理型数据流图。根据数据流图，可以得到词法分析程序的总体框架，如图1-4。

图1-4词法分析器的程序框架1.4实验步骤1.4.1步骤一编写词法分析的总控程序(1)编写词法分析的主函数scanner()词法分析的总控程序就是图1-4的程序框架。词法分析中要使用的函数将逐步在下面的三个实验中分别实现。要实现词法分析的功能，必须按照总控程序的安排，在适当的位置进行调用，当所有的函数都实现了，就构成了一个完整的词法分析程序。主函数的描述如下：a.打开输入源文件，设置行计数器为b.如果源文件没有结束，读入一行到string，行计数c.如果缓冲区非空，将缓冲区中的符号串分割为一个一个的单词，否则转0;+1，设置列计数器为0;b。(区分一个单词结束的方法是：从缓冲区读入一个非空字符，列计数+1，继续读入字符(每读入一个字符，列计数+1)，直到一个单词读完（单词结束的标志是单词分隔符，如空格符号、空白符号、换行符和界符等，但单词的分隔符不属于该单词，读入的符号串是否可以构成一个正确的单词，要根据单词的构成规则来判断，不同类别的单词其构词规则不一样，这样就可以根据不同类别的单词的识别函数来判断相应的单词构成是否有错误。单词的类别是根据读入的该单词的首字符来判断的，可以单独写一个分类函数，根据首字符判断该单词属于关键字、标识符、常数、运算符和界符中的哪一类）。d.将识别出来的单词e.根据单词的类进行不同的后期处理，如果是标识符或常数，需要将其唯一值填入符号表中。g.如果源文件已结束，关f.打印token字表和符号表到相应的文件中;(2)编写分类函数sort()及其种别码写入Token字表中。别，闭打开的源文件。单词分为标识符、常数、关键字、运算符和界符，单词必须分类进行识别。根据读入该单词的第一个字符进行分类，判断该单词是属于哪一类。如图1-4，根据单词的分类结果调用相应的识别函数识别一个单词是否正确。intsort(charch)/*传入参数ch为已读入的单词的第一个字符，据此进行分类*/{if(isdigit(ch))return常数;/*如果第一个字符是数字，则是数；*/elseif(isalpha(ch))return标识符;/*如果第一个字符是字母，则是标识符或关键字*/elseif(ch=='/')return注释;/*如果读入的是/，则可是’，则是字符则是界符*/能是注释和除号*/elseif(ch=='\'')return字符常数;/*如果第一个字符常数；*/elseif(isdelimeter(ch))return界符;/*如果出现了定义中的其它符号，elsereturnOTHER;/*否则出错处理，出现不识别的字符*/}(3)实验思考题1．为什么要编写分类函数，2．词法分析的功能是什么？你编写的词法分析程序完成了哪功些能？你认为还有哪些功能是应该实现而你没有实现的功能？3．词法分析程序能给出哪错些误？4．符5．词法分析器是如何定位错误的？在词法分析器中起什么作用？号表的作用是什么？

【步骤二定义符号表编写查找和插入函数】(1)定义关键字和界符表每一种已经定义的语言的关键字和界符都是固定的，为了给出单词的种别码，我们在编写SAMPLE语言的词法分析器时采取关键字和界符一符一种，标识符、整型常数、实型常数、字符型常数分别给一个种别码，再根据其值定义判断。Sample语言中的单词(关键字、界符、数的类型)的种别码如表1-1。表1-1SAMPLE语言单词的编码类单类类单词种别码单词种别码种别码别别notandor别词program12212223242526272829303132;,3940414243444546474849varintegerbool3‘4+“real5-//界/*charconstbegin6运*算/符*/78<符;().关if键9>then字101112<=>==elsewhile标识id符34do13:=33repeat141516整常数35实常数36untilfor常数字符常数37to17布尔常数38在C/C++语言中，这些表格可以使用结构数组定义，在pascal中可以使用记录数组定义，也可以使用其它方法来定义，如直接定义成链表的形式，可根据所设计的总体结构自行选择定义方法，具体内容可以根据程序编写的方式采取初值输入方式或后期使用时再输入的方式。上述表格可以定义成一个整体，也可以分成关键字、界符和各种常数表等多个部分分别定义。如在C语言中定义关键字如下：structentry{/*定义结构*/charword[10];/*单词本身*/inttoken;/*token值*/};structentrykeyword[]={"and",1,"array",2,"begin",3,"bool",4,"call",5,"case",6,"char",7,"do",9,"else",10};/*存放该语言能识别的关键字*/(2)编写查找函数iskeyword(char*str)和isdelimeter(char*str)判断给定的符号串是否是关键字和界符iskeyword(char*str)函数的功能是：在上述给定的关键字表中查找指定的字符串str是否存在，若存在，返回其种别码(token值)，否则返回0。查找函数可以使用顺序查找，也可以使用折半查找。例如：使用顺序查找方法查找给定单词key是否是关键字的函数原型和算法描述如下：intiskeyword(char*str)/*设keyword为所有关键字列表*//*该函数返回0表示str不是关键字，不为0表示str是关键字*/{while(关键字表没有结束)if(str=keyword[i].word)返回keyword.token;/*表示str是关键字*/elsei++；返回0;/*表示str不是关键字*/}同样编写查找是否是界符的函数isdelimeter()。(3)定义符号表编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息。这些信息通常记录在符号表中。符号表中的每一项一般包含两部分：名字，与此名字有关的信息，如类型，种属，值等。符号表主要在词法或语法分析阶段生成，可能用于语义检查、产生中间代码以及最终目标代码等不同阶段。当从源程序中识别出一个标识符或常数，就要检查符号表中是否已经存在该标识符或常数，若不存在，就应将其加入符号表，若存在就不加入。符号表可以和常数表合在一起，这可能增加查填符号表的复杂性。也可以将符号表、常数表分开建立，方便查填。定义SAMPLE语言的符号表的格式如下表，其中name项包含两个内容，一个是单词本身，一个是它的长度。可以直接将单词放在名字栏，也可以另外使用一个字符串数组，将单词本身放在字符串中，在符号表中填入该单词在字符串中的指针。NAMETOKENTYPEKINDVALADDRexample734整简变符号表可以使用结构数组来实现，也可以使用链表来实现。(4)编写查找符号表的函数isexist_sym（char*str），查找指定的字符串是否已在符号表中当识别出的单词是字符常数、实常数、整型常数或标识符时，就应该查找该字符串是否在符号表中已存在，如果不存在，就需将它加入符号表中。查找方法可以是顺序查找或折半查找，这取决于符号表的组织方式。如果符号表按照单词在文件中出现的先后顺序放入符号表中，只能采取顺序查找，如果单词在放入符号表中按照单词的大小顺序排列，可以使用折方法。方法查找sym是否存在于符号表symbol中的函数描述如下：intisexist_sym(char*str)/*假定symbol数组是符号表半查找使用顺序查找*/{while（符号表没有结束）if(str＝symbol[i].name)返回i;/*表示已查到*/否则返回0;/*表示没有查找到*/}(5)编写填入符号表的函数ins_sym(char*str,inttoken)若上述第(4)步中查找某字符串str不在符号表中，就将给定的字符串填入符号表。填入方尾部，也可以采用排序的法可以采用顺序增加序号的方法加入到表的方法将其按顺序填入某个位置，采取什么方式将直接影响查找方法。将字符串sym填入符号表symbol的函数描述如下：ins_sym(char*str,inttoken)/*将字符串str插入符号表symbol中*/{找到符号表的最后一条记录;symbol[i].name=str;symbol[i].token=token;设置symbol[i]的其它属性;}(6)编写将符号表的内容写到文件中的函数write_sym在多遍扫生成的符号表需要在下一个阶段中再使用，因此在词法分析运行完毕，应该将符号表的语义分析阶段再次读入，或者将符号表的内容显示在屏幕上。将符号表的描的编译程序中，词法分析作为单独的一遍扫描。内容写入文件中，以便在语法或内容写入文件的方式是在按符号表中现有内容的顺序，逐行打印。函数描述如下：write_sym()/*将符号表symbol中的内容写入文件*/{打开输出的符号表sym_file文件，用while(表没有结束fprintf(fp,“%s%d”,symbol[i].name,symbol[i].token);fp指向；){/*可以将符号表一行中的名字，类型，种属，值等写入文件*/i++;}关闭符号表文件；}(7)定义一个token字表当使用多遍扫描方式编写编译程序时，词法分析后必须生成一个单词表，格式如下，每当从源文件中识别出一个单词，不管是关键字、标识符、常数或界符，找到其种别码后，都应将它填入token字表（token_table）中。word（单词本身）token（单词的种别）同样可以使用结构数组或链表定义。(8)编写一个向token字表中填入内容的函数ins_token(char*str,inttoken)每当从源文件中识别出一个单词，找到其种别码后，按顺序填入到token字表中。填入函数描述类似于符号表的填入，只是只能采用顺序填入，每次填入时总是填入表的尾部。ins_token(char*str,inttoken)/*将str放入到token_table中*/{token_table[lastline].word=str;token_table[lastline].token=token;lastline=lastline+1;/*lastline表示生成的当前单词序号*//*可以使用全局变量来记录*/}(9)编写一个函数，将token字表的内容写到文件中的函数write_token词法分析的结果就是生成token_table表输出原型及算法描述如下：相应的token文件，它将作为语法分析的输入。因此，必须将上述的到文件中。函数write_token(){打开输出的token文件，用fp指向；while（表没有结束）{fprintf(fp,”%s%d”,token_table[i].word,token_table[i].token);i++;}}关闭token文件；(10)实验思考题1．查找给定的字符串是否在关键字表中有哪些方法？并说明其优缺点？2．你是如何比较一个字符串是否是关键字的？3．关键字表必须定义为结构数组吗？还可以如何定义？4．符号表的作用是什么，如何定义符号表，对符号表有哪些基本操作？5．Token文件的作用是什么，需要包含哪些信息？6．符号表和token文件中的内容有哪些相同和不同点？【步骤三单词识别函数的编写】(1)编写识别标识符的函数recog_id(charch)若第一个字符是字母，从缓冲区的当前位置开始读入字符，读到不是字母或数字的符号为止，识别它是否是一个标识符(或关键字)。识别方法可以使用状态转换图，也可以使用正规式技术，还可以用其它方式自己编写。通过识别，若不能构成标识符，提示出错信息；若是，再利用实验二的结果查找该字符串是否是关键字，若是关键字，返回关键字的种别码；若不是关键字，返回标识符的种别码。对于识别较为复杂的标识符的模块，可以先画出该单词的状态转换图或语法图，然后再根据状态图给出模块详细说明，标识符的状态转换图如下：图中0表示初态，双圈表示的状态是终态。当有引出“其它”字样的弧，表示读入了一个除该状态所有别的弧上的符号外，另外一个在字符集内的符号。有时可能需要回退该符号。下面是从一个字符串中识别一个标识符的算法描述：recogid(charch)/*ch为给定字符串的第一个字符*/{charstate='0';while(state!=2){switch(state){case'0':/*若当前是0状态，若读入一个字母，转向1状态*/if(isalpha(ch))state='1';elseerror();break;case'1':/*若当前是1状态，若读入字母或数字，仍为1状态*/if(isalnum(ch)&&(i<8))state='1';else{state=2;colno--;/*退回当前读入的字符*/}}ch=string[colno++];/*将下一个符号读入ch中*/}}(2)编写识别数的函数recogdig(charch)对给定的字符串(不含空白)，识别它是否是数，若不是，提示出错信息；若是，识别是整相应代码和字符串本身。实常数的状态转换图：数、小数、或是指数，分别返回数分为多种，下面是识别不带正负号，带指数的其它根据这个状态转换图可以编写识别实常数的识别函数。算法描述如下：intrecogdig(charch)/*识别常数（含整数和实数）*/{charstate='0';/*初始状态为0*/while(state!=7){switch(state){case'0':if(isdigit(ch))state='1';elseerror();break;/*读入一个数字case'1':if(isdigit(ch))state='1';/*仍然读入数字elseif(ch=='.')state='2';/*读入elseif((ch=='e')||(ch=='E'))state='4';/*读入else{/*已识别*/*/小数点，识别实数*/e或E，带指数*/完整数，返回*/colno--;返回整数类型;}break;case'2':if(isdigit(ch))state='3';/*读入数字*/elseerror();break;case'3':if(isdigit(ch))state='3';/*读入数字elseif((ch=='E')||(ch=='e'))state='4';/*读入e或E，指数else{/*已识别完带小数的实数，返回*/*/*/colno--;返回实数类型;}break;case'4':if(isdigit(ch))state='6';/*读入数字*/elseif(issign(ch))state='5';/*读入+，-符号*/elseerror();break;case'5':if(isdigit(ch))state='6';/*读入数字*/elseerror();break;case'6':if(isdigit(ch))state='6';/*读入数字*/else{/*已识别完带指数的实数，返回*/colno--;state=7;返回实数类型;}}ch=str[colno++];/*读入下一个符号*/}}(3)编写识别界符的函数recogdel对给定首字符的字符串(不含空白)，识别它是否是界符(单界符和双界符)，若不是，提示出错信息；若是，识别是单界符和双界符，分别返回单界符和双界符相应的代码和字符串本身。类似于查找是否是关键字，该函数从界符表中查找某字符串是否存在即可。函数可以参照前面的(1)进行编写。(4)编写识别字符常数的函数recogstr对给定首字符(‘)的字符串(不含空白)，识别它是否是字符常数，若不是，提示出错信息；若是，去掉两边的单引号，返回剩下的字符串和字符常数的代码。字符常数的状态转换图如下，从读入的第一个符号’开始表明是字符常数：函数描述如下：intrecogstr(charch)/*进入此函数时，ch为单引号*/{charstate='0';/*初始状态*/while(state!=2){switch(state){case'0':state='1';break;/*由于进入此函数时，ch为单引号，*/一个单引号，结束*/所以不需再读入case'1':if(ch=='\'')returncolno;/*读到最后的elsestate='1';/*否则一直是常数部分*/}ch=string[colno++];/*读取下一个符号*/}}(5)编写识别并去掉注释的函数handlecom带注释的字符串是以/*开始，*/结束的字符串，若是这种形状，去掉它，识别的状态转换图如下：函数描述如下：handlecom(charch,inttoken)/*ch为首先读入的/符号，token为返回值*/{读入一个符号；if(该符号为*){do{读入一个符号放入ch1