前言
最近被某学长介绍了毕昇杯编译器比赛, 有点感兴趣, 遂开始用 C 自己实现, 然后就:
还是 Java 香!
本文记录了我用 Bison 和 Flex 来构建 SysY2021 语言前端的尝试.
Show me the code.
前置声明: 大体的代码架构和使用方法在最后, 可以交叉着看.
lex
Lex 可以将输入按照正则表达式匹配然后执行对应的代码. 这个代码一般是直接返回对应 token 的类型; 如果一个 token 还有附加信息, 那么你也可以在代码里把它保存在哪个全局变量里面.
它会生成一个文件:
lex.yy.c: 包含了 yylex() 的定义
/* src/frontend/lexer.lex */
/* ==========================================================
* 一个 lex 文件大概由三部分组成
* 第一部分是下面这个被 %{ ... %} 框起来的部分
* 这里可以写一些 C 代码, 它们会被原封不动的拷贝进生成的 C 文件里
* 一般是写头文件和一些下面要用到的函数
* ========================================================== */
%{
#include "util.h"
#include "ast.h"
/* 这个是 Yacc 自动生成的头文件, 包含了 Lex 应该返回的枚举的定义和 yylval */
#include "parser.tab.h"
%}
/* ==========================================================
* 第二部分就是用来放传递给 lex 的选项的部分
* 选项以%开头, 紧跟着选项名, 后接参数
* ========================================================== */
/* 这个选项表示不需要使用 yywarp */
%option noyywrap
/* 这个选项表示 C_COMMENT 是一个状态 */
%x C_COMMENT
/* ==========================================================
* 第三部分就是每一个 token 的定义
* 包含在 %% ... %% 内
* 每一行都按如下格式: <正则表达式> <动作>
* 一般来讲每当读完一个 token, <动作> 部分就应该 return 一个 int 值, 它将作为 yylex() 的返回值
* 对于携带特殊信息的 token, 我们一般把值存进全局变量 yylval 里供程序的其他部分使用
* ========================================================== */
%%
/* 忽略空白 */
" " { continue; }
\t { continue; }
\n { continue; }
/* 处理单行注释 */
"\\".*\n { continue; }
/* 处理 C 风格的注释 */
/* 这是 lex 暴露出来的给我们手动控制 DFA 节点的写法 */
/* 当碰到 "/*" 时就进入 C_COMMENT 状态 */
"/*" { BEGIN(C_COMMENT); }
/* 当在状态 C_COMMENT 并且碰到 "*/" " 时就回到正常状态 INITIAL (lex 自己提供的) */
<C_COMMENT>"*/" { BEGIN(INITIAL); }
/* 当在状态 C_COMMENT 时, 输入一切字符都当不存在 */
<C_COMMENT>. { continue; }
/* 这里的状态处理没有考虑嵌套注释; 如果要支持的话可以在全局变量里保存一个变量 level 表示注释的层级,
* 每次碰到新的 "/*" 就 level++, "*/" " 就 level--; 当 level == 0 时才退出 C_COMMENT 状态 */
/* 关键字 */
const { return T_CONST; }
int { return T_INT; }
void { return T_VOID; }
if { return T_IF; }
else { return T_ELSE; }
while { return T_WHILE; }
break { return T_BREAK; }
continue { return T_CONTINUE; }
return { return T_RETURN; }
/* 符号, 对于特殊的字符可以用双引号括起来, 这样它们不会被当成正则表达式里的元字符, 也不需要转义 */
"," { return T_COMMA; }
";" { return T_SEMICOCLON; }
"(" { return T_PAREN_LEFT; }
")" { return T_PAREN_RIGHT; }
"[" { return T_SQU_LEFT; }
"]" { return T_SQU_RIGHT; }
"{" { return T_CURLY_LEFT; }
"}" { return T_CURLY_RIGHT; }
"=" { return T_ASSIGN; }
"+" { return T_ADD; }
"-" { return T_SUB; }
"*" { return T_MUL; }
"/" { return T_DIV; }
"%" { return T_MOD; }
"==" { return T_EQ; }
"!=" { return T_NOT_EQ; }
/* 如果有多个匹配, lex 会匹配比较靠前的规则 */
"<=" { return T_LESS_EQ; }
">=" { return T_GREATER_EQ; }
"<" { return T_LESS; }
">" { return T_GREATER; }
"!" { return T_LOG_NOT; }
"&&" { return T_LOG_AND; }
"||" { return T_LOG_OR; }
putf { return T_PUTF; }
/* 标识符 */
[a-zA-Z_][0-9a-zA-Z_]* { yylval.sval = String(yytext); return T_IDENT; }
/* 数字, 十进制, 八进制和十六进制字面量 */
[1-9][0-9]* { yylval.ival = (int)strtol(yytext, 0, 0); return T_NUM; }
0[0-7]* { yylval.ival = (int)strtol(yytext, 0, 0); return T_NUM; }
0(x|X)[0-9a-fA-F]* { yylval.ival = (int)strtol(yytext, 0, 0); return T_NUM; }
/* 字符串字面量 */
"\"".*"\"" { yylval.sval = String(yytext); return T_STR; }
/* 对于不符合以上任何匹配的, 做一个错误处理 */
. { panic("Unknown token: %s", yytext); }
%%
另外, 如果你需要在别的对正则表达式有内建支持的语言(比如Python)里快速做一个 lexer 的话, 你可以这样干:
import re
from itertools import starmap
from typing import *
def sub_regax(token_type: str, reg: str) -> str:
# 命名组合, 参见: https://docs.python.org/zh-cn/3/library/re.html#regular-expression-syntax
return f'(?P<{token_type}>{reg})'
# token 类型要求首字母大写, token 附加数据的要求首字母小写
lexer_rules = [
('LeftBracket', r'\(' ),
('RightBracket', r'\)' ),
('Number', r'(?P<num>[0-9]+)' ),
('String', r'"(?P<str>.*?)"' ),
('Identifier', r'(?P<id>[a-zA-Z][a-zA-Z0-9]*)')
]
# 直接把所有 token 对应的正则表达式都并起来, 然后编译一个大的
# 并且希望你那个语言的正则表达式的编译可以生成最优的 DFA
lexer_reg = re.compile('|'.join(starmap(sub_regax, lexer_rules)))
# 找到 d 里面 第一个 d[key] 不为 None 且首字母大写的, 并且返回 key
def get_key(d: dict[str, Union[str, Any]]) -> str:
for k, v in d.items():
if v and k[0].isupper():
return k
raise RuntimeError(f'All value in dict is none: {d}')
def regenize(inputs: Iterable[str]) -> Iterable[tuple[str, Any]]:
for input in inputs:
for tok_match in lexer_reg.finditer(input):
# tok_match.groupdict() 返回一个 dict, 里面大概是这样的:
# {'LeftBracket': None, 'RightBracket': None, 'Number': None, 'String': None, 'Identifier': 'sad0', 'num': None, 'id': 'sad0', 'str': None}
type = get_key(tok_match.groupdict())
if type in ['LeftBracket', 'RightBracket']:
yield (type, None)
elif type == 'Number':
yield (type, tok_match.group('num'))
elif type == 'String':
yield (type, tok_match.group('str'))
elif type == 'Identifier':
yield (type, tok_match.group('id'))
else:
raise RuntimeError(f'Unknown token type: {type}')
if __name__ == '__main__':
prog = '(define (p2 x) (mul x x)) \n (p2 234)'
for tok, data in regenize(prog.split('\n')):
print(tok, data)
# Output:
'''
LeftBracket None
Identifier define
LeftBracket None
Identifier p2
Identifier x
RightBracket None
LeftBracket None
Identifier mul
Identifier x
Identifier x
RightBracket None
RightBracket None
LeftBracket None
Identifier p2
Number 234
RightBracket None
'''
yacc
YACC 实现了一个 LALR(1) 的 SDT 的 parser. 每一个 Non-terminal, 在 reduce 的时候, 都会执行 reduce 成那个符号的规则对应的语义动作. 每一个 Non-terminal 都有且仅有一个属性, 这个属性可以在语义动作里通过 $ 来获取.
在内存充裕的现代, 我们一般可以直接生成整颗 AST 保存在内存中, 所以一般来讲 YACC 的语义动作里都是构建 AST 的代码.
它会生成两个文件:
parser.tab.h: 定义了所有 terminal 的枚举, 声明了 yyparser() 和 yylval, 一般我们会让 lex 和要调用 yyparser 的文件包含这个文件parser.tab.c: 定义了 yyparser() 和 yylval
/* src/frontend/parser.y */
/* ==========================================================
* 一个 yacc 文件跟 lex 文件一样由三个部分组成
* %{ ... %} ... %% ... %%
* 三个部分作用也大同小异
* 区别就在于 yacc 有很多选项可以调, 所以中间部分比较长
* ========================================================== */
%{
#include "util.h"
#include "ast.h"
#include "parser.tab.h"
/* 声明 yylex() 函数 */
extern int yylex();
/* 当出现错误时 yacc 生成的函数会调用这个东西 */
#define yyerror(s) panic("Yacc error: %s", s);
/* 如果 YYDEBUG 为 1, 那么 yacc 生成的 parser 在运行时会输出很多信息 */
#ifdef DEBUG
# undef YYDEBUG
# define YYDEBUG 1
#else
# undef YYDEBUG
# define YYDEBUG 0
#endif
/* 用来保存最后结果供外界使用的变量 */
extern Ast_List result;
%}
/* ==========================================================
* 第二部分, 在这里要写:
* 1) yylval 的类型
* 2) 各个 token(terminal) 对应于 yylval 的哪个 field
* 3) 各个 symbol(non-terminal) 对应于 yylval 的哪个 field
* 4) 起始规则
* ========================================================== */
/* 设置 yylval 为枚举类型, 有下面的这些 field */
%union {
int ival;
string sval;
Ast_Node node;
Ast_List node_list;
}
/* 设置 token 的相关属性和别名
* %token <<yylval 的 field 名>> [<token 的枚举名> ["<token 名字的替代>"]]+ */
/* 这里设置了 "如果 lexer 读到一个标识符, 那么 yylex() 应该返回一个 T_IDENT, 并且在 yylval 里的 sval 域将会有一个值;
* 在下文的规则里见到 "identifier" 就当成终结符号 标识符" */
/* 要注意这里的 <token 名字的替代>必须用双引号而不是单引号, 单引号的字符(比如'c')会被当成数字
* 意思就变成了 "当 yylex() 返回 'c' 时就意味着获得了这个 token" 而不是设置别名
* 因此, Yacc 为 token 生成的枚举类型里首个枚举值是以 256 开始的 */
%token <sval> T_IDENT "identifier" T_STR "string literal" T_PUTF "putf"
%token <ival> T_NUM "number literal"
/* 这里设置了 "如果 lexer 读到一个const, 那么 yylex() 应该返回一个 T_CONST, 并且此时 yylval 里不确定有啥;
* 在下文的规则里见到 "const" 就当成终结符号 const" */
%token T_CONST "const" T_INT "int" T_VOID "void"
%token T_IF "if" T_ELSE "else" T_WHILE "while"
%token T_BREAK "break" T_RETURN "return" T_CONTINUE "continue"
%token T_COMMA "," T_SEMICOCLON ";"
%token T_PAREN_LEFT "(" T_PAREN_RIGHT ")"
%token T_SQU_LEFT "[" T_SQU_RIGHT "]"
%token T_CURLY_LEFT "{" T_CURLY_RIGHT "}"
%token T_ASSIGN "="
%token T_ADD "+" T_SUB "-" T_MUL "*" T_DIV "/" T_MOD "%"
%token T_EQ "==" T_NOT_EQ "!=" T_LESS "<"
%token T_LESS_EQ "<=" T_GREATER ">" T_GREATER_EQ ">="
%token T_LOG_NOT "!" T_LOG_AND "&&" T_LOG_OR "||"
/* 设置 non-terminal 的相关属性 */
/* 这里设置 Non-terminal CompUnit 的规则求值之后在 yylval 的 node_list 域里有一个合法的值 */
%type <node_list> CompUnit
%type <node> FuncDef FuncParam
%type <node_list> FuncParamList
%type <node> Decl
%type <node> DefOne
%type <node_list> DefAny
%type <node> InitVal
%type <node_list> ArrInit
%type <node> Stmt Block IfStmt WhileStmt PutfForm
%type <node_list> BlockItemList
%type <node> PrimaryExp UnaryExp MulExp AddExp
%type <node> RelExp EqExp LAndExp LOrExp Cond Exp
%type <node> LVal
%type <node_list> ArrIdx FuncArgs
/* 设置起始规则为 CompUnit 对应的规则 */
%start CompUnit
%%
/* ==========================================================
* 第三部分, 在这里要写各个 Non-terminal 对应的产生式
* 只支持基本的 BNF, 不支持 EBNF
* ========================================================== */
/* 规则是, 如果碰到了 Decl CompUnit, 就规约成一个 CompUnit, 同时执行后面的语义动作
* 语义动作里, 用 $$ 指代产生式头代表的变量, $n 表示产生式体里第 n 个元素代表的变量
* 这里的语义动作会"大概"被翻译成: yylval.node_list = result = cons_Ast(yylval.node, yylval.node_list);
* 单独拎一个 result 出来是因为当 yyparse() 函数结束之后 yylval 会被回收,
* 也就是说不能通过 yylval 获取最后的结果了, 所以最后的结果要另外存一份 */
CompUnit: Decl CompUnit { $$ = result = cons_Ast($1, $2); }
| FuncDef CompUnit { $$ = result = cons_Ast($1, $2); }
| /* empty */ { $$ = result = 0; }
;
//---------------- Declaration & Definition ----------------------------
/* 在产生式体里只有一个 Block 的情况下, 可以用$<Non-terminal名字>来指代那个元素的变量
* 这里的语义动作会"大概"被翻译成: yylval.node = ast_FuncDef(FRT_INT, yylval.sval, yylval.node, yylval.node);
* 产生式体里的每一个 Symbol 都有它自己的 yylval, 用$塞进去的那个都是保存着那个 Symbol 当时被求出的那个的 yylval 的值 */
FuncDef: "int" T_IDENT "(" FuncParamList ")" Block { $$ = ast_FuncDef(FRT_INT, $2, $4, $Block); }
| "void" T_IDENT "(" FuncParamList ")" Block { $$ = ast_FuncDef(FRT_VOID, $2, $4, $Block); }
;
FuncParamList: FuncParam { $$ = cons_Ast($1, 0); }
| FuncParam "," FuncParamList { $$ = cons_Ast($1, $3); }
| /* empty */ { $$ = 0; }
;
FuncParam: "int" LVal { $$ = $LVal; }
;
Decl: "const" "int" DefAny ";" { $$ = ast_Decl(true, $DefAny); }
| "int" DefAny ";" { $$ = ast_Decl(false, $DefAny); }
;
DefOne: LVal { $$ = ast_VarDef($1, 0); }
| LVal "=" InitVal { $$ = ast_VarDef($1, $3); }
;
DefAny: DefOne { $$ = cons_Ast($1, 0); }
| DefOne "," DefAny { $$ = cons_Ast($1, $3); }
;
InitVal: Exp { $$ = ast_InitExp($Exp); }
| "{" ArrInit "}" { $$ = ast_InitArr($2); }
;
ArrInit: InitVal { $$ = cons_Ast($1, 0); }
| InitVal "," ArrInit { $$ = cons_Ast($1, $3); }
;
//---------------------------- Stmt ---------------------------
/* 语义动作留空的话, 它默认是: { $$ = $1; } */
Stmt: Block
| IfStmt
| WhileStmt
| PutfForm
| Exp ";" { $$ = ast_StmtExp($Exp); }
| LVal "=" Exp ";" { $$ = ast_StmtAssign($1, $3); }
| ";" { $$ = ast_StmtEmpty(); }
| "break" ";" { $$ = ast_StmtBreak(); }
| "continue" ";" { $$ = ast_StmtContinue(); }
| "return" ";" { $$ = ast_StmtReturn(0); }
| "return" Exp ";" { $$ = ast_StmtReturn($Exp); }
;
Block: "{" BlockItemList "}" { $$ = ast_Block($2); }
;
BlockItemList: Decl BlockItemList { $$ = cons_Ast($1, $2); }
| Stmt BlockItemList { $$ = cons_Ast($1, $2); }
| /* Empty */ { $$ = 0; }
;
IfStmt: "if" "(" Cond ")" Stmt { $$ = ast_StmtIf($Cond, $5, 0); }
| "if" "(" Cond ")" Stmt "else" Stmt { $$ = ast_StmtIf($Cond, $5, $7); }
;
WhileStmt: "while" "(" Cond ")" Stmt { $$ = ast_StmtWhile($Cond, $Stmt); }
;
PutfForm: "putf" "(" T_STR "," FuncArgs ")" ";" { $$ = ast_ExpPutf($3, $5); }
;
//----------------- Expression ----------------------------
Exp : AddExp;
Cond: LOrExp;
/* 可以看到, 如果在上面第二部分对每一个终结符设置了好看的别名的话, 就能极大地提高规则的可读性
* 比如这条规则我们就不用写 LOrExp T_OR LAndExp 而可以向下面这样写 */
LOrExp: LAndExp
| LOrExp "||" LAndExp { $$ = ast_ExpOp(OP_LOG_OR, $1, $3); }
;
LAndExp: EqExp
| LAndExp "&&" EqExp { $$ = ast_ExpOp(OP_LOG_AND, $1, $3); }
;
EqExp: RelExp
| EqExp "==" RelExp { $$ = ast_ExpOp(OP_EQ, $1, $3); }
| EqExp "!=" RelExp { $$ = ast_ExpOp(OP_NOT_EQ, $1, $3); }
;
RelExp: AddExp
| RelExp "<" AddExp { $$ = ast_ExpOp(OP_LESS, $1, $3); }
| RelExp "<=" AddExp { $$ = ast_ExpOp(OP_LESS_EQ, $1, $3); }
| RelExp ">" AddExp { $$ = ast_ExpOp(OP_GREATER, $1, $3); }
| RelExp ">=" AddExp { $$ = ast_ExpOp(OP_GREATER_EQ, $1, $3); }
;
AddExp: MulExp
| AddExp "+" MulExp { $$ = ast_ExpOp(OP_ADD, $1, $3); }
| AddExp "-" MulExp { $$ = ast_ExpOp(OP_SUB, $1, $3); }
;
MulExp: UnaryExp
| MulExp "*" UnaryExp { $$ = ast_ExpOp(OP_MUL, $1, $3); }
| MulExp "/" UnaryExp { $$ = ast_ExpOp(OP_DIV, $1, $3); }
| MulExp "%" UnaryExp { $$ = ast_ExpOp(OP_MOD, $1, $3); }
;
UnaryExp: PrimaryExp
| T_IDENT "(" FuncArgs ")" { $$ = ast_ExpCall($1, $3); }
| "+" UnaryExp { $$ = ast_ExpOp(OP_SUB, $2, 0); }
| "-" UnaryExp { $$ = ast_ExpOp(OP_ADD, $2, 0); }
| "!" UnaryExp { $$ = ast_ExpOp(OP_LOG_NOT, $2, 0); }
;
PrimaryExp: "(" Exp ")" { $$ = $2; }
| LVal { $$ = ast_ExpLval($1); }
| T_NUM { $$ = ast_ExpNum($1); }
;
LVal: T_IDENT ArrIdx { $$ = ast_Lval($1, $2); }
;
ArrIdx: ArrIdx "[" Exp "]" { $$ = cons_Ast($3, $1); }
| /* empty */ { $$ = 0; }
;
FuncArgs: Exp { $$ = cons_Ast($1, 0); }
| Exp "," FuncArgs { $$ = cons_Ast($1, $3); }
| /* empty */ { $$ = 0; }
;
使用方法
我选择的目录结构大概是这样的:
.
├── build.sh
└── src
├── ast.h # AST 对应的构造函数
├── frontend
│ ├── lexer.lex # 我们写的 Lex 文件
│ ├── lex.yy.c # Lex 生成的文件
│ ├── parser.tab.c # Yacc 生成的文件
│ ├── parser.tab.h # Yacc 生成的文件
│ └── parser.y # 我们写的 Yacc 文件
├── main.c
└── util.h # 杂项工具
主函数:
// main.c
#include "util.h"
#include "ast.h"
#include "frontend/parser.tab.h"
// 定义最后的结果
Ast_List result;
int main(int argc, char **argv) {
// 调用此函数从 STDIN 解析输入并根据输入匹配的规则执行对应的语义动作
yyparse();
// 查看输出
ast_dump_list(stdout, result);
}
构建脚本:
# build.sh
#!bash
cd SysY2021/src
# 生成前端
cd frontend
# 生成 lex.yy.c
flex lexer.lex
# 生成 parser.tab.c 和 parser.tab.h
bison -d parser.y
cd ..
if [ $1 == "production" ]
then
addition_flag="-O2"
else
addition_flag="-Wall -g -DDEBUG"
fi
# 全部编译起来并且链接
# ref: https://unix.stackexchange.com/a/19656
for c_file in $(find . | grep ".*\.c$")
do
gcc -std=c11 ${addition_flag} -c -I$PWD -o ${c_file%.c}.o $c_file
done
gcc -std=c11 ${addition_flag} $(find . | grep ".*\.o$") -o ../ssyc
执行:
./build.sh && ./ssyc
并且输入一段 SysY 语言程序, 就可以看到它对应的输出了.
参考
Flex/Bison
基本使用: calvin/flex和bison使用
比较详细, 介绍了一些C语言接口: TLDP/Lex-YACC-HOWTO
官方 Bison 文档: Bison Manual
杂项: YYSTYPE
建议使用:
%define api.value.type {double}
or
%define api.value.type {struct semantic_type}
来代替
#define YYSTYPE double
以获得更好的Bison体验.