编译原理词法分析报告

1、实验一：词法分析 一、实验目的： 1、通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。2、编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本关键字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示） 二、实验预习提示 1、 词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一

2、类符号一种别码的方式。2、 单词的BNF表示<标识符>-> <字母><字母数字串><字母数字串>-><字母><字母数字串>|<数字><字母数字串>|<下划线><字母数字串>|<无符号整数>-> <数字><数字串><数字串>-> <数字><数字串> |<加法运算符>-> +<减法运算符>->-<大于关系运算符>->><

3、大于等于关系运算符>-> >=3、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a>+”,当前字符为>，此时，分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符+，这时可知应将>解释为大于运算符。但此时，超前读了一个字符+，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4、模块结构三、实验过程和指导： （一）准备： 1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步

4、编制好程序。3.准备好多组测试数据。（二）程序要求：程序输入/输出示例：如源程序为C语言。输入如下一段：main()                                        &#

5、160;                                int a,b;a = 10; b = a + 20;要求输出如右图。（2，”main”）（5，”（“）（5，”）“）（5，”“）（1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;”）（2，”a”）

6、（4，”=”）（3，”10”）（5，”;”）（2，”b”）（4，”=”）（2，”a”）（4，”+”）（3，”20”）（5，”;”）（5，”“）要求：识别保留字：if、int、for、while、do、return、break、continue；单词种别码为1。其他的都识别为标识符；单词种别码为2。常数为无符号整形数；单词种别码为3。运算符包括：+、*、/、=、>、<、>=、<=、!= ；单词种别码为4。分隔符包括：,、;、(、)； 单词种别码为5。以上为参考，具体可自行增删。（四）程序思路（仅供参考）：这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法

7、分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将源程序全部输入到字符缓冲区中。2.取单词前：去掉多余空白。3.取单词后：去掉多余空白（可选）。4.取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）5.显示

8、结果。（五）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 四、实验原理词法分析是编译过程的第一阶段。它的任务就是对输入的字符串形式的源程序按顺序进行扫描，根据源程序的词法规则识别具有独立意义的单词（符号），并输出与其等价的Token序列。有限自动机是描述程序设计语言单词构成的工具，而状态转换图是有限自动机的比较直观的描述方法。我们使用确定的有限状态自动机，简记为DFA。根据语言的词法规则构造出识别其单词

9、的确定有限自动机DFA, 仅仅是词法分析程序的一个形式模型，距离词法分析程序的真正实现还有一定的距离。状态转换图的实现通常有两种方法，一种是用状态转换表T；另一种是直接转向法。状态转换表法又称数据中心法，是把状态转换图看作一种数据结构（状态转换表），由控制程序控制字符在其上运行，从而完成词法分析。用转换表的优点是程序短，但占存储空间多，直接转向法的优缺点正好与此相反。直接转向法又称程序中心法，是把状态转换图看成一个流程图，从状态转换图的初态开始，对它的每一个状态结点都编一段相应的程序。基本实验步骤-构造识别单词的自动机：1.根据构成规则对程序语言的单词按类构造出相应的状态转换图。2. 对各类单

10、词的状态转换图合并，构成一个能识别语言所有单词的状态转换图。合并步骤为：(1) 将各类单词的状态转换图的初始状态合并为一个唯一的初态；(2) 化简调整状态冲突和对冲突状态重新编号；(3) 如有必要，增加出错状态。五、分析及设计过程1、总体分析：词法分析器的输入输出界面词法分析程序的主要任务是从左到右扫描每行源程序，拼成单词，换成统一的内部表示(token)输出，送给语法分析器。具体包括：组织源程序的输入；按规则拼单词，并转换成二元形式；滤掉空白符，跳过注释、换行符及一些无用的符号(如字符常数的引号)进行行列计数，用于指出出错的行列号，并复制出错部分；列表打印源程序；发现并定位词法错误；生成符号

