コンパイラ入門

コンパイラ入門 C#で学ぶ理論と実践 (ソフトウェア実践講座)

本書は、C#を用いて独自のプログラム言語をコンパイルするオリジナルのコンパイラを作成していく。
理論と実践を組み合わせた総合的な解説書である。

コンパイラを自作したいなあと考えながらも、なかなか理論書を読んでも出来るものではありません。
この本は手軽に作りながら進めていけそうということで購入しました。
今日はとりあえず6章まで読み進めました。本を終了する頃には、Pascal風の言語コンパイラが完成します。

目次

第1章　 はじめに
第2章　 コンパイラ
第3章　 ステップ1:問題の把握
第4章　 ステップ2:開発環境の設定
第5章　 ステップ3:語彙定義
第6章　 ステップ4:スキャナの構築
第7章　 ステップ5:文法定義
第8章　 ステップ6:パーサの構築
第9章　 ステップ7:パーサの構築（変数と関数）
第10章　ステップ8:パーサの構築（式と代入文）
第11章　ステップ9:パーサの構築（選択文と繰り返し文）
第12章　ステップ10:シンボルテーブル
第13章　ステップ11:コードジェネレータ
第14章　ステップ12:コードジェネレータ（変数と関数）
第15章　ステップ13:コードジェネレータ（式と代入文）
第16章　ステップ14:コードジェネレータ（選択文）
第17章　ステップ15:コードジェネレータ（繰り返し文）
第18章　ステップ18:ポストモーテム（事後検証）

作成するコンパイラの構造

入力プログラム->スキャナ->パーサ->コードジェネレータ->出力結果

・フロントエンド（字句解析、構文解析など）　　・・・スキャナ、パーサ
・バックエンド（コード生成部、および最適化部）・・・コードジェネレータ

スキャナ作成　成果

・fibonacci

MODULE Fibonacci;
VAR
    n,fib1,fib2 : INTEGER;
    count,temp  : INTEGER;
    
