南京大学：《编译原理 Principles and Techniques of Compilers》课程教学电子教案（实验讲义）实验二语义分析.pdf_大学文库

版权所有南京大学计算机科学与技术系许畅等2022春季版 3.语义分析本章实验为实验二，任务是在词法分析和语法分析程序的基础上编写一个程序，对C-一源代码进行语义分析和类型检查，并打印分析结果。与实验一不同的是，实验二不再借助已有的工具，所有的任务都必须手写代码来完成。另外，虽然语义分析在整个编译器的实现中并不是难度最大的任务，但却是最细致、琐碎的任务。因此需要用心地设计诸如符号表、变量类型等数据结构的实现细节，从而正确、高效地实现语义分析的各种功能。需要注意的是，由于在后面的实验中还会用到本次实验已经写好的代码，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。 3.1 实验内容 3.11实验要求在本次实验中，我们对C一语言做如下假设，你可以认为这些就是C-一语言的特性（注意，假设3、4、5可能因后面的不同选做要求而有所改变)： 1)假设1：整型(int)变量不能与浮点型(float)变量相互赋值或者相互运算。 2)假设2：仅有int型变量才能进行逻辑运算或者作为f和while语句的条件；仅有nt型和 float型变量才能参与算术运算。 3)假设3：任何函数只进行一次定义，无法进行函数声明。 4)假设4：所有变量（包括函数的形参）的作用域都是全局的，即程序中所有变量均不能重名。 5)假设5：结构体间的类型等价机制采用名等价(Name Equivalence)的方式。 6)假设6：函数无法进行嵌套定义。 7)假设7：结构体中的域不与变量重名，并且不同结构体中的域互不重名。以上假设1至7也可视为要求，违反即会导致各种语义错误，不过我们只对后面讨论的17种错误类型进行考察。此外，你可以安全地假设输入文件中不包含注释、八进制数、十六进制数、以及指数形式的浮点数，也不包含任何词法或语法错误（除了特别说明的针对选做要求的测试)。你的程序需要对输入文件进行语义分析（输入文件中可能包含函数、结构体、一维和高维数组)并检查如下类型的错误： 1)错误类型1：变量在使用时未经定义。 45

版权所有南京大学计算机科学与技术系许畅等 2022春季版 45 3. 语义分析本章实验为实验二，任务是在词法分析和语法分析程序的基础上编写一个程序，对C−−源代码进行语义分析和类型检查，并打印分析结果。与实验一不同的是，实验二不再借助已有的工具，所有的任务都必须手写代码来完成。另外，虽然语义分析在整个编译器的实现中并不是难度最大的任务，但却是最细致、琐碎的任务。因此需要用心地设计诸如符号表、变量类型等数据结构的实现细节，从而正确、高效地实现语义分析的各种功能。需要注意的是，由于在后面的实验中还会用到本次实验已经写好的代码，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。 3.1 实验内容 3.1.1 实验要求在本次实验中，我们对C−−语言做如下假设，你可以认为这些就是C−−语言的特性（注意，假设3、4、5可能因后面的不同选做要求而有所改变）： 1) 假设1：整型（int）变量不能与浮点型（float）变量相互赋值或者相互运算。 2) 假设2：仅有int型变量才能进行逻辑运算或者作为if和while语句的条件；仅有int型和 float型变量才能参与算术运算。 3) 假设3：任何函数只进行一次定义，无法进行函数声明。 4) 假设4：所有变量（包括函数的形参）的作用域都是全局的，即程序中所有变量均不能重名。 5) 假设5：结构体间的类型等价机制采用名等价（Name Equivalence）的方式。 6) 假设6：函数无法进行嵌套定义。 7) 假设7：结构体中的域不与变量重名，并且不同结构体中的域互不重名。以上假设1至7也可视为要求，违反即会导致各种语义错误，不过我们只对后面讨论的17种错误类型进行考察。此外，你可以安全地假设输入文件中不包含注释、八进制数、十六进制数、以及指数形式的浮点数，也不包含任何词法或语法错误（除了特别说明的针对选做要求的测试）。你的程序需要对输入文件进行语义分析（输入文件中可能包含函数、结构体、一维和高维数组）并检查如下类型的错误： 1) 错误类型1：变量在使用时未经定义

