词法分析

flex用法

flex可以用于词法分析。一个flex文件可以分成2个部分：引导区和规则区（我起的名）

引导区的内容会原封不动地放到.c文件中。规则区是由若干个规则组成的区域，flex的目的就是为了把规则区的内容进行解释，变成词法分析的.c文件中。（理论：正则表达式转化为NFA，然后再转化为DFA）。规则区的每一个规则由三部分组成<执行状态><正则式><匹配规则>。在规则区内部可以执行两种特殊的操作，一种是正则式的宏定义，例如[0-9] DIGIT是将0-9的数字定义成DIGIT。一种是状态声明%START STATE，表示声明了一个新的状态，叫做STATE。最开始的时候的状态叫做INITIAL。

flex执行的逻辑是规则匹配。规则的含义是，在某个执行状态下满足正则式就执行对应的匹配规则。规则匹配的顺序是从上到下的。也就是同时满足AB两种规则，先执行A规则对应的操作，再执行B规则对应的操作。

flex生成的c文件是没有main函数的，main函数需要我们自己实现（本实验已经写好了），flex提供了接口给main函数调用，yylex()负责从文件流中进行读取分析，告诉main函数程序的下一个词是什么类型的。其内容保存在yylval类型的变量中。

再flex内部中，我们可以讲yylval的成员进行赋值以保存相关信息，最原始的匹配信息（比如”abc\n”匹配到了STRING，那么最原始的匹配信息就是”abc\n”）保存在yytext中，yymore的用途是，本次匹配的yytext会保存在下次匹配的yytext前面。

注释

CS143的实验要在cool语言上作为基础。对于一个语言来说，注释是必要的，但是对于编译器来说，注释是没必要去理解的。作为编译器的第一环，就需要略掉。cool语言的多行注释的语法是（**），单行注释的语法是–。

首先处理多行注释，按照实验文档中所示，当处于INITIAL状态的时候，遇到了（*，就代表遇到了注释，就要进入注释状态。（这个注释可能是嵌套的，还要保存这是第几层），遇到了*）就是代表推出注释。注释内部所有字符全部忽略。接着处理单行注释，当处于INITIAL状态的时候，遇到了–，就代表遇到了单行注释，就要进入单行注释状态。

字符串

cool语言也支持字符串，对于字符串的定义是从”开始的，当遇到”的符号，就代表进入了字符串状态。

对于一个字符串，首先字符串是不能包含’\\‘ ‘"‘ ‘\n’
字符串的定义是可以换行的，但是换行的时候一定要加\\
最后编译器要对转译字符进行翻译

cool语言要求，类型名大写，类型对应的实例是小写的。

flex编译出来的C语言文件

对flex编译出来的C语言文件进行简单的分析：最前面的一部分是flex自带的东西，对于每个flex文件都有的。还有一部分是flex中引导区的内容，编译的时候会原封不动地放进新生成的.c文件里面。下面是规则区，众所周知，词法分析是用DFA表示的，对于flex文件里面的每一个规则，都对应DFA的一个终止状态，当DFA进入到终止状态之后，就执行我们之前flex文件定义好的动作。下面的一部分是执行DFA操作的代码。

语法分析

复习一下！移进和规约

bison使用LR文法进行分析，分析的基础就基于移进和规约。比如说一个规则S->abc，当遇到a的时候就移进，遇到b的时候再移进，遇到c的时候再移进，这个时候移进到规则的尾部了。就可以规约成S。移进规约的基础是基于一个状态机的，状态机的每一个状态记录了可能被规约到的规则的集合，移进一个字母就会前往一个新的状态。比如说S->abc和T->abd，当遇到a的时候，这两个规则都可能被归约到，这个状态就是S->a.bc，T->a.bd。当进入了一个空状态（也就是说一个可能被归约到的规则都没有），就意味着，程序有语法错误。

文法规则

经过了flex的词法分析，现在进入文法分析的部分。flex将程序分解成了若干个token。这些token被称为终结符。当然与之相对应的是非终结符。这个在编译原理中学过。终结符是以%token定义的，非终结符是以%type定义的。在抽象语法树中，非终结符是语法树的非叶节点，终结符是语法树的叶结点。

