Skip to content

Instantly share code, notes, and snippets.

@Drumato Drumato/t1.md Secret
Last active May 4, 2019

Embed
What would you like to do?
seccampCコンパイラ自作コース

○これまでのプログラミング歴(C言語に限りません)について好きなだけ語ってください。
何か作ったものがあれば、それについても教えてください。

私は2018年4月に情報科学専門学校に入学して以来、
独学によって勉強をしてきました

プログラミングは5月の頭に、
Ruby という言語に触れた事から始まります。

Rubyを最初のプログラミング言語に選んだ理由は、
記法がシンプルで読みやすく、初心者にオススメと各所で言われていたからです。

Rubyでは返り値や関数(Rubyではメソッドですが)等、
多くのプログラミング言語に共通する知識・技術 を身につけました。

書籍学習を進めインプット活動をするのはもちろんの事、
Qiita(現在はブログに移行)で勉強したことを記事にする
アウトプット活動も同時に行い始めました。

Rubyの言語仕様を解説するQiitaの記事(プログラミング歴2ヶ月頃)

この時同時に、PythonとC言語も触り始めました。

それぞれ理由としては、
Python→流行っていたから
C言語→漠然とシステムプログラミングに用いられているって話を聞いたから
というのが挙げられます。

その後機械学習に興味を持つことになるので、
この時Pythonを勉強していてよかったなぁと今では思います。

記事の執筆等に付随して、
成果物の作成も同時に行いました。
書籍の内容を写経するだけでは実装力が身につかないと感じ始めたからです。

Pythonではプログラミングを始めて2ヶ月程度に、
貼り付けたURLにある画像を一括でダウンロードするスクリプトを書きました。
これは後述するRubyの書籍管理ツールより前に書いたもので、
(成果物とは言えないほど小さいですが)
自身で試行錯誤しながら作成した(書籍の内容を写経するわけではない)
一番最初のコードになります。

当該ツールを紹介するQiitaの記事

BeautifulSoupとRequestsを用いて
指定されたURLにリクエストを送信し、
返ってきたHTMLコンテンツ内に存在するimgタグのsrc属性から
ダウンロードしローカルに展開するスクリプトです。

大枠はどこかのブログに落ちていたコードを利用したものですが、
自身でもいろいろ改変したりしたためにかなり苦戦しました。

上記スクリプトは Seleniumを使用する形式 に変更してみたり、

wxpythonを使用する事でGUIプログラミング に挑戦してみたり等、

作って満足するだけではなく改良するまでを
プロセスとして踏むことを心がけました。

初めてRubyで作ったツールは、
自身の学習した書籍をCSV形式で管理するというものです。
これは9月ごろ(プログラミング4ヶ月目)に作ったものです。

後述しますが、Golangによって再実装を行っています。

当該ツールの内容を紹介するブログの記事
そのリポジトリ

自身の独学(特に書籍学習)のモチベーションを向上させるために作ったもので、

・書籍名、難易度、おすすめ度、カテゴリを1レコードとしてCSVファイルにAppend
・見づらいCSVのフォーマットをterminal-tableというライブラリにより見やすく表示

というのを目標に作成したものです。

当時はこれだけのツールを作るのにほぼ一日かかりましたが、
プログラミングでやりたい事を実装する楽しさと、
公式ドキュメント等を参照する癖をつけられました。

そして10月、機械学習という技術領域を知った私は、
機械学習・深層学習系の勉強を必死になってやるようになりました。

まずは書籍で体系的に理論を学ぶために、
「scikit-learnとTensorFlowによる実践機械学習」等の
網羅的且つ厳密に理論を解説している本に取り組みました。

書籍を写経しながら勉強したことについては逐一ブログにまとめたり、
自身でコードを改変する等、
常に「実装力を高める」為の勉強法を貫いてきました。

線形回帰モデルについて解説する記事

正則化項ありの線形回帰モデルについて

support vector machineについて解説する記事

機械学習というと数学的定義等の話が上がりがちですが、
「プログラミング駆動で理論を勉強する」というスタンスを崩さないように、
常にコードで理解することを目標にしていました。

またこの時gitの使い方も同時に勉強し始めました。

gitの使い方を最低限解説する記事

gitを使えるようになることでプログラミングの学習はより一層加速した感覚がありました。

この時にも継続して細々としたツールは作り続けるように努力していました。

初めてJSON APIを使い、お天気情報をCUI上に表示するRubyプログラム

そのリポジトリ

rubyでプログラムを書いていくことで、
「オブジェクト指向でプログラミング」する事の意義と恩恵が理解出来ました。

年が変わり1月(プログラミング歴8ヶ月目)にもなると、
「キレイなコードってなんだろう?」 を考えるようになりました。

特にruby等の動的型付け言語+スクリプト言語等では
気を抜くとすぐに汚いコードを書きがちだったので、

「自身のコードをリファクタリング」することで
キレイなコードを書く習慣をつけ始めました。

書籍管理ツールのコードをリファクタリングする記事

このリファクタリングでは、

・メソッドが全てクラスメソッド(インスタンスにではなく、クラス自体をレシーバとして実行するようなメソッド)であった ・コードが全体的に冗長 ・ロジック部分にio処理が沢山書かれている ・変数名が不適切

等の点に気をつけながら
自身のコードを改良しています。

特にクラスメソッドを全てインスタンスメソッドに変更したのはかなりこだわっていて、
オブジェクト指向の概念・理論的に実際に処理を行うのはインスタンスであってほしいという気持ちがありました。
このリファクタリング精神は現在も大きく役に立っている重要なメンタルだと感じています。

リファクタリングに共通するプログラミングのスタイルとして
「可読性の高いコード」がありますが、

ruby、python等の動的型付け言語では「変数の型(rubyはクラス)が分かりづらい」という側面があります。

この問題を軽減するために
pythonのアノテーションを利用し始めました。

Pythonの型アノテーションを解説する記事

可読性を大きく気にしだした時期で、
自身のコードの質が高まった感覚がありました。

この時にはコードを書くことが習慣付いていて、

自身のツイートデータをpandasというデータ加工ライブラリを使って分析した記事

書籍に記載されていたフィルタリングによるエッジ検出を実装する記事

等、
勉強したことについてコードを書いて理解を深めるというフローを半自動的に踏めるようになりました。

また、
ただプログラミングするだけではなく
「実行速度」を気にし始めました。

具体的には
システムプログラミングに親密なgolangという言語を勉強し始め、
自身の作ったツールをgo言語で再実装する等してきました。

書籍管理ツールをgoで再実装+機能拡張する記事

その続き

rubyで書いたjson apiを利用するツールをgoで書き直した記事

システムプログラミングという分野を考え始める切っ掛けとして、
python等普段から使っているプログラミング言語の内部実装に触れ始めた、というのがあります。

内部実装の例を挙げると、
pythonは変数から変数へ代入しても元の変数のアドレスがそのまま渡され、
実際に値が再代入されるまでは同じメモリを共有する、というものなどです。

pythonの変数代入をid関数で詳しく追っていく記事

私がコンパイラに興味を持ったのは
「私が利用するプログラムはどのようにして動いているのか」を知りたくなった、というのが凄く大きいです
(これは問4でも触れます)

この頃から意識し始めた「内部実装の理解」という感覚は、
現在コンパイラ自作に熱意を持っているきっかけと言っていいと思います。

同じ様にlinuxプログラミングを勉強し始め、
より低レイヤ側の技術に触れ始めました。

/initプロセスからHelloWorldするまでを解説する記事

実際にシステムプログラミングに興味を持った例をもう一つ挙げると、
ネームバリューのある脆弱性、「dirtycow」があります。

これはmbsd cybersecurity challenges に参加した際に初めて知ったもので、
linuxカーネルの脆弱性として世間に広く知れ渡っています。

これは2月頃(プログラミング歴9ヶ月)のことです。

DirtyCOWの仕組みを文章で解説する記事

このブログの記事の内容は厳密には異なり、
後にカーネルのソースを読む事で正しく理解できたのですが
低レイヤのプログラミングに取り組みたいと強く感じ始めた大きなファクターと言えます。

そして2月の中旬頃、
ついに言語処理系に興味を持ちました。

