読書メモ: コンパイラ

Intro
コンパイルのフロー
字句解析
構文解析
構文解析の種類
意味解析
🚧 コード生成
まとめ
関連/参考リンク

Intro

コンパイラ [コンピュータサイエンス教科書シリーズ] (コンピュータサイエンス教科書シリーズ 8)という本を知り合いに進めていただき読みました。意外と本自体の両方は多くないんですが、要件がまとまっていてとても読みやすい本でした。自分みたいなCSを学んでこなかった身としても理解できる内容になっていたと思います。コンパイラについての少しでも興味を持った方であればぜひ読んでみることをおすすめします。

コンパイルのフロー

コンパイルの全体フローとしては、主に以下のようになっています。

字句解析
構文解析
意味解析
コード生成

わかりやすく表現すると、以下のようになります。

単語に区切る作業
文法に合っているかチェックをする作業
意味規則に基づいたチェックをする作業
目的に基づいたチェックをする作業。（コードを効率良くする最適化を行うこともある）

では実際にどのようにして解析をしているのか、どんなことをやっているのか見ていきましょう。

字句解析

この解析フローは以下のようになっています。

入力文字列を走査
パターンにマッチしたらそこまでの文字列を一区切りにする
結果を構文解析器に渡す

例えば、以下のようなコードを字句解析してみます。

if (a != 0){
  break;
}

このコードをトークンに分けた場合、IF, LPAR, IDENT, NEQ, NUMBER, RPAR, LBAR, BREAK, SEMI, RBRAというようになります。 ifはIFに、!=はINDENTといったトークンに変換されています。

Unix環境の方であれば、lexというコマンドが使えるかと思います。これを使用して字句解析を作ることが可能です。例えば以下のようなコードがあります。

%%
[0-9]+ { printf("Number!!\n"); }
[ \t\n]+ { /* do nothing */ }
.+ { printf("other!!\n"); } 

%%

int main(){
  while(yylex()!=0){
  }
  return 0;
}

正規表現で入力を受け取ります。例えば0~9の入力があった場合はNumber!!と出力します。これがlexingです。

そしてここで変換されたトークンの結果を、次の構文解析器に渡します。

構文解析

次に構文解析です。この解析では字句解析で生成されたトークンをもとに、構文木などを生成する作業を行います。実際のコンパイラでは、字句解析と構文解析を合わせてParserと呼んだりしていることが多いように感じます。

以下のようなコードであれば、どのような構文木が生成されるかみていきましょう。

int main() {
    int a = 10;
    if (a != 0) {
        a = 0;
    }
    return 0;
}

自分が今回用意したコードのようになっているのであれば、以下のような構文木になります。

Program
└── FunctionDefinition
    └── CompoundStatement
        ├── VariableDeclaration
        │   ├── Identifier: a
        │   └── Value: 10
        ├── IfStatement
        │   ├── Condition
        │   │   ├── Left: Identifier (a)
        │   │   ├── Operator: !=
        │   │   └── Right: Number (0)
        │   └── Body
        │       └── AssignmentStatement
        │           ├── Left: Identifier (a)
        │           └── Right: Number (0)
        └── ReturnStatement
            └── Value: Number (0)

簡単に説明を載せておきます。

プログラム全体はProgram
Programの直下にFunctionDefinitionがあります。ここがmainと宣言した部分にあたります。
FunctionDefinitionの直下にCompoundStatementがあります。これは関数の本体です。
CompoundStatementの中に、順番に以下の要素があります：
1. VariableDeclaration: 変数 a を 10 で初期化します。
2. IfStatement: 条件文を表します。
  - Condition: a != 0 という条件を表します。
  - Body: if 文の本体で、ここには代入文が含まれています。
3. AssignmentStatement: a = 0 という代入を表します。
4. ReturnStatement: 関数からの戻り値 0 を表します。

構文解析の種類

構文解析には大きく二つの解析手法があります

上向き構文解析
下向き構文解析

上向き構文解析は、葉から根へと作っていくように解析が進められる解析手法です。つまり値をみて次に字句解析が行われ、構文解析がされるということ。

次に下向き構文解析は反対で、根から葉へと解析を進め、最終的に入力に合うように解析木を構築していく解析手法です。

あまりここら辺は理解できていないので今回はこれくらいにしておきます🙇‍♂️

意味解析

次に意味解析についてです。ここでは字句解析時に生成したトークンが文法的に正しいかどうかをチェックします。

例えば以下のようなケースです。

宣言されてない変数は使うことはできない
宣言されていても誤った使い方をしているものをコンパイラは発見しなければならない

具体的に、TypeScriptを例にみて行きたいと思います。

const PI = 3.14159;
PI = 3.14;

この例ではconstという定数を制御する文法に対して再代入を行おうとしているのでエラーになります。これは言語の仕様的にコンパイルエラーになるようにコンパイラは実装する必要があります。

そして意味解析では型チェックも行います。

let name: string = "Alice";
name = 42;

string型に対して、number型の値を再代入しようとしているので、これも仕様的にコンパイルエラーにならなければなりません。

今回も意味解析のコードをこちらで実装しています。以下のようなコードはエラーになります。

int main() {
    b = 10;  
    return 0;
}

bという変数は宣言されていないので、Undeclared variableというエラーになります。

🚧 コード生成

書くのにカロリーかなり使ったのでまた暇な時に書きます🙏

まとめ

アプリを開発するだけではあまりコンパイラの挙動など理解しなくても開発はできると思いますが、筆者としてはフレームワークやライブラリの挙動を理解するためにもこういった普遍的な部分の勉強が遠回りでも大事だと思っています。今後はOSSのコードを読んで実際のコードと比較しながらより理解度を深めて行きたいです。

フロントエンドは好きですが、これからは異なる分野の技術にも触れて行きます💪