11、表。token 文件和符号表用作语法分析的输入部分。2、条件分析：本实验可以作如下假定：(1)可以使用注解，用/*/标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到注释后面的结束标记，自动认为注释也结束；(2) 一行可以有多个语句，一个语句也可以分布在多行中，单词之间和语句之间可以插入任意空格，单词中间不能有空白符号，单词中间也不能有回车换行符，即单词不能跨行书写；(3) 关键字都是保留字。3、词法分析程序的总体设计词法分析程序的顶层数据流图词法分析程序的顶层数据流图，即是词法分析程序的输入输出界面图，由此可以看出词法分析程序的功能就是从源程序中读入一个个字符，依据一定的

12、构词规则，识别出各类有用的单词。其中源程序清单和错误信息从屏幕、打印机或文件输出，其余文件均以顺序文件的形式输出到外存储器上，以供下一阶段使用。由此可以得到更详细的数据流图。词法分析程序的详细数据流图在上面的数据流图中，各个加工处理完成的功能如下：加工1.1(读一行并打印)：收到读下一行命令后，从源程序读入一行，装入缓冲区，行计数，并打印。在这里需要注意的是，回车换行在源程序（文本文件）中用两个字符0D0AH来表示，而用高级语言（C 语言）读入内存后，就用一个字符0AH 来表示，这是在用高级语言编写词法分析器时常被忽略导致错误的原因。加工1.2(读一非空字符)：收到读一字符命令后，从缓冲区读人

13、一非空字符，列计数。若缓冲区已空，则再读行，列计数置0。加工1.3(分类)：根据单词的首字符以决定对不同类单词的处理。加工1.4(识别标识符)；当输入字母时，开始识别标识符或关键宇，边拼写边从缓冲区读入下一符号，当读入一非字母数字符号时，标识符识别完成，但已多读入一个符号，所以列记数回退。然后查关键字表，判断拼出的符号串是否为关键字。若是关键字，输出其种别码。否则识别的单词就是标识符，同时输出标识符及其种别码。加工1.5(识别常数)：当输入数字时，开始识别整数或实数。边拼写边读入下一符号，当遇到“.”时，还要继续拼写该常数(实数情况)。如果遇到E，要识别带指数的常数，当遇到其它非数字符号时，数

14、字常数拼写完毕，列计数也要退1。输出常数及其种别码。加工1.6(处理注解)；当输入“”时，开始识别注解或除号，若是注解时，最后两个连续读出的符号是“*”，不需再读下一符号，列计数不变。当判定是除号“”时，已多读入一字符，列计数1，输出“”的种别码。加工1.7(识别分界符)：识别其它界符，对于<、>、：、|、·等符号，还需要再读入下一符号，判别是否为双界符。若不是，列计数1，输出单词的种别码。加工1.8(识别文字常数)：当输入引号时，引号忽略，开始拼写字符常数，不断拼读下一符号，搜索下一个引号，当读入第二个引号时，字符常数拼写结束。最后列计数不减1，然后输出该常数。以上加工

15、1.41.8 都需要从缓冲区A 每次读出一个字符，进行列计数。由于假定每个单词不跨行，所以不用考虑从源程序中读出下一行到缓冲区的功能。加工1.9(输出TOKEN)：对各种界符与关键字输出其相应的二元式(TOKEN)，对常数与标识符则让它流入下一个加工。加工2(查填符号表)：如果是标识符或字符常数，首先查看名字栏和类型栏(字符常数的类型栏中填有“字符常数”，标识符栏的类型栏空白)判断有无同名和同类型的入口。如果有同名入口P1，则把P1 作为TOKEN 的自身值填入它的二元式中；如果不同名，则将字符中存入字符串表中，把它的长度和在字符串表中的开始位置及其类型(标识符为空白)填入符号表的新入口P 中

16、，并把P 作为TOKEN 的自身值填入的二元式中。对数字常数的处理如下：先查符号表VAL 栏，若发现相同的常数则直接输出其二元式。若表内无相同的常数，则将数字常数填入符号表内，在TYPE 栏内填入整型或实型，然后输出其二元式。二元式中包含该常数在符号表中的入口。4、 词法分析程序的详细设计数据流图属于输入-变换-输出形式的变换型数据流图，但加工1.31.9 构成了典型的事务处理型数据流图。根据数据流图，可以得到词法分析程序的总体框架。词法分析器的程序框架5、 实验步骤步骤一 编写词法分析的总控程序(1) 编写词法分析的主函数scanner()词法分析的总控程序就是词法分析器的程序框架。词法分析

17、中要使用的函数将逐步在下面的三个实验中分别实现。要实现词法分析的功能，必须按照总控程序的安排，在适当的位置进行调用，当所有的函数都实现了，就构成了一个完整的词法分析程序。主函数的描述如下：a.打开输入源文件，设置行计数器为0;b.如果源文件没有结束，读入一行到string，行计数+1，设置列计数器为0;c.如果缓冲区非空，将缓冲区中的符号串分割为一个一个的单词，否则转b。(区分一个单词结束的方法是：从缓冲区读入一个非空字符，列计数+1，继续读入字符(每读入一个字符，列计数+1)，直到一个单词读完（单词结束的标志是单词分隔符，如空格符号、空白符号、换行符和界符等，但单词的分隔符不属于该单词，读入

18、的符号串是否可以构成一个正确的单词，要根据单词的构成规则来判断，不同类别的单词其构词规则不一样，这样就可以根据不同类别的单词的的识别函数来判断相应的单词构成是否有错误。单词的类别是根据读入的该单词的首字符来判断的，可以单独写一个分类函数，根据首字符判断该单词属于关键字、标识符、常数、运算符和界符中的哪一类）。d.将识别出来的单词及其种别码写入Token 字表中。e.根据单词的类别，进行不同的后期处理，如果是标识符或常数，需要将其唯一值填入符号表中。g.如果源文件已结束，关闭打开的源文件。f.打印token 字表和符号表到相应的文件中;(2) 编写分类函数sort()单词分为标识符、常数、关键字

19、、运算符和界符，单词必须分类进行识别。根据读入该单词的第一个字符进行分类，判断该单词是属于哪一类。根据单词的分类结果调用相应的识别函数识别一个单词是否正确。int sort(char ch)/* 传入参数ch 为已读入的单词的第一个字符，据此进行分类*/if ( isdigit(ch) ) return 常数;/*如果第一个字符是数字，则是数；*/else if (isalpha(ch) return 标识符;/*如果第一个字符是字母，则是标识符或关键字*/else if (ch = '/') return 注释; /*如果读入的是/，则可能是注释和除号*/else if (c

20、h =''') return 字符常数; 如果第一个字符是，则是字符常数；else if (isdelimeter(ch) return 界符; /*如果出现了定义中的其它符号，则是界符*/else return OTHER; /*否则出错处理，出现不识别的字符*/步骤二 定义符号表 编写查找和插入函数(1) 定义关键字和界符表每一种已经定义的语言的关键字和界符都是固定的，为了给出单词的种别码，我们在编写SAMPLE 语言的词法分析器时采取关键字和界符一符一种，标识符、整型常数、实型常数、字符型常数分别给一个种别码，再根据其值定义判断。struct entry /*定义

21、结构*/char word10; /* 单词本身 */int token; /* token 值 */;struct entry keywords22="main",1,"int",1,"char",1,"bool",1,"if",1,"then",1,"else",1,"while",1,"do",1,"for",1,"to",1,"when",1,&qu

22、ot;return",1,"printf",1,"float",1,"function",1,"not",1,"and",1,"or",1,"dim",1,"stop",1,"end",1 ; /*存放该语言能识别的关键字*/struct entry interpunctions27="+",3,"-",3,"*",3,"/",

23、3,"<",3,">",3,"<=",3,">=",3,"=",3,"=",3,"Intconst",4,"fconst",6,"Sconst",5,"bconst",8,"",2,",",2,"'",2,""",7,"/",7,"/*"

24、,7,"*/",7,"(",2,")",2,".",2,"",2,"",2;类型单词种别码关键字main, int, char, bool, if, then, else, while, do, for, to, when, return, printf, float, function, not, and, or, dim, stop, end1分隔符( ) . ， ； 2运算符+ - * / < > <= >= = =3整数Intconst4字符串

25、Sconst5浮点数fconst6布尔数bconst8界符和注释符 / /* */7在C/C+语言中，使用结构数组定义，在pascal 中可以使用记录数组定义，也可以使用其它方法来定义，如直接定义成链表的形式，可根据所设计的总体结构自行选择定义方法，具体内容可以根据程序编写的方式采取初值输入方式或后期使用时再输入的方式。上述结构数组可以定义成一个整体，也可以分成关键字、界符和各种常数表等多个部分分别定义。(2) 编写查找函数iskeyword(char * str)和isdelimeter(char * str)判断给定的符号串是否是关键字和界符iskeyword(char * str)函数的

26、功能是：在上述给定的关键字表中查找指定的字符串str 是否存在，若存在，返回其种别码(token 值)，否则返回0。查找函数可以使用顺序查找，也可以使用折半查找。例如：使用顺序查找方法查找给定单词key 是否是关键字的函数原型和算法描述如下：int iskeyword (char * str)/*设keyword 为所有关键字列表*/*该函数返回0 表示str 不是关键字，不为0 表示str 是关键字*/while (关键字表没有结束)if (str = keywordi.word )返回keyword.token; /* 表示str 是关键字 */else i+；返回0; /* 表示str

27、不是关键字 */同样编写查找是否是界符的函数isdelimeter()。(3) 定义符号表编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息。这些信息通常记录在符号表中。符号表中的每一项一般包含两部分：名字，与此名字有关的信息，如类型，种属，值等。符号表主要在词法或语法分析阶段生成，可能用于语义检查、产生中间代码以及最终生成目标代码等不同阶段。当从源程序中识别出一个标识符或常数，就要检查符号表中是否已经存在该标识符或常数，若不存在，就应将其加入符号表，若存在就不加入。符号表可以和常数表合在一起，这可能增加查填符号表的复杂性。也可以将符号表、常数表分开建立，方便

28、查填。定义SAMPLE 语言的符号表的格式含name 项包含两个内容，一个是单词本身，一个是它的长度。可以直接将单词放在名字栏，也可以另外使用一个字符串数组，将单词本身放在字符串中，在符号表中填入该单词在字符串中的指针。符号表可以使用结构数组来实现，也可以使用链表来实现。(4) 编写查找符号表的函数isexist_sym（char *str），查找指定的字符串是否已在符号表中当识别出的单词是字符常数、实常数、整型常数或标识符时，就应该查找该字符串是否在符号表中已存在，如果不存在，就需将它加入符号表中。查找方法可以是顺序查找或折半查找，这取决于符号表的组织方式。如果符号表按照单词在文件中出现的先

29、后顺序放入符号表中，只能采取顺序查找，如果单词在放入符号表中按照单词的大小顺序排列，可以使用折半查找方法。使用顺序查找方法查找sym 是否存在与符号表symbol 中的函数描述如下：int isexist_sym(char *str) /* 假定symbol 数组是符号表*/while （符号表没有结束）if (str ) 返回i; /*表示已查到*/否则返回0; /*表示没有查找到*/(5) 编写填入符号表的函数ins_sym(char *str, int token)若上述第(4)步中查找某字符串str 不在符号表中，就将给定的字符串填入符号表。填入方法可以采用顺序

30、增加序号的方法加入到表的尾部，也可以采用排序的方法将其按顺序填入某个位置，采取什么方式将直接影响查找方法。将字符串sym 填入符号表symbol 的函数描述如下：ins_sym(char *str, int token) /*将字符串str 插入符号表symbol 中*/找到符号表的最后一条记录; = str;symboli.token = token;设置symboli的其它属性;(6) 编写将符号表的内容写到文件中的函数write_sym在多遍扫描的编译程序中，词法分析作为单独的一遍扫描。生成的符号表需要在下一个阶段中再使用，因此在词法分析运行完毕，应该将符号表的内

31、容写入文件中，以便在语法或语义分析阶段再次读入，或者将符号表的内容显示在屏幕上。将符号表的内容写入文件的方式是在按符号表中现有内容的顺序，逐行打印。函数描述如下：write_sym() /* 将符号表symbol 中的内容写入文件*/打开输出的符号表sym_file 文件，用fp 指向；while (表没有结束) fprintf (fp, “%d %s ”, symboli.token, );/*可以将符号表一行中的名字，类型，种属，值等写入文件*/i+;关闭符号表文件；(7) 定义一个token 字表当使用多遍扫描方式编写编译程序时，词法分析后必须生成一个单词表，格式

32、如下，每当从源文件中识别出一个单词，不管是关键字、标识符、常数或界符，找到其种别码后，都应将它填入token 字表（token_table）中。token（单词的种别）word（单词本身）同样可以使用结构数组或链表定义。(8) 编写一个向token 字表中填入内容的函数ins_token(char *str, int token)每当从源文件中识别出一个单词，找到其种别码后，按顺序填入到token 字表中。填入函数描述类似于符号表的填入，只是只能采用顺序填入，每次填入时总是填入表的尾部。ins_token(char *str, int token) /* 将str 放入到token_table

33、 中 */token_tablelastline.word = str;token_tablelastline.token = token;lastline = lastline +1; /*lastline 表示生成的当前单词序号*/*可以使用全局变量来记录*/(9) 编写一个函数， 将token 字表的内容写到文件中的函数write_token词法分析的结果就是生成相应的token 文件，它将作为语法分析的输入。因此，必须将上述的token_table 表输出到文件中。函数原型及算法描述如下：write_token( )打开输出的token 文件，用fp 指向；while （表没有结束）

34、fprintf(fp,” %d %s”, token_tablei.token , token_tablei.word);i+;关闭token 文件；步骤三 单词识别函数的编写(1) 编写识别标识符的函数recog_id(char ch)若第一个字符是字母，从缓冲区的当前位置开始读入字符，读到不是字母或数字的符号为止，识别它是否是一个标识符(或关键字)。识别方法可以使用状态转换图，也可以使用正规式技术，还可以用其它方式自己编写。通过识别，若不能构成标识符，提示出错信息；若是，再利用实验二的结果查找该字符串是否是关键字，若是关键字，返回关键字的种别码；若不是关键字，返回标识符的种别码。对于识别较

35、为复杂的标识符的模块，可以先画出该单词的状态转换图或语法图，然后再根据状态图给出模块详细说明，标识符的状态转换图如下：图中0 表示初态，双圈表示的状态是终态。当有引出“其它”字样的弧，表示读入了一个除该状态所有别的弧上的符号外，另外一个在字符集内的符号。有时可能需要回退该符号。下面是从一个字符串中识别一个标识符的算法描述：recogid(char ch) /* ch 为给定字符串的第一个字符*/char state='0'while (state!=2 )switch (state)case '0':/*若当前是0状态，若读入一个字母，转向1状态*/if (is

36、alpha(ch) state='1' else error();break;case '1': /*若当前是1状态，若读入字母或数字，仍为1状态*/if ( isalnum(ch) && (i<8) ) state='1'else state = 2;colno-; /*退回当前读入的字符*/ch = stringcolno+; /*将下一个符号读入ch中*/(2) 编写识别数的函数recogdig(char ch)对给定的字符串(不含空白)，识别它是否是数，若不是，提示出错信息；若是，识别是整数、小数、或是指数，分别返回

37、相应代码和字符串本身。数分为多种，下面是识别不带正负号，带指数的实常数的状态转换图：其它根据这个状态转换图可以编写识别实常数的识别函数。算法描述如下：int recogdig(char ch)/*识别常数（含整数和实数）*/char state='0' /*初始状态为0*/while (state!=7) switch (state)case '0': if (isdigit(ch) state='1' else error(); break;/*读入一个数字*/case '1': if (isdigit(ch) state=&#

38、39;1'/*仍然读入数字*/else if (ch ='.') state='2' /*读入小数点，识别实数*/else if (ch ='e') |(ch='E') state='4' /*读入e 或E，带指数*/else /* 已识别完整数，返回 */colno-;返回整数类型;break;case '2': if (isdigit(ch) state='3' /* 读入数字*/else error();break;case '3': if (isdig

39、it(ch) state='3' /* 读入数字*/else if (ch='E') | (ch='e') state ='4' /*读入e 或E，指数*/else /* 已识别完带小数的实数，返回 */colno-;返回实数类型;break;case '4': if (isdigit(ch) state='6' /*读入数字*/else if (issign(ch) state = '5' /*读入+，-符号*/else error();break;case '5'

40、: if (isdigit(ch) state='6' /*读入数字*/else error();break;case '6': if (isdigit(ch) state='6' /*读入数字*/else /* 已识别完带指数的实数，返回 */colno-;state = 7;返回实数类型;ch = strcolno+;/*读入下一个符号*/(3) 编写识别界符的函数recogdel对给定首字符的字符串(不含空白)，识别它是否是界符(单界符和双界符)，若不是，提示出错信息；若是，识别是单界符和双界符，分别返回单界符和双界符相应的代码和字符串本身

41、。类似于查找是否是关键字，该函数从界符表中查找某字符串是否存在即可。函数可以参照前面的(1)进行编写。(4) 编写识别字符常数的函数recogstr对给定首字符()的字符串(不含空白)，识别它是否是字符常数，若不是，提示出错信息；若是，去掉两边的单引号，返回剩下的字符串和字符常数的代码。字符常数的状态转换图如下，从读入的第一个符号开始表明是字符常数：函数描述如下：int recogstr (char ch) /* 进入此函数时，ch 为单引号*/char state='0' /*初始状态*/while (state!=2) switch (state) case '0': state='1' break; /*由于进入此函数时，ch 为单引号，所以不需再读入*/case '1': if (ch=''') return colno;/*读到最后的一个单引号，结束*/else state='1' /* 否则一直是常数部分 */ch = stringcolno+; /* 读取下一个符号*/(5) 编写识别并去掉注释的函数handlecom带注释的字符串是以/*开始，*/结束的字符串，若是这种形状，去掉它，识别的状态转换图如下：函数描述如下：handlecom(char