编译实验指导书.docVIP

《编译原理》实验指导书 上机实习一：词法分析 目的与要求：通过编写并上机调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将其分解后各类单词的词法分析方法。 实验内容： 输入：据教学要求和学生具体情况，从具有代表性的高级程序设计语言中，选取一个适当大小的子集，例如可以选取一类典型单词，也可以尽可能使各种类型的单词都能兼顾到。 输出：单词串的输出形式，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码，VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和分隔符，采用一词一类的编码形式。由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。不过，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上直接放置单词符号串本身。 示例： 词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式构造词法分析程序。例如，可根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译程序的词法分析程序；也可以根据文法或状态转换图利用某种语言（汇编语言或高级语言）直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。 （1）题目：试用手工方式构造具有以下单词的某一语言的词法分析程序。 1 BEGIN 2 END 3 IF 4 THEN 5 ELSE 6 7 = 8 = 9 10 11 = 12 标识符 13 无符号常数 其中标识符和无符号数的BNF定义如下： （2）处理过程：在扫描源程序字符串时，一旦识别出关键字、分隔符、标识符、无符号常数中之一，即以单词形式（各类单词均采用相同的结构，即二元式编码形式）输出。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。具体方法如下： （一）单词的分类：构造上述语言中的各类单词符号及其分类码表如下: 表Ⅰ 语言中的单词符号及其分类码表 （二）构造状态转换图（以无符号常数为例）： 由描述无符号常数的正规文法构造状态转换图如下： 其中：非终结符号无符号数、余留无符号数、十进小数、小数部分、指数部分、整指数及余留整指数分别用编号0，1，2，…，6代表，并用1，2和6代表终态。 在一个程序设计语言中，一般都含有若干类单词符号，我们可首先为每类单词都建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，最后再据此构造词法分析程序。在计算机内实现状态转换图的方法之一，是以状态图中的各个状态为行，以可能输入的各个输入符号为列，组成一个状态矩阵。其中，矩阵的元素用来指明下一个状态和扫描器应完成的语义动作（如拼接字符、数制转换、查填符号表以及输出单词的内部表示等）。由于在一个状态矩阵中，通常有许多状态都是出错状态，为了节省存放状态矩阵的存储空间，在具体实现时，常常采用更为紧凑和有效的数据结构。例如，对于文法G[无符号数]的状态转换图，可按下表的形式来存放其状态矩阵。表中，第一列为各状态Si的偏号，第二列分别列出了在每一状态下可能扫视到的输入符号aj(其中“other”是一个符号集合，用来表示在相应状态所属的那一栏中，除其前所列字符之外的全部其它字符)，第三列指出当（Si,aj）出现时应执行的语义动作（通常用若干个语句来实现，若其后空，则表示不进行任何处理），最后一栏用来指明下一状态的偏号（若其后NULL或“结束”则表示无后继状态）。 （三）利用有限自动机： 对于给定的包括五个有代表性的关键字、六种关系运算符、标识符及无符号常数组成的语言，还可以通过构造有限自动机的方法实现词法分析程序的设计。在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节的纠缠，我们现价定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序钟的标识符；在源程序的输入文本中，关键字、标识符、无符号数以关系运算的六重符号之间，至少需用一个空白字符加以分隔。显然，如果程序员恪守以上这些规定，那么程序中的单词总能得到正确的区分。 另外，由于对语言作了上述限制，因此我们就可以把关键字和