编译原理

Lab1 Report

2020-03-13 00:00 CST
2020-04-11 00:10 CST
CC BY-NC 4.0

1. 文件结构

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

  • main.c:编译程序的主入口,打开文件并调用yyparse函数
  • token.[hc]:与YYSTYPEYYLTYPEYYLVAL类型的相关定义
  • 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;  // 多叉树的第一个子结点与下一个同级结点
};

其中有一个需要特殊处理的地方就是tokensymbol。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中定义)来重定义默认的处理方式,在处理过程中不仅更新了符号的位置信息,还为非终结符号创建了语法树结点、并将右部的所有节点添加为左部结点的子树。面对空的产生式右部时,直接使用yylinenoyycolumn获取位置信息,可以处理所有空串的情况,没有为空程序这个特殊情况添加单独的处理函数。

由于所有的产生式都会调用默认的相同的处理函数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

致谢:

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