BEGIN
    WriteStr("Which fibonacci number do you wish to find?");
    ReadInt(n);
    WriteStr("The fibonacci number is ");
    IF n <= 0 
    THEN
        WriteInt(0)
    ELSE
        IF n=1 
        THEN
            WriteInt(1)
        ELSE
            fib1:=0;
            fib2:=1;
            WHILE count < n 
            DO
                temp := fib1+fib2;
                fib1 := fib2;
                fib2 := temp;
                count := count+1
            END;
            WriteInt(fib2)
        END
    END;
    WriteStr("\")
END Fibonacci.

・取得したトークンをコンソールに出力

・GetTokenメソッド

           /*************************
            *  GetToken
            *************************/
             public Token GetToken()
            {
                /* 初期化 */
                token.str = "";
                token.def = "EOF";
                token.type = "EOF";

                /* スペース飛ばす */
                c = GetCharacter();
                while (isWhiteSpace(c))
                {
                    c = GetCharacter();
                }

                /* ■ 識別子 */
                if (isAlpha(c))
                {
                    while (isAlpha(c) || isDigit(c))
                    {
                        token.str = token.str + (char)c;
                        c = GetCharacter();
                    }
                    UngetCharacter(c);/* 1文字戻す */

                    if (token.str.Equals("MODULE"))       { token.def = token.str; return token; }
                    else if (token.str.Equals("BEGIN"))   { token.def = token.str; return token; }
                    else if (token.str.Equals("END"))     { token.def = token.str; return token; }
                    else if (token.str.Equals("VAR"))     { token.def = token.str; return token; }
                    else if (token.str.Equals("INTEGER")) { token.def = token.str; return token; }
                    else if (token.str.Equals("STRING"))  { token.def = token.str; return token; }
                    else if (token.str.Equals("IF"))      { token.def = token.str; return token; }
                    else if (token.str.Equals("THEN"))    { token.def = token.str; return token; }
                    else if (token.str.Equals("ELSE"))    { token.def = token.str; return token; }
                    else if (token.str.Equals("WHILE"))   { token.def = token.str; return token; }
                    else if (token.str.Equals("DO"))      { token.def = token.str; return token; }
                    else                                  { token.def = "IDENT";   return token; }
                }

                /* ■ 数値 */
                else if (isDigit(c))
                {
                    while (isDigit(c))
                    {
                        token.str = token.str + (char)c;
                        c = GetCharacter();
                    }
                    UngetCharacter(c);/* 1文字戻す */

                    token.def = "NUMBER";
                    return token;
                }
                /* ■ 文字列 */
                else if (c == '"')
                {
                    c = GetCharacter();/* ["]を飛ばす */

                    while (c != '"')
                    {
                        token.str = token.str + (char)c;
                        c = GetCharacter();
                    }

                    token.def = "STR";
                    return token;
                }
                /* ■ 演算子 */
                /* 演算子<, <=, <> */
                else if (c == '<')
                {
                    token.str = token.str + (char)c;
                    c = GetCharacter();

                    if (c == '='
                    {
                        token.str = token.str + (char)c;
                    }
                    else if (c == '>')
                    {
                        token.str = token.str + (char)c;
                    }
                    else
                    {
                        ;/* Do Nothing */
                    }

                    if (token.str.Equals("<"))       { token.def = "LT"; return token; }
                    else if (token.str.Equals("<=")) { token.def = "LE"; return token; }
                    else if (token.str.Equals("<>")) { token.def = "NE"; return token; }
                }
                /* 演算子>, >= */
                else if (c == '>')
                {
                    token.str = token.str + (char)c;
                    c = GetCharacter();

                    /* >= */
                    if (c == '=')
                    {
                        token.str = token.str + (char)c;
                    }
                    else
                    {
                        ;/* Do Nothing */
                    }

                    if (token.str.Equals(">"))       { token.def = "GT"; return token; }
                    else if (token.str.Equals(">=")) { token.def = "GE"; return token; }
                }
                /* 演算子:, := */
                else if (c == ':')
                {
                    token.str = token.str + (char)c;
                    c = GetCharacter();

                    /* := */
                    if (c == '=')
                    {
                        token.str = token.str + (char)c;
                    }
                    else
                    {
                        ;/* Do Nothing */
                    }

                    if (token.str.Equals(":"))       { token.def = "COLON";  return token; }
                    else if (token.str.Equals(":=")) { token.def = "ASSIGN"; return token; }
                }
                /* 演算子= */
                else if (c == '=')
                {
                    token.str = token.str + (char)c;
                    token.def = "EQ";
                    return token;
                }
                /* 演算子+ */
                else if (c == '+')
                {
                    token.str = token.str + (char)c;
                    token.def = "PLUS";
                    return token;
                }
                /* 演算子- */
                else if (c == '-')
                {
                    token.str = token.str + (char)c;
                    token.def = "MINUS";
                    return token;
                }
                /* 演算子* */
                else if (c == '*')
                {
                    token.str = token.str + (char)c;
                    token.def = "MULT";
                    return token;
                }
                /* 演算子/ */
                else if (c == '/')
                {
                    token.str = token.str + (char)c;
                    token.def = "DIV";
                    return token;
                }
                /* 演算子; */
                else if (c == ';')
                {
                    token.str = token.str + (char)c;
                    token.def = "SEMICOLON";
                    return token;
                }
                /* 演算子, */
                else if (c == ',')
                {
                    token.str = token.str + (char)c;
                    token.def = "COMMA";
                    return token;
                }
                /* 演算子( */
                else if (c == '(')
                {
                    token.str = token.str + (char)c;
                    token.def = "OPEN";
                    return token;
                }
                /* 演算子) */
                else if (c == ')')
                {
                    token.str = token.str + (char)c;
                    token.def = "CLOSE";
                    return token;
                }
                /* 演算子. */
                else if (c == '.')
                {
                    token.str = token.str + (char)c;
                    token.def = "PERIOD";
                    return token;
                }
                /* EOF */
                else if (isEOF(c))
                {
                    token.str = token.str + "EOF";
                    token.def = "EOF";
                    return token;
                }
                else
                {
                    ;/* Do Nothing */
                }

                return token;
            }

パーサの実装が楽しみです。