Month: June 2020

*, /, ()を言語に追加するには演算子の優位順位を決めなければならない

– パーサの実装
入力はフラットなトークンの列で出力は入れ子構造を表す木にする

単純な生成規則
expr = num(“+” num | “-” num)*
mul = num(“*” num | “/” num)*
具象構文木(concrete syntax tree)

再帰を含む生成規則
expr = mul(“+” mul | “-” mul)*
mul = primary(“*” primary | “/” primary)
primary = num | “(” epr “)”

再帰下降構文解析
expr = mul(“+” mul | “-” mul)*
mul = primary(“*” primary | “/” primary)*
primary = num | “(” epr “)”

typedef enum {
	ND_ADD,
	ND_SUB,
	ND_MUL,
	ND_DIV
	ND_NUM,
} NodeKind;

typedef struct Node Node;

struct Node {
	NodeKind kind;
	Node *lhs;
	Node *rhs;
	int val;
};

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

Node *new_node_num(int val) {
	Node *node = calloc(1, sizeof(Node));
	node->kind = ND_NUM;
	node->val = val;
	return node;
}

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

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

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

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

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

	return new_node_num(expect_number());
}

文字列をトークン列に分割することをトークナイズするという

#include <ctype.h> // 文字の種類の判定や文字の変換
#include <stdarg.h> // 可変長引数
#include <stdbool.h> // bool, true, false
#include <stdio.h>
#include <stdlib.h> // strtol
#include <string.h>

typedef enum {
	TK_RESERVED, // 記号
	TK_NUM, // 整数トークン
	TK_EOF // 入力の終わりを表すトークン
} TokenKind;

typedef struct Token Token;

struck Token {
	TokenKind kind; // トークンの型
	Token *next; // 次の入力トークン
	int val; // kindがTK_NUMの場合、その数値
	char *str; // トークン文字列
};

// 現在着目しているトークン
Token *token;

// エラーを報告する為の関数
// printfと同じ引数
void error(char *fmt, ...){
	va_list ap;
	va_start(ap, fmt);
	vfprintf(stderr, fmt, ap);
	fprintf(stderr, "\n");
	exit(1);
}

// 次のトークが期待している記号の時には、トークンを1つ読み進めて真を返す、それ以外の場合には偽を返す
bool consume(char op){
	if(token->kind != TK_RESERVED || token->str[0] != op)
		return false;
	token = token->next;
	return true;
}

// 次のトークが期待している記号の時には、トークンを1つ読み進めて真を返す、それ以外の場合にはエラーを返す
void expect(char op){
	if(token->kind != TK_RESERVED || token->str[0] != op)
		error("'%c'ではありません", op);
	token = token->next;
}

// 次のトークが数字の場合、トークンを1つ読み進めて真を返す、それ以外の場合にはエラーを返す
int expect_number(){
	if(token->kind != TK_NUM)
		error("数ではありません");
	int val = token->val;
	token = token->ext;
	return val;
}

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

// 新しいトークンを作成してcurに繋げる
Token *new_token(TokenKind, Token *cur, char *str){
	Token *tok = calloc(1, sizeof(Token));
	tok->kind = kind;
	tok->str = str;
	cur->next = tok;
	return tok;
}

// 入力文字列pをトークナイズしてそれを返す
Token *tokenize(char *p){
	Token head;
	head.next = NULL;
	Token *cur = &head;

	while(*p){
		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()); // ldはlong d, strtolは文字列をlongに変換

	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;
}

新しいプログラミング言語を作る　イコール　コンパイラを作る　ってことなのか。
低レイヤは学習コストが高いけど、一生物の知識がつくな。

5+20-4のような式をアセンブラで書く

.intel_syntax noprefix
.global main

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

$ cc -o tmp tmp.s
$ ./tmp
$ echo $?
21

これをCで書く

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

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)); // ldはlong d, strtolは文字列をlongに変換

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

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

		fprintf(stderr, "予期しない文字です: '%c'\n", *p);
		return 1;
	}

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

strtolは数値を読み込んだ後、第2引数のポインタをアップデートして、読み込んだ最後の文字の次の文字を指すように値を更新

$ make
$ ./9cc ‘5+20-4’
.intel_syntax noprefix
.global main
main:
mov rax, 5
add rax, 20
sub rax, 4
ret

test.sh

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

	./9cc "$input" > tmp.s
	gcc -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

$ ls
9cc 9cc.c test.sh tmp tmp.s
$ sudo chmod a+x test.sh
$ sh test.sh
0 => 0
42 => 42
OK

Makefile

CFLAGS=-std=c11 -g -static

