ふつうのコンパイラをつくろうを読んで

DIGGLEのchikugoです。今回はふつうのコンパイラをつくろうという書籍を読みましたので、そちらの内容の紹介をします。本稿では細かいところは書籍に譲り、コンパイラがどのように動いているのかのイメージ感をつかめるところを目標にしたいと思います。書籍ではJava向けのパーサジェネレータのJavaCC(Java Compiler Compiler)を使用しているので本稿でもそちらを利用して解説します。

コンパイルの順序
サンプルコード
最後に
We’re hiring!

コンパイルの順序

まずはコンパイルがどのような動作順序で動いているかを示します。

プリプロセス
- プリプロセス済みのソースコードが作成される
- C言語の場合
  - #includeや#defineが処理されるなど
  - つまりヘッダファイルが取り込まれてすべてのマクロが展開される
(狭義の)コンパイル
- アセンブリ言語のソースコードを作成する
- 一般的に「.s」という拡張子がつく
アセンブル
- オブジェクトファイル(機械語)を作成する
- オブジェクトファイルとも呼ばれ、一般的に「.o」の拡張子つく
リンク
- 実行可能ファイルを作成する

(書籍より一部抜粋)

このうち狭義のコンパイルについておおまかに以下の4つの段階があります。

1. 字句解析(lexical analyze)

スキャン(scan)する
- ソースコードを単語へ分割する作業
- 例) x = 1 + 2 を「x」「=」「1」「+」「2」へ分割する
- 空白やコメント、改行は捨てられる
- スキャンするプログラムをスキャナ(scanner)という
TOKEN化する
- 「単語一つ」と「その種類」、「意味値」をまとめてTOKENと呼ぶ
- スキャンされると「単語」、「種類」、「意味値」がTOKEN化されて設定される

(書籍より一部抜粋)

2. 構文解析と意味解析

構文を解析してプログラムが理解しやすい形式の抽象構文木が作成される
意味を解析して構文として不正なものはコンパイルエラーとなる

3. 中間表現の生成

中間表現(IR、intermediate representation)に変換する
- 中間表現を生成するとそれに対応した複数の言語や、複数の機械語に対応できるという利点がある
- GCCはRTL(register trasfer language)という中間表現を使っている

4. コード生成(code generation)

中間表現をアセンブリ言語に変換する

サンプルコード

これだけではイメージしにくいと思いますので、簡単なimport文の字句解析から中間表現の生成までのサンプルコードを示します。今回は以下のようなimport文を処理するサンプルになります。

import java.util.List;
import java.util.ArrayList;

構文解析の生成はJavaCCを使用します。

サンプルコードは以下になります。

// Parser.jj
options {
    STATIC = false;
    IGNORE_CASE = false;
}

PARSER_BEGIN(MyParser)
import java.util.HashSet;
import java.util.Set;

public class MyParser {
    private static final Set<String> importedClasses = new HashSet<>();

    public static void main(String[] args) throws ParseException {
        MyParser parser = new MyParser(System.in);
        System.out.println("Parsing started...");
        ASTNode root = parser.start();
        System.out.println("Parsing completed successfully!");

        // Abstract Syntax Tree (AST) を表示
        System.out.println("\nAbstract Syntax Tree:");
        root.print("");

        // IR を生成
        System.out.println("\nGenerated IR:");
        StringBuilder ir = new StringBuilder();
        root.generateIR(ir);
        System.out.println(ir.toString());
    }

    /**
     * インポート文の完全修飾名を検証します。
     * @param fullName 検証対象の完全修飾名
     */
    private static void validateImport(String fullName) {
        if (!importedClasses.add(fullName)) {
            System.err.println("Warning: Duplicate import for '" + fullName + "'.");
        }
    }
}
PARSER_END(MyParser)

// ===== TOKEN 定義 =====
TOKEN: {
    < IMPORT: "import" >
  | < IDENTIFIER: ["a"-"z", "A"-"Z"] (["a"-"z", "A"-"Z", "0"-"9", "_"])* >
  | < DOT: "." >
  | < SEMICOLON: ";" >
}

// ===== SKIP 定義 =====
SKIP: { " " | "\t" | "\n" | "\r" }

// ===== 構文解析ルール =====