属性

对于一个非终止符，需要有属性这一个概念来记录非终止符的相关信息。属性一般可以分为两种，一种叫做继承属性，这种属性一般是抽象语法树的上层结点直接赋予的属性；另外一种是综合属性，综合属性是抽象语法树下面的节点综合计算得来的属性。

对于bison，当执行S->abc的规约的时候，可以规定一个规约动作，当执行规约操作的时候，规约动作也就一起执行了。在bison的实际应用中，规约动作一般是对S进行综合属性的赋值，和对a，b，c的继承属性的赋值。

$$是什么

在bison的规约操作中，一定会遇到对属性的操作，但是对属性的操作怎么体现在代码上呢？这里使用$开头的元素代指终结符或者非终结符。比如说$$就代替被规约的那个，$1就代表规约的元素的第一个，以此类推。所有元素都代指一个数据类型，在前面的union中定义：

%union {
    Boolean boolean;
    Symbol symbol;
    Program program;
    Class_ class_;
    Classes classes;
    Feature feature;
    Features features;
    Formal formal;
    Formals formals;
    Case case_;
    Cases cases;
    Expression expression;
    Expressions expressions;
    char *error_msg;
}

其中二元组中，前面的具体类型名，后面是代指。比如说定义%type <classes> class_list就代表class_list对应的非终止符，其$类型的变量就是Classes。

规约冲突的化解

有可能会出现移进-规约和规约-规约的冲突，比如说S->ab和T->abc，那读入了ab，是规约呢还是移进呢？这种冲突一般是由语法的二义性所导致的。有一种解决办法是定义结合性。比如说 x op y op z。那么我们可以定义%left op或者%right op。%left指定左相关性（将x与y优先分组）
%right指定右相关性（将y与z优先分组）。还有优先级的问题，后定义的要比前面定义的优先级要高。比如说：

1 2	%left '+' '-' %left '*' '/'

就代表乘除的优先级要比加减高。

迭代定义的文法

如果要写一个一种文法，由0个或者若干个1组成的句子，那怎么写呢？一般的方法就是这样：s->1S|空。在这里也是一样，对于若干个class组成的cool文件，就是classes->class classes |

语义分析

前端的review

编译器设计可以分成两个部分，第一个部分是前端，另外一个部分是后端。前端的部分主要处理和语言相关的操作，比如说C语言，Java或者本课程所提到的cool语言。后端的部分主要处理和目的机有关的内容，比如说把代码生成到x86_linux上等等。现在对前端进行一个preview。

词法分析，将源代码分解成若干个token。
语法分析，将若干个token组成一个语法分析树。通过定义好的yyparse读取。
语义分析，分析语法树上的语义单元是否出现语义逻辑错误。通过定义好的yyparse读取。

语法分析主要分析语法结构，并不对语义逻辑进行分析，比如说鸡肉吃我，这明显是符合汉语言语法的，但是并不符合标准的语义。

类表

cool语言是面向对象的语言，代码是由一组类组成的，首先最重要的就是维护类的性质。这里有一个数据结构叫做类表，可以维护类。类表的核心是一张map，这张map记录了类名和类结构体的关系。所有关于类的语义错误都可以被记录下来。

在构建的时候可以进行两方面的检查：

名字不能定义成SELF_TYPE（比如说Int之类的）
不能重复定义一个类
必须存在一个叫做Main的类。

类表构建完了之后，所有的类的名字都是合法的了，现在要检查类的继承是不是合法的。因为类的继承是不能构成环的，比如说A继承B，那么B不能继承A。完成这种检查的方式很简单，从Main类做一次拓扑排序就好。判断完了这一部分，剩下的只需要检查两个：

不能继承整数 String等类
不能继承一个不存在的类

当然不会做拓扑排序的话还有一种方法，就是遍历每个类，对每个类进行溯源，直到Object，如果遇到和这个类一样的就报错。

方法表

现在把视角往下放，进入到方法表中，现在我们对每一个类构建一个方法表，static std::map<Symbol, MethodTable> methodtables;其中一个MethodTable是一个typedef SymbolTable<Symbol, method_class> MethodTable;我们发现这就是一个符号表！

