搜索
第1页共18页实验一：词法分析一、实验目的：1、通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。2、编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本关键字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）二、实验预习提示1、词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一类符号一种别码的方式。2、单词的BNF表示标识符-字母字母数字串字母数字串-字母字母数字串|数字字母数字串|下划线字母数字串|ε无符号整数-数字数字串数字串-数字数字串|ε加法运算符-+减法运算符--大于关系运算符-大于等于关系运算符-=3、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+”,当前字符为’’，此时，分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4、模块结构第2页共18页三、实验过程和指导：（一）准备：1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。（二）程序要求：程序输入/输出示例：如源程序为C语言。输入如下一段：main(){inta,b;a=10;b=a+20;}第3页共18页要求输出如右图。（2，”main”）（5，”（“）（5，”）“）（5，”{“）（1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;”）（2，”a”）（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语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将源程序全部输入到字符缓冲区中。2.取单词前：去掉多余空白。3.取单词后：去掉多余空白（可选）。4.取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）第4页共18页5.显示结果。（五）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。四、实验原理词法分析是编译过程的第一阶段。它的任务就是对输入的字符串形式的源程序按顺序进行扫描，根据源程序的词法规则识别具有独立意义的单词（符号），并输出与其等价的Token序列。有限自动机是描述程序设计语言单词构成的工具，而状态转换图是有限自动机的比较直观的描述方法。我们使用确定的有限状态自动机，简记为DFA。根据语言的词法规则构造出识别其单词的确定有限自动机DFA,仅仅是词法分析程序的一个形式模型，距离词法分析程序的真正实现还有一定的距离。状态转换图的实现通常有两种方法，一种是用状态转换表T；另一种是直接转向法。状态转换表法又称数据中心法，是把状态转换图看作一种数据结构（状态转换表），由控制程序控制字符在其上运行，从而完成词法分析。用转换表的优点是程序短，但占存储空间多，直接转向法的优缺点正好与此相反。直接转向法又称程序中心法，是把状态转换图看成一个流程图，从状态转换图的初态开始，对它的每一个状态结点都编一段相应的程序。基本实验步骤--构造识别单词的自动机：1.根据构成规则对程序语言的单词按类构造出相应的状态转换图。2.对各类单词的状态转换图合并，构成一个能识别语言所有单词的状态转换图。合并步骤为：(1)将各类单词的状态转换图的初始状态合并为一个唯一的初态；(2)化简调整状态冲突和对冲突状态重新编号；(3)如有必要，增加出错状态。五、分析及设计过程1、总体分析：词法分析器的输入输出界面词法分析程序的主要任务是从左到右扫描每行源程序，拼成单词，换成统一的内部表示(token)输出，送给语法分析器。具体包括：–组织源程序的输入；第5页共18页–按规则拼单词，并转换成二元形式；–滤掉空白符，跳过注释、换行符及一些无用的符号(如字符常数的引号)–进行行列计数，用于指出出错的行列号，并复制出错部分；–列表打印源程序；–发现并定位词法错误；–生成符号表。token文件和符号表用作语法分析的输入部分。2、条件分析：本实验可以作如下假定：(1)可以使用注解，用/*……*/标识，但注解不能插在单词内部，注解要在一行内结束，若一行结束，没有遇到注释后面的结束标记，自动认为注释也结束；(2)一行可以有多个语句，一个语句也可以分布在多行中，单词之间和语句之间可以插入任意空格，单词中间不能有空白符号，单词中间也不能有回车换行符，即单词不能跨行书写；(3)关键字都是保留字。3、词法分析程序的总体设计词法分析程序的顶层数据流图词法分析程序的顶层数据流图，即是词法分析程序的输入输出界面图，由此可以看出词法分析程序的功能就是从源程序中读入一个个字符，依据一定的构词规则，识别出各类有用的单词。其中源程序清单和错误信息从屏幕、打印机或文件输出，其余文件均以顺序文件的形式输出到外存储器上，以供下一阶段使用。由此可以得到更详细的数据流图。第6页共18页词法分析程序的详细数据流图在上面的数据流图中，各个加工处理完成的功能如下：加工1.1(读一行并打印)：收到读下一行命令后，从源程序读入一行，装入缓冲区，行计数，并打印。在这里需要注意的是，回车换行在源程序（文本文件）中用两个字符0D0AH来表示，而用高级语言（C语言）读入内存后，就用一个字符0AH来表示，这是在用高级语言编写词法分析器时常被忽略导致错误的原因。第7页共18页加工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栏内填入整型或实型，然后输出其二元式。二元式中包含该常数在符号表中的入口。4、词法分析程序的详细设计数据流图属于输入-变换-输出形式的变换型数据流图，但加工1.3—1.9构成了典型的事务处理型数据流图。根据数据流图，可以得到词法分析程序的总体框架。第8页共18页词法分析器的程序框架5、实验步骤步骤一编写词法分析的总控程序(1)编写词法分析的主函数scanner()词法分析的总控程序就是词法分析器的程序框架。词法分析中要使用的函数将逐步第9页共18页在下面的三个实验中分别实现。要实现词法分析的功能，必须按照总控程序的安排，在适当的位置进行调用，当所有的函数都实现了，就构成了一个完整的词法分析程序。主函数的描述如下：a.打开输入源文件，设置行计数器为0;b.如果源文件没有结束，读入一行到string，行计数+1，设置列计数器为0;c.如果缓冲区非空，将缓冲区中的符号串分割为一个一个的单词，否则转b。(区分一个单词结束的方法是：从缓冲区读入一个非空字符，列计数+1，继续读入字符(每读入一个字符，列计数+1)，直到一个单词读完（单词结束的标志是单词分隔符，如空格符号、空白符号、换行符和界符等，但单词的分隔符不属于该单词，读入的符号串是否可以构成一个正确的单词，要根据单词的构成规则来判断，不同类别的单词其构词规则不一样，这样就可以根据不同类别的单词的的识别函数来判断相应的单词构成是否有错误。单词的类别是根据读入的该单词的首字符来判断的，可以单独写一个分类函数，根据首字符判断该单词属于关键字、标识符、常数、运算符和界符中的哪一类）。d.将识别出来的单词及其种别码写入Token字表中。e.根据单词的类别，进行不同的后期处理，如果是标识符或常数，需要将其唯一值填入符号表中。g.如果源文件已结束，关闭打开的源文件。f.打印token字表和符号表到相应的文件中;(2)编写分类函数sort()单词分为标识符、常数、关键字、运算符和界符，单词必须分类进行识别。根据读入该单词的第一个字符进行分类，判断该单词是属于哪一类。根据单词的分类结果调用相应的识别函数识别一个单词是否正确。intsort(charch)/*传入参数ch为已读入的单词的第一个字符，据此进行分类*/{if(isdigit(ch))return常数;/*如果第一个字符是数字，则是数