/**
 * パーサのエントリーポイント。
 * インポート文を解析し、それ以外の未知の構造をスキップします。
 */
ASTNode start(): { ASTNode root = new ASTNode("root"); }
{
    (topLevelStatement(root))*
    <EOF>
    { return root; }
}

/**
 * トップレベル構造を解析します。
 * インポート文を解析し、それ以外はスキップします。
 */
void topLevelStatement(ASTNode parent): {}
{
    importStmt(parent)
  | unknownStatement()
}

/**
 * インポート文を解析し、AST ノードを構築します。
 */
void importStmt(ASTNode parent): { 
    ASTNode node = new ASTNode("import_stmt");
    StringBuilder fullName = new StringBuilder(); 
}
{
    <IMPORT> { 
        node.addChild(new ASTNode("IMPORT"));
    }
    name(node, fullName)
    (<DOT> { 
        fullName.append("."); 
        node.addChild(new ASTNode("DOT"));
    } name(node, fullName))*
    <SEMICOLON> { 
        node.addChild(new ASTNode("SEMICOLON"));
        parent.addChild(node);
        validateImport(fullName.toString());
        System.out.println("Valid import: " + fullName);
    }
}

/**
 * 未知の文をスキップします。
 * 任意のトークンを読み飛ばし、セミコロンまたは EOF まで進む。
 */
void unknownStatement(): {}
{
    (
        <IDENTIFIER> 
      | <DOT> 
    )+ (<SEMICOLON> | <EOF>)
}

/**
 * 識別子（名前）を解析し、AST ノードを構築します。
 */
void name(ASTNode parent, StringBuilder fullName): {}
{
    <IDENTIFIER> { 
        String value = token.image;
        fullName.append(value);
        parent.addChild(new ASTNode("IDENTIFIER: " + value));
    }
}

(書籍より一部抜粋)

// ASTNode.java

import java.util.ArrayList;
import java.util.List;

public class ASTNode {
    private String value;
    private List<ASTNode> children = new ArrayList<>();

    public ASTNode(String value) {
        this.value = value;
    }

    public void addChild(ASTNode child) {
        children.add(child);
    }

    public void print(String prefix) {
        System.out.println(prefix + value);
        for (ASTNode child : children) {
            child.print(prefix + "  ");
        }
    }

    public void generateIR(StringBuilder ir) {
        // import_stmt の場合
        if (value.equals("import_stmt")) {
            StringBuilder fullName = new StringBuilder();
            for (ASTNode child : children) {
                if (child.value.startsWith("IDENTIFIER: ")) {
                    if (fullName.length() > 0) fullName.append(".");
                    fullName.append(child.value.substring("IDENTIFIER: ".length()));
                }
            }
            if (fullName.length() > 0) {
                ir.append("LOAD ").append(fullName).append("\n");
            }
        }

        // 子ノードを再帰的に処理
        for (ASTNode child : children) {
            child.generateIR(ir);
        }
    }
}

JavaCCの文法について

JavaCCの文法ページはこちら。

PARSER_BEGINからPARSER_ENDまで

これはJavaCC特有の構文で、生成されるJavaコードのクラス名を指定します。

TOKEN命令とSKIP命令

TOKEN命令にそれぞれ正規表現規則を記述するとJavaCCのTOKENマネージャーは、正規表現の一致ごとにオブジェクトを作成してそれをパーサーに返します。 SKIP命令は空白やタブなど文法として意味をなさない用のTOKENマネージャーが無視する命令になります。

構文解析ルールとBNF

例えば構文解析ルールの以下のようなコードは、

ASTNode start(): { ASTNode root = new ASTNode("root"); }
{
    (topLevelStatement(root))*
    <EOF>
    { return root; }
}

以下のようなBNF(wiki)と対応関係があります。

<start> ::= (<topLevelStatement>)* <EOF>

BNFはJavaCCで構文解析ルールを指定する際に使用される標準生成規則です。 { return root; } のコードはBNFにはないJavaCC固有の記述で、ルールに基づいて抽象構文木(AST)を作成するコードなります。

事前準備と実行

事前準備としてJavaを使うのでJDKのインストールとJavaCCより、javacc-..*.jarをダウンロードしてくる必要があります。

ソースコードをコンパイルして実行します。まずは下記のようなコマンドによりMyParser.javaなどのファイルを自動生成します。