きっかけはセキュリティ・キャンプの講師を務める
川合さんにお会いしたことですが、
サイボウズ・ラボユースの面接でお話した時に
「プログラミング言語を作る上で前提知識が沢山必要だと日和る必要はなくて、
やりたいと思ったその感情でやってみれば案外できるもんだよ」
という旨のお話をいただきました。

私はその言葉に感銘を受けて、
そのお話を聞いたあと本屋に直行し、
「goでつくるインタプリタ」という書籍を購入し手をつけました。

この本との出会いは私の学生生活の中でも
特に大きなターニングポイントとなったことでしょう。

本書籍の1、2章の内容を解説する記事

本書籍がgolangを題材にインタプリタ言語(コンパイラで言うフロントエンド部分)を、
本一冊を通して自作するという趣旨の本で、
私が言語処理系に熱中する根本の要因となった本でもあります。

またこの書籍の大きな特徴として、
プログラミング技法として避けて通れない「テスト」を紹介するというものがあります。

一冊を通して「monkey」というプログラミング言語を開発していきますが、
徹底してテスト駆動開発のスタイルを踏襲しています。

ユニットテストを勉強するために別途書籍を購入したというわけではないですが、
この書籍のおかげでテストを書くことの重要性が理解できたと言っても過言ではありません。

言語処理系の勉強をし始めて一ヶ月頃には当該書籍を読み終え、
今度は「自作でインタプリタ言語」を作り始めました。

自作言語のリポジトリ

自作言語を紹介する記事

まずこの自作言語で特に重視した点を紹介します。

・テストは書く
・マルチバイト文字に対応する ・circleciを使うことに慣れる

テストについては先程触れたとおりです。
プログラムを書く上での効率がテストを書くのと書かないのとでは段違いですし、
テストによってコードの堅牢性が担保されます。

次にマルチバイト文字に対応する、ということについてですが、
これはgolangのruneを利用してunicodeのコードポイントごとに文字を抽出できます。

(自作言語上でマルチバイト文字の抽出がうまく出来ている画像)

これは文字列をインデックスで取り出すようなコードを自作言語上で行っているものになります。

通常、文字列のインデックスは「1バイト毎」に切り取っているため、
golang上で"astこんにちはparser"[3]のようにすると

のように、上手くひらがな一文字を抽出出来ません。

この実装はgolangの理解とコンピュータ上で文字がどのように処理されているかを学ぶ上で非常に役立ちました。

そして4月に入り、
ついにコンパイラの勉強に着手しました。

フロントエンド部分の字句解析→構文解析→ast生成の流れが大まかに理解できたことと、
より高レベルで、より低レイヤーな開発をしたいと考えていたからです。

コンパイラの勉強をしようと思い立った私に立ちはだかった壁に、
「日本語の文献が少ない」という事がありました。

有名で優れていると言われる書籍には「読みづらい」というレビューがあり、
どのように勉強すればいいのか戸惑ってしまったこともあります。

そんな時にどきゅねおさんという方の こんなスライド を拝見しました。

cコンパイラ自作コースの講師を務めるrui ueyamaさんの8ccをgoで再実装した、という趣旨のものです。
「コンパイラ作りの魅力を語る」という表題に相応しい素敵な内容の資料でした。

勉強方法に悩んでいた私はこの資料を見て、
「目の前にコンパイラ界隈で有名な方が書いた実際に動くコードがある。
これは他の何者にも代えがたい最高の学習リソースじゃないか!」と思いました。

実際に4月の頭からrui ueyamaさんの9ccをgoで再実装し始めたのがこの時になります。
どきゅねおさんのスライドに出会わなければ今でも右往左往と「不毛な」時間を費やしていたことでしょう。

9ccをGoで再実装しているリポジトリ

当該リポジトリを紹介する記事

同時にコンパイラに関するブログの記事も複数執筆しました。

四則演算における再帰下降構文解析器の挙動を解説する記事

一文字変数の宣言・利用をgdbを用いて解説する記事

gccのアセンブリを見る記事

時系列的には少し前なのですが(3月頃)、
サイボウズ・ラボユース研究生として
深層生成モデルのサーベイとtext-to-imageタスクの実装も行っています。

これは主にstackgan++、attnganに代表されるような
sota手法を参考にしながら、
pythonによって日々少しずつ進捗を挙げています。

サイボウズ・ラボユースとしての活動を日々記録するリポジトリ

今日に至るまで以上のような経歴をたどってきましたが、
ずっと一貫して大事にしてきたのは
「やりたいことをやりたいままにやりたいだけプログラミングする」という考え方です。

これはプログラミングでも特に重要な本質だと思っていて、
私が2018年4月に入学してからの一年間を支える一番大きなポリシーにもなっています。

○コンパイラがソースコードから実行バイナリを生成する過程について、
現在知っている範囲で説明してください。
ソースコードの言語については、好きなものでかまいません。

ここではC言語のソースコードを例にとって説明していきます。
ソースコードの表現はバッククォートで括ります。

ソースコードを解析してからバイナリを生成するまで、
「大まかに」言うと次のようなフェーズを辿ります。

  • プリプロセス(コンパイラではないソフトウェア、プリプロセッサの責務)
  • ソースコード解析
    • 字句解析
    • 構文解析
    • ASTノード生成
  • 中間表現生成
  • (狭義の)コンパイル
    • 中間表現とアーキテクチャ固有の命令セット、ニーモニックを対応
  • アセンブル(アセンブラというソフトウェアが担う役割だが、一般的にコンパイルするというときアセンブルも内包される)
    • ELFフォーマットに準拠したオブジェクトファイル
    • アセンブリ言語から機械語を生成する
  • リンク(同じくリンカの役割だが広義のコンパイルに含まれる時もある)

以下詳しく各フェーズについて解説していきます。

プリプロセス

C言語のソースコードには #include<stdio.h>等、
ヘッダファイルのinclude宣言が先頭に記載されています。

C言語におけるプリプロセスは大きく分けて

  • ヘッダファイルの展開
  • コメントの削除

等があります。

まずヘッダファイルの展開ですが、
ここではポピュラーであり分かりやすい stdio.h の展開を例に取ります。
私達はstdio.hをインクルードすることでprintf関数を含む多くのAPIを利用できますが、

これにはプリプロセッサの仕事が大きく作用しています。

gccではcppというプリプロセッサが動いています。

C言語は関数の定義順が大きく影響する言語です。
書く関数はソースコード上で自身より先に(ファイルで言えば上に)定義されていなければ、
各関数はその関数を「知りません」。

より具体的に言えば、
コンパイラがその関数名を 未定義の識別子 として判定します。

C言語にはプロトタイプ宣言という方法で、
main関数に識別子の存在を「知らせる」という技がありますが、
ファイル内でprintf関数のプロトタイプ宣言を記述しなくても、
main関数はprintf関数等を「知っている」状態になっています。
より具体的に言えば、
コンパイラがprintf関数を定義済み識別子と認識します。

プリプロセッサはヘッダファイルを参照し、
各API関数の定義を同ファイル内に展開します。

実際に展開した様子です。

#include<stdio.h>

int main(void){
  printf("Hello,World!\n"); //コメント
  return 0;
}

プリプロセス実行結果

実際にprintfのプロトタイプ宣言が確認出来ると思います。

またコメントというコメントも出力された結果の末尾で削除されているのが確認できると思います。

他にはマクロ定義を追って展開したり、
定数を即値に変換したり等が挙げられます。

プリプロセッサの実装によって差異は異なりますが、
最も大きな仕事はヘッダファイルの展開に他なりません。

プリプロセッサはコンパイル時に動作するような字句解析器とは独立して、
プリプロセス専用のトークナイズ処理を行う実装が必要です。

同様に構文解析のアルゴリズムもC言語とは異なるものを用います。

まずCプリプロセッサの挙動・アルゴリズムですが、
Daveという方がその実装の詳細を発表しています。

参考: Dave Prosser's C Preprocessing Algorithm

Dave氏は 完全なCプリプロセッサを実装 するために約5年間を費やし、
このアルゴリズムを考えたようです。

実装を解説するPDFファイルには、
擬似コードと共にC言語における マクロ展開 アルゴリズムが紹介されています。

**ISO Draft**には、
具体的なC言語の規格が定義されています。

