chibiccを読む～Cコンパイラコードリーディング～ ステップ8

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ8に該当
github.com

今回行うこと

ファイル分割とMakefileの変更(コンパイラのソースコードを分割する)

コンパイラのソースコード

chibicc.h

https://github.com/rui314/chibicc/commit/3396747fcbf51ae45aa162f5c9c41fa719050421#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R1
https://github.com/rui314/chibicc/blob/3396747fcbf51ae45aa162f5c9c41fa719050421/chibicc.h#L1

#include <ctype.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//
// tokenize.c
//

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer literals
  TK_EOF,      // End-of-file markers
} TokenKind;

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
  int len;        // Token length
};

void error(char *fmt, ...);
void error_at(char *loc, char *fmt, ...);
bool consume(char *op);
void expect(char *op);
int expect_number();
bool at_eof();
Token *new_token(TokenKind kind, Token *cur, char *str, int len);
Token *tokenize();

extern char *user_input;
extern Token *token;

//
// parse.c
//

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_EQ,  // ==
  ND_NE,  // !=
  ND_LT,  // <
  ND_LE,  // <=
  ND_NUM, // Integer
} NodeKind;

// AST node type
typedef struct Node Node;
struct Node {
  NodeKind kind; // Node kind
  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side
  int val;       // Used if kind == ND_NUM
};

Node *expr();

//
// codegen.c
//

void codegen(Node *node);

main.c

https://github.com/rui314/chibicc/commit/3396747fcbf51ae45aa162f5c9c41fa719050421#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR1
https://github.com/rui314/chibicc/blob/3396747fcbf51ae45aa162f5c9c41fa719050421/main.c#L1

#include "chibicc.h"

int main(int argc, char **argv) {
  if (argc != 2)
    error("%s: invalid number of arguments", argv[0]);

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();
  Node *node = expr();

  // Traverse the AST to emit assembly.
  codegen(node);
  return 0;
}

tokenize.c

https://github.com/rui314/chibicc/commit/3396747fcbf51ae45aa162f5c9c41fa719050421#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R1
https://github.com/rui314/chibicc/blob/3396747fcbf51ae45aa162f5c9c41fa719050421/tokenize.c#L1

#include "chibicc.h"

char *user_input;
Token *token;

// Reports an error and exit.
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Reports an error location and exit.
void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, ""); // print pos spaces.
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Consumes the current token if it matches `op`.
bool consume(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    return false;
  token = token->next;
  return true;
}

// Ensure that the current token is `op`.
void expect(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    error_at(token->str, "expected \"%s\"", op);
  token = token->next;
}

// Ensure that the current token is TK_NUM.
int expect_number() {
  if (token->kind != TK_NUM)
    error_at(token->str, "expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

bool at_eof() {
  return token->kind == TK_EOF;
}

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str, int len) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  tok->len = len;
  cur->next = tok;
  return tok;
}

bool startswith(char *p, char *q) {
  return memcmp(p, q, strlen(q)) == 0;
}

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Multi-letter punctuator
    if (startswith(p, "==") || startswith(p, "!=") ||
        startswith(p, "<=") || startswith(p, ">=")) {
      cur = new_token(TK_RESERVED, cur, p, 2);
      p += 2;
      continue;
    }

    // Single-letter punctuator
    if (strchr("+-*/()<>", *p)) {
      cur = new_token(TK_RESERVED, cur, p++, 1);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p, 0);
      char *q = p;
      cur->val = strtol(p, &p, 10);
      cur->len = p - q;
      continue;
    }

    error_at(p, "invalid token");
  }

  new_token(TK_EOF, cur, p, 0);
  return head.next;
}

parse.c

https://github.com/rui314/chibicc/commit/3396747fcbf51ae45aa162f5c9c41fa719050421#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR1
https://github.com/rui314/chibicc/blob/3396747fcbf51ae45aa162f5c9c41fa719050421/parse.c#L1

#include "chibicc.h"

Node *new_node(NodeKind kind) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  return node;
}

Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) {
  Node *node = new_node(kind);
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

Node *new_num(int val) {
  Node *node = new_node(ND_NUM);
  node->val = val;
  return node;
}

Node *expr();
Node *equality();
Node *relational();
Node *add();
Node *mul();
Node *unary();
Node *primary();

// expr = equality
Node *expr() {
  return equality();
}

// equality = relational ("==" relational | "!=" relational)*
Node *equality() {
  Node *node = relational();

  for (;;) {
    if (consume("=="))
      node = new_binary(ND_EQ, node, relational());
    else if (consume("!="))
      node = new_binary(ND_NE, node, relational());
    else
      return node;
  }
}

// relational = add ("<" add | "<=" add | ">" add | ">=" add)*
Node *relational() {
  Node *node = add();

  for (;;) {
    if (consume("<"))
      node = new_binary(ND_LT, node, add());
    else if (consume("<="))
      node = new_binary(ND_LE, node, add());
    else if (consume(">"))
      node = new_binary(ND_LT, add(), node);
    else if (consume(">="))
      node = new_binary(ND_LE, add(), node);
    else
      return node;
  }
}

// add = mul ("+" mul | "-" mul)*
Node *add() {
  Node *node = mul();

  for (;;) {
    if (consume("+"))
      node = new_binary(ND_ADD, node, mul());
    else if (consume("-"))
      node = new_binary(ND_SUB, node, mul());
    else
      return node;
  }
}

// mul = unary ("*" unary | "/" unary)*
Node *mul() {
  Node *node = unary();

  for (;;) {
    if (consume("*"))
      node = new_binary(ND_MUL, node, unary());
    else if (consume("/"))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
  }
}

// unary = ("+" | "-")? unary
//       | primary
Node *unary() {
  if (consume("+"))
    return unary();
  if (consume("-"))
    return new_binary(ND_SUB, new_num(0), unary());
  return primary();
}

// primary = "(" expr ")" | num
Node *primary() {
  if (consume("(")) {
    Node *node = expr();
    expect(")");
    return node;
  }

  return new_num(expect_number());
}

codegen.c

https://github.com/rui314/chibicc/commit/3396747fcbf51ae45aa162f5c9c41fa719050421#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR1
https://github.com/rui314/chibicc/blob/3396747fcbf51ae45aa162f5c9c41fa719050421/codegen.c#L1

#include "chibicc.h"

void gen(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");
}

void codegen(Node *node) {
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  gen(node);

  // A result must be at the top of the stack, so pop it
  // to RAX to make it a program exit code.
  printf("  pop rax\n");
  printf("  ret\n");
}

テストコード

test.sh
https://github.com/rui314/chibicc/blob/3396747fcbf51ae45aa162f5c9c41fa719050421/test.sh

#!/bin/bash
assert() {
  expected="$1"
  input="$2"

  ./chibicc "$input" > tmp.s
  gcc -static -o tmp tmp.s
  ./tmp
  actual="$?"

  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 0
assert 42 42
assert 21 '5+20-4'
assert 41 ' 12 + 34 - 5 '
assert 47 '5+6*7'
assert 15 '5*(9-6)'
assert 4 '(3+5)/2'
assert 10 '-10+20'
assert 10 '- -10'
assert 10 '- - +10'

assert 0 '0==1'
assert 1 '42==42'
assert 1 '0!=1'
assert 0 '42!=42'

assert 1 '0<1'
assert 0 '1<1'
assert 0 '2<1'
assert 1 '0<=1'
assert 1 '1<=1'
assert 0 '2<=1'

assert 1 '1>0'
assert 0 '1>1'
assert 0 '1>2'
assert 1 '1>=0'
assert 1 '1>=1'
assert 0 '1>=2'

echo OK

Makefile

https://github.com/rui314/chibicc/commit/3396747fcbf51ae45aa162f5c9c41fa719050421#diff-76ed074a9305c04054cdebb9e9aad2d818052b07091de1f20cad0bbac34ffb52R1
https://github.com/rui314/chibicc/blob/3396747fcbf51ae45aa162f5c9c41fa719050421/Makefile#L1

CFLAGS=-std=c11 -g -static
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)

chibicc: $(OBJS)
	$(CC) -o $@ $(OBJS) $(LDFLAGS)

$(OBJS): chibicc.h

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean

chibiccを読む～Cコンパイラコードリーディング～ ステップ7

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ7に該当
github.com

今回作成するコンパイラ

比較演算子(<、<=、>、>=、==、!= を扱えるコンパイラを作成する)

コンパイラのソースコード

https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c

#include <ctype.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//
// Tokenizer
//

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer literals
  TK_EOF,      // End-of-file markers
} TokenKind;

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
  int len;        // Token length
};

// Input program
char *user_input;

// Current token
Token *token;

// Reports an error and exit.
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Reports an error location and exit.
void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, ""); // print pos spaces.
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Consumes the current token if it matches `op`.
bool consume(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    return false;
  token = token->next;
  return true;
}

// Ensure that the current token is `op`.
void expect(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    error_at(token->str, "expected \"%s\"", op);
  token = token->next;
}

// Ensure that the current token is TK_NUM.
int expect_number() {
  if (token->kind != TK_NUM)
    error_at(token->str, "expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

bool at_eof() {
  return token->kind == TK_EOF;
}

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str, int len) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  tok->len = len;
  cur->next = tok;
  return tok;
}

