代码生成方法

1.1 代码生成方法

1.1.1 代码生成概述

代码生成的一种做法是遍历AST和调用符号表信息，直接一边遍历，一边生成代码。也可以将树形AST结构转化为由字符串这一基本类型组成的复杂线性数据结构中，再调用输出函数进行输出，后者虽工作量稍大，但代码逻辑更加清晰，便于维护和扩展，所以本小组采用后者实现代码生成。
①遍历AST、查符号表，将代码保存到线性数据结构，这些数据结构将在下一部分进行介绍
②按照C程序结构，遍历各线性数据结构，输出代码

1.1.2 对应关系分析

1.1.2.1 头文件

头文件的需求来自于库程序的调用，PASCAL-S仅支持read、write、writeln、exit四种库程序的调用，其中exit对应了返回值语句，所以剩下的三个过程对应到C程序就是printf和scanf这两个语句，这两个语句包含在stdio.h头文件中。我们将在所有生成函数调用、过程调用代码的位置调用一个函数专门来检查所调用和函数和过程是否是库程序，如果是库程序，则需标记相应的头文件。最后输出代码的时候，输出被标记了的头文件即可。
这样设计而不是对read、write、writeln进行特判，保证了我们编译器的可扩展性，后续如果要添加对别的库程序的支持，对于代码的修改将会特别容易进行。
另外，在C99中C语言加入了对bool类型的支持，但仍需加入stdbool.h头文件，考虑到boolean类型是PASCAL-S程序的基本类型，生成的C语言代码中，将自动加入stdbool.h头文件。
综上，如果源程序包含输入输出语句，则输出的C代码会包含stdio.h头文件，同时输出的C代码必然会包含stdbool.h头文件。

1.1.2.2 程序结构

PASCAL-S程序中不包含头文件之类的成分，如何在C程序中确定需要的头文件已在上文阐述。
PASCAL-S程序的主程序名在C语言中没有对应的内容，因为在C语言中，入口函数固定名称为main。我们需要在C程序中专门设置一个程序，取名为PASCAL程序的主程序名。然后main函数只要简单的调用该函数即可。
PASCAL-S程序中，定义在主程序部分的常量和变量可以被所有的子程序引用，这相当于C语言中的全局变量和全局常量。
结构良好的C程序需要将所有程序的声明放在main函数之前，这些程序的声明中，除了包括PASCAL-S程序中声明的所有子程序，还应包括我们在上文提到的PASCAL-S主程序对应到C程序的声明。
main函数中只需要调用PASCAL-S主程序对应到的C程序即可。
最后还应包含所有子程序的定义，当然也应包含PASCAL-S主程序对应到的C程序的定义。

1.1.2.3 类型关键字的对应关系

1.1.2.4 运算符的对应关系

1.1.2.5 引用参数与指针

PASCAL-S支持引用参数，C不支持，所以在C中只能用指针来代替参数引用，由于我们记录类型，所以涉及的指针操作不会很复杂。
首先在调用程序时，形参变量前需加入取地址符；其次在程序定义时，需将引用参数的定义改为对应类型的指针；在程序体内，所有涉及到原引用参数的，都需要加上解引用符；还需特殊考虑引用参数又作为实参调用，同时对应的形参也是引用参数的情形，此时实参直接为该指针变量即可，不需要解引用符，当然也可以解引用后再取地址。
具体转化方法将在后文介绍。

1.1.2.6 常量和变量定义

对于常量定义，pascal中的const关键字作用域较大，不局限于下一个分号，而C语言中，每一分号隔出的部分都要单独使用一个const关键字。且pascal中的常量在定义时不需要指明类型，但是C语言需要。所以在我们需要在词法分析阶段完成对常量类型的自动识别，在目标代码生成时，指明对应的类型。
pascal在声明变量时，除了要说明类型，还要再前面加上var关键字，C语言中没有这样的关键字，只需要指明类型即可。var关键字的作用域与const关键字相同。

1.1.2.7 主程序参数列表