java -cp ~/javacc/javacc-7.0.13.jar javacc Parser.jj

生成されたjavaファイルをさらにコンパイルします。

javac ASTNode.java MyParser.java

コンパイルされたparserを実行します。

java MyParser
Parsing started...

Parsing started...と入力を促されるのでimport文を入力します。

import java.util.List;
import java.util.ArrayList;

入力後にcontrol + D(macの場合)を入力すると結果が得られます。

Parsing completed successfully!

Abstract Syntax Tree:
root
  import_stmt
    IMPORT
    IDENTIFIER: java
    DOT
    IDENTIFIER: util
    DOT
    IDENTIFIER: List
    SEMICOLON
  import_stmt
    IMPORT
    IDENTIFIER: java
    DOT
    IDENTIFIER: util
    DOT
    IDENTIFIER: ArrayList
    SEMICOLON

Generated IR:
LOAD java.util.List
LOAD java.util.ArrayList

これで字句解析から構文解析、中間表現の生成までできました。

まずは字句解析のTOKEN化から順に解説していきます。

TOKEN化

import文用のサンプルとしてのTOKEN定義を示します。

// ===== TOKEN 定義 =====
TOKEN: {
    < IMPORT: "import" >
  | < IDENTIFIER: ["a"-"z", "A"-"Z"] (["a"-"z", "A"-"Z", "0"-"9", "_"])* >
  | < DOT: "." >
  | < SEMICOLON: ";" >
  | < EQUAL: "=" >
  | < SINGLE_QUOTE: "'" >
  | < STRING_LITERAL: "'" (~["'"])* "'" >
}

入力内容が単語に分解された後に、上記のTOKEN定義により正規表現に一致しているか判定されてTOKENとして保持されます。

例えば以下のようなTOKENに分類されます。

# 入力: import java.util.List;
<IMPORT> "import"
<IDENTIFIER> "java"
<DOT> "."
<IDENTIFIER> "util"
<DOT> "."
<IDENTIFIER> "List"
<SEMICOLON> ";"

# 入力: import java.util.ArrayList;
<IMPORT> "import"
<IDENTIFIER> "java"
<DOT> "."
<IDENTIFIER> "util"
<DOT> "."
<IDENTIFIER> "ArrayList"
<SEMICOLON> ";"

構文解析

ASTNode root = parser.Start();

で構文解析ルールの

/**
 * パーサのエントリーポイント。
 * インポート文を解析し、それ以外の未知の構造をスキップします。
 */
ASTNode start(): { ASTNode root = new ASTNode("root"); }
{
    (topLevelStatement(root))*
    <EOF>
    { return root; }
}

が呼ばれて構文解析が開始されます。 topLevelStatementでトップレベル構造を解析します。

/**
 * トップレベル構造を解析します。
 * インポート文を解析し、それ以外はスキップします。
 */
void topLevelStatement(ASTNode parent): {}
{
    importStmt(parent)
  | unknownStatement()
}

インポート文を解析し、それ以外はunknownStatementでサンプルのためスキップします。

/**
 * インポート文のリストを解析します。
 */
void importStmts(ASTNode parent): {}
{
    ( importStmt(parent) )*
}

( importStmt(parent) )* でimportStmt が 0回以上繰り返し呼び出されます。

/**
 * インポート文を解析し、AST ノードを構築します。
 */
void importStmt(ASTNode parent): { 
    ASTNode node = new ASTNode("import_stmt");
    StringBuilder fullName = new StringBuilder(); 
}
{
    <IMPORT> { 
        node.addChild(new ASTNode("IMPORT"));
    }
    name(node, fullName)
    ("." { 
        fullName.append("."); 
        node.addChild(new ASTNode("DOT"));
    } name(node, fullName))*
    <SEMICOLON> { 
        node.addChild(new ASTNode("SEMICOLON"));
        parent.addChild(node);
        validateImport(fullName.toString());
        System.out.println("Valid import: " + fullName);
    }
}

<IMPORT> { node.addChild(new ASTNode("IMPORT")); }

IMPORT TOKENが出現した場合はノードに追加します。 (import java.util.List; の import の部分)

name(node, fullName)

名前(識別子)を解析して、ノード(node)に追加しつつ、完全修飾名(fullName)を構築します。(import java.util.List; の java の部分)