bool startswith(char *p, char *q) {
  return memcmp(p, q, strlen(q)) == 0;
}

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Multi-letter punctuator
    if (startswith(p, "==") || startswith(p, "!=") ||
        startswith(p, "<=") || startswith(p, ">=")) {
      cur = new_token(TK_RESERVED, cur, p, 2);
      p += 2;
      continue;
    }

    // Single-letter punctuator
    if (strchr("+-*/()<>", *p)) {
      cur = new_token(TK_RESERVED, cur, p++, 1);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p, 0);
      char *q = p;
      cur->val = strtol(p, &p, 10);
      cur->len = p - q;
      continue;
    }

    error_at(p, "invalid token");
  }

  new_token(TK_EOF, cur, p, 0);
  return head.next;
}

//
// Parser
//

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_EQ,  // ==
  ND_NE,  // !=
  ND_LT,  // <
  ND_LE,  // <=
  ND_NUM, // Integer
} NodeKind;

// AST node type
typedef struct Node Node;
struct Node {
  NodeKind kind; // Node kind
  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side
  int val;       // Used if kind == ND_NUM
};

Node *new_node(NodeKind kind) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  return node;
}

Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) {
  Node *node = new_node(kind);
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

Node *new_num(int val) {
  Node *node = new_node(ND_NUM);
  node->val = val;
  return node;
}

Node *expr();
Node *equality();
Node *relational();
Node *add();
Node *mul();
Node *unary();
Node *primary();

// expr = equality
Node *expr() {
  return equality();
}

// equality = relational ("==" relational | "!=" relational)*
Node *equality() {
  Node *node = relational();

  for (;;) {
    if (consume("=="))
      node = new_binary(ND_EQ, node, relational());
    else if (consume("!="))
      node = new_binary(ND_NE, node, relational());
    else
      return node;
  }
}

// relational = add ("<" add | "<=" add | ">" add | ">=" add)*
Node *relational() {
  Node *node = add();

  for (;;) {
    if (consume("<"))
      node = new_binary(ND_LT, node, add());
    else if (consume("<="))
      node = new_binary(ND_LE, node, add());
    else if (consume(">"))
      node = new_binary(ND_LT, add(), node);
    else if (consume(">="))
      node = new_binary(ND_LE, add(), node);
    else
      return node;
  }
}

// add = mul ("+" mul | "-" mul)*
Node *add() {
  Node *node = mul();

  for (;;) {
    if (consume("+"))
      node = new_binary(ND_ADD, node, mul());
    else if (consume("-"))
      node = new_binary(ND_SUB, node, mul());
    else
      return node;
  }
}

// mul = unary ("*" unary | "/" unary)*
Node *mul() {
  Node *node = unary();

  for (;;) {
    if (consume("*"))
      node = new_binary(ND_MUL, node, unary());
    else if (consume("/"))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
  }
}

// unary = ("+" | "-")? unary
//       | primary
Node *unary() {
  if (consume("+"))
    return unary();
  if (consume("-"))
    return new_binary(ND_SUB, new_num(0), unary());
  return primary();
}

// primary = "(" expr ")" | num
Node *primary() {
  if (consume("(")) {
    Node *node = expr();
    expect(")");
    return node;
  }

  return new_num(expect_number());
}

//
// Code generator
//

void gen(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");
}

int main(int argc, char **argv) {
  if (argc != 2)
    error("%s: invalid number of arguments", argv[0]);

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();
  Node *node = expr();

  // Print out the first half of assembly.
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // Traverse the AST to emit assembly.
  gen(node);

  // A result must be at the top of the stack, so pop it
  // to RAX to make it a program exit code.
  printf("  pop rax\n");
  printf("  ret\n");
  return 0;
}

追加・修正されたコンパイラのソースコード

Token構造体

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR25
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L25

struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
  int len;        // Token length
};

トークンの文字列の長さを記録するためにlenメンバを追加します。

tokenize関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR115
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L115

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Multi-letter punctuator
    if (startswith(p, "==") || startswith(p, "!=") ||
        startswith(p, "<=") || startswith(p, ">=")) {
      cur = new_token(TK_RESERVED, cur, p, 2);
      p += 2;
      continue;
    }

    // Single-letter punctuator
    if (strchr("+-*/()<>", *p)) {
      cur = new_token(TK_RESERVED, cur, p++, 1);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p, 0);
      char *q = p;
      cur->val = strtol(p, &p, 10);
      cur->len = p - q;
      continue;
    }

    error_at(p, "invalid token");
  }

  new_token(TK_EOF, cur, p, 0);
  return head.next;
}

文字列の先頭アドレスを取得する(変更なし)

  char *p = user_input;

トークンからなる連結リストのヘッダーを作成する(変更なし)

  Token head;
  head.next = NULL;
  Token *cur = &head;

空白文字の場合(変更なし)

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

複数文字の記号の場合

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR115
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L115

    // Multi-letter punctuator
    if (startswith(p, "==") || startswith(p, "!=") ||
        startswith(p, "<=") || startswith(p, ">=")) {
      cur = new_token(TK_RESERVED, cur, p, 2);
      p += 2;
      continue;
    }

条件式にある4つのstartwith関数のいずれかがtrueを戻り値とした場合→文字p*が、"=="、"!="、"<="、">=" のいずれかの文字列の一部だった場合は、new_token関数を呼び出して、記号を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
次の文字を取得するためにchar型へのポインタpを2バイト分(2文字分)インクリメントしてからwhile文のループを継続します。

1文字の記号の場合

    // Single-letter punctuator
    if (strchr("+-*/()<>", *p)) {
      cur = new_token(TK_RESERVED, cur, p++, 1);
      continue;
    }

str関数の第一引数の文字列に”<”と” >”を追加します。

数字の場合

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR132
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L132

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p, 0);
      char *q = p;
      cur->val = strtol(p, &p, 10);
      cur->len = p - q;
      continue;
    }

strol関数を呼び出す前に文字のアドレス値をchar型へのポインタqに保存し、文字列の長さp - qを生成されたトークンに記録します。

その他の場合(変更なし)

    error_at(p, "invalid token");

トークン列の終端を表すトークンを生成する(変更なし)

  new_token(TK_EOF, cur, p, 0);

連結リストの先頭トークンを戻り値としてリターンする(変更なし)

return head.next;

new_token関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR92
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L92

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str, int len) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  tok->len = len;
  cur->next = tok;
  return tok;
}

トークンを生成する(変更なし)

  Token *tok = calloc(1, sizeof(Token));

生成されたトークンのメンバに値を設定する

  tok->kind = kind;
  tok->str = str;
  tok->len = len;

kindの値(トークンの種類、トークンの型)、strの値(トークンの文字列)、lenの値(トークンの文字列の長さ)を生成されるトークン構造体のメンバに設定します。

生成されたトークンを連結リストに追加する(変更なし)

  cur->next = tok

生成されたトークンを戻り値としてリターンする(変更なし)

  return tok;

startswith関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR97
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L97

bool startswith(char *p, char *q) {
  return memcmp(p, q, strlen(q)) == 0;
}

startswith関数は、引数pが指定する文字列と引数qが指定する文字列が同じであるかを判定します。
引数pが指定する文字列と引数qが指定する文字列が同じ場合は、trueが戻り値となります。
引数pが指定する文字列と引数qが指定する文字列が異なる場合は、falseが戻り値となります。

memcmp関数は、第一引数のアドレスから配置されているデータと第二引数のアドレスから配置されているデータを第三引数で指定されたバイトサイズ分だけ比較します。
第一引数のアドレスから配置されているデータ > 第二引数のアドレスから配置されているデータの場合は、戻り値は正の値、
第一引数のアドレスから配置されているデータ = 第二引数のアドレスから配置されているデータの場合は、戻り値は0の値、
第一引数のアドレスから配置されているデータ < 第二引数のアドレスから配置されているデータの場合は、戻り値は負の値、
になります。

consume関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR58
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L58

// Consumes the current token if it matches `op`.
bool consume(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    return false;
  token = token->next;
  return true;
}

文字ではなく文字列を扱えるように改良します。