pascal主程序头中包含了一个无类型的标识符列表。经查阅资料，这个标识符列表类似于c语言中main函数的参数列表，但由于PASCAL-S缺少相应的语法支持，导致主程序参数没有任何实际用途，所以我们的编译器在代码生成阶段，将忽略主程序参数列表。

1.1.2.8 数组下标

PASCAL-S的数组下标上下界均可由用户定义，实际上，上下界甚至可以是负数，但由于文法限制，PASCAL-S仅支持无符号数的数组上下界。在C程序中，数组的下界是固定的，也就是0，程序定义数组时，给出每一维的大小为ni，也就定义了每一维的上界为ni-1。下标转化方法将在后文给出。

1.1.2.9 数组引用列表

PASCAL-S的数组下标引用列表用中括号包围，每一维的下标表达式之间用逗号分隔。
C的数组每一维的下标表达式均用中括号包括，同时也起到了分隔的作用。

1.1.2.10 返回语句

1.1.2.11 复合语句块

PASCAL-S中复合语句块由BEGIN和END关键字包括，而C语言中则由一对大括号包括。
PASCAL-S中，复合语句块的最后一条语句后可以没有分号，但实际上按照文法来说，最后一条语句后面一定没有分号，如果从形式上看最后一条语句后面是有分号的，那么就可以认为最后一条语句为空语句（这么说非常的违反直觉，但实际上文法就是这么定义的）。所以在PASCAL-S中，即使看上去只有一条语句，如果这条语句后面出现了一个分号，那这一条语句也必须用BEGIN和END包括为一个复合语句块，if语句的then语句部分就是一个典型的例子；但是C程序的每一条语句都必须包含分号。

1.1.2.12 循环语句

注意，PASCAL-S的repeat-until循环语句的含义为，执行循环语句体，直到满足条件；而C的do-while循环语句的含义为，执行循环语句体，直到条件不满足，所以在转化时，需要将在原有条件表达式的基础上取反。

1.1.2.13 if分支语句

在if分支语句上，两者并没有多大的差别。
PASCAL-S中的结构为： if 条件表达式 then 语句;
if 条件表达式 then 语句1 else 语句2;
C中的结构为： if(条件表达式) 语句;
if(条件表达式) 语句1 else 语句2;

1.1.2.14 赋值语句

两者的区别仅在于赋值号上，PASCAL-S中为:=，C中为=，这在运算符的对应关系中已经说明。

1.1.2.15 程序的无参调用

PASCAL-S中无参调用时，只需要程序名即可；C中无参调用时，需要在程序名后加上一对括号，括号中不包含任何内容。

1.1.2.16 输入调用

PASCAL-S调用read进行输入，C调用scanf进行输入；
read在调用时，只需要提供用逗号分隔的普通变量（或数组元素）列表即可，而scanf不仅需要变量列表，还需一个格式控制符字符串。
类型与其格式控制符的对应关系如下：

PASCAL-S不支持boolean类型变量的输入。

1.1.2.17 输出调用

PASCAL-S调用write或writeln进行输出，C调用printf进行输出；
write在调用时，只需要提供用逗号分隔的表达式列表即可，而printf不仅需要表达式列表，还需一个格式控制符字符串。
writeln除了需要在格式控制符字符串的最后加入一个换行符，与write没有任何区别。
其类型与格式控制符的对应关系可以参考输入。
另外还需强调输出对于boolean变量的支持。PASCAL-S支持boolean表达式的输出，而C程序不支持bool类型的直接输出，一种常见的做法是用%d格式控制符，这也得益于C程序对于布尔型和整型之间的隐式类型转换规则，如下表所示：

但是在PASCAL-S中，输出布尔表达式的值时，输出的就是true或者false。为了实现这种输出效果，我们并没有采用上文的解决方案，具体方法将在后文给出，这里仅讨论对应关系。

1.1.2.18 程序头

可见C程序对于函数和过程的定义更加统一，可以将“void”视为一种特殊的返回值类型。

1.1.2.19 程序参数列表

