C コンパイラをつくってみる (3)

構文木の導入

1+2*3 を 1+(2*3) として計算するためには、トークンを左から消費していくだけではいけない。

加減算と乗除算の生成規則を階層立てて定義し、トークンを再帰的に処理していくことで、演算子の結合順位を実現する。

# 加減算・乗除算の階層を分けた生成規則
add := mul | add "+" mul | add "-" mul
mul := num | mul "*" num | mul "/" num

トークン列の左から消費して、トップダウンに構文解析をすることを LL 法というらしい。今回はトークン1つを見て生成規則を決めるので、 LL(1) 。

enum class ASTNodeType{
  BINARY_ADD,
  BINARY_SUB,
  BINARY_MUL,
  BINARY_DIV,
  NUMBER
};
struct ASTNode{
  ASTNodeType type;
  ASTNode const* lhs;
  ASTNode const* rhs;
  int value;
};

こんな感じで構文木のノードを定義し、

ASTNode* add(std::vector<Token>::const_iterator& token_itr){
  ASTNode* node = mul(token_itr);
  for(;;){
    if(consume(TokenType::PLUS, token_itr)){
      node = newNodeBinary(ASTNodeType::BINARY_ADD, node, mul(token_itr));
    }else if(consume(TokenType::MINUS, token_itr)){
      node = newNodeBinary(ASTNodeType::BINARY_SUB, node, mul(token_itr));
    }else{
      return node;
    }
  }
}

1つのトークンを見て再帰的に解析関数を呼び出す。

構文木からスタックマシン風アセンブリの生成

木構造になった計算順序を実際に実現するために、スタックポインタを使ってスタックマシン風に計算する。

RV32I で即値 (node->value) の push はこんな感じで作った。

std::cout <<
  "  addi sp, sp, -" << stack_size << "\n"
  "  li   a0, " << node->value << "\n"
  "  sw   a0, 0(sp)\n";

二項演算子が出てきたら、2つの値をポップ（a0, a1 にロード）して…

std::cout <<
  "  lw  a1, 0(sp)\n"
  "  lw  a0, " << stack_size << "(sp)\n"
  "  addi sp, sp, " <<  stack_size*2 << "\n";

構文木ノードのタイプに応じて命令を発行する。

if(node->type == ASTNodeType::BINARY_ADD){
  std::cout << "  add a0, a0, a1\n";
}else if ...

構文木のルートノードから再帰的に「lhs, rhs, 自分」の命令を出力していくことで、計算順序を考慮した四則演算のプログラムを出力できる。

成功したテストケースはこんな感じ。

 5    + 20            - 4 => 21
 3*2 => 6
 18/3 => 6
 1+3*2 => 7
 1+10/2*4-1 => 20
 (1+2)*3 => 9  // 括弧も実装された

差分はこちら

rsp

C コンパイラをつくってみる (3)

構文木の導入

構文木からスタックマシン風アセンブリの生成

参考文献