現在着目しているトークンの文字列を調べる

  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    return false;

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列長と引数opで指定された文字列長が異なる場合(strlen(op)の戻り値とstrlen(op)の戻り値が異なる場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合(memcmp(token->str, op, token->len)の戻り値が0以外の値になる場合)は、戻り値をflaseとしてリターンします。

strlen関数は、引数が指定する文字列の長さ(バイトサイズ)を戻り値として取得します。

memcmp関数は、第一引数のアドレスから配置されているデータと第二引数のアドレスから配置されているデータを第三引数で指定されたバイトサイズ分だけ比較します。
第一引数のアドレスから配置されているデータ > 第二引数のアドレスから配置されているデータの場合は、戻り値は正の値、
第一引数のアドレスから配置されているデータ = 第二引数のアドレスから配置されているデータの場合は、戻り値は0の値、
第一引数のアドレスから配置されているデータ < 第二引数のアドレスから配置されているデータの場合は、戻り値は負の値、
になります。

着目しているトークンを次のトークンに変更する(変更なし)

  token = token->next;
  return true;

expect関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR67
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L67

// Ensure that the current token is `op`.
void expect(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    error_at(token->str, "expected \"%s\"", op);
  token = token->next;
}

文字ではなく文字列を扱えるように改良します。

現在着目しているトークンの文字列を調べる

  if (token->kind != TK_RESERVED || strlen(op) != strlen(op) ||
      memcmp(token->str, op, token->len))
    error_at(token->str, "expected \"%s\"", op);

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列長と引数opで指定された文字列長が異なる場合(strlen(op)の戻り値とstrlen(op)の戻り値が異なる場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合(memcmp(token->str, op, token->len)の戻り値が0以外の値になる場合)は、error関数を呼び出して、メッセージを出力してから処理を終了します。

strlen関数は、引数が指定する文字列の長さ(バイトサイズ)を戻り値として取得します。

memcmp関数は、第一引数のアドレスから配置されているデータと第二引数のアドレスから配置されているデータを第三引数で指定されたバイトサイズ分だけ比較します。
第一引数のアドレスから配置されているデータ > 第二引数のアドレスから配置されているデータの場合は、戻り値は正の値、
第一引数のアドレスから配置されているデータ = 第二引数のアドレスから配置されているデータの場合は、戻り値は0の値、
第一引数のアドレスから配置されているデータ < 第二引数のアドレスから配置されているデータの場合は、戻り値は負の値、
になります。

着目しているトークンを次のトークンに変更する(変更なし)

token = token->next;

NodeKind

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR154
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L154

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_EQ,  // ==
  ND_NE,  // !=
  ND_LT,  // <
  ND_LE,  // <=
  ND_NUM, // Integer
} NodeKind;

==、!=、<、<=にそれぞれ対応するノードの型(ノードの種類)を追加します。
>、>=、に対応するノードの型は定義せず、 < や <= に対応するノードを生成するときに子ノードを入れ替えることで、< や <= の処理を再現します(詳細はrelational関数、gen関数)。

expr関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR197
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L197

// expr = equality
Node *expr() {
  return equality();
}

expr関数は、生成規則 expr = equality に基づいて、抽象構文木のノードを生成します。

equality

  return equality();

equality関数を呼び出して、抽象構文木のノードを生成します。
生成したノードのアドレスが戻り値となります。

equality関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR202
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L202

// equality = relational ("==" relational | "!=" relational)*
Node *equality() {
  Node *node = relational();

  for (;;) {
    if (consume("=="))
      node = new_binary(ND_EQ, node, relational());
    else if (consume("!="))
      node = new_binary(ND_NE, node, relational());
    else
      return node;
  }
}

equality関数は、生成規則 equality = relational ("==" relational | "!=" relational)* に基づいて、抽象構文木のノードを生成します。

relational

  Node *node = relational();

「"=="とrelational、または、"!="とrelational」を0回以上

  for (;;) {
    if (consume("=="))
      node = new_binary(ND_EQ, node, relational());
    else if (consume("!="))
      node = new_binary(ND_NE, node, relational());
    else
      return node;
  }

relational関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR216
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L216

// relational = add ("<" add | "<=" add | ">" add | ">=" add)*
Node *relational() {
  Node *node = add();

  for (;;) {
    if (consume("<"))
      node = new_binary(ND_LT, node, add());
    else if (consume("<="))
      node = new_binary(ND_LE, node, add());
    else if (consume(">"))
      node = new_binary(ND_LT, add(), node);
    else if (consume(">="))
      node = new_binary(ND_LE, add(), node);
    else
      return node;
  }
}

relational関数は、生成規則 relational = add ("<" add | "<=" add | ">" add | ">=" add)* に基づいて、抽象構文木のノードを生成します。

add

  Node *node = add();

add関数を呼び出して、抽象構文木のノードを生成します。

「"<"とadd または "<="とadd または ">"とadd または ">="とadd」を0回以上

  for (;;) {
    if (consume("<"))
      node = new_binary(ND_LT, node, add());
    else if (consume("<="))
      node = new_binary(ND_LE, node, add());
    else if (consume(">"))
      node = new_binary(ND_LT, add(), node);
    else if (consume(">="))
      node = new_binary(ND_LE, add(), node);
    else
      return node;
  }

consume("<")の戻り値がtrueとなる場合→着目しているトークンが < の場合は、new_binary関数を呼び出して、< 記号を表現するノードを生成します。< 記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのadd関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のadd関数で生成されたノードを子ノードとして持ちます。

consume("<=")の戻り値がtrueとなる場合→着目しているトークンが <= の場合は、new_binary関数を呼び出して、<= 記号を表現するノードを生成します。<= 記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのadd関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のadd関数で生成されたノードを子ノードとして持ちます。

consume(">")の戻り値がtrueとなる場合→着目しているトークンが > の場合は、new_binary関数を呼び出して、< 記号を表現するノードを生成します。
ここでは、> 記号を表現するノードを生成せずに、第二引数と第三引数を入れ替えることで、> の処理を再現します。

consume(">=")の戻り値がtrueとなる場合→着目しているトークンが >= の場合は、new_binary関数を呼び出して、<= 記号を表現するノードを生成します。
ここでは、>= 記号を表現するノードを生成せずに、第二引数と第三引数を入れ替えることで、>= の処理を再現します。

上記以外の場合は、最後に生成されたノードのアドレスを戻り値としてリターンします。

add関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR239
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L239

// add = mul ("+" mul | "-" mul)*
Node *add() {
  Node *node = mul();

  for (;;) {
    if (consume("+"))
      node = new_binary(ND_ADD, node, mul());
    else if (consume("-"))
      node = new_binary(ND_SUB, node, mul());
    else
      return node;
  }
}

add関数は、生成規則 add = mul ("+" mul | "-" mul)* に基づいて、抽象構文木のノードを生成します。

mul

  Node *node = mul();

mul関数を呼び出して、抽象構文木のノードを生成します。

「"+"とmul または "-"とmul」を0回以上

  for (;;) {
    if (consume("+"))
      node = new_binary(ND_ADD, node, mul());
    else if (consume("-"))
      node = new_binary(ND_SUB, node, mul());
    else
      return node;
  }

consume("+")の戻り値がtrueとなる場合→着目しているトークンが + の場合は、new_binary関数を呼び出して、加算記号を表現するノードを生成します。この加算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのmul関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。

consume("-")の戻り値がtrueとなる場合→着目しているトークンが - の場合は、new_binary関数を呼び出して、減算記号を表現するノードを生成します。この減算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのprimary関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。

上記以外の場合は、最後に生成されたノードのアドレスを戻り値としてリターンします。

mul関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR253
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L253

// mul = unary ("*" unary | "/" unary)*
Node *mul() {
  Node *node = unary();

  for (;;) {
    if (consume("*"))
      node = new_binary(ND_MUL, node, unary());
    else if (consume("/"))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
  }
}

unary(変更なし)

  Node *node = unary();

「"*"とprimary または "/"とprimary」を0回以上

  for (;;) {
    if (consume("*"))
      node = new_binary(ND_MUL, node, unary());
    else if (consume("/"))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
   }

consume関数の引数を文字から文字列に変更します。

unary関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR265
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L265

Node *unary() {
  if (consume("+"))
    return unary();
  if (consume("-"))
    return new_binary(ND_SUB, new_num(0), unary());
  return primary();
}

unary関数は、生成規則 unary =("+" | "-")? unary | primaryに基づいて、抽象構文木のノードを生成します。

「"+"または"-" を0回か1回」とunaray

  if (consume("+"))
    return unary();
  if (consume("-"))
    return new_binary(ND_SUB, new_num(0), unary());

consume関数の引数を文字から文字列に変更します。

primary(変更なし)

 return primary();

primary関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR274
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L274

// primary = "(" expr ")" | num
Node *primary() {
  if (consume("(")) {
    Node *node = expr();
    expect(")");
    return node;
  }

  return new_num(expect_number());
}

primary関数は、生成規則 primary = "(" expr ")" | num に基づいて、抽象構文木のノードを生成します。

"("とexprと")"

  if (consume("(")) {
    Node *node = expr();
    expect(")");
    return node;
  }

consume関数・expect関数の引数を文字から文字列に変更します。

num(変更なし)

return new_num(expect_number());

gen関数！

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR313
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L313

void gen(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");
}

数値を得るためのアセンブリコードを生成する(変更なし)

  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

二項演算を行うアセンブリコードを生成する

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");

ノードの型がND_EQの場合(ノードの種類が==の場合)、ノードの型がND_NEの場合(ノードの種類が!=の場合)、ノードの型がND_LTの場合(ノードの種類が<の場合)、ノードの型がND_LEの場合(ノードの種類が<=の場合)、それぞれの場合に応じてアセンブリコードを生成する処理を追加します。
> や >= に対応するアセンブリコードは生成せず、抽象構文木の作成中において < や <= に対応するノードの子ノードを入れ替えることで、> や >= の処理を再現します(詳しくはrelational関数)

cqo
cqo命令は、RAXにセットされている値を128ビット値に符号拡張して、その符号拡張された128ビット値のうち、上位64ビットをRDXに、下位64ビットをRAXにセットします。

idiv rdi
idiv命令は、上位64ビットがRDXにセットされた値、下位64ビットがRAXにセットされた値からなる符号拡張された128ビット値をRDIにセットされている値で除算します。

cmp
cmp命令は、第一オペランドの値と第二オペランドの値を比較し、その比較した結果を、EFLAGSレジスタのフラグに以下のように反映させます。
第一オペランドの値 > 第二オペランドの値 の場合 → CF(キャリーフラグ)=1、ZF(ゼロフラグ)=0
第一オペランドの値 = 第二オペランドの値 の場合 → CF(キャリーフラグ)=0、ZF(ゼロフラグ)=1
第一オペランドの値 < 第二オペランドの値 の場合 → CF(キャリーフラグ)=0、ZF(ゼロフラグ)=0

sete
、、、

setne
、、、

setl
、、、

setle
、、、

movzb
movzb命令は、1byte(8bit)のレジスタにセットされている値を64bitに符号拡張してから、mov命令と同じ処理を行います。

テストコード

test.sh
https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R30
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/test.sh#L30

#!/bin/bash
assert() {
  expected="$1"
  input="$2"
  ./chibicc "$input" > tmp.s
  gcc -static -o tmp tmp.s
  ./tmp
  actual="$?"
  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}
assert 0 0
assert 42 42
assert 21 '5+20-4'
assert 41 ' 12 + 34 - 5 '
assert 47 '5+6*7'
assert 15 '5*(9-6)'
assert 4 '(3+5)/2'
assert 10 '-10+20'
assert 10 '- -10'
assert 10 '- - +10'

assert 0 '0==1'
assert 1 '42==42'
assert 1 '0!=1'
assert 0 '42!=42'

assert 1 '0<1'
assert 0 '1<1'
assert 0 '2<1'
assert 1 '0<=1'
assert 1 '1<=1'
assert 0 '2<=1'

assert 1 '1>0'
assert 0 '1>1'
assert 0 '1>2'
assert 1 '1>=0'
assert 1 '1>=1'
assert 0 '1>=2'

echo OK

Makefile

https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/Makefile

CFLAGS=-std=c11 -g -static

chibicc: main.o
	$(CC) -o $@ $? $(LDFLAGS)

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean

chibiccを読む～Cコンパイラコードリーディング～ ステップ6

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ6に該当
github.com

今回作成するコンパイラ

単項プラスと単項マイナス(単項プラスと単項マイナスを扱えるコンパイラを作成する)

コンパイラのソースコード

https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/main.c

#include <ctype.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//
// Tokenizer
//

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer literals
  TK_EOF,      // End-of-file markers
} TokenKind;

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
};

