抽象机代码生成

发表于 更新于 分类于 阅读次数： Changyan：

代码生成

回填链表的设计

由于我们需要在一遍扫描中生成指令代码，但是遇到分支循环语句时，由于执行时间的限制，我们暂时看不到后续跳转的位置，因此我们就需要一种数据结构将需要跳转的位置保存下来，当我们执行到合适的位置的时候对其进行回填。而具体的数据结构设计如下：

1
2
3
4
5
6
7
struct backpatchlist
{
  int inst_remain;
  struct backpatchlist *tail;
  struct backpatchlist *next;
};

首先是一个用于存储待回填的指令标号字段，紧接着是链表的尾指针，最后是存储下一个链表结构的字段。尾指针的设计我认为是比较合理的，其避免了两个均持有一定元素的链表在合并时的遍历问题，即寻找合适的插入位置。而如果存储了尾指针，首先初始必为只持有一个元素的两个链表合并，我们对其执行以下操作，这样后续的合并操作我们就可以用O(1)的时间复杂度来完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
struct backpatchlist *merge(struct backpatchlist *bpl1, struct backpatchlist *bpl2){
  if(!bpl1 && !bpl2){
    return nullptr;
  } else if(!bpl1 && bpl2){
    return bpl2;
  } else if(bpl1 && !bpl2){
    return bpl1;
  } else{
    bpl1->tail->next = bpl2;
    bpl1->tail = bpl2->tail;
    return bpl1;
  }
}

控制语句跳转时机

code_design

对于控制语句我们需要在合适的位置插入必要的语义动作，具体来说如下

首先我们需要对表达式生成代码，从代码执行的角度来看，最后表达式的运算结果会被放到栈顶，假设为a，那么我们就需要比较该值是否为0来判断是不是需要跳转到else分支后的语句执行，那么就需要在这里插入一个brf的语义动作，他会用下一条语句的标号生成一个回填链表la以及一条有条件跳转指令jpc，之所以用下一条语句的标号刚好对应我们之后生成的jpc指令。

如果条件成立，那么我们就顺序执行L1语句部分的内容，当执行完L1我们就需要从if语句跳出，因此这里首先需要插入一条jmp指令，而因为我们还没有执行完if语句，所以此时我们还不知道对应的跳转标号，因此也需要一个回填链表lb。在者因为L1也可以是一个if或while语句，因此当内部的循环执行完毕的时候也会需要跳出整个循环，故我们需要保存L1内部的回填链表，用于执行后续操作。

当执行到else的时候，此时我们就知道表达式不成立的时候需要跳转的位置，因此对la回填，回填标号是下一条语句。继续执行会执行到L2，显然L2也可以是一个if或while语句，因此当内部的循环执行完毕的时候也会需要跳出整个循环，故我们需要保存L2内部的回填链表，最后识别到fi的时候我们将内部需要跳出循环的所有回填链表进行合并，传递给调用者用于执行后续操作。

对于while语句的话，我们唯一可以跳出循环的条件就是表达式不成立的情况，如果表达式成立我们需要重复执行内部语句内容。因此我们需要保存进入while时的指令标号用于后续跳转。之后brf语义动作和if语句相同，不做赘述。继续往下执行就到了L部分，同样的道理L也可以是一个if或while语句，因此当内部的循环执行完毕的时候也会需要跳出整个循环，故我们需要保存L内部的回填链表，且此时while语句执行完毕，我们也知道了跳出的位置标号，故回填，而在此之前需要先生成一条无条件跳转指令jmp，跳转目标为我们在进入while时保存的标号。

构造每一条指令的生成动作

以lod为例

1
2
3
4
5
6
void generate_instr_sto(Token_t t) {
  int ret = serchslot(t.str);
  inst_array[instr_cnt].op = _sto;
  inst_array[instr_cnt].a = ret;
  instr_cnt++;
}

在这里我们只需要将指令数组的对应位置进行赋值即可。并且对于一个变量我们需要检索全局符号表以找到其对应的位置。

插入语义动作

在这里我们需要做的就是需要将相应的代码生成函数插入到语法分析的代码中，然后将其输入到制定的代码输出文件。我们对while和if做过具体的介绍，因此我们以while为例，看看其具体的插入时机及位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @brief 
 * parse while statement
 * while E do L od
 * nothing on successful
 * call handle_error() function on failure 
 * @return struct backpatchlist* 
 */
struct backpatchlist *parse_while_stmt(){
  Token_t hold_token = tokens[p_token];
  match(hold_token,TK_WHILE);
  hold_token = get_token(); // skip while keyword

  int instr_start = nextinst();   // @ini
  parse_expression();
  struct backpatchlist *la = brf(); // @brf
  hold_token = tokens[p_token];

  if (TK_DO == hold_token.type) {
    hold_token = get_token(); // skip do keyword
    struct backpatchlist *lst = parse_stmt_list();

    generate_instr_jmp(instr_start);   // @br

    backpatch(lst, instr_start);  // @patch
  }
  return la;
}

这一部分也是很简单的，很明显根据我们之前的分析在对应位置插入相应的语义动作即可。

代码生成

这一步我们需要做的工作相对简单，即读取指令数组的指令，根据不同的指令类型拼接上对应的操作数，将其输入到对应的指定文件中，举例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool out_ssam_code(FILE* fd){
  char instr[8] = {'\0'};
  for(int i = 0; i < instr_cnt; ++i){
    switch (inst_array[i].op)
    {
    case _add:
      sprintf(instr, "add\n");
      break;
    // more
    case _lit:
      sprintf(instr, "lit  %d\n" ,inst_array[i].a);
      break;
    }
    // more
    fprintf(fd, "%s", instr);
  }
  printf(GREEN"[success] generate simple stack machine code successful!\n"NONE);
  return true;
}

测试

测试文件代码

以求解鸡兔同笼问题的代码为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//source code
var head, foot, cock, rabbit, n;
n := 0;
read(head);
read(foot);
cock := 1;
while (cock < head) + (cock = head) do
  rabbit := head - cock;
  if (cock * 2 + rabbit * 4) = foot then
    write(cock);
    write(rabbit);
    n := n+1
  else
    skip
  fi;
  cock := cock + 1
od;
if n = 0 then write(0) else skip fi


生成ssam代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
int  5
lit  0
sto  0
lit  0
sto  1
lit  0
sto  2
lit  0
sto  3
lit  0
sto  4
lit  0
sto  4
red  0
red  1
lit  1
sto  2
lod  2
lod  0
lth
lod  2
lod  0
equ
add
jpc  53
lod  0
lod  2
sub
sto  3
lod  2
lit  2
mul
lod  3
lit  4
mul
add
lod  1
equ
jpc  48
lod  2
wrt
lod  3
wrt
lod  4
lit  1
add
sto  4
jmp  48
lod  2
lit  1
add
sto  2
jmp  17
lod  4
lit  0
equ
jpc  60
lit  0
wrt
jmp  60
nop

验证

我们用四组测试数据验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
data 1:
head = 8
foot = 24

=> answer 
cock = 4
rabbit = 4

data 2:
head = 5
foot = 18

=> answer 
cock = 1
rabbit = 4

data 3:
head = 19
foot = 48

=> answer 
cock = 14
rabbit = 5

data 4:
head = 7
foot = 32

=> answer 
0 (无解)

实际运行效果与预期一致

valid