以下プリプロセッサに関係する言語仕様を紹介します。
実行バイナリの生成とは直接関係ありませんが、
Cプリプロセッサがどのようなディレクティブを展開するのかを知る事が出来ます。

Conditional inclusion

#ifdef INTEGER_CONSTANT
    /* do something...*/
#endif

のようにして用いる文です。
整数の定数INTEGER_CONSTANTが既に定義されていれば、
#endifまでをブロックとし、実行するようなコードになっています。

サンプルコードで解説します。

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

#define DEBUG

int main(void){

  srand((unsigned)time(NULL));
  int secret_number = rand() % 10 + 1;
  #ifdef DEBUG
    printf("SecretNumber is %d\n",secret_number);
  #endif
  int input;
  printf("Please input number\n");
  scanf("%d",&input);

  printf("Your Number : %d\n",input);
  if(secret_number == input ){
    printf("number is correct!\n");
    return 0;
  }
  printf("wrong number!\n");


  return 0;
}

簡単な数当てゲームを作ってみました。
ここでは#define DEBUGによってマクロ定数を定義しています。

このコードをコンパイルし実行すると、

のように、
隠し番号が出力され、
ゲームの挙動を細かく確認しながらプログラミングすることが出来ます。

#DEFINE DEBUGの行をコメントアウトすれば、
printf("SecretNumber is %d\n",secret_number);の行は実行されません。

main関数内に#ifdefディレクティブがあるのが気に入らない場合は、
#elseを用いて次のように記述できます。

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

//#define DEBUG

#ifdef DEBUG
 const int debugflg = 1;
#else
 const int debugflg = 0;
#endif

int main(void){

  srand((unsigned)time(NULL));
  int secret_number = rand() % 10 + 1;
  if(debugflg)
    printf("SecretNumber is %d\n",secret_number);
  int input;
  printf("Please input number\n");
  scanf("%d",&input);

  printf("Your Number : %d\n",input);
  if(secret_number == input ){
    printf("number is correct!\n");
    return 0;
  }
  printf("wrong number!\n");


  return 0;
}

gcc -E c.cとして、
プリプロセス結果を見てみましょう。

# 10 "c.c"
const int debugflg = 0;

int main(void){

  srand((unsigned)time(
# 15 "c.c" 3 4
                      ((void *)0)
# 15 "c.c"
                          ));
  int secret_number = rand() % 10 + 1;
  if(debugflg)
    printf("SecretNumber is %d\n",secret_number);
  int input;
  printf("Please input number\n");
  scanf("%d",&input);

  printf("Your Number : %d\n",input);
  if(secret_number == input ){
    printf("number is correct!\n");
    return 0;
  }
  printf("wrong number!\n");


  return 0;
}

const int debugflg = 0;だけが残っており、
確かに条件処理が実行されている 事が確認できました。

#ifディレクティブを使用することで、

#if (DEBUG && LOGLEVEL >= 30)
  printf("Warning:unexpected such as number:%d",invalid_number);
#endif

のような挙動を起こす事も可能です。

Source file inclusion

ヘッダ・ソースファイルを展開するためのディレクティブです。

#include宣言等がここに内包されます。

  • #include <Standard-headerfile>
  • #include <userdefined-headerfile>
  • #include <preprocessing token>

がサポートされています。

三番目だけあまり見ないので、
ここで解説を加えます。

#define ARCHITECTURE "x86_64"

#if ARCHITECTURE == "x86_64"
  #define HEADFILE "IA.h"
#elif ARCHITECRE == "POWERPC"
  #define HEADFILE "POWERPC.h"
#else
  #define HEADFILE "UNKNOWN.h"
#endif

#include HEADFILE

のようにして、include宣言のオペランドを変更させる場合に用います。


上記に述べた以外にも、以下のようなディレクティブが存在します

  • Macro replacement
    • #define,#,##,#undef
  • Line Control
    • #line
  • error directive
    • #error
  • Pragma directive
    • #pragma
  • Null directive

(C言語における)プリプロセスまとめ

  • #include等、preprocess directiveを解析し、展開する
  • コメント削除等を行う

ソースコード解析

概要

次のコードを見てみます。

#include "stdio.h"

int sum(int a,int b);

int main(void){
    int num = 10;
    printf("%d\n",sum(num,10));

    return 0;
}

これは実際に動作するC言語のコードですが、
このコードを 「最も高レイヤ」であり「C言語の構文を具現化したもの」 として考えます。

次にかなり抽象化されたものを紹介します。

<import header-file>

<Expression Statement --Prototype-->

<Definition function>

ソースコードの構成要素を意味のまとまった実体に分割しています。

これを実現するのが ソースコード解析という手法になります。

ソースコード解析のやることは、

  • 言語仕様に準拠したトークンを定義
  • 正しく最小単位(トークン)に分割できるように ルールベースで字句解析器を定義
  • トークンを一つ一つジャンプしながら 構文が正しいかどうかチェック
  • 正しい場合は ASTノード を生成する。
    • 関数定義のノードを例に取ると、 引数の数関数名 等を保持することが目標

中間表現の生成はソースコード解析には含めないこととします。
ここではAST構築までを扱います。


字句解析

ソースコード解析の目指すところは、
上記に示したように「具体的なソースコードを言語仕様に準拠した抽象的な実体」に変換することです。

int num = 10;

この例でいうところの num は変数名です。

実際に代入される10の部分はint型の即値、int型を返す関数呼び出し等が使えます。

<type-INT> <IDENTIFER> <ASSIGN> <Literal-INT> <SEMICOLON>

変数の初期化を **「トークン毎」**に見ています。

これは 字句解析 というフェーズで、
ソースコードを C言語で意味を持つ最小単位に分割 する処理になります。
字句解析・トークナイズ処理は ルールベース であり、
機械学習タスクのように モデルを定義して推論させる というわけではありません。

C言語に(ほぼ)準拠したトークン定義

上記に示したコードのように、
まず 言語毎に使用するトークンを定義しておきます。

これは予約語( キーワード とも)だけではなく、
INTLITとリテラルに用いるようなものも定義しておきます。

goccの実装では、
予約語を列挙したMapを定義しています。

var keywords = map[string]TokenType{
	"_Alignas":       ALIGNAS,
	"_Atomic":        ATOMIC,
	"alignof":        ALIGNOF,
	"auto":           AUTO,
	"break":          BREAK,
	"_Bool":          BOOL,
	"case":           CASE,
	"const":          CONST,
	"char":           CHAR,
	"continue":       CONTINUE,
	"default":        DEFAULT,
	"do":             DO,
	"double":         DOUBLE,
	"else":           ELSE,
	"enum":           ENUM,
	"extern":         EXTERN,
	"float":          FLOAT,
	"for":            FOR,
	"goto":           GOTO,
	"if":             IF,
	"inline":         INLINE,
	"int":            INT,
	"long":           LONG,
	"register":       REGISTER,
	"restrict":       RESTRICT,
	"return":         RETURN,
	"short":          SHORT,
	"signed":         SIGNED,
	"sizeof":         SIZEOF,
	"static":         STATIC,
	"struct":         STRUCT,
	"switch":         SWITCH,
	"typedef":        TYPEDEF,
	"unsigned":       UNSIGNED,
	"void":           VOID,
	"volatile":       VOLATILE,
	"while":          WHILE,
	"_Complex":       COMPLEX,
	"_Generic":       GENERIC,
	"_Noreturn":      NORETURN,
	"_Static_assert": STATICASSERT,
	"_Thread_local":  THREADLOCAL,
}

このMapはどうやって用いるかと言うと、
識別子を解析する際に
ユーザが定義した変数・定数・関数なのか、
それとも言語に組み込まれた予約語なのかを判定するために用いることが出来ます。

//LookupIdent judge whether Keywords include the token or not
func LookupIdent(ident string) TokenType { //識別子が予約語かどうか
	if tok, ok := keywords[ident]; ok {
		return tok
	}
	return IDENT
}

私達は識別子の意味を考える事が出来るので、

int add(void){

}

のようなコードを見た時、

int,voidは型の名前で、
addは私達がつけた関数名だと判断出来ますが、

コンパイラは違いがわかりません。
同じくアルファベットで構成された文字列と考えます。

これは後述しますが、
字句解析時にASCIIコードを用いるなど、
機械的に決められたルールによってソースコードを解析しているからです。