// Input program
char *user_input;

// Current token
Token *token;

// Reports an error and exit.
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Reports an error location and exit.
void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, ""); // print pos spaces.
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Consumes the current token if it matches `op`.
bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

// Ensure that the current token is `op`.
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error_at(token->str, "expected '%c'", op);
  token = token->next;
}

// Ensure that the current token is TK_NUM.
int expect_number() {
  if (token->kind != TK_NUM)
    error_at(token->str, "expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

bool at_eof() {
  return token->kind == TK_EOF;
}

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Punctuator
    if (strchr("+-*/()", *p)) {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error_at(p, "invalid token");
  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

//
// Parser
//

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_NUM, // Integer
} NodeKind;

// AST node type
typedef struct Node Node;
struct Node {
  NodeKind kind; // Node kind
  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side
  int val;       // Used if kind == ND_NUM
};

Node *new_node(NodeKind kind) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  return node;
}

Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) {
  Node *node = new_node(kind);
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

Node *new_num(int val) {
  Node *node = new_node(ND_NUM);
  node->val = val;
  return node;
}

Node *expr();
Node *mul();
Node *unary();
Node *primary();

// expr = mul ("+" mul | "-" mul)*
Node *expr() {
  Node *node = mul();

  for (;;) {
    if (consume('+'))
      node = new_binary(ND_ADD, node, mul());
    else if (consume('-'))
      node = new_binary(ND_SUB, node, mul());
    else
      return node;
  }
}

// mul = unary ("*" unary | "/" unary)*
Node *mul() {
  Node *node = unary();

  for (;;) {
    if (consume('*'))
      node = new_binary(ND_MUL, node, unary());
    else if (consume('/'))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
  }
}

// unary = ("+" | "-")? unary
//       | primary
Node *unary() {
  if (consume('+'))
    return unary();
  if (consume('-'))
    return new_binary(ND_SUB, new_num(0), unary());
  return primary();
}

// primary = "(" expr ")" | num
Node *primary() {
  if (consume('(')) {
    Node *node = expr();
    expect(')');
    return node;
  }

  return new_num(expect_number());
}

//
// Code generator
//

void gen(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  }

  printf("  push rax\n");
}

int main(int argc, char **argv) {
  if (argc != 2)
    error("%s: invalid number of arguments", argv[0]);

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();
  Node *node = expr();

  // Print out the first half of assembly.
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // Traverse the AST to emit assembly.
  gen(node);

  // A result must be at the top of the stack, so pop it
  // to RAX to make it a program exit code.
  printf("  pop rax\n");
  printf("  ret\n");
  return 0;
}

追加・修正されたコンパイラのソースコード

mul関数

https://github.com/rui314/chibicc/commit/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR186
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/main.c#L186

// mul = unary ("*" unary | "/" unary)*
Node *mul() {
  Node *node = unary();

  for (;;) {
    if (consume('*'))
      node = new_binary(ND_MUL, node, unary());
    else if (consume('/'))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
  }
}

mul関数は、生成規則 mul = unary ("*" unary | "/" unary)* に基づいて、抽象構文木のノードを生成します。

unary

https://github.com/rui314/chibicc/commit/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR188
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/main.c#L188

Node *node = unary();

primary関数をunary関数に変更。

「"*"とprimary または "/"とprimary」を0回以上

  for (;;) {
    if (consume('*'))
      node = new_binary(ND_MUL, node, unary());
    else if (consume('/'))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;

第三引数のprimary関数をunary関数に変更。

unary関数

https://github.com/rui314/chibicc/commit/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR200
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/main.c#L200

// unary = ("+" | "-")? unary
//       | primary
Node *unary() {
  if (consume('+'))
    return unary();
  if (consume('-'))
    return new_binary(ND_SUB, new_num(0), unary());
  return primary();
}

unary関数は、生成規則 unary =("+" | "-")? unary | primaryに基づいて、抽象構文木のノードを生成します。
(低レイヤを知りたい人のためのCコンパイラ作成入門で説明している生成規則と少し異なることに注意)

「"+"または"-" を0回か1回」とunaray

  if (consume('+'))
    return unary();
  if (consume('-'))
    return new_binary(ND_SUB, new_num(0), unary());

consume('+')の戻り値がtrueとなる場合→着目しているトークンが + の場合は、unary関数を再帰的に呼び出します。
(パースの段階で加算記号を表現するノードと数値を表現するノードを生成するのではなく、数値を表現するノードのみを生成します。+xをxに置き換える)

consume('-')の戻り値がtrueとなる場合→着目しているトークンが - の場合は、new_binary関数を呼び出して、減算記号を表現するノードを生成します。この減算記号を表現するノードは、第二引数のnew_num(0)で生成されたノードと第三引数のunary()で生成されたノードを子ノードとして持ちます。
(パースの段階で減算記号を表現するノードと数値を表現するノードの2つを生成するのではなく、減算記号を表現するノードと0を表現するノードと数値を表現するノードの3つを生成します。-xを0-xに置き換える)

primary

 return primary();

consume('+')の戻り値もconsume('-')の戻り値もfalseとなる場合→着目しているトークンが + でも - でもない場合は、primary関数を呼び出します。

テストコード

test.sh
https://github.com/rui314/chibicc/commit/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R26
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/test.sh

#!/bin/bash
assert() {
  expected="$1"
  input="$2"
  ./chibicc "$input" > tmp.s
  gcc -static -o tmp tmp.s
  ./tmp
  actual="$?"
  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}
assert 0 0
assert 42 42
assert 21 '5+20-4'
assert 41 ' 12 + 34 - 5 '
assert 47 '5+6*7'
assert 15 '5*(9-6)'
assert 4 '(3+5)/2'
assert 10 '-10+20'
assert 10 '- -10'
assert 10 '- - +10'

echo OK

Makefile

https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/Makefile

CFLAGS=-std=c11 -g -static

chibicc: main.o
	$(CC) -o $@ $? $(LDFLAGS)

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean

chibiccを読む～Cコンパイラコードリーディング～ ステップ5

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ5に該当
github.com

今回作成するコンパイラ

四則演算のできる言語の作成(四則演算の式を扱えるコンパイラを作成する)

コンパイラのソースコード

https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c

#include <ctype.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//
// Tokenizer
//

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer literals
  TK_EOF,      // End-of-file markers
} TokenKind;

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
};

// Input program
char *user_input;

// Current token
Token *token;

// Reports an error and exit.
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Reports an error location and exit.
void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, ""); // print pos spaces.
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Consumes the current token if it matches `op`.
bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

// Ensure that the current token is `op`.
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error_at(token->str, "expected '%c'", op);
  token = token->next;
}

