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
嵌套即可触发错误。
致谢:
- 感谢各位助教大大的解答与帮助;
- 感谢黄秉焜、周涛同学提供两个大型测试用例,感谢董杨静同学提供的测试脚本。
Loading Comments By Disqus