张天昀的个人博客

编译原理

Lab1 Report

1. 文件结构

Code文件夹下不同代码文件的功能如下所示：

main.c：编译程序的主入口，打开文件并调用yyparse函数
token.[hc]：与YYSTYPE、YYLTYPE、YYLVAL类型的相关定义
tree.[hc]：定义语法树（STNode）数据类型与相关函数
lexical.l：flex程序
syntax.y：bison程序

2. 数据结构

语法树的结点数据结构与各个成员的说明如下：

struct STNode {
  int line, column;             // 语法单元的出现的行、列号
  int token, symbol;            // 词法单元序号和语法单元序号
  const char* name;             // 语法单元的名称
  bool empty;                   // 语法单元是否为空串
  union {
    unsigned int    ival;       // 整数数值
    float           fval;       // 浮点数数值
    enum ENUM_RELOP rval;       // 关系运算符枚举数值
    char            sval[64];   // 字符串值
  };
  struct STNode *child, *next;  // 多叉树的第一个子结点与下一个同级结点
};

其中有一个需要特殊处理的地方就是token和symbol。Flex在进行词法分析后返回的词法单元序号会经过bison翻译后得到语法单元序号，使用语法单元序号才能在yytname中找到对应的语法单元名称字符串。这个过程是通过如下方式实现的：

在flex扫描到词法单元后，创建语法树结点并设置symbol = -1。
在bison进行规约时，左部结点的token = -1。遍历右部时，如果发现右部结点symbol == -1，则调用YYTRANSLATE宏获得对应的符号序号。然后查询yytname表获得符号名称的字符串。

3. 词法分析

词法分析部分使用了多个宏定义函数来保持代码简洁，并通过FLEXDEBUG宏控制词法分析的调试模式：若开启调试，则使用lexical.l中的函数，并会打印具体的词法单元；若关闭调试则不会有额外的输出信息，词法单元作为函数返回值传递给bison进行后续处理。

使用到的宏的含义如下（前两个在lexical.l中定义，后三个在token.h中定义）：

TOKENIFY(t)：
- 调试模式打开时，直接打印词法单元；
- 调试模式关闭时，创建一个新的语法树节点并初始化，然后将词法单元的类型值t返回。
YY_USER_ACTION：更新yylloc中的位置信息。
GETYYLVAL(SPEC, TYPE)：将yytext中的字符串转化成对应类型的值，作为函数返回值返回。
SETYYLVAL(TYPE)：将上面这个宏函数的返回值赋值给yylval变量。
ACTYYLVAL(TYPE)：对yytext的值采取特殊操作（如文本拷贝）。

4. 语法分析

语法分析部分也通过宏YYDEBUG控制调试模式，并对yyparse函数打包实现了yydebug变量的注入，避免在main.c文件中单独定义调试宏。

int yyparse_wrap() {  // 在syntax.y文件中定义
#if YYDEBUG
  yydebug = 1;        // 如果启用调试，则注入yydebug
#endif
  return yyparse();   // 调用yyparse开始分析输入流
}

语法分析部分同样也使用了宏函数YYLLOC_DEFAULT（在syntax.y中定义）来重定义默认的处理方式，在处理过程中不仅更新了符号的位置信息，还为非终结符号创建了语法树结点、并将右部的所有节点添加为左部结点的子树。面对空的产生式右部时，直接使用yylineno和yycolumn获取位置信息，可以处理所有空串的情况，没有为空程序这个特殊情况添加单独的处理函数。

由于所有的产生式都会调用默认的相同的处理函数YYLLOC_DEFAULT，所以只有Program这个非终结符号符号有额外的操作，整个语法定义部分非常简洁；处理到Program非终结符号时，将当前的语法树结点赋值为语法树的根结点，语法分析结束后即可直接递归打印语法树。

5. 错误恢复

对于文法错误，如果是出现了非法的数字，则按照如下规则处理：

抛出A类型错误，并忽略该行后续的其他错误（一行只报一条）；
不从yytext中获取值，并将这个符号强制作为ID处理（因为ID的在语法中的通用性最强）。

在语法分析时，如果出现语法错误则尝试从对应的终结符号进行同步；但特别的是，如果出现了对称符号漏打一个的情况，会按照如下方式处理：

尝试从对应的终结符号同步：如foo = bar[3[4];，此为最好的情况
尝试从;处同步（Exp会占用一个;，因此会舍弃两条语句）：如foo = bar[3;
尝试从}处同步：如函数末尾出现错误，由于会舍弃多个函数体，后续无法继续分析。此为最坏的情况。

6. 实验的感想、问题与致谢

实验一的感想：

Flex和Bison的耦合性过高，外加没有找到好用的语法高亮插件，写起来很累。
如果是自己写编译器、其他程序，我会选择遇到错误就报错退出，而不是带着错误继续分析。

遇到的问题与解决方案：

在macOS环境下链接flex库需要使用-ll选项而不是-lfl，后改用Ubuntu 19.10作为实验环境。
Bison的%error-verbose选项在新版本中被弃用，因此没有使用详细的语法错误输出。
Bison处理递归过深的情况时会抛出memory exhausted的错误。大约5000层CompSt嵌套即可触发错误。

Memory Exhausted

致谢：

感谢各位助教大大的解答与帮助；
感谢黄秉焜、周涛同学提供两个大型测试用例，感谢董杨静同学提供的测试脚本。