// Ensure that the current token is TK_NUM.
int expect_number() {
  if (token->kind != TK_NUM)
    error_at(token->str, "expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

bool at_eof() {
  return token->kind == TK_EOF;
}

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Punctuator
    if (strchr("+-*/()", *p)) {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error_at(p, "invalid token");
  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

//
// Parser
//

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_NUM, // Integer
} NodeKind;

// AST node type
typedef struct Node Node;
struct Node {
  NodeKind kind; // Node kind
  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side
  int val;       // Used if kind == ND_NUM
};

Node *new_node(NodeKind kind) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  return node;
}

Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) {
  Node *node = new_node(kind);
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

Node *new_num(int val) {
  Node *node = new_node(ND_NUM);
  node->val = val;
  return node;
}

Node *expr();
Node *mul();
Node *primary();

// expr = mul ("+" mul | "-" mul)*
Node *expr() {
  Node *node = mul();

  for (;;) {
    if (consume('+'))
      node = new_binary(ND_ADD, node, mul());
    else if (consume('-'))
      node = new_binary(ND_SUB, node, mul());
    else
      return node;
  }
}

// mul = primary ("*" primary | "/" primary)*
Node *mul() {
  Node *node = primary();

  for (;;) {
    if (consume('*'))
      node = new_binary(ND_MUL, node, primary());
    else if (consume('/'))
      node = new_binary(ND_DIV, node, primary());
    else
      return node;
  }
}

// primary = "(" expr ")" | num
Node *primary() {
  if (consume('(')) {
    Node *node = expr();
    expect(')');
    return node;
  }

  return new_num(expect_number());
}

//
// Code generator
//

void gen(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  }

  printf("  push rax\n");
}

int main(int argc, char **argv) {
  if (argc != 2)
    error("%s: invalid number of arguments", argv[0]);

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();
  Node *node = expr();

  // Print out the first half of assembly.
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // Traverse the AST to emit assembly.
  gen(node);

  // A result must be at the top of the stack, so pop it
  // to RAX to make it a program exit code.
  printf("  pop rax\n");
  printf("  ret\n");
  return 0;
}

追加・修正されたコンパイラのソースコード

main関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR252
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L252

int main(int argc, char **argv) {
  if (argc != 2)
    error("%s: invalid number of arguments", argv[0]);

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();
  Node *node = expr();

  // Print out the first half of assembly.
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // Traverse the AST to emit assembly.
  gen(node);

  // A result must be at the top of the stack, so pop it
  // to RAX to make it a program exit code.
  printf("  pop rax\n");
  printf("  ret\n");
  return 0;
}

コマンドライン引数の個数をチェックする(変更なし)

  if (argc != 2)
    error("%s: invalid number of arguments", argv[0]);

トークナイズを行う(変更なし)

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();

パースを行う

  Node *node = expr();

expr関数を呼び出して、抽象構文木を作成します。戻り値は抽象構文木のルートノードのアドレスです。

部分的にアセンブリコードを生成する①(変更なし)

  // Print out the first half of assembly.
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

部分的にアセンブリコードを生成する②

  // Traverse the AST to emit assembly.
  gen(node);

gen関数を呼び出し、抽象構文木を用いてアセンブリコードを生成します。

部分的にアセンブリコードを生成する③

  // A result must be at the top of the stack, so pop it
  // to RAX to make it a program exit code.
  printf("  pop rax\n");
  printf("  ret\n");
  return 0;

抽象構文木の最終的な結果を表す値がスタックに退避されているので(gen関数の最後ではアセンブリコード"push rax"を生成しているので)、アセンブリコード"pop rax"を生成して、抽象構文木の最終的な結果を表す値がraxレジスタにセットされるようにします。最後にアセンブリコード"ret"を生成します。

tokenize関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR108
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L108

Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Punctuator
    if (strchr("+-*/()", *p)) {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error_at(p, "invalid token");
  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

文字列の先頭アドレスを取得する(変更なし)

  char *p = user_input;

トークンからなる連結リストのヘッダーを作成する(変更なし)

  Token head;
  head.next = NULL;
  Token *cur = &head;

空白文字の場合(変更なし)

    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

+-*/()の場合

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR108
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L108

    // Punctuator
    if (strchr("+-*/()", *p)) {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

str関数は、第一引数で指定された文字列から、第二引数で指定された文字を探索します。
第二引数の文字がみつかった場合は、第一引数の文字列において第二引数の文字が位置しているアドレス値が戻り値となります。
第二引数の文字がみつからなかった場合は、NULLが戻り値となります。
条件式strchr("+-*/()", *p) が真となる場合→文字*pが +、-、*、/、(、) のいずれかの場合は、new_token関数を呼び出して、記号を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
次の文字を取得するためにchar型へのポインタpをインクリメントしてからwhile文のループを継続します(char型へのポインタpを後置インクリメントしているので、評価前のpの値(+または-の文字を指定するアドレス)が引数として渡されます)。

数字の場合(変更なし)

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

その他の場合

    error_at(p, "invalid token");
  }

エラーメッセージを変更。

トークン列の終端を表すトークンを生成する(変更なし)

  new_token(TK_EOF, cur, p);

連結リストの先頭トークンを戻り値としてリターンする(変更なし)

return head.next;

NodeKind

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR131
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L131

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_NUM, // Integer
} NodeKind;

enum型を用いて、ノードの種類(ノードの型)を表現する名前付き整数定数を定めます。さらに、typedefキーワードを用いて、enum型をNodeKind型として定義します。

Node構造体

typedef struct Node Node;
struct Node {
  NodeKind kind; // Node kind
  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side
  int val;       // Used if kind == ND_NUM
};

ノードを表現するデータ構造であるNode構造体を定義します。
さらに、typedefキーワードを用いて、Node構造体をNode型として定義します。

new_node関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR148
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L148

Node *new_node(NodeKind kind) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  return node;
}

new_node関数は、抽象構文木のノードを新規に生成します。

ノードを生成する

  Node *node = calloc(1, sizeof(Node));

calloc関数を呼び出して、ノード構造体の生成に必要なメモリ領域を割り当てます。
calloc関数は、第二引数で指定されたバイトサイズ分のメモリ領域を、第一引数で指定された数だけ、割り当てます。
今回は、sizeof(Node)バイトのメモリ領域を1つ割り当てています。

生成されたノードのメンバに値を設定する

  node->kind = kind;
  

引数で指定されたkindの値(ノードの種類、ノードの型)を生成されるノード構造体のメンバに設定します。

生成されたノードを戻り値としてリターンする

return node;

生成されたノード構造体のアドレスを戻り値としてリターンします。