正确的，对语义操作到这里我们发现，其实所有的表都是符号表！符号表记录了每一个区域的所有定义的符号的信息。编译原理课上其实学过，一个作用域就会有一个符号表，当编译器想要搜索一个符号究竟是啥意思的时候，就会从符号表上进行搜索。这里又提到了作用域，其实在编译器的实践中，作用域会体现在符号表上的层数上，比如说一个类是第一层，类里面的方法定义是第二层，等等。当语义分析来到了这一层之后，就要新建一个这一层的符号表。当语义分析脱离了这一层之后，这一层定义的符号表就没有用了。其实这就像个stack。

简单介绍以下本项目的符号表，本符号表通过一个叫做Scope的东东来进行作用域管理，当来一个新的作用域的时候，新建一个，当离开一个作用的时候，销毁一个，当要在该作用域加一个元素的时候，就可以使用Scope(scope,new_element)来添加。原理和栈一样！

现在已经对每个类都组织好了符号表，每个类都记录好所含的成员或者方法。组织的方法就是对类的Feature进行读取，这个Feature已经在语法分析的时候已经做好了，和上面的一样，还是对这个符号表进行检查。检查需要检查重载的性质。父类定义了个方法，子类的同名方法必须要和父类同名方法一致。

首先第一个问题，就是怎么获取到父类？这里使用之前构建好的类表的EetInheritance，代码浅显易懂，就是回溯！

std::list<Symbol> ClassTable::GetInheritancePath(Symbol type) {
    if (type == SELF_TYPE) {
        type = curr_class->GetName();
    }

    std::list<Symbol> path;

    // note that Object's father is No_class
    for (; type != No_class; type = m_classes[type]->GetParent()) {
        path.push_front(type);  
    }

    return path;
}

第二个问题，就是知道了父类，怎么指导父类有没有这个元素呢？可以自己实现一个lookup函数，因为父类也已经构建好了一组方法表，找就完事了。

DAT * lookup(SYM s)
{
   for(ScopeList *i = tbl; i != NULL; i=i->tl()) {
for( Scope *j = i->hd(); j != NULL; j = j->tl()) {
    if (s == j->hd()->get_id()) {
 return (j->hd()->get_info());
    }
}
   }
   return NULL;
}

上面贴出来的是人家写好的lookup，照着用就好了。其实也只是遍历而已。

最后一个问题就是怎么判断函数参数的个数，其实早在语法分析的时候已经把所有的参数信息全部放到Formal这里面去了。

属性表

本项目维护了一个属性表，这个属性表就是一个符号表，全局，仅此一个。这个符号表帮助我们进行最后的语义检查。

程序的总的框架还是类，对每个类进行分析。这里我们首先引入一个问题。类的继承构成Scope的迭代吗？其实构成的。首先想一下

{
    int a;
    {
        int a;
        int b；
    }
    // can I get the value of a here? which a? What about b?
}

在第一层括号是访问不到第二层的a的内容的。父类的作用域中无法访问到子类的元素，但是子类的作用域可以访问父类的元素，还可以重写。那么子类的作用域是不是像第二层的，父类的作用域是不是像第一层的！能理解这一点可以加深对作用域的思考。

好话说回属性表，组织好一个属性表之后，就需要依据属性表的元素进行分析了对类里面每个元素进行分析了！

check分成两部分，一部分是方法，一部分是属性。

首先谈谈方法吧，首先，方法内部也会存在大量的作用域嵌套！所以更新作用域表是很有必要的。因为进入了一个新方法的分析，就需要打开一个作用域。其次，方法的分析分为两部分，一个是对参数的分析，一个是对内容的分析。参数是一个参数表，需要对参数表的名字和类型进行分析。内容本质上，就是一个表达式。我们需要分析表达式的返回类型是不是和方法定义的匹配。

接着谈谈属性吧，一般来说，属性后面需要添加一个初始化语句，我们还需要对这个初始化语句进行分析，看看其类型。

表达式

无论是上面的方法表达式和初始化语句，都是表达式，对表达式的类型分析是非常有必要的，因为语言都是由一组组的表达式构成的，表达式的类型非常丰富，需要考虑到各种各样的表达式的构成。这一部分不表。

代码生成