("." { fullName.append("."); node.addChild(new ASTNode("DOT")); } name(node, fullName))*

TOKENと名前(識別子)を繰り返し解析してノードに追加します。 (import java.util.List; の .util.List の部分)

<SEMICOLON> { node.addChild(new ASTNode("SEMICOLON")); }

セミコロン ; を解析し、ノードに追加します。

    <IDENTIFIER> { 
        String value = token.image;
        fullName.append(value);
        parent.addChild(new ASTNode("IDENTIFIER: " + value));
    }

ちなみにコードに唐突に出現するtokenはJavaCCによっての内容が自動設定されたTOKENになります。

構文解析が終わると以下のような抽象構文木が生成されます。

# 入力例
import java.util.List;
import java.util.ArrayList;

実際にはimport文以外の様々な構文を処理する必要がありますので、それを構文解析ルールとして記述する必要があります。

意味解析

意味解析はコンパイルエラーになるような不正な構造の検出です。

サンプルではimport文が重複していたら警告表示するようになっています。

    /**
     * インポート文の完全修飾名を検証します。
     * @param fullName 検証対象の完全修飾名
     */
    private static void validateImport(String fullName) {
        if (!importedClasses.add(fullName)) {
            System.err.println("Warning: Duplicate import for '" + fullName + "'.");
        }
    }

実際には他にも存在チェックや型チェック、スコープチェックなどの様々なチェックが必要になります。

重複した入力があると以下のようなWarningが出力されます。

java MyParser
Parsing started...
import java.util.List;
import java.util.ArrayList;
import java.util.List;

Warning: Duplicate import for 'java.util.List'.

中間表現生成

構文解析で生成された以下の抽象構文木から中間表現を生成します。

まずはrootから処理がはじまり、

root.generateIR(ir);

rootの場合はvalueがrootなので子ノードが再帰的に処理されます。抽象構文木のimport_stmtノード以下が対象になり、例としてimport java.util.List;の場合はjava.util.Listが保持されて、それにLOAD命令が先頭に付与されて最終的にLOAD java.util.Listに変換されます。

    public void generateIR(StringBuilder ir) {
        // import_stmt の場合
        if (value.equals("import_stmt")) {
            StringBuilder fullName = new StringBuilder();
            for (ASTNode child : children) {
                if (child.value.startsWith("IDENTIFIER: ")) {
                    if (fullName.length() > 0) fullName.append(".");
                    fullName.append(child.value.substring("IDENTIFIER: ".length()));
                }
            }
            if (fullName.length() > 0) {
                ir.append("LOAD ").append(fullName).append("\n");
            }
        }

        // 子ノードを再帰的に処理
        for (ASTNode child : children) {
            child.generateIR(ir);
        }
    }

以下のような入力がされた場合は、

import java.util.List;
import java.util.ArrayList;

以下のような中間表現が出力されます。

Generated IR:
LOAD java.util.List
LOAD java.util.ArrayList

最後に

ここまでで、まだ書籍上では半分くらいしか進めていません。残りとして中間言語からアセンブリ言語のソース作成や、そこから機械語への変換と実行可能ファイルの作成などもあります。今回は長くなってしまったので都合上、ここまでとしたいと思います。また今回は概要を掴むということで書籍の内容からはかなり簡略化と独自化をしています。詳細な部分やこの先に興味があるかたは書籍を読んでみてください。

We’re hiring!

DIGGLEではともにプロダクトを開発・運用をしてくれるエンジニアを大募集中です。少しでも興味があれば、ぜひ下記採用サイトからエントリーください。 カジュアル面談も実施しているので、気軽なお気持ちでご応募いただければと思います！

herp.careers

DIGGLE開発者ブログ

予実管理クラウドDIGGLEのプロダクトチームが、技術や製品開発について発信します

ふつうのコンパイラをつくろうを読んで

コンパイルの順序

1. 字句解析(lexical analyze)

2. 構文解析と意味解析

3. 中間表現の生成

4. コード生成(code generation)

サンプルコード

JavaCCの文法について

PARSER_BEGINからPARSER_ENDまで

TOKEN命令とSKIP命令

構文解析ルールとBNF

事前準備と実行

TOKEN化

構文解析

意味解析

中間表現生成

最後に

We’re hiring!