问题描述
同题SDT的话题⋯题主问这个问题的主要目的是想不生成AST直接生成比AST更底层的IR么,至少是某种带label的IR?
不然的话for语句要生成AST的SDT规则很普通,跟其它语句/表达式差不了多少,多半也就不需要专门问了。
Syntax Directed Translation,语法制导翻译 <- 为题主之外的同学放个关键词。
顺带放个传送门:
语法制导翻译是干什么的? - RednaxelaFX 的回答题主这个问题其实最关键的地方在于for循环涉及的跳转相应的label要如何处理;除了跳转之外for语句并没有什么特别的SDT规则。
如果不是要完整的C语言而只要一个子集的话,C4就是一个不生成AST而通过SDT直接边parse边生成目标代码的好例子:
c4/c4x86.c at master · EarlGray/c4 · GitHub可惜它没有实现for/break/continue,所以对题主的问题来说不够用。
不过还是有现成可以借鉴的例子来回答题主的问题。
龙书第2版的附录A里的代码例子是对一种简单的语言的基于SDT的编译器前端,它有实现while/do-while/break,如果要加上for/continue的支持基本上照搬已有代码就可以做到。
该附录A的对应代码可以在龙书官网获取:
Compilers: Principles, Techniques, and Tools (Dragon Book)龙书附录A的做法跟我后面要讲的做法道理上一致。后面再说。
要更直接对应的例子的话,可以拿比较老版本的GCC的前端代码来看:
http://yaxx.googlecode.com/svn/branches/yaxx-proc/gcc-3.4.0/gcc/c-parse.y(Google Code要关闭了,看官们如果要从这个链接抓代码的话要快点动手)
或者GitHub镜像:
https://github.com/gcc-mirror/gcc/blob/gcc-3_3_2-release/gcc/c-parse.in其中跟for循环相关的部分:
select_or_iter_stmt:
/* ... 省略 ... */
| FOR
{ $<ttype>$ = build_stmt (FOR_STMT, NULL_TREE, NULL_TREE,
NULL_TREE, NULL_TREE);
add_stmt ($<ttype>$); }
'(' for_init_stmt
{ stmt_count++;
RECHAIN_STMTS ($<ttype>2, FOR_INIT_STMT ($<ttype>2)); }
xexpr ';'
{ if ($6)
FOR_COND ($<ttype>2)
= c_common_truthvalue_conversion ($6); }
xexpr ')'
{ c_in_iteration_stmt++;
FOR_EXPR ($<ttype>2) = $9; }
c99_block_lineno_labeled_stmt
{ RECHAIN_STMTS ($<ttype>2, FOR_BODY ($<ttype>2));
c_in_iteration_stmt--;}
| /* ... 省略 ... */
;
for_init_stmt:
xexpr ';'
{ add_stmt (build_stmt (EXPR_STMT, $1)); }
| decl
{ check_for_loop_decls (); }
;
/* Parse a single real statement, not including any labels. */
stmt:
/* ... 省略 ... */
| c99_block_start select_or_iter_stmt c99_block_end
{ if (flag_isoc99)
RECHAIN_STMTS ($1, COMPOUND_BODY ($1));
$$ = NULL_TREE; }
| BREAK ';'
{ stmt_count++;
if (!(c_in_iteration_stmt || c_in_case_stmt))
{
error ("break statement not within loop or switch");
$$ = NULL_TREE;
}
else
$$ = add_stmt (build_break_stmt ()); }
| CONTINUE ';'
{ stmt_count++;
if (!c_in_iteration_stmt)
{
error ("continue statement not within a loop");
$$ = NULL_TREE;
}
else
$$ = add_stmt (build_continue_stmt ()); }
| /* ... 省略 ... */
;
GCC的老版本是直接有yacc系语法文件,而另一个C编译器,lcc,则是类似龙书附录A的做法,在手写的递归下降parser里做语法制导翻译:
lcc/stmt.c at b4ab752496079030005550c508a825a81c5d1056 · drh/lcc · GitHubstatic void forstmt(int lab, Swtch swp, int lev) {
int once = 0;
Tree e1 = NULL, e2 = NULL, e3 = NULL;
Coordinate pt2, pt3;
t = gettok();
expect('(');
definept(NULL);
if (kind[t] == ID)
e1 = texpr(expr0, ';', FUNC);
else
expect(';');
walk(e1, 0, 0);
pt2 = src;
refinc *= 10.0;
if (kind[t] == ID)
e2 = texpr(conditional, ';', FUNC);
else
expect(';');
pt3 = src;
if (kind[t] == ID)
e3 = texpr(expr0, ')', FUNC);
else {
static char stop[] = { IF, ID, '}', 0 };
test(')', stop);
}
if (e2) {
once = foldcond(e1, e2);
if (!once)
branch(lab + 3);
}
definelab(lab);
statement(lab, swp, lev);
definelab(lab + 1);
definept(&pt3);
if (e3)
walk(e3, 0, 0);
if (e2) {
if (!once)
definelab(lab + 3);
definept(&pt2);
walk(e2, lab, 0);
} else {
definept(&pt2);
branch(lab);
}
if (findlabel(lab + 2)->ref)
definelab(lab + 2);
}
lcc直接用整数来表示label target,然后在IR里使用显式的Label节点来表示一个“位置”。
definelab(int)就是创建一个新Label节点的函数。branch(int)就是生成“无条件跳转到参数所指定的label target”的IR节点。
======================================================
把前面的例子都忽略,咱从头来讲。
先确定语义和IR形式。
下面我们把for语句的各部分命名为:
for (init; cond; step)
body
/* after */然后假定我们要生成的IR是某种线性IR,暂时不管控制流图的生成。如果要同时生成控制流图其实只要稍微调整一下实现就能做到——每个label在绑定后会导致一个基本块的结束和另一个基本块的开始。
for循环的语义要生成中间代码的话可以有几种形式,参考我之前一帖的讨论:
对C语义的for循环的基本代码生成模式这里假定我们用上面提到的“第一种”形式,就会是这样:
...
for_init
Label_for_cond:
if (for_cond) goto Label_for_after
for_body
Label_for_step:
for_step
goto Label_for_cond
Label_for_after:
...一个for语句会涉及3个label:循环条件的label,循环递增的label,循环结束后的label。
这么一来,for循环里的break就会跳转到Label_for_after,而continue则会跳转到Label_for_step。这个结构用来描述while/do-while循环的label也够用,只要把cond和step设为同一个label即可。
可以用一个由链表实现的栈来跟踪记录当前parse到的循环的嵌套状况:
struct loop_t {
struct label_t *cond, *step, *after;
struct loop_t *prev; // 构成栈用的单向链
};
struct loop_t *current_enclosing_loop = NULL; // 当前parse所处的循环Label会有三个状态:
- 刚创建,尚未绑定
- 待绑定
- 完成绑定
本文的伪代码例子假定:
- make_label() 用于创建abel,进入状态1;
- bind_label(label_t l) 用于把label从状态1迁移到状态2;
- 在bind_label()之后生成新的IR阶段会让处于状态2的label完成绑定,进入状态3。
在线性IR里,一个label表示在这个线性IR里的一个“位置”。那么怎样才能确定一个“位置”呢?如果有下标/地址的话,用下标/地址就OK;如果没有下标,那把线性IR想像成一个单向或双向链表,要确定一个“位置”可以指定该位置在某条IR指令之后、另一条IR指令之前。
于是我们的label_t也可以相应设计为记录其之前的IR指令是谁、之后的IR指令又是谁。每当新创建一个label_t时,我们还不知道它将要代表的位置前后的IR,所以处于状态1;等到该label之前的IR都生成好之后,我们知道了该label_t之前的IR是谁,但还不知道之后是谁;所以可以通过调用bind_label()把一个label_t放入一个pending_labels(待绑定label)列表里,等下一条IR生成出来时把pending_labels列表里的label全部跟新生成的IR绑定在一起。
在线性IR里,另一种处理label的做法是直接让label作为IR节点的一种,这样就自然的能在IR序列中占有“位置”,这也是常见做法之一。这里的例子其实不论label是用哪种方式实现,在语法制导翻译里的抽象动作都差不多。
再看SDT具体要做的事情。SDT首先得有语法,然后在语法的基础上添加语义动作。我会要么参考老版本GCC的语法文件,要么参考这个:
https://gist.github.com/codebrainz/2933703#file-c99-y有了语法之后,我会在SDT里利用前面定义好的loop_t结构体来跟踪循环的嵌套状况:
(类似Bison语法的伪代码)
for_statement:
FOR
{
/* 创建AST用。可选 */
$$ = make_for_statement();
/* 记录循环嵌套层次 */
struct loop_t* l = make_loop();
l->cond = make_label();
l->step = make_label();
l->after = make_label();
l->prev = current_enclosing_loop;
current_enclosing_loop = l;
}
'(' for_init_stmt
{
$$->init = $4;
/* 生成for_init的代码 */
gen_expression($$->init);
/* 把Label_for_cond绑定在for_init之后 */
bind_label(current_enclosing_loop->cond);
}
for_cond_stmt
{
$$->cond = $6;
/* 生成跳转到循环之后的条件跳转 */
gen_conditional_jump($$->cond, current_enclosing_loop->after);
}
for_expr ')'
{
$$->step = $8;
}
statement
{
$$->body = $11;
/* 生成for_body的代码 */
gen_statement($$->body);
/* 把Label_for_step绑定在for_body之后 */
bind_label(current_enclosing_loop->step);
/* 生成for_step的代码 */
gen_expression($$->step);
/* 生成跳转回循环条件的代码 */
gen_jump(current_enclosing_loop->cond);
/* 循环结束。把Label_for_after绑定在循环之后 */
bind_label(current_enclosing_loop->after);
/* 把之前用到尚未绑定的label的IR修正到绑定后的值。可选 */
patch_labels();
/* 把当前循环从循环层次记录栈中弹出 */
current_enclosing_loop = current_enclosing_loop->prev;
}
;
break_statement:
BREAK
{
if (current_enclosing_loop == NULL) report_error();
else {
gen_jump(current_enclosing_loop->after);
}
}
;
continue_statement:
CONTINUE
{
if (current_enclosing_loop == NULL) report_error();
else {
gen_jump(current_enclosing_loop->step);
}
}
;
大概就是这样啦。细节啥得要具体到题主具体的编译器的其它部分融合进去了。
在这个思路上,具体实现可以有不少变种。
例如说“循环层次的栈”不一定要自己维护显式的栈。龙书附录A的parser是递归下降式,parse的过程中调用栈就可以构成一个隐式的栈。所以龙书附录A的代码用Stmt.Enclosing来记录“循环层次栈”的“栈顶”,然后在处理while和do-while的方法里用局部变量savedStmt来隐式记录栈的“prev”链。
这种思路在V8的Hydrogen里也有体现。里面用到了一个BreakAndContinueInfo / BreakAndContinueScope来处理break和continue的目标:
hydrogen.cc另外要提醒的是,上面我给的伪代码的“label栈”的思路是对的,但为了把伪代码写得简单而故意忽略了一点:C语言里break和continue的可能跳转目标并不总是在同一层——continue只能在循环里出现,break除了能在循环里出现外还可以在switch里出现。所以实际要实现完整的C的话,break和continue得各自有自己的“label栈”。嘛,实际实现到那里肯定就会发现这点了。