版权所有南京大学计算机科学与技术系许畅等2022春季版 2)错误类型2：函数在调用时未经定义。 3)错误类型3：变量出现重复定义，或变量与前面定义过的结构体名字重复。 4)错误类型4：函数出现重复定义（即同样的函数名出现了不止一次定义）。 5)错误类型5：赋值号两边的表达式类型不匹配。 6)错误类型6：赋值号左边出现一个只有右值的表达式。 7)错误类型7：操作数类型不匹配或操作数类型与操作符不匹配（例如整型变量与数组变量相加减，或数组（或结构体）变量与数组（或结构体）变量相加减)。 8)错误类型8：return语句的返回类型与函数定义的返回类型不匹配。 9)错误类型9：函数调用时实参与形参的数目或类型不匹配。 10) 错误类型10：对非数组型变量使用“[]”（数组访问）操作符。 11) 错误类型11：对普通变量使用“(.)”或“0”（函数调用)操作符。 12) 错误类型12：数组访问操作符“[.]”中出现非整数（例如1.5)。 13) 错误类型13：对非结构体型变量使用“”操作符。 14) 错误类型14：访问结构体中未定义过的域。 15) 错误类型15：结构体中域名重复定义（指同一结构体中），或在定义时对域进行初始化（例如struct A{inta=0;})。 16) 错误类型16：结构体的名字与前面定义过的结构体或变量的名字重复。 17) 错误类型17：直接使用未定义过的结构体来定义变量。其中，要注意三点：一是关于数组类型的等价机制，同C语言一样，只要数组的基类型和维数相同我们即认为类型是匹配的，例如inta[10[2]和intb[5[3]即属于同一类型；二是我们允许类型等价的结构体变量之间的直接赋值（见后面的测试样例），这时的语义是，对应的域相应赋值（数组域也如此，按相对地址赋值直至所有数组元素赋值完毕或目标数组域已经填满)；三是对于结构体类型等价的判定，每个匿名的结构体类型我们认为均具有一个独有的隐藏名字，以此进行名等价判定。除此之外，你的程序可以选择完成以下部分或全部的要求： 1)要求21：修改前面的C一语言假设3，使其变为“函数除了在定义之外还可以进行声明”。函数的定义仍然不可以重复出现，但函数的声明在相互一致的情况下可以重复出现。任一函数无论声明与否，其定义必须在源文件中出现。在新的假设3下，你的程序还需要检查两类新的错误和增加新的产生式： 46

版权所有南京大学计算机科学与技术系许畅等 2022春季版 46 2) 错误类型2：函数在调用时未经定义。 3) 错误类型3：变量出现重复定义，或变量与前面定义过的结构体名字重复。 4) 错误类型4：函数出现重复定义（即同样的函数名出现了不止一次定义）。 5) 错误类型5：赋值号两边的表达式类型不匹配。 6) 错误类型6：赋值号左边出现一个只有右值的表达式。 7) 错误类型7：操作数类型不匹配或操作数类型与操作符不匹配（例如整型变量与数组变量相加减，或数组（或结构体）变量与数组（或结构体）变量相加减）。 8) 错误类型8：return语句的返回类型与函数定义的返回类型不匹配。 9) 错误类型9：函数调用时实参与形参的数目或类型不匹配。 10) 错误类型10：对非数组型变量使用“[…]”（数组访问）操作符。 11) 错误类型11：对普通变量使用“(…)”或“()”（函数调用）操作符。 12) 错误类型12：数组访问操作符“[…]”中出现非整数（例如a[1.5]）。 13) 错误类型13：对非结构体型变量使用“.”操作符。 14) 错误类型14：访问结构体中未定义过的域。 15) 错误类型15：结构体中域名重复定义（指同一结构体中），或在定义时对域进行初始化（例如struct A { int a = 0; }）。 16) 错误类型16：结构体的名字与前面定义过的结构体或变量的名字重复。 17) 错误类型17：直接使用未定义过的结构体来定义变量。其中，要注意三点：一是关于数组类型的等价机制，同C语言一样，只要数组的基类型和维数相同我们即认为类型是匹配的，例如int a[10][2]和int b[5][3]即属于同一类型；二是我们允许类型等价的结构体变量之间的直接赋值（见后面的测试样例），这时的语义是，对应的域相应赋值（数组域也如此，按相对地址赋值直至所有数组元素赋值完毕或目标数组域已经填满）；三是对于结构体类型等价的判定，每个匿名的结构体类型我们认为均具有一个独有的隐藏名字，以此进行名等价判定。除此之外，你的程序可以选择完成以下部分或全部的要求： 1) 要求2.1：修改前面的C−−语言假设3，使其变为“函数除了在定义之外还可以进行声明”。函数的定义仍然不可以重复出现，但函数的声明在相互一致的情况下可以重复出现。任一函数无论声明与否，其定义必须在源文件中出现。在新的假设3下，你的程序还需要检查两类新的错误和增加新的产生式：