new_binary関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR154
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L154

Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) {
  Node *node = new_node(kind);
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

new_binary関数は、抽象構文木のノード(子ノードを2つ持つ)を新規に生成します。

ノードを生成する

Node *node = new_node(kind);

new_node関数を呼び出して、抽象構文木のノードを新規に生成します。

生成されたノードに2つの子ノードを登録する

  node->lhs = lhs;
  node->rhs = rhs;

引数lhsの値(左の子ノードを指定するアドレス)と引数rhsの値(右の子ノードを指定するアドレス)を生成されるノード構造体のメンバに設定します。

生成されたノードを戻り値としてリターンする

return node

生成されたノード構造体のアドレスを戻り値としてリターンします。

new_num関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR161
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L161

Node *new_num(int val) {
  Node *node = new_node(ND_NUM);
  node->val = val;
  return node;
}

new_binary関数は、抽象構文木のノード(数値に対応する外部ノード)を新規に生成します。

ノードを生成する

Node *node = new_node(ND_NUM);

new_node関数を呼び出して、抽象構文木のノードを新規に生成します。

生成されたノードのメンバに値を設定する

node->val = val;

引数で指定されたvalの値(ノードの種類、ノードの型)を生成されるノード構造体のメンバに設定します。

生成されたノードを戻り値としてリターンする

return node;

生成されたノード構造体のアドレスを戻り値としてリターンします。

expr関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR172
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L172

Node *expr() {
  Node *node = mul();

  for (;;) {
    if (consume('+'))
      node = new_binary(ND_ADD, node, mul());
    else if (consume('-'))
      node = new_binary(ND_SUB, node, mul());
    else
      return node;
  }
}

expr関数は、生成規則 expr = mul ("+" mul | "-" mul)* に基づいて、抽象構文木のノードを生成します。

mul

Node *node = mul();

mul関数を呼び出して、抽象構文木のノードを生成します。

「"+"とmul または "-"とmul」を0回以上

  for (;;) {
    if (consume('+'))
      node = new_binary(ND_ADD, node, mul());
    else if (consume('-'))
      node = new_binary(ND_SUB, node, mul());
    else
      return node;
  }

consume('+')の戻り値がtrueとなる場合→着目しているトークンが + の場合は、new_binary関数を呼び出して、加算記号を表現するノードを生成します。この加算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのmul関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。

consume('-')の戻り値がtrueとなる場合→着目しているトークンが - の場合は、new_binary関数を呼び出して、減算記号を表現するノードを生成します。この減算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのprimary関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。

上記以外の場合は、最後に生成されたノードのアドレスを戻り値としてリターンします。

mul関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR186
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L186

Node *mul() {
  Node *node = primary();

  for (;;) {
    if (consume('*'))
      node = new_binary(ND_MUL, node, primary());
    else if (consume('/'))
      node = new_binary(ND_DIV, node, primary());
    else
      return node;
  }
}

mul関数は、生成規則 mul = primary ("*" primary | "/" primary)* に基づいて、抽象構文木のノードを生成します。

primary

Node *node = primary();

primary関数を呼び出して、抽象構文木のノードを生成します。

「"*"とprimary または "/"とprimary」を0回以上

  for (;;) {
    if (consume('*'))
      node = new_binary(ND_MUL, node, primary());
    else if (consume('/'))
      node = new_binary(ND_DIV, node, primary());
    else
      return node;

consume('*')の戻り値がtrueとなる場合→着目しているトークンが * の場合は、new_binary関数を呼び出して、乗算記号を表現するノードを生成します。この乗算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのprimary関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。

consume('/')の戻り値がtrueとなる場合→着目しているトークンが / の場合は、new_binary関数を呼び出して、除算記号を表現するノードを生成します。この除算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのprimary関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。

上記以外の場合は、最後に生成されたノードのアドレスを戻り値としてリターンします。

primary関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR200
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L200

Node *primary() {
  if (consume('(')) {
    Node *node = expr();
    expect(')');
    return node;
  }

  return new_num(expect_number());
}

primary関数は、生成規則 primary = "(" expr ")" | num に基づいて、抽象構文木のノードを生成します。
(低レイヤを知りたい人のためのCコンパイラ作成入門では、primary = num | "(" expr ")" となっていますがどちらでも問題ありません)

"("とexprと")"

  if (consume('(')) {
    Node *node = expr();
    expect(')');
    return node;
  }

consume('(')の戻り値がtrueとなる場合→着目しているトークンが ( の場合は、expr関数を呼び出します。
expr関数内でトークン列の読み進めや抽象構文木のノード生成が終わった後は、着目しているトークンが ) であることが期待されているので、expect(')')を呼び出します。最後に、expr関数で生成されたノードのアドレスを戻り値としてリターンします。

num

return new_num(expect_number());

consume('(')の戻り値がfalseとなる場合→着目しているトークンが ( ではない場合は、new_num関数を呼び出して、expect_number関数で読み取ったトークンに対応する抽象構文木のノードを生成し、生成されたノードのアドレスを戻り値としてリターンします。

gen関数

https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR214
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L214

void gen(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  }

  printf("  push rax\n");
}

gen関数は、引数で指定された抽象構文木のノードを用いて、アセンブリコードを生成します。

数値を得るためのアセンブリコードを生成する

  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

再帰的に呼び出されるgen関数の基底となる処理です(抽象構文木の外部ノードを生成する処理です)。
引数で指定されたノードの型がND_NUMの場合は(ノードの種類が整数の場合は)、"push (ノードが持つ整数の値)"を生成し、リターンします。

二項演算の対象となる値を得るためのアセンブリコードを生成する

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

gen(node->lhs)関数を呼び出して、ノードlhsに対応する値(左の部分木の結果)を得るために必要となるアセンブリコードを生成します。
gen(node->rhs)関数を呼び出して、ノードrhsに対応する値(右の部分木の結果)を得るために必要となるアセンブリコードを生成します。
生成されるアセンブリコードの実行時を考慮すると、ノードlhsに対応する値とノードrhsに対応する値はスタックに退避されている状態なので、ノードlhsに対応する値とノードrhsに対応する値をレジスタにセットして演算対象とするために、 アセンブリコード"pop rdi" と "pop rax"を生成します。
スタックには、ボトムからトップの方向へ、ノードlhsに対応する値、ノードrhsに対応する値、の順で退避されているので、rdiレジスタにはノードrhsに対応する値が、raxレジスタにはノードlhsに対応する値が、それぞれセットされます。

二項演算を行うアセンブリコードを生成する

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  }

  printf("  push rax\n");

ノードの型に応じて、演算で必要となるアセンブリコードを生成します。
ノードの型がND_ADDの場合は(ノードの種類が加算記号の場合は)、アセンブリコード”add rax, rdi”を生成します。
ノードの型がND_SUBの場合は(ノードの種類が減算記号の場合は)、アセンブリコード”sub rax, rdi”を生成します。
ノードの型がND_MULの場合は(ノードの種類が乗算記号の場合は)、アセンブリコード”imul rax, rdi”を生成します。
ノードの型がND_DIVの場合は(ノードの種類が除算記号の場合は)、アセンブリコード”cqo”と”idiv rdi”を生成します。
最後に演算結果の値をスタックへ退避させるために、アセンブリコード"push rax"を生成します。

テストコード

test.sh
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R23
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/test.sh

#!/bin/bash
assert() {
  expected="$1"
  input="$2"

  ./9cc "$input" > tmp.s
  cc -o tmp tmp.s
  ./tmp
  actual="$?"

  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 0
assert 42 42
assert 21 "5+20-4"
assert 41 " 12 + 34 - 5 "
assert 47 '5+6*7'
assert 15 '5*(9-6)'
assert 4 '(3+5)/2'

echo OK

Makefile

https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/Makefile

CFLAGS=-std=c11 -g -static

chibicc: main.o
	$(CC) -o $@ $? $(LDFLAGS)

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean

chibiccを読む～Cコンパイラコードリーディング～ ステップ4

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ4に該当
github.com

今回作成するコンパイラ

エラーメッセージを改良(エラーメッセージを改良したコンパイラを作成する)。

コンパイラのソースコード

https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/main.c

#include <ctype.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer literals
  TK_EOF,      // End-of-file markers
} TokenKind;

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
};

// Input program
char *user_input;

// Current token
Token *token;

// Reports an error and exit.
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Reports an error location and exit.
void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, ""); // print pos spaces.
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Consumes the current token if it matches `op`.
bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

// Ensure that the current token is `op`.
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error_at(token->str, "expected '%c'", op);
  token = token->next;
}

// Ensure that the current token is TK_NUM.
int expect_number() {
  if (token->kind != TK_NUM)
    error_at(token->str, "expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

bool at_eof() {
  return token->kind == TK_EOF;
}

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Punctuator
    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error_at(p, "expected a number");
  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

int main(int argc, char **argv) {
  if (argc != 2) {
    error("%s: invalid number of arguments", argv[0]);
    return 1;
  }

  user_input = argv[1];
  token = tokenize();

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // The first token must be a number
  printf("  mov rax, %d\n", expect_number());

  // ... followed by either `+ <number>` or `- <number>`.
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

  printf("  ret\n");
  return 0;
}

追加・修正されたコンパイラのソースコード

main関数

https://github.com/rui314/chibicc/commit/c6ff1d98a1419e69c31902447e2caa85af4e9844#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR129
https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/main.c#L129

int main(int argc, char **argv) {
  if (argc != 2) {
    error("%s: invalid number of arguments", argv[0]);
    return 1;
  }

  user_input = argv[1];
  token = tokenize();

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // The first token must be a number
  printf("  mov rax, %d\n", expect_number());

  // ... followed by either `+ <number>` or `- <number>`.
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

  printf("  ret\n");
  return 0;
}

コマンドライン引数の個数をチェックする(変更なし)

  if (argc != 2) {
    error("%s: invalid number of arguments", argv[0]);
    return 1;
  }

トークナイズを行う

  user_input = argv[1];
  token = tokenize();

文字列の何バイト目でエラーが生じたかを計算するために、文字列の先頭アドレスをグローバル変数user_inputに格納してからトークナイズを行います。

https://github.com/rui314/chibicc/commit/c6ff1d98a1419e69c31902447e2caa85af4e9844#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR23
https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/main.c#L23

// Input program
char *user_input;

部分的にアセンブリコードを生成する①(変更なし)

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

部分的にアセンブリコードを生成する②(変更なし)

  // The first token must be a number
  printf("  mov rax, %d\n", expect_number());

部分的にアセンブリコードを生成する③(変更なし)

  // ... followed by either `+ <number>` or `- <number>`.
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

部分的にアセンブリコードを生成する④(変更なし)

  printf("  ret\n");
  return 0;

error_at関数

https://github.com/rui314/chibicc/commit/c6ff1d98a1419e69c31902447e2caa85af4e9844#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR38
https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/main.c#L38

// Reports an error location and exit.
void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, ""); // print pos spaces.
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

error_at関数は、トークナイズ途中の文字を指定するアドレスloc、引数fmtで指定された文字列、可変部の引数を用いてメッセージを出力し、プログラム(プロセス)を終了させます。

va_list apについて

va_startマクロ・vprintf関数などを使用するために必要となるva_list型の変数apを宣言します。

va_start(ap, fmt)について

va_list型の変数apを初期化して可変個の引数を扱えるようにするために、va_startマクロを呼び出します。
第一引数には先ほど宣言したva_list型の変数apを、第二引数には可変部分の引数の直前にある引数fmtを指定する必要があります。

エラーが生じた文字の算出を計算する

int pos = loc - user_input;

トークナイズの対象となる文字列において、先頭の文字からエラーが生じた文字まで何文字分(何バイト分)あるかを算出します。

fprintf(stderr, "%s\n", user_input)について

fprintf関数は、第一引数のファイルポインタが指定するファイルに、第二引数のchar型へのポインタが指定する文字列データを書き込みます。
今回の場合は、標準エラー出力ファイルに、user_inputが指定する文字列が書き込ます(コンソール画面にトークナイズの対象となる文字列が表示されます)。

fprintf(stderr, "%*s", pos, "")について

fprintf関数を呼び出して、標準エラー出力ファイルに、空白文字をpos文字分書き込みます(コンソール画面に空白文字がpos文字分表示されます)。
書式指定フィールドのwidthフィールドに＊が指定されている時は、引数posが指定する文字幅の分だけ表示します。

fprintf(stderr, "^ ")ついて

fprintf関数を呼び出して、標準エラー出力ファイルに ^ を書き込みます(コンソール画面に、トークナイズの対象となる文字列のうちエラーが生じた文字の下に ^ が表示されます)。

vfprintf(stderr, fmt, ap)について

vfprintf関数は、可変個の引数を扱うことができるfprintf関数です。
標準エラー出力ファイルに、fmtが指定する文字列データを書き込みます(コンソール画面に文字列が表示されます)。

fprintf(stderr, "\n")について

fprintf関数を呼び出して、標準エラー出力ファイルに、\nを書き込みます(コンソール画面で改行が行われます)。

exit(1)について

exitシステムコールを呼び出して、このプログラム(プロセス)の処理を終了させます。
引数で指定した1の値が終了ステータスになります。

tokenize関数

https://github.com/rui314/chibicc/commit/c6ff1d98a1419e69c31902447e2caa85af4e9844#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR116
https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/main.c#L116

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Punctuator
    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error_at(p, "expected a number");
  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

文字列の先頭アドレスを取得する

char *p = user_input;

グローバル変数user_inputから、トークナイズの対象となる文字列の先頭アドレスを取得します。

トークンからなる連結リストのヘッダーを作成する(変更なし)

  Token head;
  head.next = NULL;
  Token *cur = &head;

空白文字の場合(変更なし)

    if (isspace(*p)) {
      p++;
      continue;
    }

+ または - の場合(変更なし)

    // Punctuator
    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

数字の場合(変更なし)

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

その他の場合

    error_at(p, "expected a number");

上記のいずれにも該当しなかった場合は、error_at関数を呼び出して、メッセージを出力してからプログラムを終了させます。

トークン列の終端を表すトークンを生成する(変更なし)

  new_token(TK_EOF, cur, p);

連結リストの先頭トークンを戻り値としてリターンする(変更なし)

return head.next;

expect関数

https://github.com/rui314/chibicc/commit/c6ff1d98a1419e69c31902447e2caa85af4e9844#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR63
https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/main.c#L63

// Ensure that the current token is `op`.
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error_at(token->str, "expected '%c'", op);
  token = token->next;
}