トークンに最低限必要な情報は、

  • 実際の入力
  • トークンの種類

です。
上記のコードではそれぞれ、
Type,Literalが該当します。

これ以外にもトークン時点で値情報を保持する場合もありますし、
デバッグのために ソースコード上での行・列情報 を保持するというのも考えられます。

トークンは定義するだけでは利用出来ず、
字句解析器によって初めて成り立ちます。

字句解析器は次のように定義されます。

type Lexer struct {
	input                  string
	position, readPosition int
	ch                     rune
	Line                   int
	Col                    int
	Filename               string
}

inputは入力されたソースコードであり、
position,readPositionによってinputを辿って行きます。

Go言語はUnicodeコードポイントを用いたrune単位の解析が出来ますが、
その他プログラミング言語で字句解析器を定義する場合は、
ASCIIコードをベースに字句解析をしていきます。

ここにASCIIコードの対応表を示します。

このコードを見ると、
文字とそれに対応するASCIIコードが示されています。
字句解析を行う時には、
受け取ったソースコード中の文字がASCIIコード表のどの範囲にあるかを逐次判定しながら、
字句解析器のオフセットを進めていきます。

ソースコードとASCIIが深い関係にある例として、
次のコードを見てみましょう。

#include<stdio.h>

int main(void){
  printf("%d\n",'A'); //char型の文字Aを10進数のフォーマット指定子で出力する。
  return 0;
}

このコードの出力結果は、
**65**となります。

この65は上記のASCIIコード表でいうAに相当しますよね。
このように、文字はASCIIコードで表す事が可能です。
GoはUnicodeコードポイントという点では異なりますが、
文字を番号で表すという点については同じです。

実際にソースコード上の文字列を解析する関数をいくつか見てみましょう。

func isDigit(ch rune) bool { //数値か判定する関数
	return '0' <= ch && ch <= '9'
}