版权所有南京大学计算机科学与技术系许畅等2022春季版 a)错误类型18：函数进行了声明，但没有被定义。 b)错误类型19：函数的多次声明互相冲突（即函数名一致，但返回类型、形参数量或者形参类型不一致)，或者声明与定义之间互相冲突。 ©)由于C-一语言文法中并没有与函数声明相关的产生式，因此你需要先对该文法进行适当修改。对于函数声明来说，我们并不要求支持像"int foo(int,float)”'这样省略参数名的函数声明。在修改的时候要留意，你的改动应该以不影响其它错误类型的检查为原则。 2)要求22：修改前面的C-一语言假设4，使其变为“变量的定义受可嵌套作用域的影响，外层语句块中定义的变量可在内层语句块中重复定义（但此时在内层语句块中就无法访问到外层语句块的同名变量)，内层语句块中定义的变量到了外层语句块中就会消亡，不同函数体内定义的局部变量可以相互重名”。在新的假设4下，完成错误类型1至17的检查。 3)要求23：修改前面的C一语言假设5，将结构体间的类型等价机制由名等价改为结构等价(Structural Equivalence)。例如，虽然名称不同，但两个结构体类型struct a{intx;float y;}和struct b{inty;float z;}仍然是等价的类型。注意，在结构等价时不要将数组展开来判断，例如struct A{inta;struct{float f,inti;}b[1o];}和struct B{struct{inti;float f;}b[10: intb}是不等价的。在新的假设5下，完成错误类型1至17的检查。 3.1.2输入格式你的程序的输入是一个包含C-一源代码的文本文件，该源代码中可能会有语义错误。你的程序需要能够接收一个输入文件名作为参数。例如，假设你的程序名为C℃、输入文件名为 test1、程序和输入文件都位于当前目录下，那么在Linux命令行下运行./cc testl即可获得以 testl作为输入文件的输出结果。 3.1.3输出格式实验二要求通过标准输出打印程序的运行结果。对于那些没有语义错误的输入文件，你的程序不需要输出任何内容。对于那些存在语义错误的输入文件，你的程序应当输出相应的错误信息，这些信息包括错误类型、出错的行号以及说明文字，其格式为： Error type[错误类型]at Line[行号]：[说明文字]. 说明文字的内容没有具体要求，但是错误类型和出错的行号一定要正确，因为这是判断输出的错误提示信息是否正确的唯一标准。请严格遵守实验要求中给定的错误分类，否则将影响 47

版权所有南京大学计算机科学与技术系许畅等 2022春季版 47 a) 错误类型18：函数进行了声明，但没有被定义。 b) 错误类型19：函数的多次声明互相冲突（即函数名一致，但返回类型、形参数量或者形参类型不一致），或者声明与定义之间互相冲突。 c) 由于C−−语言文法中并没有与函数声明相关的产生式，因此你需要先对该文法进行适当修改。对于函数声明来说，我们并不要求支持像“int foo(int, float)”这样省略参数名的函数声明。在修改的时候要留意，你的改动应该以不影响其它错误类型的检查为原则。 2) 要求2.2：修改前面的C−−语言假设4，使其变为“变量的定义受可嵌套作用域的影响，外层语句块中定义的变量可在内层语句块中重复定义（但此时在内层语句块中就无法访问到外层语句块的同名变量），内层语句块中定义的变量到了外层语句块中就会消亡，不同函数体内定义的局部变量可以相互重名”。在新的假设4下，完成错误类型1至17的检查。 3) 要求2.3：修改前面的C−−语言假设5，将结构体间的类型等价机制由名等价改为结构等价（Structural Equivalence）。例如，虽然名称不同，但两个结构体类型struct a { int x; float y; }和struct b { int y; float z; }仍然是等价的类型。注意，在结构等价时不要将数组展开来判断，例如struct A { int a; struct { float f; int i; } b[10]; }和struct B { struct { int i; float f; } b[10]; int b;}是不等价的。在新的假设5下，完成错误类型1至17的检查。 3.1.2 输入格式你的程序的输入是一个包含C−−源代码的文本文件，该源代码中可能会有语义错误。你的程序需要能够接收一个输入文件名作为参数。例如，假设你的程序名为cc、输入文件名为 test1、程序和输入文件都位于当前目录下，那么在Linux命令行下运行./cc test1即可获得以 test1作为输入文件的输出结果。 3.1.3 输出格式实验二要求通过标准输出打印程序的运行结果。对于那些没有语义错误的输入文件，你的程序不需要输出任何内容。对于那些存在语义错误的输入文件，你的程序应当输出相应的错误信息，这些信息包括错误类型、出错的行号以及说明文字，其格式为： Error type [错误类型] at Line [行号]: [说明文字]. 说明文字的内容没有具体要求，但是错误类型和出错的行号一定要正确，因为这是判断输出的错误提示信息是否正确的唯一标准。请严格遵守实验要求中给定的错误分类，否则将影响

