《编译原理》实验任务书.doc

编译原理实验指导书上机实习一：词法分析目的与要求：通过编写并上机调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将其分解后各类单词的词法分析方法。实验内容：输入：据教学要求和学生具体情况，从具有代表性的高级程序设计语言中，选取一个适当大小的子集，例如可以选取一类典型单词，也可以尽可能使各种类型的单词都能兼顾到。输出：单词串的输出形式，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码，VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和分隔符，采用一词一类的编码形式。由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。不过，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上直接放置单词符号串本身。示例：词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式构造词法分析程序。例如，可根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译程序的词法分析程序；也可以根据文法或状态转换图利用某种语言（汇编语言或高级语言）直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。（1）题目：试用手工方式构造具有以下单词的某一语言的词法分析程序。1 BEGIN2 END3 IF4 THEN5 ELSE6 <7 <=8 =9 <>10 >11 >=12 标识符13 无符号常数其中标识符和无符号数的BNF定义如下：（2）处理过程：在扫描源程序字符串时，一旦识别出关键字、分隔符、标识符、无符号常数中之一，即以单词形式（各类单词均采用相同的结构，即二元式编码形式）输出。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。具体方法如下：（一）单词的分类：构造上述语言中的各类单词符号及其分类码表如下:表 语言中的单词符号及其分类码表（二）构造状态转换图（以无符号常数为例）：由描述无符号常数的正规文法构造状态转换图如下：其中：非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>分别用编号0，1，2，6代表，并用1，2和6代表终态。在一个程序设计语言中，一般都含有若干类单词符号，我们可首先为每类单词都建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，最后再据此构造词法分析程序。在计算机内实现状态转换图的方法之一，是以状态图中的各个状态为行，以可能输入的各个输入符号为列，组成一个状态矩阵。其中，矩阵的元素用来指明下一个状态和扫描器应完成的语义动作（如拼接字符、数制转换、查填符号表以及输出单词的内部表示等）。由于在一个状态矩阵中，通常有许多状态都是出错状态，为了节省存放状态矩阵的存储空间，在具体实现时，常常采用更为紧凑和有效的数据结构。例如，对于文法G<无符号数>的状态转换图，可按下表的形式来存放其状态矩阵。表中，第一列为各状态Si的偏号，第二列分别列出了在每一状态下可能扫视到的输入符号aj(其中“other”是一个符号集合，用来表示在相应状态所属的那一栏中，除其前所列字符之外的全部其它字符)，第三列指出当（Si,aj）出现时应执行的语义动作（通常用若干个语句来实现，若其后空，则表示不进行任何处理），最后一栏用来指明下一状态的偏号（若其后NULL或“结束”则表示无后继状态）。（三）利用有限自动机：对于给定的包括五个有代表性的关键字、六种关系运算符、标识符及无符号常数组成的语言，还可以通过构造有限自动机的方法实现词法分析程序的设计。在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节的纠缠，我们现价定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序钟的标识符；在源程序的输入文本中，关键字、标识符、无符号数以关系运算的六重符号之间，至少需用一个空白字符加以分隔。显然，如果程序员恪守以上这些规定，那么程序中的单词总能得到正确的区分。另外，由于对语言作了上述限制，因此我们就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后继输入的字母或数字字符一次性拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查表，若查到此字符串，则取出相应的类别码；反之，则表明该字符串为一标识符。采用上述策略后，可以得到一个如下图所示的有限自动机（以状态转换图表示），并在图中添加了当进行状态转移时，词法分析程序所应执行的语义动作。（注：为了防止实习量过大，达不到实习的目的，在此将无符号常数简化为无符号整常数）。据此，可用C语言编出符合以上几项要求的一个相应的词法分析程序，如以下程序所示。（3）提示：程序所用的若干函数以及主程序有待于具体编写。另外，事先需建立好保留字表，以备查询。变量各表和常数表则在词法分析过程中建立。（4）要求：A. 上机前的准备。根据实习目的和要求，用C语言编写一个规模适当的词法分析程序以及程序流图，并选择相应的数据结构。B. 调试。将各个模块连接成一个整体程序。C. 测试。用于调试的例子应有词法正确的，也有错误的字符串。D. 输出结果。主要将调试例子与词法分析结果以对照形式输出，必要时给出正误信息。E. 扩充（任选）。有余力的学生可适当扩大题目（实验成绩有加分）。例如：扩充关键字的数目允许实型常数加词法错误检查增加单词类（如算术运算符等）处理对象是整个C语言的字符集合F. 编写上机实验报告。最后提交的结果应该包括：描述语言的文法。单词分类码表。状态转换图及状态矩阵。源程序。源程序说明。两个以上的输入字符串的例子及其输出的结果。注意：不接受没有源程序说明，或者说明和程序不符合的作业。上机实习二：语法分析目的与要求：通过设计、编制、调试一个典型的语法分析程序（选择有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，作为编制语法分析程序的依据），实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。实验内容：输入：文法。选择对各种常见程序语言都通用的语法结构作为分析对象，并且应与所选语法分析方法比较贴近。输出：如果输入符号串是合法的句子，输出“yes”并且给出每一步归约的过程；如果不是句子，输出“No“，并且输出栈里面已经归约的符号。示例：（1）题目：对于如下文法，编写与调试一个语法分析程序。题目一：试采用C语言编制递归下降法的语法分析程序，并用它对FORTRAN语言算术表述式的一个简化子集进行语法分析。分析过程不嵌入任何的语义动作。分析对象的BNF定义如下：算法：下图为用递归下降法分析上述算术表达式的框图。图中（a）为ZC函数，（b）为E函数，（c）为T函数，（d）为F函数，（e）为SYM函数，（f）为ADVANCE函数。其中ZC函数为总控程序，主要完成：（1） 通知外界键入算术表达式。（2） 控制E函数分析算术表达式。（3） 根据分析结果之正误，分别输出不同的信息。ZC函数被设计成可以分析无穷多个算术表达式。E，T，F三个函数分别对应算术表达式、项和因式三个产生式的处理。它利用到两个公共函数。一个是函数SYM，它负责从输入字符串ST中取出下一个字符，并存入SYM中等得分析。另一个是ADVANCE过程，负责剔除ST中的首字符，可通过挪动字符串指针的办法来实现。变量TZ之值标志分析的结果（表达式是否有错）。扩充：有余力的同学，可适当扩大分析对象（试验成绩有加分），例如：l 算术表达式中变量还可以是属组元素、函数调用等。l 除算术表达式外，还可进一步分析关系表达式等。l 加强语法检查，尽可能多地、确切地指出各种错误。题目二： 试用C语言编制算符优先文法的语法分析程序。分析对象为赋值语句。该赋值语句的左部只限简单变量，右部为一算术表达式的子集，不包括函数，数组元素等。该赋值语句的BNF定义如下：算法：算符优先分析的算法如下程序所示。其中，使用了一个分析栈stack，用来在分析过程中存放当前句型的某一前缀，一是句型的最左素短语在栈顶形成，便立即进行归约。如果我们希望在分析过程中为句子建立一棵“语法树”，则可在每移进一个终结符号时，就建立一个末端结点而在用某一产生式将句型的最左素短语归约为某个费终结符号N时，就建立以N为标记的结点，此结点的各子结点（从左到右）依次是最左素短语的各个符号。扩充：有余力的同学，可选作以下内容（上机试验成绩有加分）：l 加强语法检查，对语法有错的语句，给出必要的错误说明信息。l 增加赋值语句的功能。如左部变量可以是数组元素；右部表达式中可含数组元素、函数调用等。l 输出分析过程的信息。如分析栈、符号栈、当前应被归约的最左子串、归约后所得的符号等。提示：l 确定文法的机内表示方法。l 分别编写计算布尔矩阵B>，B=及B<的程序，为此，还需要编写计算布尔矩阵的B的闭包B+的子程序，供计算上述各布尔矩阵时调用。l 编制判定优先矩阵是否有多重定义元素的程序，用来判断所给文法是否为算符优先文法。l 输出各优先关系的布尔矩阵以及有关的判定结果的信息。要求：A. 上机前的准备。结合所选择的题目要求，用C语言编写一个语法分析程序及程序流图，同时考虑相应的数据结构。B. 调试。改写试验一中的词法分析程序，并将它编写为子程序形式，和语法分析程序一起构成一个完整的程序。C. 测试。供测试的例子应包括符合语法规则的语句，以及分析程序能够判别的若干错例。D. 结果输出。对于所输入的字符串，不论对错，都应有明确的信息告诉外界。E. 编写上机实验报告。最后提交结果应该包括：l 输入的文法。l 源程序。l 源程序说明。l 函数的作用。全局变量作用说明。l 两个以上的文法输入文件的例子。注意：不接受没有源程序说明，或者说明和程序不符合的作业。上机实习三：语义分析程序实现目的与要求：在语法分析的基础上，通过设计、编制、调试一个典型的语义分析程序，实现在词法分析、语法分析程序基础上编写相应的语义子程序，进行语义检查，产生中间代码，进一步掌握语法制导翻译方法。实验内容：输入：对于常用高级语言（如Pascal、C语言）的源程序从左到右进行扫描，在词法分析、语法分析的基础上采用最有代表性的语义分析方法进行语义分析。输出：将源程序转换为中间代码形式表示输出，有错的输出错误信息。示例：题目：编写与调试相应语义分析程序，针对简单赋值语句用所学过的语法分析方法进行语法分析，并且进行相应的语义分析，输出四元式表示。最终将词法分析、语法分析组合一起，形成一个小型编译系统。语法制导翻译模式是对文法中的每一产生式，都附加一“语义动作”或“语义子程序”，且在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，同时调用相应的语义子程序。每个语义子程序都指明了相应产生式中各个符号的具体含义，并规定了使用该产生式进行分析时所应采取的语义动作。因此语法制导翻译模式在一遍扫描中，既完成语法分析任务，又完成语义分析和中间代码生成方面的工作。（1）简单算术表达式和赋值语句的翻译参考文法：1）S -> A 2）A -> V:=E 3）E -> E+T4）E -> T 5）T -> T*F 6）T -> F7）F -> (E) 8）F -> i 9）V -> iA赋值语句(所含变量具有同一类型)的翻译： B赋值语句(所含变量类型不同)的翻译: 许多语言允许混合类型运算，但在运算前须转换为相同类型。 引入类型转换四元式（itr, A, 0, T），将整型变量A转换为实型变量T； 引入语义变量X.TYPE表示变量类型 ； 例如对于产生式E(1)->E(2) + T(1), 带有类型信息的语义子程序可写成 （2）布尔表达式的语法制导翻译首先将文法 E->EE|EE|E|(E)|i|i rop i 改写为 E -> EE|EE|E|(E)|i|i rop i E ->E E ->E 引入语义变量和语义函数 NXQ：指示下一个四元式的全局变量 Gen( int op, int Arg1, int Arg2, int Result) ：产生一个四元式, 且NXQ+ Merge(int p1, int p2)：将首指针分别为p1和p2的两个链合并为一条，并返回新的链头指针p2。 Backpatch(int p, int t)：以四元式序号t回填以p为链首的链具体描述如下：（3）程序流程控制语句的语法制导翻译常见控制结构包括序列结构、条件分支结构和while循环三种。下面是简单程序流程结构的S-属性翻译文法：扩充：有余力的同学，可选作以下内容：l 增加语义分析程序，完成布尔表达式、简单程序结构的翻译。l 输出分析过程的信息。如词法分析结果、语法分析结果、语义分析结果。要求：A. 上机前的准备。编写一个语义分析程序及程序流图，完成编译系统的设计。B. 调试。改写试验一中的词法分析程序，试验二中语法分析程序并将它们编写为子程序形式，和语义分析一起构成一个完整的程序。C. 测试。供测试的例子应包括符合语义规则的语句，以及分析程序能够判别的若干错例。D. 结果输出。对于所输入的字符串，不论对错，都应有明确的信息告诉外界。E. 编写上机实验报告。最后提交结果应该包括：l 输入的文法。l 源程序。l 源程序说明。l 函数的作用。全局变量作用说明。l 两个以上的例子，含有错误的例子。注意：不接受没有源程序说明，或者说明和程序不符合的作业。说明：基本题是必须完成的。扩充部分可以选作，但是没有完成扩充部分的同学的上机实验的总成绩不能高于90分。