func isLetter(ch rune) bool { //アルファベットか判定する関数
	return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

渡されたruneが文字の範囲に存在するかを判定しています。

この関数を用いて実際に文字の判定をしてみましょう。

package main

import "fmt"

func main() {
        for _, char := range "GOLGO13" {
                fmt.Printf("%s: isLetter? => %v\n", string(char), isLetter(char))
        }
}

func isLetter(ch rune) bool { //アルファベットか判定する関数
        return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

GOLGO13という文字列を一つずつ取り出し、
文字かどうかチェックします。
出力結果を以下に示します。

G: isLetter? => true
O: isLetter? => true
L: isLetter? => true
G: isLetter? => true
O: isLetter? => true
1: isLetter? => false
3: isLetter? => false

このようにソースコード上の文字を解析する関数を作ったら、
後は言語要素毎により上位の関数を定義します。
例えば識別子を受け付ける関数は、

func (l *Lexer) readIdentifier() string {
	position := l.position //現在の位置をとっておき
	for isLetter(l.ch) { //文字である間
		l.readChar() //読み進めて
	}
	return string([]rune(l.input[position:l.position])) //文字と判別した範囲の文字列を返す
}

のように記述します。
字句解析は何度も言うようにルールベースで進めるプロセスである点が重要です。

具体的な字句解析器・字句解析のコードはこちらにあります

構文解析

構文解析は、入力されたソースコードが言語仕様の構文上間違っていないかどうかをチェックしつつ、
合っている場合はASTノードを定義します。

構文解析器は様々あるが、
最もメジャーであり最も実装がシンプルなものに
再帰下降構文解析器が挙げられます。

こちらの記事では、
四則演算を例に再帰下降構文解析器の挙動を解説しています。

構文解析のコードから、
stmt()関数を見てみましょう。

この関数は、
現在パーサーが見ているトークンからASTノードの種類を定め、
その後の挙動を変化させています。

intであれば変数定義だとしてdecl()関数(変数定義を解析する関数)を、
returnであればreturn文だとしてassign()関数(Expressionを解析する関数)を呼び出しています。

ここでは

int sum = 10;

というコードを題材に、
構文解析の様子を追ってみましょう。
まずdecl()関数を呼び出します。

func (p *Parser) decl() *Node {
	n := &Node{Type: ND_VARDEF, CType: *p.typeCheck()}

	if p.curToken.Type != token.IDENT {
		logrus.Errorf("variable name expected, but got %s", p.curToken.Literal)
	}
	n.Name = p.curToken.Literal
	p.nextToken()

	if p.curToken.Type == token.ASSIGN {
		p.nextToken()
		n.Init = p.assign()
	}

	p.expect(token.SEMICOLON)
	return n

}

この関数はASTノードの種類をND_VARDEF( variable define)とし、
構文解析をスタートします。

型名の次には変数名が来なければなりません。
なので

if p.curToken.Type != token.IDENT {
		logrus.Errorf("variable name expected, but got %s", p.curToken.Literal)
	}

という処理を加え、エラー出力をしています。

n.Nameは変数名・関数名を保有するメンバです。

p.nextToken()によってオフセットを進め、
=であるかをチェックします。

=であれば初期化文としてまた解析を行います。

因みにC言語の文法として

int sum;

というのがありますよね。
この場合はif p.curToken.Type == token.ASSIGNの処理には入らないので、
セミコロンを受け付けて解析を終了しています。

n.Initp.assign()によってノードが代入されます。

p.assign()は代入式の右辺を解析するとても大きな関数です。
コード量は小さいですが、様々な関数を呼び出す大元の関数をなっています。

今回は即値10を代入しているので、
様々な関数を辿った結果10が返ってきます。

このように、
ソースコード一つに対して構文解析関数が対応するようになっており、
トークン列のオフセット (字句解析は1文字をオフセット) を進めながら構文解析が行われるようになっています。

このようにして定義されたASTノードは、
Node構造体として返されます。

type Node struct {
	CType     ClangType //C言語上の型
	Type      NodeType //ノードの種類
	Lhs       *Node //左子ノード
	Rhs       *Node //右子ノード
	Val       int //即値用の値
	Expr      *Node //return <expression>等の式部分
	Name      string //識別子の名前等
	Stmts     []*Node //for文等が持つ文の集まり
	Condition *Node //if文の条件式
	Then      *Node //if文における実行部分
	Else      *Node //else文
	Args      []*Node //関数定義におけるパラメータ群
	Body      *Node //for文等、ブレースに囲まれた部分
	Init      *Node //for文の初期化文等
	Inc       *Node //for文のi++等
	Stacksize int
	Offset    int
}

この実装では全てのASTノードは*Nodeによって管理される為、
ASTについてはこの構造体を見れば詳細がわかるという利点があります。

また関数も小分けされない為に、
複雑に大量の関数が入り乱れる、という事態を回避出来るようになっています。

欠点として、

構造体が大きくなりすぎるとコードが見づらい・把握しにくいというものがあります。

この欠点は、

  • ベースの構造体 Nodeを定義する
    • TypeName等、殆どのASTノードで必要なメンバのみ定義
  • ジャンルごとに構造体をラップする構造体を定義し、 Nodeを埋め込む
    • if文、for文は複数文を格納するためBlockStatementとする
    • 関数の実体・変数の実体は同じく identifier等にしておく

という方法を用いる事で改善出来ます。


先程とは違うアプローチとして、

  • ASTノードの種類を小分けに
  • 各ノード毎に解析関数を定義

という方法があります。
実際に、
**Go言語でつくるインタプリタ**という書籍では
この実装方法を取っていました。

ここではその実装を紹介します。

まず、最も抽象的かつ全てのASTノードの親を定義します。

type Node interface {
	TokenLiteral() string
	String() string
}

そして、 等、
構文要素を直下に定義します。

type Statement interface {
	Node
	statementNode()
}
type Expression interface {
	Node
	expressionNode()
}

後は各構文に対して、
対応するノードを定義するだけです。

ここでは return文を例に紹介します。

return文は、

return <expression>という形を取りますよね。

type ReturnStatement struct {
	Token       token.Token //returnが格納
	ReturnValue Expression //expressionを解析して代入
}

func (rs *ReturnStatement) statementNode()       {}
func (rs *ReturnStatement) TokenLiteral() string { return rs.Token.Literal }

後は、
この return statementを解析する関数を定義します。

func (p *Parser) parseReturnStatement() *ast.ReturnStatement {
	stmt := &ast.ReturnStatement{Token: p.curToken} //returnを見ている状態で呼び出される

	p.nextToken() //オフセットを進める

	stmt.ReturnValue = p.parseExpression(LOWEST) //演算の優先順位を考慮しながらExpressionを定義
	if p.peekTokenIs(token.SEMICOLON) { //セミコロンが記述されてなくても良いように
		p.nextToken()
	}
	return stmt
}

この実装方法の場合、
先に述べた方法と比べて次の特徴があります。

  • メリット
    • 「各ASTノードを定義→解析関数を定義」というフローに添えばいいだけなのでとても簡単
    • コードの可読性は高い( 修正するときは特定のノードを参照するだけでいい )
  • デメリット
    • 構文に比較的制約を課す(後述)

構文に制約を課すというデメリットについて詳しく解説します。

この実装方法は、

  • 各文の先頭を見る
  • 対応する解析関数に飛ばす
    • return なら parseReturnStatement()
    • defなら parseDefStatement()
    • <identifier>なら次のチェックを
      • 次のトークン=なら parseReAssignStatement()
      • そうでなければ parseExpressionStatement()

このように、
先頭に対して解析するフローを制御しているのです。

Node構造体で一括管理する手法では、
解析する最中で Node.Typeを変化させる事で、
汎用性の高い関数+巨大な構造体によるASTの生成を実現しています。

ASTごとに解析関数を定義している場合、

int main(void){

}

というコードを見た時、

  • intが来たので変数定義だとする
    • 次のトークンはmainと識別子なので上手くいく
    • けど(で関数定義だと 初めてわかる

ということから、
現在見ているトークン・次のトークン・その次のトークンの、
3つの情報を解析器に持たせる必要があります。

構文解析がかなり複雑になってしまいますよね。


C言語のプログラムを大きく分けると、

  • Expression …変数定義の右辺
  • Mul …Expression内で用いられる乗除演算
  • Function …C言語で言えば一番大きな単位。stmt()関数の上

等が存在しますが、
プログラムに存在する言語要素ごとに解析関数を定義し、
後はif文やfor文等、C言語を構成する文法ごとに解析関数を取り回しています。

余談ですがこれはボトムアップ方式とも呼ばれ、
一度定義した部品ともいえる関数を再利用して様々な構文を解析出来るため、
プログラムの設計として優れているといえます。

ASTノードの生成方法は他にもあって、
「Goでつくるインタプリタ」では
if文、return文という単位毎に解析関数を定義しています。

この場合再利用するわけではなく、
各解析関数ごとにトークン列のオフセットを進めるため、
可読性は高いですが、コード量は多くなりがちです。

ソースコード解析まとめ

  • コンパイラ(内の解析器) にソースコードを入力する
    • 入力されたコード→トークン列→AST のフローで変換していく
  • 字句解析 は、入力されたコードから トークン列 を生成する。
    • トークンとは ソースコード上において意味を持つ最小単位
    • 識別子と予約語は 辞書のようなもの を定義して判別できるように
  • 構文解析 は、トークン列を受け付けて 整合性をチェック
    • 言語仕様に即した構文であれば ASTに組み込む
    • 再帰下降構文解析は最も実装がシンプル

中間表現生成

ここからは先程生成したASTから中間表現を生成するフェーズになります。
中間表現というのは ASTノードの情報をできるだけ保持したまま
アセンブリコードを出力する為の表現です。

中間表現とニーモニックは1対1に対応しています。
私がGo言語で再実装している9ccを例に取ってみましょう。

IR_MOVという中間表現から、
mov reg1, reg2というニーモニックを生成している様子です。

このIR_MOVは様々なASTノードから生成されます。
変数定義のために即値がレジスタに読み込まれますが、
そのときにも勿論IR_MOVの中間表現が作られますし、
ret命令を実行する時には最終的な演算結果をeaxに格納する為に
IR_MOVが生成されます。

goccの場合はかなり冗長なアセンブリが生成されます。
これは最適化の処理があまり組まれていないからです。

int main(void){
  int a = 2;
  int b = 3;
  return a+b;
}

というコードをそれぞれgcc( -O3 オプションをつけて )とgoccでコンパイルしてみると、

↓gocc

.intel_syntax noprefix
.global main
main:
  push rbp
  mov rbp,rsp
  sub rsp, 16
  push r12
  push r13
  push r14
  push r15
  mov r10, 2
  mov r11, rbp
  sub r11, 8
  mov [r11], r10
  mov r10, 3
  mov r11, rbp
  sub r11, 16
  mov [r11], r10
  mov r10, rbp
  sub r10, 8
  mov r10, [r10]
  mov r11, rbp
  sub r11, 16
  mov r11, [r11]
  add r10, r11
  mov rax, r10
  jmp .Lend0
.Lend0:
  pop r15
  pop r14
  pop r13
  pop r12
  mov rsp, rbp
  pop rbp
  ret

↓gcc

        .file   "c.c"
        .intel_syntax noprefix
        .text
        .section        .text.startup,"ax",@progbits
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
        mov     eax, 5
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
        .section        .note.GNU-stack,"",@progbits

と大きな違いが見られます。

gccは定数展開等、多くの最適化パスが適用されている事がわかります。

コンパイラの実装によって中間表現の種類も様々です。
代表的なものに**SSA(静的単一代入)**があります。

これは(擬似コードを示します)、

a = 2
a = 3
b = a

のようなコードを、

a_1 = 2
a_2 = 3
b_1 = a_2

として保持しておく中間表現の形式です。

ここで a_1に代入するコードは完全に冗長であり、
コンパイル時に最適化の一環で削除が可能になります。

今日のコンパイラ実装で最も用いられている中間表現形式であり、
例に上げたように 最適化しやすい形を取ることが出来ます。

実装によっては段階的に中間表現を生成するものもあります。

高級言語(元々のソースコード)→ 高レベルな中間表現アーキテクチャ固有の中間表現→アセンブリ

のような感じです。
中間表現の段階を多く踏むことで、最適化の実装がしやすいという背景があります。

(狭義の)コンパイル

ここで中間表現に対応したニーモニックの生成が行われます。

中間表現は

  • オペランドの状態
    • 即値であればその値だったり
    • レジスタであればそれを示す番号だったり
  • ニーモニックの種類
    • movだったりpushだったりjleだったり

の情報を保持しています。
後はそれにアセンブリコードを対応付けるだけです。

コンパイルの本体は中間表現に変換する部分とも言えそうです。

実際に変換するコードを紹介します。

for _, ir := range fn.IRs {
	switch ir.Operand {
	case IR_IMM:
		fmt.Fprintf(f, "  mov %s, %d\n", Registers[ir.Lhs], ir.Rhs)
	case IR_SUBIMM:
		fmt.Fprintf(f, "  sub %s, %d\n", Registers[ir.Lhs], ir.Rhs)
	case IR_MOV:
		fmt.Fprintf(f, "  mov %s, %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
	case IR_RETURN:
		fmt.Fprintf(f, "  mov rax, %s\n", Registers[ir.Lhs])
		fmt.Fprintf(f, "  jmp %s\n", ret)
	case IR_LOAD:
		fmt.Fprintf(f, "  mov %s, [%s]\n", Registers[ir.Lhs], Registers[ir.Rhs])
	case IR_STORE:
		fmt.Fprintf(f, "  mov [%s], %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
	case IR_SAVEARGS:
		for i := 0; i < ir.Lhs; i++ {
			fmt.Fprintf(f, "  mov [rbp-%d], %s\n", (i+1)*8, argRegisters[i])
		}
	case IR_ADD:
		fmt.Fprintf(f, "  add %s, %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
	case IR_SUB:
		fmt.Fprintf(f, "  sub %s, %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
	case IR_MUL:
		fmt.Fprintf(f, "  mov rax, %s\n", Registers[ir.Rhs])
		fmt.Fprintf(f, "  mul %s\n", Registers[ir.Lhs])
		fmt.Fprintf(f, "  mov %s, rax\n", Registers[ir.Lhs])
	case IR_DIV:
		fmt.Fprintf(f, "  mov rax, %s\n", Registers[ir.Lhs])
		fmt.Fprintf(f, "  cqo\n")
		fmt.Fprintf(f, "  div %s\n", Registers[ir.Rhs])
		fmt.Fprintf(f, "  mov %s, rax\n", Registers[ir.Lhs])
	case IR_LABEL:
		fmt.Fprintf(f, ".L%d:\n", ir.Lhs)
	case IR_UNLESS:
		fmt.Fprintf(f, "  cmp %s, 0\n", Registers[ir.Lhs])
		fmt.Fprintf(f, "  je .L%d\n", ir.Rhs)
	case IR_JMP:
		fmt.Fprintf(f, "  jmp .L%d\n", ir.Lhs)
	case IR_LT:
		fmt.Fprintf(f, "  cmp %s, %s\n", Registers[ir.Lhs], Registers[ir.Rhs])
		fmt.Fprintf(f, "  setl %s\n", Registers8[ir.Lhs])
		fmt.Fprintf(f, "  movzb %s, %s\n", Registers[ir.Lhs], Registers8[ir.Lhs])
	case IR_CALL:
		for i := range ir.Args {
			fmt.Fprintf(f, "  mov %s, %s\n", argRegisters[i], Registers[ir.Args[i]])
		}
		fmt.Fprintf(f, "  push r10\n")
		fmt.Fprintf(f, "  push r11\n")
		fmt.Fprintf(f, "  mov rax, 0\n")
		fmt.Fprintf(f, "  call %s\n", ir.Name)
		fmt.Fprintf(f, "  pop r11\n")
		fmt.Fprintf(f, "  pop r10\n")
		fmt.Fprintf(f, "  mov %s, rax\n", Registers[ir.Lhs])
	case IR_NOP:
		break
	default:
		logrus.Errorf("Unknown Operator")
}

goccの実装では、
Functionという構造体毎に中間表現の配列が格納されています。

FunctionはC言語のプログラム上で最も大きな単位であり、

#include<stdio.h>

int sum(int a,int b);

int main(void){
  int a = 3;
  int b = 5;
  printf("result:%d\n",sum(a,b));
  return 0;
}

int sum(int a,int b){
  return a+b;
}

でいえば、
mainsumがそれぞれ構造体 Functionになります。

Function の持つ中間表現の配列を回し、
次々にアセンブリコードを出力していきます。

goccにおいて fはファイルディスクリプタのラップであり、
標準出力やファイルなどを操作できる実装になっています。

文字列

コンパイラは言語仕様によって、
バイナリにデータを組み込む、という挙動を示します。

具体例を紹介します。

次のようなコードを記述し、
コンパイルしてみます。

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

const char name[] = "Drumato";
int main(void){
  char *buf = (char*)malloc(sizeof(char)*strlen(name));
  strcpy(buf,name);
  printf("%s\n",buf);
  return 0;
}
        .file   "c.c"
        .intel_syntax noprefix
        .text
        .globl  name
        .section        .rodata
        .align 8
        .type   name, @object
        .size   name, 8
name:
        .string "Drumato"
        .text
        .globl  main
        .type   main, @function
main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     edi, 7
        call    malloc@PLT
        mov     QWORD PTR -8[rbp], rax
        mov     rax, QWORD PTR -8[rbp]
        mov     rdx, QWORD PTR name[rip]
        mov     QWORD PTR [rax], rdx
        mov     rax, QWORD PTR -8[rbp]
        mov     rdi, rax
        call    puts@PLT
        mov     eax, 0
        leave
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
        .section        .note.GNU-stack,"",@progbits

.rodataセクションに nameシンボルが定義されていることがわかります。

.rodataセクjションはその名の通り読み込み専用領域を表し、
データセグメントの中でも特に静的な空間となっています。

#include <stdio.h>
#include <string.h>

char name[] = "Drumato";
int main(void) {
    strcpy(name, "ahahaha");
    printf("%s\n", name);
    return 0;
}

のようにコードを変更すると、
書き換え可能なデータセグメント(.dataセクション)"Drumato"`が格納されます。

        .file   "c.c"
        .intel_syntax noprefix
        .text
        .globl  name
        .data
        .align 8
        .type   name, @object
        .size   name, 8
name:
        .string "Drumato"
        .text
        .globl  main
        .type   main, @function
main:
        push    rbp
        mov     rbp, rsp
        movabs  rax, 27417840313264225
        mov     QWORD PTR name[rip], rax
        lea     rdi, name[rip]
        call    puts@PLT
        mov     eax, 0
        pop     rbp
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
        .section        .note.GNU-stack,"",@progbits

movabsの右オペランドには、
リトルエンディアンで表示されたASCIIコードが入っています。
(10進数のため見づらいですが)

文字列に限らず、
コンパイラは静的なリテラル値をバイナリに組み込む事で省メモリ化を実現しているのです。

また、
malloc関数のように 動的にメモリをアロケートする関数は、
プロセス空間のヒープ領域を利用しています。
この空間は静的にデータが格納されているわけではなく、
プログラムの実行によって動的にデータが格納されていくというわけです。


アセンブル

アセンブルとは、
先程生成したアセンブリコードをバイナリに変換します。
変換されたファイルを オブジェクトファイルと言い、
後述しますが ELF形式 に準拠している場合がほとんどです。

ここからはコンパイラの役割から外れる場合もありますが、
gcc等一般的に用いられるコンパイラは勿論この機能をサポートしています。

主に行われる事は、

  • アセンブリに対応したバイナリに変換する
  • ELFフォーマットに準拠したファイルを排出する

の2つです。

バイナリ変換

アセンブリはアーキテクチャによって固有の命令セットが用意されており、
それぞれ オペコード を指定することでCPUに命令実行させる事が出来ます。

オペランドにレジスタが来るのか、即値が来るのか。
レジスタ(即値)は何ビット長なのかによってオペコードは細かく変化します。

詳細にはプロセッサの仕様書に記載されていることが多く、
またアセンブラの実装をしている人は多くないため 自作する場合はとても難しいです。

const (
	ASCIICode = 0x0a

	AAA = 0x37
	AAD = 0xd5
	AAM = 0xd4
	AAS = 0x3f

	ADCAImm8    = 0x14
	ADCAImm16   = 0x15
	ADCRMImm8   = 0x80
	ADCRMImm8_2 = 0x83
	ADCRMImm16  = 0x81
	ADCRM8      = 0x10
	ADCRM16     = 0x11
	ADCR8       = 0x12
	ADCR16      = 0x13

	MovRM32    = 0x89
	MovRImm8   = 0xb0
	MovRImm16  = 0xb8
	MovRImm32  = 0xb8
	MovRMImm8  = 0xc6
	MovRMImm16 = 0xc7
	MovRMImm32 = 0xc7
	PushR32    = 0x50
	PopR32     = 0x58
)

これは私の自作しているアセンブラのオペコード一覧の一部です。

x86ニーモニックに対してこのようにオペコードが対応しており、
アセンブル時にはオペランドがレジスタか?即値か?
はたまたビット長は?
などなどを解析しながら機械語に変換していきます。

ELfフォーマット準拠

上記に示したように機械語に変換したアセンブリコードは、
ELFフォーマットに従ってファイルに配置されます。
ELFフォーマットについては記事を書いているのでそちらも合わせてご覧ください。

基本的に命令は.textセクションに格納されていきます。
またプログラムに利用されるデータ構造は.data.bssに格納されます。

これらセクションはOS( 厳密にはOSに組み込まれているローダ)が、
プログラムを実行する上で必要な情報を辿れるように ヘッダ情報が付与されています。

逆に言うと、
実行可能なファイルを作成するためには、
ELFフォーマットに準拠したバイナリを構成する必要がある、ということです。


リンカ

最後に、プログラムがlibc.so.6等のライブラリを実行ファイルにリンクします。

動的リンク のバイナリの場合は、
実行時にライブラリを参照出来るようにパス等の情報がDYNAMICセグメントに格納されます。

実際にlddコマンドを実行してみます。

$ ldd a.out
    linux-vdso.so.1 (0x00007fffeebd9000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fbd78eb0000)
    /lib64/ld-linux-x86-64.so.2 (0x00007fbd79600000)

のように、libcの情報が表示されています。

gccを利用する場合、-staticフラグを付けることで 静的リンクが可能になります。

この場合バイナリにlibc等ライブラリの機能が組み込まれる為、
実行時にライブラリを参照する必要はなくなります。

そのかわり ファイルサイズは動的リンクに比べとても大きく なります。
また、ライブラリの情報を格納するセクションが新たに追加されます。

readelf -hコマンドを用いると詳しく確認できますが、
リンク方式の違いは生成ファイルの違いを生んでいることがわかります。

同じELFバイナリでも、
動的リンクの場合は DYN (Shared Object File)に、
静的リンクの場合はEXEC (Executable file)になります。

どちらの場合であれ、この時既に実行可能なバイナリが生成できていると言えます。

動的リンクの場合は実行時にライブラリを参照するため、
Linux Namespace等の機能でマウント名前空間を変更すれば上手く実行できなくなります。

C言語のコンパイラを書く際に、最も難しいポイントはどこだと思いますか?考えたことや、これまでのプログラミング経験をもとに、具体的に書いてください。

私が考える最も難しい部分は、
ASTノードに対応した中間表現を生成し、アセンブリコードを出力する部分です。

これは少し範囲が広いかもしれませんが、
特に中間表現とアセンブリコードは密接な関係にあり、分けて話をすることが出来ません。

難しいと思った理由は、

コンパイル後のアセンブリコードがきちんと頭に入っていないと行けない

ということです。

私はRui Ueyamaさんの9ccをGoで再実装する勉強法を取っていますが、
アセンブリコードに馴染みが無かった私は、
出力されるアセンブリの意味がわからないこともしばしばありました。

例えば次のようなコードです。

mov [rsi], r10

この時 rsirspと同じ値が入っています。
つまり、 スタックのトップを指すアドレス が格納されています。

このコードは、
スタックに r10 に格納された値を積む という意味ですが、
[] 記号の意味を正しく理解していないと、
rsi にロードしてどうすんの?」 となってしまいます。

今回の例で言えば、
[] は間接アドレッシングを示し、
実際には rsiの指すアドレスにr10の値をロードするのですが、
私はこれを理解するために少し時間を費やしました。

その他にも DWORDの意味などなど、
システムプログラミング・低レイヤープログラミングに慣れていないと理解に時間がかかる部分は多いです。

コンパイラ自作は多くの分野に対する広い知識を必要とすると考えています。
具体的には、

  • C言語等既存の言語をサポートするコンパイラの場合
    • 対象言語の 完全な理解
    • サポートするアーキテクチャの理解(命令セット・レジスタ・スタックの仕様などなど)
    • 既存のサービスが対応している機能の追従(gccで言えばコンパイルだけではなくプリプロセスも出来る等)

余談ですが 自作言語のコンパイラを実装する場合 は上記に加えて、

  • コンパイラ以前に自作言語の設計が確かなものでないといけない
    • e.g.関数定義方法はfunc ident()か、fn ident()か?等
    • 言語の組み込みライブラリにも手を出すとかなりのコスト
  • テストの仕方も難しい
    • 世の中にその言語を使って 正しく動くコード が無い
    • テストケースの用意も自分がしなければならない
  • 勿論デバッガとかもない

という欠点があります。

この問題を解決する為の方法

恐らくですが、
現時点の私はまだまだ低レイヤープログラミングに精通していないです。

そのために コンパイラの吐くアセンブリの理解 にも長い時間がかかってしまうし、
x86(x86-64)アーキテクチャの理解も不足しています。

同じくバイナリ( ELF実行形式)に対する知識も全く足りません。
readelfコマンドを自作するなどして理解を深める努力をしていますが、
システムプログラミングに手を付け始めたばかりなのでまだまだ手探りの状態と言えます。

まずはもっと多くの事に取り組むべきだと感じています。
具体的には

  • アセンブリを書いてみる
    • ただ読んで理解するだけじゃなくて、アセンブリコードを実際に書く
  • C言語( 又は低レイヤープログラミングに親密な言語)をもっともっと使い込む
    • 今は Rust に手を出して、低レイヤーに触れる取り組みを続けている
    • ELFローダ・リンカ、デバドラ開発等、自身が興味を持ったもの何でも作ってみる
  • インプット活動をもっとやる。手を動かすのも大事だが私の場合そもそも知識が足りなすぎる
    • 今はIA-32 Intel Manualを読んで、内容を深掘りしながら記事にまとめたり
    • 坂井さんのリンカ・ローダ本、アセンブラ本に手を出そうと考えている
    • 後はLinuxカーネルの解析とかやってみたり

事を行うことで、
コンパイラの動きがより詳しくわかるのでは?と考えています。


話を本題に戻しますが、
C言語のコンパイラを作る上で難しいポイントはもう一つあります。

それは、
ホスト言語による実装がC言語の実行速度に直結してしまうということです。

C言語でプログラミングする大きな利点の一つに、

  • 省メモリである( 最も柔軟にメモリ管理が出来る )
  • 実行速度が高速である( 数十年前の言語であるにも関わらず新進気鋭に勝るとも劣らない )

というものがありますよね。

これらメリットには言語仕様の影響も勿論ありますが、
何よりデファクトスタンダードとなっている gcc の実装が大変優れている、
より厳密には gccは長い年月をかけて最適化を実装してきた という事が挙げられます。

実際に例をあげようと思います。
下に示すコードを-O0オプションでコンパイルしてみます。

main() {
        int a=2; 
        int b=3+2; 
        return a*b;
}

余談ですがC言語では mainの前に型を付けなくてもコンパイル出来ます
(警告が出力されますし本来推奨されない書き方ですが)
同様にvoidも省略出来ます。

さて、このプログラムをコンパイルした結果を見てみましょう。
gcc -S -fno-asynchronous-unwind-tables -O0 -masm=intel
としています。

        .file   "c.c"
        .intel_syntax noprefix
        .text
        .globl  main
        .type   main, @function
main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR -8[rbp], 2
        mov     DWORD PTR -4[rbp], 5
        mov     eax, DWORD PTR -8[rbp]
        imul    eax, DWORD PTR -4[rbp]
        pop     rbp
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
        .section        .note.GNU-stack,"",@progbits

やっていることはとてもシンプルで、

  • 関数プロローグ
  • スタックに即値を積むことでローカル変数の定義
    • int b=2+3;の定数部分は既に計算されている
  • imul命令で返り値を計算し関数のエピローグ

という感じです。
既にいくつかの最適化パスが適用され、アセンブリコードはとても小さなものになっています。

因みに-O3オプションをつけてコンパイルしてみましょう。

        .file   "c.c"
        .intel_syntax noprefix
        .text
        .section        .text.startup,"ax",@progbits
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
        mov     eax, 10
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
        .section        .note.GNU-stack,"",@progbits

なんと変数定義すらしていません。
いきなり定数をリターンしています。

( -O3オプションを使うべきかという議論はひとまず置いておいて)
gccにはこれだけの最適化を適用するポテンシャル があります。

C言語が今日に至るまで使われ続けているのは、
gccの吐くニーモニックがとてもキレイで、冗長性が取っ払われているからと言えそうです。

自作コンパイラでこのレベルの最適化を実装するのには 長い時間と深い知識が必要になります。

この問題を解決するための方法

私が言語処理系に興味を持ったのは2月の中旬ごろになります。
そこから 一ヶ月間程度で ホスト言語に乗っかる簡素なインタプリタ言語を作成し、
その後 4月に入ってからコンパイラの勉強を始めました。

そのため、
自作コンパイラについての知見が圧倒的に足りないと感じています。

コンパイラ自作の技術書等は一冊も読んでいません。
Rui Ueyamaさんの9ccを写経する以外のリソースを現在利用していないのです。

なのでまずは、
世の中のコンパイラがどのように動いているのかを詳しく知る必要があると考えています。

その為に空いた時間に Go言語のセルフホストコンパイラを読んでみたりしています。

Web上で自作コンパイラをやっている人のコードを読んでみたりするのも手かもしれません。

とにかく、
まだまだ知識が足りない為にコードの全体像が意識できてないということは考えられます。

また、
最適化の具体的な実装方法については完全に無知です。
何もわかっていません。

世間には 最適化に特化した技術書があるようなので、
いずれ読もうと思っています。

何か他にアピールしたいことがあれば、自由に書いてください。この設問も含め、誤ったことを書いていても減点はしません。書いておきたいことはなんでも書いてください。

**私はほぼ同時期にSecHack365**に応募しています。

そこでは、

フルスクラッチ開発によるセキュアなシステムプログラミング言語・コンパイラ及び静的解析ツール等の開発 をテーマに、
一年間開発活動を行いたいと考えています。

SecHackに合格するかは定かではありませんが、
例え選考に残らなかったとしても、
同様のテーマで独自に開発をやりたいという気持ちがあります。

無事合格しました。
一年間努力したいと思います。

ここでは私が考えている
フルスクラッチでシステムプログラミング言語の開発のイメージをお話するべく、
実際にSecHackに応募した際に添付した文章のうち、

  • テーマ設定理由
    • 一年間そのテーマに取り組む上でやりたいこと

のみ全文を引用して紹介しておきたいと思います。

私のコンパイラ自作に対する熱意が伝われば幸いです。


テーマ設定理由

テーマ名 「フルスクラッチ開発によるセキュアなシステムプログラミング言語・コンパイラ及び静的解析ツール等の開発」


使用言語・プラットフォーム

  • Golang(予定)
  • Rust(より低レイヤーに親密な言語としてピックアップ)
  • C(定番だができればRustを用いたい)

大まかなビジョン

  • セキュアな言語の開発
  • 言語をサポートするコンパイラ(プリプロセスからリンクまでを行う、所謂"広義の"コンパイラ)
  • プリプロセッサ、アセンブラ、リンカを総動員したコレクション。
  • 脆弱性(及び脆弱性になりうるコード)のアテンション
  • SSA(静的単一代入)形式に代わる中間表現の考案・実装
  • 言語に組み込むパッケージの開発
  • 言語処理系・セキュアなコンパイラについてのドキュメント作成

SecHackでやりたいこと・ テーマの設定理由

「推奨テーマ」にある「オープンソース・ソフトウェア改造によるセキュリティ機能の開発」と似ていますが、
gcc等の既存プログラムを改造するのではなく、
コンパイラ自体をフルスクラッチで開発するところから行いたいと思います。

ヘッダファイルを展開し、アセンブリ言語にコンパイルし、
ライブラリとリンキングしてバイナリ(ELF)を出力するまでの基盤から開発したいと考えています。

実際に規格・言語仕様に準拠したコンパイラの開発と並行して、
Exploitを防ぐようなセキュリティ機構を実装していきたいです。

私は(ミニマムではありますが)言語の自作を経験したことがあるので、
C言語のコンパイラと制限しなくても自作でセキュアな言語を作成することにも高い関心と興味があります。
その場合には C言語と同等以上の実行速度を担保 しながら、
セキュリティ機構を備えたコンパイラを作成したいです。

実際の開発に先立ってセキュリティ(特に低レイヤーの)知識が必要となるために、
開発に並行してそれら知識の補完に優先して取り組むつもりでいます。
具体的な勉強法としては gccその他既存のコンパイラのコードを読み込んで、
その実装を模倣する( ゆくゆくは改善する )が上げられます。
現在はCTFのPwn・Rev問題を勉強しながら、 コンパイラ(ソースコード)の脆弱性についての知識を深めています。

また、デットコードの削除等において特に優れた性能を発揮する SSA等の主要な中間表現ですが、
これにとって代わるような優れた中間表現の種類を編み出したいです。

具体的には過去にないような新規性のあるアプローチを持ってして コンパイラの最適化を行ったり、
またセキュリティ上脆弱なコードを差し替えるなどです。

また、「他分野の技術領域」の知識・内容を積極的に取り入れたいと考えています。
具体的には組み込みライブラリを実装することで、
Rubyのnet/http,Goのsyscallパッケージのような プラットフォームでサポートする仕組みを実現したいです。
これには「技術に対する深く広い理解」を必要とするため、
開発を通して自身の勉強が加速する事や、 単純にコンパイラの利便性向上に大きく貢献することが動機としてあります。

以下実際に考えているものの一部を紹介します。

ネットワーク系のパッケージ

RFCを読みながら各種プロトコル通信をサポートするパッケージの実装。

暗号の生成

ハッシュ化関数・セキュリティ暗号アルゴリズムをサポートするパッケージの実装

エスケープ関数

PHPでいう htmlspecialchars()関数のようなもの。
関数の引数にSanitizeして欲しい文字列を可変長渡すことで、 出力される際にエスケープされる、
またはメモリ・変数に格納される際に変更される 等。

セキュアなコンパイラ自作が一番のテーマとなりますが、
ここでの「コンパイラ」は、 プリプロセス、アセンブル、リンクを行う gccのような拡張コンパイラを想定しています。
アセンブリを出力するだけにとどまらず、 アーキテクチャ依存のニーモニックを機械語に変換し、
複数オブジェクトファイルをまとめあげて実行可能バイナリを生成するまでを出来るようなものを作りたいと思います。
これには低レイヤーに対する深い理解と、
システムプログラミングの豊富な経験が必要だと思うので、
自己学習を並行して進めながら取り組みたいと思います。

また、私は今Cybozu Lab Youth 8thとして、
「深層生成モデルによるText-To-Illustタスクへのアプローチ」というテーマで 研究をしています。

コンパイラ開発のサブセットに「セキュリティ上の問題を指摘する静的解析ツール」を掲げ、
自身の機械学習の知識を活用できればなぁと考えています。
具体的にはソースコードを入力することでアテンションできるようなモデルの作成です。

機械学習以外にも、適用できるような知識は多数あると考えております。
例えばDockerを抜きにGolangを語ることは出来ないと思います。
RubyにおけるRuby on Railsも同様ですね。

言語処理系を開発するのと同時に、
その言語を用いたツールの開発などもできればより知識の適用範囲・自身のスキルアップにつながると考えております。

最後に、私は本SecHack365で一年間活動したものを 「全ドキュメント化」したいと考えています。

理由は次の3点です。

  • 言語処理系・セキュアなコンパイラ自作の日本語の文献があまり無い
  • 特に独学者にとって優れた無料(場合によっては有料)の文献を作成したい
  • 自身のアウトプット活動の一環となる

まず「現状日本語で言語処理系の文献が少ない」というのがありますが、 これは実際に私が勉強する上で感じたことです。 ] 「Goでつくるインタプリタ」という書籍は大変平易な文章でわかりやすく、
また体系的に処理系実装の概観をするものですが、
Go言語が書けるか、読めるかどうかで 勉強のハードルはかなり変わってくるでしょう。

私は「特定プログラミング言語によらない体系的な資料の作成」を考えており、
それを実現するための手法をいくつか考えています。

単純にソースコードの利用をしない(又は擬似コードでの解説)か、
複数言語で実装しておき、解説では一つの言語を利用するがリポジトリを参照できるようになっている等です。
これについては実際に作成する時に検討していきたいと考えています。

次に私はIT技術を勉強する多くの方と同じ様に、 あらゆる技術は「独学で」勉強しています。
具体的には

  • 技術書・Web上のリソース
  • 自身の頭で試行錯誤

などです。

私がブログを継続しているのはそういった独学者にとって
有用なリソースを提供できないか?というのが大きいです。

今回のSecHack365で活動したことを逐一残しておくことで、
コンパイラの実装を行いたいという人に対する有益な文献を作りたいと思っています。

3つ目に、「自身のアウトプット活動を促進する1ファクターとなる」事が挙げられます。

私は普段自身の勉強したことを (どんな小さなことでも)ブログにまとめていますが、
それは「コミュニティ・リソースから得た知見を還元するため」という理由を 大きく孕んでいます。

SecHackは弊学の先輩から教えていただいた人材育成プログラムですが、
先輩が私に教えてくれたように、
私はブログを見てくれる多くの方に SecHackとはどういうもので、
一年間コンパイラの勉強をして何が身についたかを知れるようにしたいと思います。
そのために日報の作成・ドキュメント化を推進し、 一年間での開発を充実させたいと思います。


終わりに

最初に述べた通り、

  • セキュアな
  • 実行速度も高速な
  • 組み込みライブラリ等のサポートが充実した
  • Linter等のエコシステムが揃っている
  • 可能であれば自作の

言語・それをサポートするコンパイラの自作には
非常に高い熱意とやる気を持っていることを自負しています。

セキュリティ・キャンプでの活動にその熱意が活かせればと思います。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.