9cc: 9cc.c

test: 9cc
	sh test.sh

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

.PHONY: test clean

GCCの構文解析は、再帰下降構文解析法(recursive descent parsing)を使っている

下記のシンプルなアセンブリもコンパイラと言える。

.intel_syntax noprefix
.globl main

main:
        mov rax, 42
        ret

### Intel記法とAT&T記法

mov rbp, rsp // intel
mov %rsp, %rbp // AT&T ...結果レジスタが第二引数にくる

mov rax, 8 // intel
mov $8, %rax // AT&T ...数字には$をつける

mov [rbp + rcx * 4 - 8], rax // intel
mov %rax, -8(rbp, rcx, 4) // AT&T 

### コンパイラの作成

#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;
}

$ gcc -o 9cc 9cc.c
$ ./9cc 345 > tmp.s
$  cat tmp.s
.intel_syntax noprefix
.global main
main:
	mov rax, 345
	ret

$ gcc -o tmp tmp.s
$ ./tmp
$ echo $?
89

あれ？　345が89になるな。何故だ？ あ、0〜255の範囲でないと行けないからですな。

### 関数のアセンブリ変換
呼び出した関数が終了した後に、元々実行していたアドレス(リターンアドレス)に戻ってくる必要がある
リターンアドレスはメモリ上のスタックに保存される
スタックは、スタックの一番上のアドレスを保持する1つの変数のみを使って実装できる
スタックトップを保持している記憶領域をスタックポインタという

c

#include <stdio.h>

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

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

アセンブリ

.intel_syntax noprefix
.globl plus, main

plus:
		add rsi, rdi
		mov rax, rsi
		ret

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

第一引数はRDIレジスタ、第二引数はRSIレジスタに入れる約束になっている
callは関数を呼び出す。具体的にはアドレスをスタックにプッシュし、ジャンプ
addはrsiレジスタに上書きされて保存される
返り値はRAXに入れることになっている
retでスタックからアドレスを1つポップ

CPUはメモリを読み書きすることでプログラムの実行を進めていく

コンパイラは、構文解析、中間パス、コード生成というステージがある
コンパイラが動作するマシンのことを「ホスト」、コンパイラが出力したコードが動作するマシンのことを「ターゲット」という
ホストとターゲットが異なるコンパイラをクロスコンパイラという

### CPU
現在実行中の命令アドレスをCPU内部に保持していて、そのアドレスから命令を読み出して、そこに書かれていることを行い、そして次の命令を読み出して実行する
現在実行中のアドレスのことをプログラムカウンタ(PC)やインストラクションポインタ(IP)という
cpuが実行するプログラム形式そのもののことを機械語(machine code)という
CPUの分岐命令(branch instruction)を使うと、次の命令以外の任意のアドレスに設定することができる(ジャンプ、分岐)　eg.if文やループ文など
プログラムカウンタ以外にも少数のデータ保存領域を持っており、レジスタと呼ぶ
2つのレジスタの値を使って何らかの演算を行い、結果をレジスタに書き戻すというフォーマットになっている
命令を命令セットアーキテクチャ(instruction set architecture)という
x86-64命令セットはAMD64、Intel64, x64などと呼ばれることがある
-> awsでインスタンスを作ろうとするとき “64-bit x86″と表示されるが、このx86は命令セットのこと

### アセンブラ
アセンブリは機械語にほぼそのまま1対1で対応する言語
$ objdump -d -M intel /bin/ls

/bin/ls: file format elf64-x86-64

Disassembly of section .init:

0000000000003758 <_init@@Base>:
3758: 48 83 ec 08 sub rsp,0x8
375c: 48 8b 05 7d c8 21 00 mov rax,QWORD PTR [rip+0x21c87d] # 21ffe0 <__gmon_start__>
3763: 48 85 c0 test rax,rax
3766: 74 02 je 376a <_init@@Base+0x12>
3768: ff d0 call rax
376a: 48 83 c4 08 add rsp,0x8
376e: c3 ret

——–
3758: 48 83 ec 08 sub rsp,0x8
3758はメモリのアドレス
48 83 ec 08は命令の機械語
sub rsp,0x8はアッセンブリ　rspから8を引く

### Cとアセンブラ

#include <stdio.h>

int main(int argc, char** argv[]){

	return 42; // 終了コード

}

$ gcc -o test test.c
$ ./test
$ echo $?　　// 終了コードは$?にセットされる
42

### アセンブリファイルの作成
アセンブリファイルの拡張子は.s

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

プログラミング勉強の良いところは、後からどんどん繋がってくることだな