現在着目しているトークンの文字列を調べる

  if (token->kind != TK_RESERVED || token->str[0] != op)
    error_at(token->str, "expected '%c'", op);

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合は、error_at関数を呼び出して、メッセージを出力し処理を終了します。

着目しているトークンを次のトークンに変更する(変更なし)

token = token->next;

expect_number関数

https://github.com/rui314/chibicc/commit/c6ff1d98a1419e69c31902447e2caa85af4e9844#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR70
https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/main.c#L70

int expect_number() {
  if (token->kind != TK_NUM)
    error_at(token->str, "expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

現在着目しているトークンの種類が整数であることを確認する

  if (token->kind != TK_NUM)
    error_at(token->str, "expected a number");

現在着目しているトークンの型がTK_NUMではない場合(トークンの種類が整数ではない場合)、error_at関数を呼び出して、メッセージを出力し処理を終了します。

着目しているトークンを次のトークンに変更する(変更なし)

  int val = token->val;
  token = token->next;
  return val;

テストコード

test.sh
https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/test.sh

#!/bin/bash
assert() {
  expected="$1"
  input="$2"

  ./chibicc "$input" > tmp.s
  gcc -static -o tmp tmp.s
  ./tmp
  actual="$?"

  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 0
assert 42 42
assert 21 '5+20-4'
assert 41 ' 12 + 34 - 5 '

echo OK

Makefile

https://github.com/rui314/chibicc/blob/c6ff1d98a1419e69c31902447e2caa85af4e9844/Makefile

CFLAGS=-std=c11 -g -static

chibicc: main.o
	$(CC) -o $@ $? $(LDFLAGS)

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean

chibiccを読む～Cコンパイラコードリーディング～ ステップ3

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ3に該当
github.com

今回作成するコンパイラ

トークナイザを導入(トークナイザが導入されたコンパイラ)

コンパイラのソースコード

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c

#include <ctype.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer literals
  TK_EOF,      // End-of-file markers
} TokenKind;

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
};

// Current token
Token *token;

// Reports an error and exit.
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Consumes the current token if it matches `op`.
bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

// Ensure that the current token is `op`.
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("expected '%c'", op);
  token = token->next;
}

