如何对C语言的FOR语句给出一个生成中间代码的语法制导定义?

同题
关注者
43
被浏览
1562
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的前端代码来看:
yaxx.googlecode.com/svn
(Google Code要关闭了,看官们如果要从这个链接抓代码的话要快点动手)
或者GitHub镜像:github.com/gcc-mirror/g
其中跟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 · GitHub
static 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会有三个状态:
  1. 刚创建,尚未绑定
  2. 待绑定
  3. 完成绑定
本文的伪代码例子假定:
  • 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的语法文件,要么参考这个:gist.github.com/codebra

有了语法之后,我会在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栈”。嘛,实际实现到那里肯定就会发现这点了。