终于结束了前端的工作，来到了后端的工作，在前端的时候，我们构建了一个语法树，根据语法树的信息判断了语义信息，验证了语义信息的正确性，现在我们根据这个语法树和相关的语义信息，进行代码生成。

堆和栈

堆和栈是从大一学习C语言开始就老生长谈的一个话题了，简单的说，堆和栈是存放数据的两个区域。堆呢，一般负责存放静态的，不咋变化的数据。栈呢，一般存放动态的，一直在变的数据。针对数据的相关性质，可以对数据分配不同的存放模式。对于堆中的数据，我们一般可以进行简单的管理，对于栈中的数据，我们可以临时使用一个sp寄存器当作指针进行访存。

代码生成的总体步骤

类表构建：还是和PA4一样的思路，对于类，首先构建一个类表来记录相关的信息。这个类表记录了系统已有的标准类和用户自己定义的类的一切信息。
全局变量：构建好了类的信息之后，第一步是构建全局变量。这一部分的操作是固定的，根据MIPS的定义，首先要建立基本类的定义，比如说Str，Int等类。以标签的形式存在于汇编语句中。
定义GC：方便内存管理
常量：记录各种各样的常量值，放在最前面。因为常量的值是不可以更改的。
类名：记录每个类及其子类。初始化相关的类。
构建虚表：将每个类的方法的入口地址记录下来。
原型对象构建：所有的类都会从一个原型对象继承属性和方法。
类的构造函数构建：
类的方法构建:

Environment

这个Environment其实就是各种变量存放的位置，对于一个变量a，我们可以在编译的时候对其进行空间的分配。由于MIPS（RISC-V）也一样的访存是以寄存器+偏移的形式进行间接访问管理的。所以说就在这里记录变量的地址了。那函数的入口地址怎么记录呢？

虚表

学过C++的应该知道虚函数，在这里，每一个method可以认为是一个虚函数。在调用虚函数的入口地址的时候，是需要调用晚期绑定类型对应的入口地址，这时候需要查找虚函数的入口地址，然后构造汇编指令。函只在C++中，如果要有virtual，我们就需要把它添加进vTable。并且每个类(而不是类实例)都有自己的虚表，因此vTable就变成了vTables。虚表存放的位置一般存放在模块的常量段中，从始至终都只有一份。

对于cool语言来说，也是需要虚表，我们默认所有函数，都是虚函数。所以说构建一个虚表是很有必要的。在实践中，我们使用code_dispatchTabs函数来记录虚函数的地址，每一个表项由类名，方法名和地址构成

表达式生成

分配了数据的位置，那可以进行代码的生成了。

在CS143的课程中，提到了表达式的生成。比如说有个表达式，a+b，那么我们可以递归的来计算，首先将a的值放到a0寄存器中，然后把a0寄存器的值放到栈顶，更新栈。接着把b的值计算出来放到a0，取栈顶的值放到t1，最后计算a0+t1。这是一个简单的表达式计算的方法。

这里体验了CT和RT的联动，CT指的是编译时所做的操作，RT指的是运行时所做的操作。上面说明的是CT的操作，而RT的操作就被抽象成了a的值的计算了！这样可以实现多态。

函数调用

在讲函数的调用之前，首先要明确一个概念，叫做caller和callee，假如说在main函数调用了用户自己写的函数a，那么main就是caller，callee就是a。Caller-saved register（又名易失性寄存器AKA volatile registers, or call-clobbered）用于保存不需要在各个调用之间保留的临时数据。Callee-saved register（又称非易失性寄存器AKA non-volatile registers, or call-preserved）用于保存应在每次调用中保留的长寿命值。当调用者进行过程调用时，可以期望这些寄存器在被调用者返回后将保持相同的值，这使被调用者有责任在返回调用者之前保存它们并恢复它们。

学过汇编的都知道，在进行函数调用的时候，执行过程是这样的：

caller将所有参数进行入栈
调用函数（j指令）
callee保存caller的fp
callee设置fp为sp
callee保存其他callee-save寄存器
callee将a0保存在s0中
callee执行函数体
callee回复之前保存的寄存器
恢复栈帧为调用前的状态
跳转ra保存的返回地址