# Compiler2

**Repository Path**: zhao-1264/compiler2

## Basic Information

- **Project Name**: Compiler2
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-04-06
- **Last Updated**: 2024-04-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README



## 编译原理实验一

**姓名：殷天润 学号：171240565 邮箱：171240565@smail.nju.edu.cn 班级：基础班** 

#### 项目环境:

1. GNU LINUX Realease: Ubuntu 18.04.3 LTS,5.3.0-40-generic
2. GCC version:7.5.0
3. GNU Flex version:2.6.4
4. GNU Bison version: 3.0.4

#### 实现功能

1.完成了必做内容+所有的选做内容

  - 通过flex实现了词法结构的分析
  - 在flex中通过添加正则表达式完成了词法错误的查找（包括浮点数，十六进制，八进制数，整数错误），主要是通过预测可能的错误实现然后书写相应的正则表达式实现的；在发现相应错误的时候仍然会返回相应的Token,比如0x9g会返回INT,并且我会把相应的值设置成0;	相应的错误会的正确显示；

- 通过flex实现了注释的忽略，主要是通过input()以及while语句完成的；在/*模式中我也专门判断了eof防止$/********$直到文件末尾产生的死循环；注释我选择直接忽略，不会返回Token;
- 通过bison完成了语法分析的部分；我参考了[bison的中文手册](https://blog.csdn.net/sirouni2003/article/details/400672#SEC96)，通过$prec,实现了MINUS(负号)的右结合优先级；
- 我完成了语法部分的一部分错误恢复，修改了yyerror，使得能够按照要求报错；
- 通过实现一个node多叉树结构体，我在flex里面构建终结符节点，在bison相应的位置构建非终结符节点，并且将终结符节点连接到相应的非终结符节点上，实现了多叉树；在bison中因为获得的变量数目是不确定的，我查询了RUNOOB使用了va_list类型;
- 为了能够让全都是注释的文件正确显示Program(eof行号)这个需求，我在flex文件中添加了全局flag:emptyflag,当处理到非注释的词法时会变成1，初始为0；我设置了一个全局的变量emptystart,在bison文件中的ExtDefList-->$\varepsilon$处更新为yylineno;当全是注释的时候用emptystart更新Program节点的行数值；
- 我完成了条件编译的debug辅助函数，通过DEBUGNOW,DEBUGBISONNOW两个宏定义控制显示一些信息；

#### 编译方法

1. 使用make 编译，make test测试相应test文件夹的对应文件，或者./parser test.cmm 测试

2. 使用

   > flex lexical.l
   > bison -d syntax.y
   > gcc main.c syntax.tab.c -lfl -ly -o parser;编译，通过./parser test.cmm测试相应的测试集合；

#### 反馈

1. 我觉得讲义讲bison 语法单元的位置的时候应该额外说明一下 %locations应该放在.y文件，否则会报错，相应的[stackoverflow回答](https://stackoverflow.com/questions/43419585/how-to-resolve-a-yylloc-undeclared-error);我觉得错误恢复这部分内容在阅读讲义的时候有些疑惑(当然相应的手册以及flex and bison这本书也写的不是很具体);如果相应的Appendix部分能够给一个去水印的版本方便复制粘贴(或者给一个文本文件之类的)，能够有效减少手打笔误的挫败感;
2. 我使用了计算机拔尖班共同维护的一个[测试库](https://github.com/massimodong/compilers-tests)进行了测试，感谢我的同学们；





## 编译原理实验二

**姓名：殷天润 学号：171240565 邮箱：171240565@smail.nju.edu.cn 班级：基础班** 

#### 项目环境:

1. GNU LINUX Realease: Ubuntu 18.04.4 LTS,5.3.0-40-generic
2. GCC version:7.5.0
3. GNU Flex version:2.6.4
4. GNU Bison version: 3.0.4

#### 实现功能

1. 完成了必做内容+所有的选做内容

2. 主要的实现包括符号表的实现和具体语义分析的实现;

3. 符号表的实现:

   1. 主要实现在symbol_table.c中,我有两个符号表,一个用来存包括: 函数名,结构体名,变量名在内的符号,称为符号表A;一个用来存放结构体的域名,称为符号表B；
   2. 符号表A和符号表B主体都是哈希表,使用讲义给的函数计算名字的哈希值;符号表B中的名字在进入符号表之前会进行额外的处理,即将结构体名添加到域名的后面;比如struct A{int a;};中的a填入符号表B之前会先变成aA然后再加入;这样的设计主要是考虑到域名的要求,检验错误15,方便查询;并且因为这样的组合名字最长到64位,我用的char指针来进行储存;
   3. 符号表A的主体是哈希表,我使用桶也就是一个链表来防止重名或者冲突;为了体现局部作用域,我另外开了一个全局的链表设计成了一个栈,每一次进入局部作用域的时候新建一个栈结点并且返回给上层;每一次插入元素的时候,首先插入到哈希表中(桶使用头插,新加入的元素在头部),然后再根据栈结点找到对应栈的末尾元素,然后把对应的元素加进去,这样的结构是类似于十字链表的;当退出局部作用域的时候,就根据栈尾的元素进行遍历,然后再哈希表里面删除对应的元素,free相应的空间,然后删除对应的栈结点;
   4. 符号表中的每一个node都有kind(区分变量,结构体名,符号名),lnext(哈希表链表),cnext(局部作用域链表),field(存储type,名字),ifdef(区分声明),depth(深度,确定作用域);
   5. 我有两个主要的查询符号表A的函数,一个是query_symbol,一个是query_symbol_exist,一个是返回当前depth的符号,一个是返回<当前depth的桶的第一个符号;这样可以解决全局符号,局部符号的使用问题;
   6. 另外我还在这个文件中实现了比较两种type类型的check_type函数,主要用于比较两种type是否结构等价;其中在和同学的讨论中,我认为array这个类型其实有两种等价标准,一个是弱等价,用于两个array的比较,只需要深度一样即可,比如int $a[99][100],b[3]$中,$b=a[97]$是合法的;还有一个是强等价,用于结构体结构等价比较中的array,此时结构体等价必然要求array的size和深度都要相同才行;
   7. 我额外实现了show_global_table();show_scope_table;一个是横向一个纵向的打印符号表A进行debug;

4. 语义分析部分:semantic.c中

   1. 主体结构: dfs; 我所有的语义分析都是基于lab1的语法树做的,宏观而言的工作是从语法树中获得信息,然后进行填表,查表分析;大部分调用的函数我都采用递归实现,少部分需要进行额外链表链接的部分,比如structspecifier部分我使用了循环实现,通过多个指针+while的结构完成了struct中链表的组装工作;

   2. 我在语义分析文件中维护了一个$depth\_$,初始也就是全局的时候是0,每进入一个compst加一,在插入符号表的时候都会携带这个信息来维护变量的作用域;通过$depth\_$和上述的用于符号表A的局部链表结构,我完成了局部作用域的实现;

   3. 对于每一个变量都有ifdef用来标记是声明还是定义,这个主要用于实现要求2.1,为了实现这个要求,我在插入每一个函数声明的时候，除了基本的类型，参数检查外，我会检查符号表中是否已经有了该函数的声明或者定义，如果有了就不再插入这个声明;因为我的符号表A的query是返回该桶中的第一个符号，这样的设计可以防止声明-定义-声明导致的误认为该函数还是声明的错误;

      另外当插入函数声明的时候，我还在symbol_table.c中开了一个链表用来记录声明过的函数,当程序检查完之后遍历这个链表检查所有声明过的函数是否被定义;

      我觉得要求2.1和错误类型2有一定的冲突，当出现声明a;调用a;定义a;这种结构的时候调用a如果抠字眼的话是犯了错误类型2的错误的,我是根据gcc的通用情况，不报这样的错误;**我觉得要求2.1的讲义中需要添加修改错误类型2为:函数调用时未经声明或者定义这样的字眼,更加严谨一点;**

   4. 我大部分的程序是根据产生式书写的递归形式的,比如ExtDef_s(...){xxx;type a=Specifier_s(...);FunDec_s(..a..);...}这种,略过不谈;我细说一下我用循环实现的structspecifier和vardec里面的数组部分；

      之所以使用循环是因为struct结构中需要进行额外的链表链接操作,和其他单独定义的变量不一样，缺点是代码可读性的降低和难以debug;这个循环结构我主要通过strcmp确定处于产生式的位置,然后通过两个FieldList类型的指针result,tempfield进行链表的获取,记录,链接,最后给struct的structure元素result这个指针;

      struct的遍历是顺序和产生式一致的,在vardec中的遍历顺序和要链接的链表顺序是相反的,具体而言对于$a[10][3][2]$访问的顺序是2->3->10->ID,但是要组成的是ID->10->3->2->INT这样的链表结构,因此我的方法是首先进行一次遍历获得深度,然后根据这个深度malloc一个type_list数组,然后再遍历一次填写数组,最后根据这个数组组装成链表;

5. 主要的bug:

   1. 我的strcmp可能有3-5次忘记写==,给我的警醒是以后写代码的时候要么宏定义,要么使用$0= =strcmp()$这样的结构;
   2. 一些理解的疏漏,我因此更新了好多次query和insert函数,用于获得更多的信息;
   3. 我在编写代码的时候为了防止疏漏加了很多assert(0);因此经常会有一些"漏网之鱼",触发assert(0);这种方法找到了很多报错了之后没有即使return的bug;

6. 感觉可以还可以改进的地方:

   1. 使用循环的地方可能有一些冗余,我感觉array处理的链表扫了3次不是那么高效,也许可以只扫两次;
   2. 代码太长了一点,我零零碎碎包括注释加起来2k3左右,实在是太不简洁了;

#### 编译方法

1. 使用make 编译，make test测试相应test文件夹的对应文件，或者./parser test.cmm 测试


#### 反馈

1. 再一次感谢同学们一起出的测试,帮助很多！
2. 讲义的一些问题写的不是很清楚，在群里也有讨论，如果可能的话下一版把这些讨论之后的案例加进去，这样讲义就更严谨了！







## 编译原理实验三

**姓名：殷天润 学号：171240565 邮箱：171240565@smail.nju.edu.cn 班级：基础班** 

#### 项目环境:

1. GNU LINUX Realease: Ubuntu 18.04.4 LTS,5.3.0-40-generic
2. GCC version:7.5.0
3. GNU Flex version:2.6.4
4. GNU Bison version: 3.0.4

#### 实现功能

1. 完成了必做内容+所有的选做内容

2. 主要的实现包括符号表的实现和具体语义分析的实现;

3. 符号表的实现:

   1. 主要实现在symbol_table.c中,我有两个符号表,一个用来存包括: 函数名,结构体名,变量名在内的符号,称为符号表A;一个用来存放结构体的域名,称为符号表B；
   2. 符号表A和符号表B主体都是哈希表,使用讲义给的函数计算名字的哈希值;符号表B中的名字在进入符号表之前会进行额外的处理,即将结构体名添加到域名的后面;比如struct A{int a;};中的a填入符号表B之前会先变成aA然后再加入;这样的设计主要是考虑到域名的要求,检验错误15,方便查询;并且因为这样的组合名字最长到64位,我用的char指针来进行储存;
   3. 符号表A的主体是哈希表,我使用桶也就是一个链表来防止重名或者冲突;为了体现局部作用域,我另外开了一个全局的链表设计成了一个栈,每一次进入局部作用域的时候新建一个栈结点并且返回给上层;每一次插入元素的时候,首先插入到哈希表中(桶使用头插,新加入的元素在头部),然后再根据栈结点找到对应栈的末尾元素,然后把对应的元素加进去,这样的结构是类似于十字链表的;当退出局部作用域的时候,就根据栈尾的元素进行遍历,然后再哈希表里面删除对应的元素,free相应的空间,然后删除对应的栈结点;
   4. 符号表中的每一个node都有kind(区分变量,结构体名,符号名),lnext(哈希表链表),cnext(局部作用域链表),field(存储type,名字),ifdef(区分声明),depth(深度,确定作用域);
   5. 我有两个主要的查询符号表A的函数,一个是query_symbol,一个是query_symbol_exist,一个是返回当前depth的符号,一个是返回<当前depth的桶的第一个符号;这样可以解决全局符号,局部符号的使用问题;
   6. 另外我还在这个文件中实现了比较两种type类型的check_type函数,主要用于比较两种type是否结构等价;其中在和同学的讨论中,我认为array这个类型其实有两种等价标准,一个是弱等价,用于两个array的比较,只需要深度一样即可,比如int $a[99][100],b[3]$中,$b=a[97]$是合法的;还有一个是强等价,用于结构体结构等价比较中的array,此时结构体等价必然要求array的size和深度都要相同才行;
   7. 我额外实现了show_global_table();show_scope_table;一个是横向一个纵向的打印符号表A进行debug;

4. 语义分析部分:semantic.c中

   1. 主体结构: dfs; 我所有的语义分析都是基于lab1的语法树做的,宏观而言的工作是从语法树中获得信息,然后进行填表,查表分析;大部分调用的函数我都采用递归实现,少部分需要进行额外链表链接的部分,比如structspecifier部分我使用了循环实现,通过多个指针+while的结构完成了struct中链表的组装工作;

   2. 我在语义分析文件中维护了一个$depth\_$,初始也就是全局的时候是0,每进入一个compst加一,在插入符号表的时候都会携带这个信息来维护变量的作用域;通过$depth\_$和上述的用于符号表A的局部链表结构,我完成了局部作用域的实现;

   3. 对于每一个变量都有ifdef用来标记是声明还是定义,这个主要用于实现要求2.1,为了实现这个要求,我在插入每一个函数声明的时候，除了基本的类型，参数检查外，我会检查符号表中是否已经有了该函数的声明或者定义，如果有了就不再插入这个声明;因为我的符号表A的query是返回该桶中的第一个符号，这样的设计可以防止声明-定义-声明导致的误认为该函数还是声明的错误;

      另外当插入函数声明的时候，我还在symbol_table.c中开了一个链表用来记录声明过的函数,当程序检查完之后遍历这个链表检查所有声明过的函数是否被定义;

      我觉得要求2.1和错误类型2有一定的冲突，当出现声明a;调用a;定义a;这种结构的时候调用a如果抠字眼的话是犯了错误类型2的错误的,我是根据gcc的通用情况，不报这样的错误;**我觉得要求2.1的讲义中需要添加修改错误类型2为:函数调用时未经声明或者定义这样的字眼,更加严谨一点;**

   4. 我大部分的程序是根据产生式书写的递归形式的,比如ExtDef_s(...){xxx;type a=Specifier_s(...);FunDec_s(..a..);...}这种,略过不谈;我细说一下我用循环实现的structspecifier和vardec里面的数组部分；

      之所以使用循环是因为struct结构中需要进行额外的链表链接操作,和其他单独定义的变量不一样，缺点是代码可读性的降低和难以debug;这个循环结构我主要通过strcmp确定处于产生式的位置,然后通过两个FieldList类型的指针result,tempfield进行链表的获取,记录,链接,最后给struct的structure元素result这个指针;

      struct的遍历是顺序和产生式一致的,在vardec中的遍历顺序和要链接的链表顺序是相反的,具体而言对于$a[10][3][2]$访问的顺序是2->3->10->ID,但是要组成的是ID->10->3->2->INT这样的链表结构,因此我的方法是首先进行一次遍历获得深度,然后根据这个深度malloc一个type_list数组,然后再遍历一次填写数组,最后根据这个数组组装成链表;

5. 主要的bug:

   1. 我的strcmp可能有3-5次忘记写==,给我的警醒是以后写代码的时候要么宏定义,要么使用$0= =strcmp()$这样的结构;
   2. 一些理解的疏漏,我因此更新了好多次query和insert函数,用于获得更多的信息;
   3. 我在编写代码的时候为了防止疏漏加了很多assert(0);因此经常会有一些"漏网之鱼",触发assert(0);这种方法找到了很多报错了之后没有即使return的bug;

6. 感觉可以还可以改进的地方:

   1. 使用循环的地方可能有一些冗余,我感觉array处理的链表扫了3次不是那么高效,也许可以只扫两次;
   2. 代码太长了一点,我零零碎碎包括注释加起来2k3左右,实在是太不简洁了;

#### 编译方法

1. 使用make 编译，make test测试相应test文件夹的对应文件，或者./parser test.cmm 测试


#### 反馈

1. 再一次感谢同学们一起出的测试,帮助很多！
2. 讲义的一些问题写的不是很清楚，在群里也有讨论，如果可能的话下一版把这些讨论之后的案例加进去，这样讲义就更严谨了！







## 编译原理实验四

**姓名：殷天润 学号：171240565 邮箱：171240565@smail.nju.edu.cn 班级：基础班** 

#### 项目环境:

1. GNU LINUX Realease: Ubuntu 18.04.4 LTS,5.3.0-40-generic,Xming
2. GCC version:7.5.0
3. GNU Flex version:2.6.4
4. GNU Bison version: 3.0.4
5. spim

#### 实现功能

1. 必做内容

2. 大体介绍:在前几次实验的基础上将实验三的中间代码翻译成了MIPS32的伪指令;翻译的方式是根据上一个实验的线性ir结构进行逐条翻译,分配寄存器的方法是朴素寄存器分配,也就是所有的局部变量都会压入栈中,然后需要时取出/修改的操作;

3. 栈的维护实现方式:

   我使用一个数据结构stack_node模仿了栈中元素,并且记录了和栈顶的偏移的值(取负);我通过stack_no的结构体的stack_sp,stack_fp来模仿当前栈的栈顶和栈底;每一次进入新的函数的时候都会把stack_fp之后的内容清空并且重新初始化stack_sp,stack_fp,同时我会对这个函数做一次扫描,统计要开辟的占空间一次性进行开辟,并且确定好每个变量的offset,存入stack_node链表中,对于函数的参数,我是在开辟局部变量之前确定的,因为对于一个函数,它的参数应该是调用它的对象实现压入栈的,因此只需要做好offset的关联工作就可以了;

   这个结构体和实际的Mips32的栈的区别主要在于,MIPS32的栈的fp其实需要用一个栈来存储,但是因为扫描函数仅仅一遍不需要递归,所以实现我的结构体的时候不需要存储stack_fp,每一次都初始化到stack_head->next就行了;

4. 我额外的用来debug的trick:

   我使用了宏来控制注释和输出,有两个宏记录在common.h中,SI_DEBUG启动之后可以打印我的栈结构的offset,SI_DEBUG2打开之后会将中间代码以注释的形式插入到一条条伪指令中,并且会注释掉原来的read部分的“Enter an integer:\n";

5. 因为我L3优化的有限,加上lab4没有使用更好的寄存器分配方式,代码空间和时间都需要比较大的宽容;

#### 编译方法

使用make编译,make test生成out.s,使用spim即可执行

#### 反馈

1. 感觉讲义的朴素寄存器那块可能需要进一步讲一下栈结构,一开始我用静态的方式在.data区开辟内存做的,结果当然禁不起递归的考验!虽然这块确实非常简单,但是可能还是需要提示一下方向减少不必要的时间?