PASCAL-S的结构为
[var] 标识符列表 : 类型 ; [var] 标识符列表 : 类型 ; ……
C的结构为
类型 标识符, 类型 标识符, ……
PASCAL-S中引用参数需要加上var关键字，C中引用参数需要在类型后加上“&”。

1.1.3 重要细节

1.1.3.1 头文件标记方法

每次碰到函数或过程调用时，该函数将检查函数或过程名是否属于库程序，如果属于库程序，需要标记其所属的头文件。
先介绍两个数据结构。

map<string,string> mp_subprogramToHeadFile;//过程、函数到C程序头文件的映射  
map<string,bool> mp_headFileShow;//头文件是否出现的映射

我们首先检查mp_subprogramToHeadFile的键值中是否包含当前程序名，如果包含，则以mp_subprogramToHeadFile的属性值作为mp_headFileShow的键值，将mp_headFileShow的属性值标记为true。

1.1.3.2 bool表达式的输出

前面已经提到PASCAL-S中，输出boolean类型是按照原样输出的，即为真时输出true，为假时输出false，我们也将实现这种效果。
write语句的多个输出表达式，将以bool表达式进行分隔，转化为多个部分，每个bool表达式本身作为一个部分。例如write(表达式1，表达式2，表达式3，表达式4，表达式5，表达式6)，如果表达式3和表达式4是bool表达式，那么将分为以下四部分：

• 1、2
• 3
• 4
• 5、6

如果当前部分是不含bool类型的，则按照正常方法转换；
如果当前部分是一条bool表达式，则转化为如下形式：
if(bool表达式)
printf(“true”);
else
printf(“false”);

1.1.3.3 数组下标转化

假设PASCAL中某一维的下标上下界为[a,b]，那么C中的上下界就为[0,b-a]。
假设引用该维的表达式为X，则在代码生成时，该表达式应写为X-a。

1.1.3.4 语句缩进控制

为了保持输出代码的整洁，需要为每一条语句定义一个缩进值，即该语句前面的制表符个数。
需要控制缩进的情况如下：

1.1.3.5 表达式优先级和输出时的括号

实际上这一部分无需任何处理，因为我们的表达式抽象成的AST子树已经完美的阐述了运算符之间的优先级关系，也无需自己增添括号。
但是考虑到编译器的可扩展性，我们设计了一个根据优先级添加括号的算法，同时也可以使得一些表达式的更加易读。
例如语句a:=—b; 经过我们的处理后，生成的C代码为a=-(-b)。
首先我们为表达式赋予优先级的概念，表达式的优先级就是其AST树形结构的根节点运算符的优先级，可以用如下表表示：

   对于每一个包含运算符的复杂表达式，需要考虑其操作数表达式是否需要外加括号，其操作数表达式的优先级，也就是其操作数表达式对应的AST树形结构的根节点的运算符的优先级，如果比当前运算符优先级低，就需要给操作数表达式外加括号，具体策略如下：

1.1.3.6 引用参数转化为指针

假设该变量为a，按照下表分情况讨论，其输出代码分别为：

   对上面的表格，去除不存在项，并“合并同类项”，精简为下表：

   所以在函数和过程调用时，需要检查实参对应的形参是否为引用参数，将该信息作为布尔型变量的参数传入到获取变量代码的函数中，然后在该函数中，再获取该变量是否是当前所在程序的引用参数，结合上表就可以得知最终应该输出怎样的代码。

1.1.3.7 程序头中的引用参数

只需要将引用参数定义为对应类型的指针变量即可。

1.1.4 生成的C程序结构

C程序结构如下所示，注意main_function在实际的代码中，应被PASCAL-S的主程序名取代。

//Head files
//Overall constant definiton
//Overall variable definition
//Subprogram declaration
void main_function();
int fun();
void pro();
……
//Main function
int main() {
    test();
    return 0;
}
//Subprogram definition
void main_function() {
    ……
}
int fun() {
    ……
}
void pro() {
    ……
}
……