ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

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

// token　type 構造体
typedef enum {
    TK_RESERVED, // op
    TK_NUM,
    TK_EOF, // end of input
} TokenKind;

typedef struct Token Token;

// token　
struct Token {
    TokenKind kind; // token type
    Token *next; // next token
    int val; // TK_NUM value
    char *str; // token char
};

// now focus token
Token *token;

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

// if the next token is expected symbol, read forward one token and 
// return true.
bool consume(char op) {
    if(token->kind != TK_RESERVED | token->str[0] != op)
        return false;
    token = token->next;
    return true;
}

// if the next token is expected symbol, read forward one token and 
// otherwise report an error.
void expect(char op) {
    if(token->kind != TK_RESERVED | token->str[0] != op)
        error("'%c'ではありません。", op);
    token = token->next;
}

// if the next token is expected number, read forward one token and 
// otherwise report an error.
int expect_number() {
    if(token->kind != TK_NUM)
        error("数ではありません");
    int val = token->val;
    token = token->next;
    return val;
}

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

// create a new token and connect it to curl.
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 the input string p and return it
Token *tokenize(char *p) {
    Token head;
    head.next = NULL;
    Token *cur = &head;

    while (*p) {
        // skip space
        if(isspace(*p)){
            p++;
            continue;
        }

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

        if(isdigit(*p)) {
            cur = new_token(TK_NUM, cur, p);
            cur->val = strtol(p, &p, 10);
            continue;
        }
        error("トークナイズできません");
    }

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



int main(int argc, char **argv){
    if(argc != 2) {
        fprintf(stderr, "引数の個数が正しくありません\n");
        return 1;
    }

    token = tokenize(argv[1]);

    printf(".intel_syntax noprefix\n");
    printf(".global main\n");
    printf("main:\n");
    printf("    mov rax, %ld\n", expect_number());

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

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

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

コンパイラはまず構文解析を行なってトークン列を抽象構文木に変換し、その構文木をアセンブリに変換

### 再帰下降構文解析
生成規則による演算子の優先順位
expr = mul (“+” mul | “-” mul)*
mul = num (“*” num | “/” num)*
// 足し算よりも掛け算が常に下に現れる

expr = mul (“+” mul | “-” mul)*
mul = primary (“*” primary | “/” primary)*
primary = num | “(” expr “)”

まずassemblerから

.intel_syntax noprefix
.globl main
main:
        mov rax, 5
        add rax, 20
        sub rax, 4
        ret

c

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

int main(int argc, char **argv){
    if(argc != 2) {
        fprintf(stderr, "引数の個数が正しくありません\n");
        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, "予期しない文字です: '%c'\n", *p);
        return 1;
    }

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

$ make
cc -std=c11 -g -static 9cc.c -o 9cc
$ ./9cc ‘5+20-4’
.intel_syntax noprefix
.global main
main:
mov rax, 5
add rax, 20
sub rax, 4
ret

main:
        mov rbp, rsp
        mov %rsp, %rbp
        
        mov rax, 8
        mov $8, %rax

        mov [rbp + rcx * 4 - 8], rax
        mov %rax, -8(rbp, rcx, 4)

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

int main(int argc, char **argv){
    if(argc != 2) {
        fprintf(stderr, "引数の個数が正しくありません\n");
        return 1;
    }

    printf(".intel_syntax noprefix\n");
    printf(".global main\n");
    printf("main:\n");
    printf("    mov rax, %d\n", atoi(argv[1]));
    printf("    ret\n");
    return 0;
}

$ cc -o 9cc 9cc.c
$ ./9cc 123 > tmp.s

.intel_syntax noprefix
.global main
main:
    mov rax, 123
    ret

テストスクリプト

#!/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

echo OK

Makefile

CFLAGS=-std=c11 -g static

9cc: 9cc.c11
test: 9cc
	./test.sh

clean:
	rm -f 9cc *.o *~ tmp*

.PHONY: test clean

逆アセンブルとは機械語をアセンブラに変換すること
objdump は一つ以上のオブジェクトファイルについて情報を表示

$ objdump -d -M intel /bin/ls
…
Disassembly of section .fini:

0000000000016200 <.fini>:
16200: d503201f nop
16204: a9bf7bfd stp x29, x30, [sp, #-16]!
16208: 910003fd mov x29, sp
1620c: a8c17bfd ldp x29, x30, [sp], #16
16210: d65f03c0 ret

一番左の 16200: は機械語が入っているメモリ
d503201f は実際の機械語

int main() {
    return 42;
}

$ cc -o test1 test1.c
$ ./test1
$ echo $?
42

$?をechoで終了コマンドを出力

test2.s

.intel_syntax noprefix
.globl main
main:
    mov rax, 42
    ret

### 関数呼び出し
関数で元々実行していたアドレスをリターンアドレスという
リターンアドレスはメモリのスタック上に保存される
スタックトップを保持している記憶領域をスタックポインタという

int plus(int x, int y) {
	return x + y;
}

int main() {
	return plus(3, 4);
}

第一引数はRDIレジスタ、第二引数はRSIレジスタに入れる
x86-64は通常2つのレジスタしか受け取らない
関数からの返り値はRAXに入れるとなっている
callとretは対になる命令

.intel_sytax noprefix
.global plus, main

plus:
	add rsi, rdi
	mov rax, rsi
	ret

main:
	mov rdi, 3
	mov rsi, 4
	call plus
	ret

.text
.global _start
_start:
mov     x2,  #13
adr     x1,  msg
str     x2, [sp, #-16]!
str     x1, [sp, #-16]!
ldr     x1, [sp], #16
ldr     x2, [sp], #16
mov     x0,  #1 
mov     x8,  #64
svc     #0
mov     x0,  xzr
mov     x8,  #93
svc     #0 
msg:
.asciz "hello world"

$ as -o source.o source.s
$ ld -o source source.o
$ ./source
hello world

スタックポインタは16バイトで整列されていることを要求するためずらす
svc #0 はx0からx8のレジスタの値を

source

print("hello world")

compiler.js

var {exec, write, show, error} = require("./utils.js");
var lexer = require("./lexer.js");
var parser = require("./parser-comp.js");
var genasm = require("./genasm.js");

var source = read("source.3");

var tokens = lexer(source);

show("処理前tokens =", tokens);

parser(tokens);

console.log("-------------");

exec("as source.s -o source.o");

exec("ld -lc --dynamic-linker /lib64/ld-linux-x86-64.so.2 -o exec source.o");

console.log(exec("./exec"));

parser-comp.js

module.exports = parser;
var {write,expect,accept,show,error} = require("./utils.js");
var tokens;

function parser(t) {
    tokens = t;
    return callprint();
}

function callprint(){
    if(tokens.length==0) return;

    expect(tokens,"print");

    expect(tokens,"(");

    var msg = tokens.shift();
    var codes = [];

    codes.push(".text");
    codes.push(".global _start");
    codes.push("_start:");

    codes.push("mov     x2,  #13");
    codes.push("adr     x1,  msg");

    codes.push("mov     x0,  #1 ");
    codes.push("mov     x8,  #64");

    codes.push("svc     #0");
    codes.push("mov     x0,  xzr");
    codes.push("mov     x8,  #93");
    codes.push("svc     #0 ");
    codes.push("msg:");
    codes.push(".asciz " + msg);
    codes.push("\n");

    var asm = codes.join("\n")+"\n";

    write("source.s",asm);

    expect(tokens,")");
}

utils.js

module.exports = {exec, write, read, show, error, accept, expect}

function exec(cmd) {
    return require('child_process').execSync(cmd, {encoding:"utf8"});
}

function write(filename, data){
    require('fs').writeFileSync(filename,data);
}

parser-comp.jsのcallfunctionでarm64用のassemblyを書いて保存する。
assemblerの実行は別に分ける。
interpreterの方はrun.jsで実行していたが、アセンブリの作成が入ってくるのね。