版权所有南京大学计算机科学与技术系许畅等2022春季版你的实验评分。输入文件中可能包含一个或者多个错误（但每行最多只有一个错误），你的程序需要将它们全部检查出来。当然，有些时候输入文件中的一个错误会产生连锁反应，导致别的地方出现多个错误（例如，一个未定义的变量在使用时由于无法确定其类型，会使所有包含该变量的表达式产生类型错误)，我们只会去考察你的程序是否报告了较本质那个的错误（如果难以确定哪个错误更本质一些，建议你报告所有发现的错误)。但是，如果源程序里有错而你的程序没有报错或报告的错误类型不对，又或者源程序里没有错但你的程序却报错，都会影响你的实验评分。 3.1.4测试环境你的程序将在如下环境中被编译并运行（同实验一）： 1)GNU Linux Release:Ubuntu 12.04,kernel version 3.2.0-29; 2)GCC version 4.6.3; 3)GNU Flex version 2.5.35; 4)GNU Bison version 2.5. 一般而言，只要避免使用过于冷门的特性，使用其它版本的Liux或者GCC等，也基本上不会出现兼容性方面的问题。注意，实验二的检查过程中不会去安装或尝试引用各类方便编程的函数库（如gb等），因此请不要在你的程序中使用它们。 3.1.5提交要求实验二要求提交如下内容（同实验一）： 1)Flex、Bison以及C语言的可被正确编译运行的源程序。 2)一份PDF格式的实验报告，内容包括： )你的程序实现了哪些功能？简要说明如何实现这些功能。清晰的说明有助于助教对你的程序所实现的功能进行合理的测试。 b)你的程序应该如何被编译？可以使用脚本、makefile或逐条输入命令进行编译，请详细说明应该如何编译你的程序。无法顺利编译将导致助教无法对你的程序所实现的功能进行任何测试，从而丢失相应的分数。 ©)实验报告的长度不得超过三页！所以实验报告中需要重点描述的是你的程序中的亮点，是你认为最个性化、最具独创性的内容，而相对简单的、任何人都可以做 48

版权所有南京大学计算机科学与技术系许畅等 2022春季版 48 你的实验评分。输入文件中可能包含一个或者多个错误（但每行最多只有一个错误），你的程序需要将它们全部检查出来。当然，有些时候输入文件中的一个错误会产生连锁反应，导致别的地方出现多个错误（例如，一个未定义的变量在使用时由于无法确定其类型，会使所有包含该变量的表达式产生类型错误），我们只会去考察你的程序是否报告了较本质那个的错误（如果难以确定哪个错误更本质一些，建议你报告所有发现的错误）。但是，如果源程序里有错而你的程序没有报错或报告的错误类型不对，又或者源程序里没有错但你的程序却报错，都会影响你的实验评分。 3.1.4 测试环境你的程序将在如下环境中被编译并运行（同实验一）： 1) GNU Linux Release: Ubuntu 12.04, kernel version 3.2.0-29； 2) GCC version 4.6.3； 3) GNU Flex version 2.5.35； 4) GNU Bison version 2.5。一般而言，只要避免使用过于冷门的特性，使用其它版本的Linux或者GCC等，也基本上不会出现兼容性方面的问题。注意，实验二的检查过程中不会去安装或尝试引用各类方便编程的函数库（如glib等），因此请不要在你的程序中使用它们。 3.1.5 提交要求实验二要求提交如下内容（同实验一）： 1) Flex、Bison以及C语言的可被正确编译运行的源程序。 2) 一份PDF格式的实验报告，内容包括： a) 你的程序实现了哪些功能？简要说明如何实现这些功能。清晰的说明有助于助教对你的程序所实现的功能进行合理的测试。 b) 你的程序应该如何被编译？可以使用脚本、makefile或逐条输入命令进行编译，请详细说明应该如何编译你的程序。无法顺利编译将导致助教无法对你的程序所实现的功能进行任何测试，从而丢失相应的分数。 c) 实验报告的长度不得超过三页！所以实验报告中需要重点描述的是你的程序中的亮点，是你认为最个性化、最具独创性的内容，而相对简单的、任何人都可以做

南京大学：《编译原理 Principles and Techniques of Compilers》课程教学电子教案（实验讲义）实验二 语义分析

南京大学：《编译原理 Principles and Techniques of Compilers》课程教学电子教案（实验讲义）实验二语义分析