// Ensure that the current token is TK_NUM.
int expect_number() {
  if (token->kind != TK_NUM)
    error("expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

bool at_eof() {
  return token->kind == TK_EOF;
}

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

// Tokenize `p` and returns new tokens.
Token *tokenize(char *p) {
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Punctuator
    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error("invalid token");
  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

int main(int argc, char **argv) {
  if (argc != 2) {
    error("%s: invalid number of arguments", argv[0]);
    return 1;
  }

  token = tokenize(argv[1]);

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // The first token must be a number
  printf("  mov rax, %d\n", expect_number());

  // ... followed by either `+ <number>` or `- <number>`.
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

  printf("  ret\n");
  return 0;
}

追加・修正されたコンパイラのソースコード

main関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR105
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L105

int main(int argc, char **argv) {
  if (argc != 2) {
    error("%s: invalid number of arguments", argv[0]);
    return 1;
  }

  token = tokenize(argv[1]);

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // The first token must be a number
  printf("  mov rax, %d\n", expect_number());

  // ... followed by either `+ <number>` or `- <number>`.
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

  printf("  ret\n");
  return 0;
}

コマンドライン引数の個数をチェックする

  if (argc != 2) {
    error("%s: invalid number of arguments", argv[0]);
    return 1;
  }

argcの値が2であること→コマンドライン引数が2個であること→プログラムを実行するときに渡された引数が1つであることを確認します。
argcの値が2ではない場合は、error関数を実行して、メッセージを出力してからプログラムを終了させます。

トークナイズを行う

token = tokenize(argv[1]);

tokenize関数を呼び出して、argv[1]が指定する文字列をトークナイズします。
tokenには連結リストの先頭トークンを指定するアドレスが格納されます。

部分的にアセンブリコードを生成する①

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

部分的にアセンブリコードを生成する②

 printf("  mov rax, %d\n", expect_number());

トークン列の先頭は整数であることが期待されているので、expect_number関数を呼び出してトークンを1つ読み進めます。
また、expect_number関数の戻り値は、その整数の値となります。

部分的にアセンブリコードを生成する③

  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

at_eof()関数の戻り値がtrueになるまで→着目しているトークンがトークン列の終端を表すトークンになるまで、while文のループを継続します。
consume('+')の戻り値がtrueになる場合は、アセンブリコード"add rax, expect_number関数の戻り値"を生成します。
consume('+')の戻り値がfalseになる場合は、着目しているトークンは - であることが期待されているので、expect('-')を呼び出してから、アセンブリコード"sub rax, expect_number関数の戻り値"を生成します。

部分的にアセンブリコードを生成する④

  printf("  ret\n");
  return 0;

error関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR26
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L26

// Reports an error and exit.
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

error関数は、引数fmtで指定された文字列と可変部の引数を用いてメッセージを出力し、プログラム(プロセス)を終了させます。

va_list ap について

va_startマクロ・vprintf関数などを使用するために必要となるva_list型の変数apを宣言します。

va_start(ap, fmt) について

va_list型の変数apを初期化して可変個の引数を扱えるようにするために、va_startマクロを呼び出します。
第一引数には先ほど宣言したva_list型の変数apを、第二引数には可変部分の引数の直前にある引数fmtを指定する必要があります。

vfprintf(stderr, fmt, ap) について

vfprintf関数は、可変個の引数を扱うことができるfprintf関数です。
標準エラー出力ファイルに、fmtが指定する文字列データを書き込みます(コンソール画面に文字列が表示されます)。

fprintf(stderr, "\n") について

fprintf関数を呼び出して、標準エラー出力ファイルに、\nを書き込みます(コンソール画面で改行が行われます)。

exit(1) について

exitシステムコールを呼び出して、このプログラム(プロセス)の処理を終了させます。
引数で指定した1の値が終了ステータスになります。

TokenKind

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR8
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L8

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer literals
  TK_EOF,      // End-of-file markers
} TokenKind;

enum型を用いて、トークンの種類(トークンの型)を表現する名前付き整数定数を定めます。さらに、typedefキーワードを用いて、enum型をTokenKind型として定義します。

Token構造体

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR14
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L14

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
};

トークンを表現するデータ構造であるToken構造体を定義します。
さらに、typedefキーワードを用いて、Token構造体をToken型として定義します。

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR24
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L24

Token *token;

また、パースやアセンブリコード生成の際に着目しているトークンをグローバル変数tokenで表現します。

tokenize関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR72
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L72

// Tokenize `p` and returns new tokens.
Token *tokenize(char *p) {
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Punctuator
    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error("invalid token");

  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

tokenize関数は、引数pで指定された文字列をトークン列に分割します。

トークンからなる連結リストのヘッダーを作成する

  Token head;
  head.next = NULL;
  Token *cur = &head;

トークン構造体headを定義し、これから作成する連結リスト(トークン構造体からなる連結リスト)のヘッダーとします。
nextメンバの初期値はNULL、連結リストの終端をcurで表現します。

空白文字の場合(while文内で一文字ずつ文字を読み込んだ時)

    if (isspace(*p)) {
      p++;
      continue;
    }

isspace(*p)の戻り値が0以外の場合は→文字*pが空白文字だった場合は、次の文字を取得するためにchar型へのポインタpをインクリメントしてからwhile文のループを継続します。
isspace関数は、引数で指定された文字が空白文字であるかを判定します。引数で指定された文字が空白文字である場合は0以外の値が戻り値となり、引数で指定された文字が空白文字ではない場合は、0が戻り値となります。

+ または - の場合(while文内で一文字ずつ文字を読み込んだ時)

    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

文字*pが+または-だった場合は、new_token関数を呼び出して、記号を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
次の文字を取得するためにchar型へのポインタpをインクリメントしてからwhile文のループを継続します(char型へのポインタpを後置インクリメントしているので、評価前のpの値(+または-の文字を指定するアドレス)が引数として渡されます)。

数字の場合(while内で一文字ずつ文字を読み込んだ時)

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

isdigit関数は、引数で指定された文字が数字であるかを判定します。引数で指定された文字が数字である場合は0以外の値が戻り値となり、引数で指定された文字が数字ではない場合は0が戻り値となります。
isdigit(*p)の戻り値が0以外の場合は→文字*pが数字だった場合は、new_token関数を呼び出して、数値を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
strtol関数を呼び出して新規に生成されたトークンにその数値を記録してから、while文のループを継続します(strtol関数の引数pには、数字の次にある文字を指定するアドレスが格納されます)。

その他の場合(while内で一文字ずつ文字を読み込んだ時)

    error("invalid token");

上記のいずれにも該当しなかった場合は、error関数を呼び出して、メッセージを出力してからプログラムを終了させます。

トークン列の終端を表すトークンを生成する

  new_token(TK_EOF, cur, p);
  return head.next;

最後に、トークン列の終端を表すトークンを生成します。

連結リストの先頭トークンを戻り値としてリターンする

return head.next;

連結リストの先頭トークン(連結リストのヘッダーの次にあるトークン)のアドレスを戻り値としてリターンします。

new_token関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR63
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L63

Token *new_token(TokenKind kind, Token *cur, char *str) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

new_token関数は、新規にトークンを生成し、引数curで指定されたトークンと生成されたトークンを連結させます。

トークンを生成する

Token *tok = calloc(1, sizeof(Token));

calloc関数を呼び出して、トークン構造体の生成に必要なメモリ領域を割り当てます。
calloc関数は、第二引数で指定されたバイトサイズ分のメモリ領域を、第一引数で指定された数だけ、割り当てます。
今回は、sizeof(Token)バイトのメモリ領域を1つ割り当てています。

生成されたトークンのメンバに値を設定する

  tok->kind = kind;
  tok->str = str;

引数で指定されたkindの値(トークンの種類、トークンの型)とstrの値(トークンの文字列)を生成されるトークン構造体のメンバに設定します。

生成されたトークンを連結リストに追加する

cur->next = tok;

引数curで指定されたトークン構造体のnextメンバに、生成されたトークンのアドレスを格納します。

生成されたトークンを戻り値としてリターンする

return tok;

生成されたトークン構造体のアドレスを戻り値としてリターンします。

at_eof関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR59
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L59

bool at_eof() {
  return token->kind == TK_EOF;
}

at_eof関数は、現在着目しているトークンがトークン列の終端であるかを判定します。
現在着目しているトークンがトークン列の終端である場合はtrueを、現在着目しているトークンがトークン列の終端ではない場合はfalseを、戻り値としてリターンします。

consume関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR35
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L35

bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

consume関数は、現在着目しているトークンの文字列が引数opで指定された文字列と同じであるかを判定します。

現在着目しているトークンの文字列を調べる

  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合は、戻り値をflaseとしてリターンします。

着目しているトークンを次のトークンに変更する

  token = token->next;
  return true;

上記以外の場合は、着目しているトークンを次のトークンに変更し、戻り値をtrueとしてリターンします。

expect関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR43
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L43

void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("expected '%c'", op);
  token = token->next;
}

expect関数は、現在着目しているトークンの文字列が引数opで指定された文字列と同じである場合に、トークンを1つ読み進めます。

現在着目しているトークンの文字列を調べる

  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("expected '%c'", op);

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合は、error関数を呼び出して、メッセージを出力し処理を終了します。

着目しているトークンを次のトークンに変更する

 token = token->next;

上記以外の場合は、着目しているトークンを次のトークンに変更します。

expect_number関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR50
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L50

int expect_number() {
  if (token->kind != TK_NUM)
    error("expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

expect_number関数は、現在着目しているトークンの種類が整数である場合に、トークンを1つ読み進めます。

現在着目しているトークンの種類が整数であることを確認する

  if (token->kind != TK_NUM)
    error("expected a number");

現在着目しているトークンの型がTK_NUMではない場合(トークンの種類が整数ではない場合)、error関数を呼び出して、メッセージを出力し処理を終了します。

着目しているトークンを次のトークンに変更する

  int val = token->val;
  token = token->next;
  return val;

上記以外の場合は、着目しているトークンを次のトークンに変更し、トークンが持つ整数値を戻り値としてリターンします。

テストコード

test.sh
https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R22
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/test.sh#L22

#!/bin/bash
assert() {
  expected="$1"
  input="$2"

  ./chibicc "$input" > tmp.s
  gcc -static -o tmp tmp.s
  ./tmp
  actual="$?"

  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 0
assert 42 42
assert 21 '5+20-4'
assert 41 ' 12 + 34 - 5 '

echo OK

Makefile

https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/Makefile

CFLAGS=-std=c11 -g -static

chibicc: main.o
	$(CC) -o $@ $? $(LDFLAGS)

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean

chibiccを読む～Cコンパイラコードリーディング～ ステップ2

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ2に該当
github.com

今回作成するコンパイラ

加減算のできるコンパイラの作成(「加減算を含む式」を入力から読んで「その加減算を実行時に行うアセンブリ」を出力するコンパイラを作成する)

コンパイラのソースコード

main.c
https://github.com/rui314/chibicc/commit/afc9e8f05faddf051aa3a578520d6484ab451282#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR10
https://github.com/rui314/chibicc/blob/afc9e8f05faddf051aa3a578520d6484ab451282/main.c#L10

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "%s: invalid number of arguments\n", argv[0]);
    return 1;
  }

  char *p = argv[1];

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");
  printf("  mov rax, %ld\n", strtol(p, &p, 10));

  while (*p) {
    if (*p == '+') {
      p++;
      printf("  add rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    if (*p == '-') {
      p++;
      printf("  sub rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    fprintf(stderr, "unexpected character: '%c'\n", *p);
    return 1;
  }

  printf("  ret\n");
  return 0;
}

コマンドライン引数の個数をチェックする(変更なし)

  if (argc != 2) {
    fprintf(stderr, "%s: invalid number of arguments\n", argv[0]);
    return 1;
  }

アセンブリコードを生成する

  char *p = argv[1];

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");
  printf("  mov rax, %ld\n", strtol(p, &p, 10));

  while (*p) {
    if (*p == '+') {
      p++;
      printf("  add rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    if (*p == '-') {
      p++;
      printf("  sub rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    fprintf(stderr, "unexpected character: '%c'\n", *p);
    return 1;
  }

  printf("  ret\n");
  return 0;

strtol関数について
strtol関数は、第一引数で指定された文字列の先頭部分にある数字を、第三引数で指定された基数で、取得します。
第二引数のアドレスが指定するポインタには、第一引数で指定された文字列の先頭部分にある数字の次にある文字を指定するアドレスが格納されます。

char *p = "5+20-4";
strtol(p, &p, 10));

例えば上記のようなプログラムの場合、第一引数pで指定された文字列"5+20-4"の先頭部分にある数字"5"を、第三引数で指定された基数(10進数)で、取得します(strtol関数の戻り値が5になります)。
第二引数のアドレス&pが指定するポインタpには、第一引数で指定された文字列"5+20-4"の先頭部分にある数字"5"の次にある文字"+"を指定するアドレスが格納されます。

コンパイラが出力するアセンブリコード

「5+20-4」を入力から読んだ場合

.intel_syntax noprefix
.globl main

main:
        mov rax, 5
        add rax, 20
        sub rax, 4
        ret

テストコード

test.sh
https://github.com/rui314/chibicc/commit/afc9e8f05faddf051aa3a578520d6484ab451282#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R21
https://github.com/rui314/chibicc/blob/afc9e8f05faddf051aa3a578520d6484ab451282/test.sh#L21

#!/bin/bash
assert() {
  expected="$1"
  input="$2"

  ./chibicc "$input" > tmp.s
  gcc -static -o tmp tmp.s
  ./tmp
  actual="$?"

  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 0
assert 42 42
assert 21 '5+20-4'

echo OK

Makefile

https://github.com/rui314/chibicc/blob/afc9e8f05faddf051aa3a578520d6484ab451282/Makefile

CFLAGS=-std=c11 -g -static

chibicc: main.o
	$(CC) -o $@ $? $(LDFLAGS)

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean