Teeny Tinyコンパイラーを作ろう、その1

[5/5/2020]

外はとてもいい天気なので、コンパイラーを作ってみよう。コンパイラの仕組みについての知識は必要ありません。Pythonを使って独自のプログラミング言語Teeny Tinyを実装し、Cコードにコンパイルする。約500行のコードで、コンパイラをカスタマイズして拡張し、10億ドル規模の量産可能な独自のコンパイラにするために必要な初期インフラを提供する。

このチュートリアルは、動作するコンパイラーを構築するためのステップ・バイ・ステップの一連の投稿である。すべてのソースコードはGitHubのrepoにあります。すべての投稿をフォローしても、数時間しかかからないと思います。

私たちが実装しようとしているTeeny Tiny言語は、BASICの方言です。構文はきれいでシンプルです。もしCのような構文がお好みなら、最後にコンパイラを修正するのは簡単です。以下はTeeny Tiny言語でのプログラム例です：

PRINT "How many fibonacci numbers do you want?"
INPUT nums

LET a = 0
LET b = 1
WHILE nums > 0 REPEAT
    PRINT a
    LET c = a + b
    LET a = b
    LET b = c
    LET nums = nums - 1
ENDWHILE

このプログラムはユーザーの入力に基づいてフィボナッチ数列の項を出力する： 0 1 1 2 3 5 8 13…

この言語では、プログラミング言語に期待されるさまざまな基本操作ができる。特に、以下のようなものをサポートする：

数値変数
基本的な算術演算
If文
Whileループ
テキストと数値の印刷
数値の入力
ラベルとgoto
コメント

これは標準的な機能のサブセットだが、関数や配列、ファイルからの読み書き、else文さえないことにお気づきだろうか。しかし、この小さな構成要素セットだけで、実際には多くのことができる。また、コンパイラのセットアップも簡単なので、他の多くの機能を後から追加することも容易である。

コンパイラの概要

私たちのコンパイラーは、上に示した3つのステップを踏む。まず、入力されたソースコードが与えられると、そのコードをトークンに分割する。これは英語の単語や句読点のようなものだ。第2に、トークンを解析して、私たちの言語で許容される順序にあることを確認する。ちょうど英語の文章が動詞と名詞の特定の構造に従っているように。第三に、私たちの言語が翻訳するCコードを生成する。

この3つのステップをコードの主要な構成として使用する。LEXER, PARSER, EMITTERはそれぞれ独自のPythonコードファイルを持っています。このチュートリアルはこれらのステップに基づいて3つの部分に分かれています。もしこのコンパイラを拡張するのであれば、さらにいくつかのステップを追加することになるでしょうが、それについては触れないでおきます。

Lexerの概要

コンパイラの最初のモジュールはlexerと呼ばれる。Teeny Tinyコードの文字列が与えられると、レキサーは1文字ずつ繰り返し処理を行い、2つのことを行います。もしレキサーがこれを実行できなければ、無効なトークンであるとしてエラーを報告します。

図は lexer の入力と出力の例を示している。Teeny Tinyのコードが与えられたら、レキサーはトークンがどこにあるか、タイプ（キーワードなど）とともに判断しなければならない。スペースはトークンとして認識されないことがわかりますが、レキサーはトークンの終わりを知る一つの方法としてスペースを使います。

いよいよコードに入りましょう。まず、lex.py ファイルの lexer の構造から始めます：

``` {.prettyprint .lang-python} class Lexer: def init(self, source): pass

# 次の文字を処理する。
def nextChar(self):
    pass

# 先読み文字を返す。
def peek(self):
    pass

# 無効なトークンが見つかりましたので、エラーメッセージを表示して終了します。
def abort(self, message):
    pass
    
# 改行以外の空白文字はスキップする（これは文の終わりを示すのに使う）。
def skipWhitespace(self):
    pass
    
# コード内のコメントをスキップする。
def skipComment(self):
    pass

# 次のトークンを返す。
def getToken(self):
    pass ```

私は、必要と思われる関数をすべてスケッチし、それから戻って埋めていくのが好きだ。関数getTokenはlexerの核となるものだ。この関数は、コンパイラが次のトークンの準備をするたびに呼び出され、トークンの分類を行います。nextCharとpeekは、次の文字を探すためのヘルパー関数です。 skipWhitespaceは、私たちが気にしないスペースとタブを消費します。abortは、無効なトークンを報告するために使用します。

lexerは、入力文字列の現在の位置とその位置の文字を追跡する必要があります。これらはコンストラクタで初期化します：

``` {.prettyprint .lang-python} def init(self, source): self.source = source + ‘\n’ # ソースコードを文字列としてlexする。最後のトークン/ステートメントのレキシング/解析を簡略化するために、改行を追加してください。 self.curChar = ‘’ # 文字列内の現在の文字。 self.curPos = -1 # 文字列内の現在位置。 self.nextChar()

レキサーは入力コードを必要とするので、それに改行を追加する（これは後のチェックを簡略化するためである）。**curChar**は、レキサがトークンの種類を決定するために常にチェックするものである。なぜ *source[curPos]* としないのですか？それは、境界チェックでコードが散らかるからだ。その代わりに、**nextChar**でこれを行う：

``` {.prettyprint .lang-python}
    # 次の文字を処理する。
    def nextChar(self):
        self.curPos += 1
        if self.curPos >= len(self.source):
            self.curChar = '\0'  # EOF
        else:
            self.curChar = self.source[self.curPos]

これはレキサーの現在位置をインクリメントし、現在の文字を更新する。入力の最後に達した場合は、その文字をファイル終了マーカーに設定します。curPosとcurCharを変更するのはここだけです。しかし、curPosを更新せずに、次の文字を先読みしたいこともあります：

``` {.prettyprint .lang-python} # 先読み文字を返す。 def peek(self): if self.curPos + 1 >= len(self.source): return ‘\0’ return self.source[self.curPos+1]

これらの関数が動作することを確認しましょう。新しいファイル **teenytiny.py** を作ってテストしてみましょう：

``` {.prettyprint .lang-python}
from lex import *

def main():
    source = "LET foobar = 123"
    lexer = Lexer(source)

    while lexer.peek() != '\0':
        print(lexer.curChar)
        lexer.nextChar()

main()

これを実行すると、入力文字列、LET foobar = 123の各文字が改行されて出力されるはずである：

L
E 
T 

f 
o 
o 
b 
a 
r 

= 

1 
2 
3

トークンの分類

しかし、私たちが欲しいのは単なる文字ではなく、トークンである！個々の文字をどのように組み合わせてトークンを作るかを計画する必要がある。以下は、Teeny Tiny言語の主なレキサーのルールです：

演算子。1 つまたは 2 つの連続した文字がマッチします： + - * / = == != > < >= <=
文字列。ダブルクォーテーションの後に0個以上の文字とダブルクォーテーションが続くもの。次のようなものです： "hello,world!˶”、”˶”など。
数字。1つまたは複数の数値文字の後にオプションの小数点と1つまたは複数の数値文字が続きます。例えば 15 および 3.14
識別子。アルファベット文字の後に0文字以上の英数字が続く。
キーワード。完全に一致するテキスト： label、goto、print、input、let、if、then、endif、while、repeat、endwhile。

次に、Lexer クラスで getToken 関数を開始します：

``` {.prettyprint .lang-python} # Return the next token. def getToken(self): # このトークンの最初の文字をチェックして、それが何であるかを判断する。 # もしそれが複数文字の演算子（例：!=）、数字、識別子、キーワードであれば、残りを処理する。 if self.curChar == ‘+’: pass # Plus token. elif self.curChar == ‘-‘: pass # Minus token. elif self.curChar == ‘*’: pass # Asterisk token. elif self.curChar == ‘/’: pass # Slash token. elif self.curChar == ‘\n’: pass # Newline token. elif self.curChar == ‘\0’: pass # EOF token. else: # Unknown token! pass

    self.nextChar() ```

これはいくつかの可能性のあるトークンを検出するが、まだ役に立つことは何もしない。次に必要なのは、トークンの種類とコードの正確なテキストを追跡するための Token クラスです。これをとりあえず lex.py に置きます：

``` {.prettyprint .lang-python}

Token contains the original text and the type of token.

class Token:
def init(self, tokenText, tokenKind): self.text = tokenText # The token’s actual text. Used for identifiers, strings, and numbers. self.kind = tokenKind # The TokenType that this token is classified as.

トークンのタイプを指定するために、enumとして**TokenType**クラスを作成します。長く見えますが、これは言語が許容する全てのトークンを指定します。*import enum* を **lex.py** の先頭に追加し、このクラスを追加します：

``` {.prettyprint .lang-python}
# TokenType は、トークンのすべてのタイプを表す列挙型です。
class TokenType(enum.Enum):
    EOF = -1
    NEWLINE = 0
    NUMBER = 1
    IDENT = 2
    STRING = 3
    # Keywords.
    LABEL = 101
    GOTO = 102
    PRINT = 103
    INPUT = 104
    LET = 105
    IF = 106
    THEN = 107
    ENDIF = 108
    WHILE = 109
    REPEAT = 110
    ENDWHILE = 111
    # Operators.
    EQ = 201  
    PLUS = 202
    MINUS = 203
    ASTERISK = 204
    SLASH = 205
    EQEQ = 206
    NOTEQ = 207
    LT = 208
    LTEQ = 209
    GT = 210
    GTEQ = 211

これで、getTokenを拡張して、特定のトークンを検出したときに実際に何かを実行できるようになりました：

``` {.prettyprint .lang-python} # 次のトークンを返す。 def getToken(self): token = None

    # このトークンの最初の文字をチェックして、それが何であるかを判断する。
    # もしそれが複数文字の演算子（例：!=）、数字、識別子、キーワードであれば、残りを処理する。
    if self.curChar == '+':
        token = Token(self.curChar, TokenType.PLUS)
    elif self.curChar == '-':
        token = Token(self.curChar, TokenType.MINUS)
    elif self.curChar == '*':
        token = Token(self.curChar, TokenType.ASTERISK)
    elif self.curChar == '/':
        token = Token(self.curChar, TokenType.SLASH)
    elif self.curChar == '\n':
        token = Token(self.curChar, TokenType.NEWLINE)
    elif self.curChar == '\0':
        token = Token('', TokenType.EOF)
    else:
        # Unknown token!
        pass
        
    self.nextChar()
    return token ```

このコードでは、基本的な算術演算子と改行、ファイル終了マーカーを検出するようにレキサーをセットアップしている。else節は、許可されないものをすべて検出するためのものである。

では、mainを変更して、今のところうまくいっているかどうかを見てみよう：

``` {.prettyprint .lang-python} def main(): source = “+- */” lexer = Lexer(source)

token = lexer.getToken()
while token.kind != TokenType.EOF:
    print(token.kind)
    token = lexer.getToken() ```

これを実行すると、次のように表示されるはずだ：

TokenType.PLUS
TokenType.MINUS
Traceback (most recent call last):
  File "e:/projects/teenytiny/part1/teenytiny.py", line 12, in 
    main()
  File "e:/projects/teenytiny/part1/teenytiny.py", line 8, in main
    while token.kind != TokenType.EOF:
AttributeError: 'NoneType' object has no attribute 'kind'

ウホッ！何かが間違っていた。getTokenがNoneを返す唯一の方法は、elseブランチが取られた場合だ。もう少しうまく処理しよう。 import sysをlex.pyの先頭に追加し、abort関数を次のように定義します：

``` {.prettyprint .lang-python} # Invalid token found, print error message and exit. def abort(self, message): sys.exit(“Lexing error. “ + message)

そして、**getToken**の*else*を次のように置き換える：

``` {.prettyprint .lang-python}
        else:
            # Unknown token!
            self.abort("Unknown token: " + self.curChar)

もう一度プログラムを実行する

TokenType.PLUS
TokenType.MINUS
Lexing error. Unknown token:

まだ問題はあるが、これで少しは理解できるようになった。最初の2つのトークンの後、何かがおかしくなったようだ。未知のトークンは見えない。入力文字列を振り返ってみると、空白を処理していないことに気づくかもしれない！skipWhitespace関数を実装する必要があります：

``` {.prettyprint .lang-python} # 改行以外の空白文字はスキップする。 def skipWhitespace(self): while self.curChar == ‘ ‘ or self.curChar == ‘\t’ or self.curChar == ‘\r’: self.nextChar()

ここで、**getToken**の最初の行に*self.skipWhitespace()*を記述する。プログラムを実行すると、出力が表示されます：

``` prettyprint
TokenType.PLUS
TokenType.MINUS
TokenType.ASTERISK
TokenType.SLASH
TokenType.NEWLINE

進展！

この時点で、== や >= のような2つの文字で構成される演算子のレキシングに移ることができる。これらの演算子はすべて同じ方法で字句解析される。最初の文字をチェックし、次に2番目の文字を見て、それが何であるかを確認してから、どうするかを決定する。getTokenの SLASH トークンの elif の後にこれを追加する：

``` {.prettyprint .lang-python} elif self.curChar == ‘=’: # このトークンが = か == かをチェックする if self.peek() == ‘=’: lastChar = self.curChar self.nextChar() token = Token(lastChar + self.curChar, TokenType.EQEQ) else: token = Token(self.curChar, TokenType.EQ)

**peek**関数を使えば、*curChar*を破棄することなく、次の文字が何であるかを調べることができる。以下は、同じように動作する残りの演算子のコードである：

``` {.prettyprint .lang-python}
        elif self.curChar == '>':
            # このトークンが > か >= かをチェックする。
            if self.peek() == '=':
                lastChar = self.curChar
                self.nextChar()
                token = Token(lastChar + self.curChar, TokenType.GTEQ)
            else:
                token = Token(self.curChar, TokenType.GT)
        elif self.curChar == '<':
                # このトークンが < か <= かをチェックする。
                if self.peek() == '=':
                    lastChar = self.curChar
                    self.nextChar()
                    token = Token(lastChar + self.curChar, TokenType.LTEQ)
                else:
                    token = Token(self.curChar, TokenType.LT)
        elif self.curChar == '!':
            if self.peek() == '=':
                lastChar = self.curChar
                self.nextChar()
                token = Token(lastChar + self.curChar, TokenType.NOTEQ)
            else:
                self.abort("Expected !=, got !" + self.peek())

唯一少し違うのは、!=という演算子である。これは、!文字が単独では無効であるため、=を続けなければならないからである。他の文字は単独でも有効ですが、レキサーは貪欲なので、可能であれば複数文字演算子の1つとして受け入れます。

これらの演算子をテストするには、入力を"+- */ >>= = !="に更新すればよい：

TokenType.PLUS
TokenType.MINUS
TokenType.ASTERISK
TokenType.SLASH
TokenType.GT
TokenType.GTEQ
TokenType.EQ
TokenType.NOTEQ
TokenType.NEWLINE

これでプログラムは、言語の演算子をすべて受け入れることができる。では、何が残っているのだろうか？コメント、文字列、数値、識別子、キーワードのサポートを追加する必要がある。ひとつひとつ確認しながらテストしていこう。

# 文字はコメントの開始を示す。レキサーがこれを見るたびに、改行があるまで、それ以降のテキストをすべて無視することがわかる。コメントはトークンではないが、レキサーはこのテキストをすべて捨てて、次に気になるものを見つけられるようにする。また、コメント末尾の改行を捨てないことも重要です。改行はそれ自体がトークンであり、まだ必要な場合があるからです。skipCommentに埋めてください：

``` {.prettyprint .lang-python} # コード内のコメントをスキップする。 def skipComment(self): if self.curChar == ‘#’: while self.curChar != ‘\n’: self.nextChar()

簡単だ！さて、この関数を**nextToken**から呼び出すと、関数の最初の数行は次のようになる：

``` {.prettyprint .lang-python}
    # 次のトークンを返す。
    def getToken(self):
        self.skipWhitespace()
        self.skipComment()
        token = None
    ...

試しに"+- # This is a comment!\n */\”と入力すると次のような結果を見るでしょう。

TokenType.PLUS
TokenType.MINUS
TokenType.NEWLINE
TokenType.ASTERISK
TokenType.SLASH
TokenType.NEWLINE

このコメントは完全に無視されていることに注意してほしい！

この言語では、ダブルクォーテーションで始まり、もう1つのクォーテーションまで続く文字列を印刷することができます。後でCにコンパイルしやすくするために、いくつかの特殊文字は許さないことにする。getTokenの大きなelse if文のブロックに次のコードを追加する：

``` {.prettyprint .lang-python} elif self.curChar == ‘"’: # クォーテーションの間の文字列を取得する。 self.nextChar() startPos = self.curPos

        while self.curChar != '\"':
            # 文字列中の特殊文字を許可しない。エスケープ文字、改行、タブ、%は禁止。
            # この文字列にはC言語のprintfを使用します。
            if self.curChar == '\r' or self.curChar == '\n' or self.curChar == '\t' or self.curChar == '\\' or self.curChar == '%':
                self.abort("Illegal character in string.")
            self.nextChar()

        tokText = self.source[startPos : self.curPos] # 部分文字列を取得する。
        token = Token(tokText, TokenType.STRING) ```

このコードは単なるwhileループで、2つ目のクォーテーション・マークまで続く。無効な文字が見つかった場合は、エラーメッセージとともに中断されます。これまで取り上げた他のトークンとは何かが違います。トークンのテキストを文字列の内容（引用符を除く）に設定します。

入力を再度"+- \"This is a string\" # This is a comment!\n */"で更新し、プログラムを実行する：

TokenType.PLUS
TokenType.MINUS
TokenType.STRING
TokenType.NEWLINE
TokenType.ASTERISK
TokenType.SLASH
TokenType.NEWLINE

数字に話を移そう。私たちの言語では、数字を1桁以上の数字（0～9）と定義し、その後に小数点以下の数字を1桁以上続けなければならない。つまり、48と3.14は許されるが、.9と1.は許されない。再びpeek関数を使用して、1文字先を調べます。文字列トークンと同様に、トークンのテキストを実際の数値に設定できるように、数値の始点と終点を記録しておきます。

``` {.prettyprint .lang-python} elif self.curChar.isdigit(): # 先頭の文字は数字なので、これは数字でなければならない。 # 連続するすべての桁と、小数部がある場合は小数部を取得する。 startPos = self.curPos while self.peek().isdigit(): self.nextChar() if self.peek() == ‘.’: # Decimal! self.nextChar()

            # 小数の後に少なくとも1桁の数字がなければならない。
            if not self.peek().isdigit(): 
                # エラー！
                self.abort("Illegal character in number.")
            while self.peek().isdigit():
                self.nextChar()

        tokText = self.source[startPos : self.curPos + 1] # 部分文字列を取得する。
        token = Token(tokText, TokenType.NUMBER) ```

入力"+-123 9.8654*/"でテストしてみてください：

TokenType.PLUS
TokenType.MINUS
TokenType.NUMBER
TokenType.NUMBER
TokenType.ASTERISK
TokenType.SLASH
TokenType.NEWLINE

これでレキサーはほぼ完成だ！

最後の大きな仕事は、識別子とキーワードを扱うことだ。識別子のルールは、アルファベットで始まり、0文字以上の英数字が続くものです。しかし、それをTokenType.IDENTと呼ぶ前に、それがキーワードの1つでないことを確認する必要がある。 getTokenにこれを追加します：

``` {.prettyprint .lang-python} elif self.curChar.isalpha(): # 先頭の文字は文字なので、識別子かキーワードでなければならない。 # 連続するすべての英数字を取得する。 startPos = self.curPos while self.peek().isalnum(): self.nextChar()

        # トークンがキーワードのリストにあるかどうかをチェックする。
        tokText = self.source[startPos : self.curPos + 1] # 部分文字列を取得する。
        keyword = Token.checkIfKeyword(tokText)
        if keyword == None: # 識別子
            token = Token(tokText, TokenType.IDENT)
        else:   # キーワード
            token = Token(tokText, keyword) ```

他のトークンとほとんど同じです。しかし、TokenクラスでcheckIfKeywordを定義する必要がある：

``` {.prettyprint .lang-python} @staticmethod def checkIfKeyword(tokenText): for kind in TokenType: # すべてのキーワード enum 値が 1XX であることに依存する。 if kind.name == tokenText and kind.value >= 100 and kind.value < 200: return kind return None

これは、トークンがキーワードのリストにあるかどうかをチェックするだけである。キーワードは、enum値として101-199を持つように任意に設定した。

さて、入力文字列 *\"IF+-123 foo\*THEN/\"* で識別子とキーワードをテストする。

``` prettyprint
TokenType.IF
TokenType.PLUS
TokenType.MINUS
TokenType.NUMBER
TokenType.IDENT
TokenType.ASTERISK
TokenType.THEN
TokenType.SLASH
TokenType.NEWLINE

そしてターミナルからの出力はどのように見えるか：

これだ。私たちのレキサーは、言語が必要とするすべてのトークンを正しく識別できる！これでコンパイラの最初のモジュールが完成した。

もしこれが圧倒的だと思ったとしても、まだあきらめないでほしい！レキサーはコンパイラの中で最も退屈で、最も面白くない部分だと思う。次はコードを解析する。つまり、トークンが意味のある順序で並んでいることを確認し、そしてコードを出力する。

ここまでのソースコードは、Github repoにある。

このチュートリアルのパート2に進んでください。他のお勧めの本

-レキシカル解析 (Wikipedia)

Goでインタプリタを書く (Amazon)
インタプリタを作る (Amazon, web)

Teeny Tinyコンパイラーを作ろう、その2

[6/5/2020]

外は雨模様なので、Teeny Tinyコンパイラの開発を続けよう。まだの人はpart1を読んでください。ソースコードはGitHubのrepoにあります。チュートリアルのこの部分には少し前置きが必要ですが、コンパイラの完成まであと少しです！

要約すると、私たちは独自のプログラミング言語Teeny Tiny用のコンパイラを作っています。(1)lexing: 入力コードをトークンと呼ばれる小片に分割する、(2)parsing: トークンが私たちの言語が許容する順序にあることを検証する、(3)emitting: 適切なCコードを生成する。レキサーについてはその1で説明したので、ここではパーサーに焦点を当てる。

パーサーの概要

パーサーは、コードが正しい構文に従っていることを確認するコンポーネントです。これは、トークンを1つずつ見て、言語が定義している順序が正しいかどうかを判断します。

上の図は、パーサーが行うことを少し単純化した例である。パーサーへの入力はトークンの列で、出力はパース・ツリーです。パース・ツリーとは、単なるテキスト文字列やトークンの並びよりも、コードをより構造的に表現したものです。このツリーを作成するプロセスについては、この記事の残りの部分で説明する。ツリーは時に怖いものだが、このために複雑なデータ構造を構築することはない。むしろ、パーサーのコールスタックを利用して、暗黙のうちに解析ツリーを構築していきます。

コードの構造を検証したり、解析ツリーを構築したりする前に、Teeny Tinyがどのような構造を許可しているかを知っておく必要があります。

文法の概要

Teeny Tinyには文法が必要です。これは、Teeny Tinyで有効なすべてのコードを記述するための正式な方法です。構文エラーについてコンパイラに怒鳴られたことがあるとしたら、それはあなたのコードが言語の文法に従っていないからです。

これは英語を習ったときとあまり変わりません。英語の文とそれに対応する解析木の例を見てみよう：

パーサーはTeeny Tinyのコードと同じような処理を行う。

さて、ではどうやって言語の文法を作るのだろうか？これは部分的には創造的であり、部分的には技術的である。構文の多くは、何よりも文体的な選択である。ほとんどのプログラミング言語の正式な文法を調べることもできる。文法は通常、標準的な記法で書かれているが、記法の詳細は今はあまり重要ではない。パーサーを実装できればいいのだ。

以下はTeeny Tinyの文法の一部である：

program ::= {statement}

これは次のように読める：プログラムという文法規則があり、それは0個以上のステートメントで構成されている。ステートメントとは何か？別の文法規則である：

statement ::= "PRINT" (expression | string) nl

ここでのstatementルールは、PRINTキーワードの後に式または文字列を続け、改行することで定義される。expressionとnlは、参照している他の文法規則である。stringはレキサーのトークンの一種です。

statementルールを拡張して、複数のオプションを持たせることもできます：

statement ::= "PRINT" (expression | string) nl
    | "LET" ident "=" expression nl

つまり、PRINT文かLET文のどちらかである（パイプ記号の|はorを意味する）。LET文は変数に値を代入するための文です。LET文は変数に値を代入するための文であり、LETキーワードの後にidentと"="、そして式と改行で定義される。identはレキサのトークンの一種で、変数識別子である。expressionはもう一つの文法規則で、数式用である。

ルールは非常に一般的なものから始まり、より具体的になっていく傾向がある。先ほどの英語の解析ツリーの例と同じです。もうひとつ、文の種類を見てみましょう。

statement ::= "PRINT" (expression | string) nl
    | "LET" ident "=" expression nl
    | "IF" comparison "THEN" nl {statement} "ENDIF" nl

さて、この言語ではIF文も使用できる。このルールで重要なのは、再帰的であるということだ。ステートメントルールは、実際にはステートメント*ルールを参照する。これがプログラミング言語の力だ！

これがTeeny Tinyプログラミング言語の文法全体です：

program ::= {statement}
statement ::= "PRINT" (expression | string) nl
    | "IF" comparison "THEN" nl {statement} "ENDIF" nl
    | "WHILE" comparison "REPEAT" nl {statement} "ENDWHILE" nl
    | "LABEL" ident nl
    | "GOTO" ident nl
    | "LET" ident "=" expression nl
    | "INPUT" ident nl
comparison ::= expression (("==" | "!=" | ">" | ">=" | "<" | "<=") expression)+
expression ::= term {( "-" | "+" ) term}
term ::= unary {( "/" | "*" ) unary}
unary ::= ["+" | "-"] primary
primary ::= number | ident
nl ::= '\n'+

まだすべてを理解する必要はない。これから少しずつ理解していこう。パーサーを実装するとき、これらの文法ルールのそれぞれが、Pythonコードの中で独自の関数を持つようになるというマジックがあります。文法からコードへの一対一のマッピングです。

この記法についてもう少し知りたい方は… {}はゼロ以上、[]はゼロか1、+は左から1つ以上、()はグループ化、|は*論理和です。単語は他の文法規則への参照か、レキサーですでに定義したトークンへの参照です。キーワードと演算子は引用符で囲まれた文字列で表します。

この文法が与えられると、パーサーは次のような木を生成する：

ご想像の通り、小さなプログラムでも非常に大きな解析木を生成する。それでも構わない！我々はパーサーに大変な仕事をさせるのだ！(注：上の例では、ツリーを少し小さくするために改行ルールを省略しています)

さて、いよいよコードに入りましょう！

コードのセットアップ

もうすぐ存在するパーサを使うために main 関数をセットアップする必要があります。で teenytiny.py を更新します：

``` {.prettyprint .lang-python} from lex import * from parse import * import sys

def main(): print(“Teeny Tiny Compiler”)

if len(sys.argv) != 2:
    sys.exit("Error: Compiler needs source file as argument.")
with open(sys.argv[1], 'r') as inputFile:
    source = inputFile.read()

# レキサーとパーサーを初期化する。
lexer = Lexer(source)
parser = Parser(lexer)

parser.program() # パーサーを起動する。
print("Parsing completed.")

main()

コンパイラーは、コマンドライン引数としてファイル名を入力用にオープンすることを期待するようになる。パーサー・オブジェクトはレキサーを制御し、必要に応じて新しいトークンを要求する。次に、パーサオブジェクトを実装します。

**parse.py**を作成し、次のように始めます：

``` {.prettyprint .lang-python}
import sys
from lex import *

# パーサー・オブジェクトは現在のトークンを追跡し、コードが文法にマッチするかどうかをチェックする。
class Parser:
    def __init__(self, lexer):
        pass

    # 現在のトークンがマッチした場合にtrueを返す。
    def checkToken(self, kind):
        pass

    # 次のトークンがマッチすれば真を返す。
    def checkPeek(self, kind):
        pass

    # 現在のトークンにマッチするか試す。一致しない場合はエラー。現在のトークンを進めます。
    def match(self, kind):
        pass

    # 現在のトークンを進めます。
    def nextToken(self):
        pass

    def abort(self, message):
        sys.exit("Error. " + message)

前の記事で書いたように、私は必要と思われるメソッドをすべてスケッチしてから、それを埋めていくのが好きだ。

checkToken関数とcheckPeek関数は、現在のトークンと次のトークンのどちらを次に適用するかをパーサーに決定させます。これらの関数を Parser クラスに追加します：

``` {.prettyprint .lang-python} # 現在のトークンがマッチした場合にtrueを返す。 def checkToken(self, kind): return kind == self.curToken.kind

# 次のトークンがマッチした場合にtrueを返す。
def checkPeek(self, kind):
    return kind == self.peekToken.kind ```

パーサーが適用すべき文法規則をすでに知っている場合には、match関数を使用する。この関数は、現在のトークンが特定の何かであることを期待します。また、checkTokenが使用されている場合などには、nextTokenで次のトークンにスキップします。

``` {.prettyprint .lang-python} # 現在のトークンにマッチするか試す。一致しない場合はエラー。現在のトークンを進めます。 def match(self, kind): if not self.checkToken(kind): self.abort(“Expected “ + kind.name + “, got “ + self.curToken.kind.name) self.nextToken()

# 現在のトークンを進めます。
def nextToken(self):
    self.curToken = self.peekToken
    self.peekToken = self.lexer.getToken()
    # No need to worry about passing the EOF, lexer handles that. ```

パーサーも初期化する必要がある。以下は、__init__のコードである：

``` {.prettyprint .lang-python} def init(self, lexer): self.lexer = lexer

    self.curToken = None
    self.peekToken = None
    self.nextToken()
    self.nextToken()    # カレントとピークを初期化するために、これを2回コールする。 ```

すぐにすべてをテストする。

パーサーのコアとなる仕組みができたので、次は実際に言語を解析する必要がある。そのためには、文法をコードにマッピングする。文法の各ルールに対して、パーサーのマッチング関数があります。コードをツリー構造にしたかったことを覚えているだろうか？次に実装する構文解析関数のコール・グラフがそれを実現する。

###ステートメントの解析

これから文法を調べ、ルールごとに関数を実装していく。ルールが別のルールを参照するときは、その関数を呼び出す。ルールが特定のトークンを期待するときは match を呼び出し、複数のオプションがあるときは checkToken を呼び出します。PRINTのようなステートメントの解析から始めて、数学式の解析に進みます。

まず、program を実装しましょう。この関数はパーサーをキックオフし、文法の親ルールになります。それでは、文法の最初の行を参照してみましょう：

program ::= {statement}

この行は、プログラムが0個以上のステートメントで構成されていることを意味する。これをコードにマッピングするには、parserクラスの最後に次のコードを追加します：

``` {.prettyprint .lang-python} # プロダクション・ルール

# program ::= {statement}
def program(self):
    print("PROGRAM")

    # Pプログラム中のすべてのステートメントを調べる。
    while not self.checkToken(TokenType.EOF):
        self.statement() ```

文法にあるように、これは何もなくなるまでstatementを呼び続ける。翻訳がいかに簡単だったかわかるだろうか？パーサーが何をしているのかわかりやすくするために、各関数から印刷することにする。

文法の次のルールはstatementで、実際には7種類のルールがあります。この関数はパーサーの中で一番大きな関数ですが、1つ1つ分割していけば簡単です。この関数の内部には、7つの異なるステートメントそれぞれに対するif条件があります。以下は最初のタイプの文の文法です：

statement ::= "PRINT" (expression | string) nl

この文は、最初に “PRINT “トークンを期待する。次に、数学式か文字列トークンのどちらかが続く。最後に改行が必要です。このコードを parser クラスに追加します：

``` {.prettyprint .lang-python} # 以下の記述のうちひとつを… def statement(self): # 最初のトークンをチェックして、これがどのようなステートメントなのかを確認する。

    # "PRINT" (expression | string)
    if self.checkToken(TokenType.PRINT):
        print("STATEMENT-PRINT")
        self.nextToken()

        if self.checkToken(TokenType.STRING):
            # 単純な文字列。
            self.nextToken()
        else:
            # 式を期待する。
            self.expression()

    # 改行。
    self.nl() ```

テストしやすくするために、改行を処理するnl関数を実装します。これはすべての文に適用されるので、statement関数の最後に呼び出します。この関数は、少なくとも1つの改行文字を想定して動作しますが、それ以上の改行文字も許容します。この関数を parser クラスに追加します：

``` {.prettyprint .lang-python} # nl ::= ‘\n’+ def nl(self): print(“NEWLINE”)

    # 少なくとも1つの改行が必要。
    self.match(TokenType.NEWLINE)
    # しかし、もちろん余分な改行も許可する。
    while self.checkToken(TokenType.NEWLINE):
        self.nextToken() ```

テストの時間だ！hello.teenyというファイルを作成し、PRINT "hello, world!"という内容でコンパイラの入力とします。入力ファイルを引数として teenytiny.py を実行します：

うまくいった！1行のTeeny Tinyコードが正常に解析されました。複数のPRINT文で試してみましょう。入力コードを次のように更新してください：

PRINT "hello, world!"
PRINT "second line"
PRINT "and a third..."

プログラムを再実行してください。表示されるはずです：

Teeny Tiny Compiler
PROGRAM
STATEMENT-PRINT
NEWLINE
STATEMENT-PRINT
NEWLINE
STATEMENT-PRINT
NEWLINE
Parsing completed.

ファンタスティック！次のステイトメントのタイプに移ると、文法は次のようになる：

    | "IF" comparison "THEN" nl {statement} "ENDIF" nl

この行はorで始まるので、文法の前の行からの続きであることになり、次に"IF"トークンを期待する。次に、別の文法規則である比較を参照しますが、これは後で関数として定義します。これは foo > 5 のような条件を許容します。その後、この言語は"THEN"トークンの後に改行が続くことを期待します。その後、if文の本体が来ます、これは0個以上のステートメントが可能です。最後に、"ENDIF"トークンと改行で終わります。この elif を statement 関数の if に追加します：

``` {.prettyprint .lang-python} # “IF” comparison “THEN” {statement} “ENDIF” elif self.checkToken(TokenType.IF): print(“STATEMENT-IF”) self.nextToken() self.comparison()

        self.match(TokenType.THEN)
        self.nl()

        # 本文中に0個以上の記述がある。
        while not self.checkToken(TokenType.ENDIF):
            self.statement()

        self.match(TokenType.ENDIF) ```

self.nl()がまだstatement関数の最後にあることを確認してください。これはまだテストできないので、次の文法ルールに移る。whileループの文法ルールである。この文法は、先ほどのif文とほとんど同じです。

    | "WHILE" comparison "REPEAT" nl {statement nl} "ENDWHILE" nl

コードも似ている。これはまだstatement関数に追加している部分であることを忘れないでほしい：

``` {.prettyprint .lang-python} # “WHILE” comparison “REPEAT” {statement} “ENDWHILE” elif self.checkToken(TokenType.WHILE): print(“STATEMENT-WHILE”) self.nextToken() self.comparison()

        self.match(TokenType.REPEAT)
        self.nl()

        # ループ本体に0個以上のステートメント。
        while not self.checkToken(TokenType.ENDWHILE):
            self.statement()

        self.match(TokenType.ENDWHILE) ```

この時点でパターンがお分かりいただけただろう。残りのstatementの形もほとんど同じである：

    | "LABEL" ident nl
    | "GOTO" ident nl
    | "LET" ident "=" expression nl
    | "INPUT" ident nl

これは、statement関数の最後のコードである：

``` {.prettyprint .lang-python} # “LABEL”識別子 elif self.checkToken(TokenType.LABEL): print(“STATEMENT-LABEL”) self.nextToken() self.match(TokenType.IDENT)

    # "GOTO" 識別子
    elif self.checkToken(TokenType.GOTO):
        print("STATEMENT-GOTO")
        self.nextToken()
        self.match(TokenType.IDENT)

    # "LET" 識別子 "=" 式
    elif self.checkToken(TokenType.LET):
        print("STATEMENT-LET")
        self.nextToken()
        self.match(TokenType.IDENT)
        self.match(TokenType.EQ)
        self.expression()

    # "INPUT" 識別子
    elif self.checkToken(TokenType.INPUT):
        print("STATEMENT-INPUT")
        self.nextToken()
        self.match(TokenType.IDENT)

    # これは有効なステートメントではない エラーです！
    else:
        self.abort("Invalid statement at " + self.curToken.text + " (" + self.curToken.kind.name + ")")

    # 改行。
    self.nl() ```

最後のelseに注目してほしい。もしパーサーがステートメントを期待していても、私たちが定義した7つの型のどれにもマッチしなければ、エラーを投げるはずだ。

テストの時間だ。入力ファイルを次のように更新する：

LABEL loop
PRINT "hello, world!"
GOTO loop

これを実行すると、次のような出力が得られる：

Teeny Tiny Compiler
PROGRAM
STATEMENT-LABEL
NEWLINE
STATEMENT-PRINT
NEWLINE
STATEMENT-GOTO
NEWLINE
Parsing completed.

パーサーを壊してみることも必要だ。例えば、"JUMP GOTO"のように、我々が実装したどのステートメント・フォームでも解析されないような無意味な入力を試してみよう：

Teeny Tiny Compiler
PROGRAM
Error! Invalid statement at JUMP (IDENT)

先に進む前にひとつだけ。program 関数は現在、入力の先頭の改行を扱えないが、それを修正するのは簡単だ：

``` {.prettyprint .lang-python} # program ::= {statement} def program(self): print(“PROGRAM”)

    # この文法では改行が必要なので、余分な改行は省略する必要がある。
    while self.checkToken(TokenType.NEWLINE):
        self.nextToken()

    # プログラム中のすべてのステートメントを解析する。
    while not self.checkToken(TokenType.EOF):
        self.statement() ```

式の解析

パーサーは本当に完成しつつある！現在、言語の約半分を実装しています。まだ式が足りない。式とは、1+5*3 のような数学式や、foo>=10 のようなブーリアン式のように、評価されて値になるものである。式に関連する文法は以下の通りである：

comparison ::= expression (("==" | "!=" | ">" | ">=" | "<" | "<=") expression)+
expression ::= term {( "-" | "+" ) term}
term ::= unary {( "/" | "*" ) unary}
unary ::= ["+" | "-"] primary
primary ::= number | ident

この部分の文法は、読者には奇妙に、あるいは複雑に見えるかもしれない。なぜこの5つのルールに分けるのか？なぜこうしないのか？expression ::= primary {operator primary}のようなものではだめなのでしょうか？答えは優先順位である。

優先順位のレベルを変えるには、文法規則を順番に整理する。より高い優先順位を持つ演算子は、構文解析ツリーの下位に位置するように、文法内で “下位 “に配置する必要がある。構文木のトークンに最も近い（つまり、木の葉に最も近い）演算子が、最も高い優先順位を持つことになります。もうひとつの考え方は、演算子とオペランドの結合の厳密さです。構文解析の際、あるレベルに演算子がない場合、次のレベルに進み、ツリー内に1つだけ子を持つノードを作成します。

こうすることで、数式に期待される演算の順序が強制されます。1+2*3は9ではなく7と評価される。文法規則を見ると、単項演算子の+と-は文法では "下位演算子"なので、二項演算子の+と-より優先順位が高い* と/より優先順位が高くなります。上の解析木はこれを示しています。乗算演算子は常にプラス演算子よりもツリー内で下位になります。単項の否定演算子はさらに下位になります。同じ優先順位の演算子が複数ある場合は、左から右に処理されます。このパターンに従うことで、より多くの優先順位レベル（および演算子）を追加することができる。

comparisonルールは少し違う。比較演算子（例えば、!=）を数式で使用することはできない。そこで、それらが許される場所（つまり、IF文やWHILEループ）をコントロールするために、少なくとも1つの比較演算子を必要とする特別なルールを設けている。比較演算子の左辺と右辺はexpressionである。今、数式だけを許容する場所ではexpressionを、ブーリアン式を許容する場所ではcomparisonを想定しています。comparisonのコードは次のとおりである：

``` {.prettyprint .lang-python} # comparison ::= expression ((“==” | “!=” | “>” | “>=” | “<” | “<=”) expression)+ def comparison(self): print(“COMPARISON”)

    self.expression()
    # 少なくとも1つの比較演算子と別の式でなければならない。
    if self.isComparisonOperator():
        self.nextToken()
        self.expression()
    else:
        self.abort("Expected comparison operator at: " + self.curToken.text)

    # 0個以上の比較演算子および式を持つことができる。
    while self.isComparisonOperator():
        self.nextToken()
        self.expression() ```

コードを読みやすくするために、isComparisonOperatorを作った：

``` {.prettyprint .lang-python} # 現在のトークンが比較演算子であれば真を返します。 def isComparisonOperator(self): return self.checkToken(TokenType.GT) or self.checkToken(TokenType.GTEQ) or self.checkToken(TokenType.LT) or self.checkToken(TokenType.LTEQ) or self.checkToken(TokenType.EQEQ) or self.checkToken(TokenType.NOTEQ)

このコードでは数式を表す：

``` {.prettyprint .lang-python}
    # expression ::= term {( "-" | "+" ) term}
    def expression(self):
        print("EXPRESSION")

        self.term()
        # 0以上の+/-と式を持つことができる。
        while self.checkToken(TokenType.PLUS) or self.checkToken(TokenType.MINUS):
            self.nextToken()
            self.term()

termとunaryを表すコード：

``` {.prettyprint .lang-python} # term ::= unary {( “/” | “*” ) unary} def term(self): print(“TERM”)

    self.unary()
    # 0以上の*//と式を持つことができる。
    while self.checkToken(TokenType.ASTERISK) or self.checkToken(TokenType.SLASH):
        self.nextToken()
        self.unary()


# unary ::= ["+" | "-"] primary
def unary(self):
    print("UNARY")

    # オプションの単項 +/-
    if self.checkToken(TokenType.PLUS) or self.checkToken(TokenType.MINUS):
        self.nextToken()        
    self.primary() ```

最後に、文法の最後の部分である。primaryは数字トークンかidentトークンで、これは変数名である。コードは

``` {.prettyprint .lang-python} # primary ::= number | ident def primary(self): print(“PRIMARY (“ + self.curToken.text + “)”)

    if self.checkToken(TokenType.NUMBER): 
        self.nextToken()
    elif self.checkToken(TokenType.IDENT):
        self.nextToken()
    else:
        # Error!
        self.abort("Unexpected token at " + self.curToken.text) ```

式をテストする準備はできただろうか？入力ファイルにLET foo = bar * 3 + 2と入れて実行してください：

Teeny Tiny Compiler
PROGRAM
STATEMENT-LET
EXPRESSION
TERM
UNARY
PRIMARY (bar)
UNARY
PRIMARY (3)
TERM
UNARY
PRIMARY (2)
NEWLINE
Parsing completed.

さあ、やってみよう：

LET foo = bar * 3 + 2
IF foo > 0 THEN
    PRINT "yes!"
ENDIF

かなり長い出力になるはずだ：

Teeny Tiny Compiler
PROGRAM
STATEMENT-LET
EXPRESSION
TERM
UNARY
PRIMARY (bar)
UNARY
PRIMARY (3)
TERM
UNARY
PRIMARY (2)
NEWLINE
STATEMENT-IF
COMPARISON
EXPRESSION
TERM
UNARY
PRIMARY (foo)
EXPRESSION
TERM
UNARY
PRIMARY (0)
NEWLINE
STATEMENT-PRINT
NEWLINE
NEWLINE
Parsing completed.

パーサーは入れ子のループやif文も許す。試してみてください。

LET foo = bar * 3 + 2
IF foo > 0 THEN
    IF 10 * 10 < 100 THEN
        PRINT bar
    ENDIF
ENDIF

やった！すべてが解析された！

有効性のチェック

祝勝会に行く前に、もっとテストしてみよう。このTeeny Tinyコードを実行してみよう：

PRINT index
GOTO main

つまり、入力されたコードは文法に則っていても、無意味なのだ。宣言されていない変数をPRINTし、宣言されていないラベルをGOTOしようとしているのだ。コンパイラーはこれを何とかすべきだ！パースしている最中に、コンパイラーはどの変数とラベルが宣言されたか、またどのラベルがGOTOされたかを追跡することができる。もし宣言されていない変数が参照されていれば、エラーを表示することができる。構文解析の最後に、すべてのラベルが宣言されているかどうかを確認することもできます。ラベルは参照される前にgotoされることがあるので、ラベルとgotoの両方を追跡する。

3つのセットを初期化するために、__init__を更新する：

``` {.prettyprint .lang-python} def init(self, lexer): self.lexer = lexer

    self.symbols = set()    # これまでに宣言された変数。
    self.labelsDeclared = set() # これまでに宣言されたラベル。
    self.labelsGotoed = set() # 今までにGotoしたラベル。

    self.curToken = None
    self.peekToken = None
    self.nextToken()
    self.nextToken()    # カレントとピークを初期化するために、これを2回コールする。 ```

これで、label または goto ステートメントをパースするときに、セットを更新するようになった。statement関数のlabelとgotoのコードを次のように置き換える：

``` {.prettyprint .lang-python} # “LABEL “識別子 elif self.checkToken(TokenType.LABEL): print(“STATEMENT-LABEL”) self.nextToken()

        # このラベルがまだ存在しないことを確認する。
        if self.curToken.text in self.labelsDeclared:
            self.abort("Label already exists: " + self.curToken.text)
        self.labelsDeclared.add(self.curToken.text)

        self.match(TokenType.IDENT)

    # "GOTO "識別子
    elif self.checkToken(TokenType.GOTO):
        print("STATEMENT-GOTO")
        self.nextToken()
        self.labelsGotoed.add(self.curToken.text)
        self.match(TokenType.IDENT) ```

この仕組みは、ラベルがすでにlabelsDeclaredに存在している場合、コードがそのラベルを2度宣言しようとしていることを意味する。これは許されないので、コンパイラーはエラーメッセージを出して中断する。まだ存在しない場合は、セットに追加する。GOTOが解析されるたびに、ラベルをlabelsGotoedに挿入する。これは複数回発生する可能性がある。

宣言されていないラベルへのGOTOがないことを確認するために、 programを更新する必要がある。構文解析が完了したら、コンパイラーは labelsGotoed 内のすべてのラベルが labelsDeclared 内にもあることを確認するだけでよい。

``` {.prettyprint .lang-python} # program ::= {statement} def program(self): print(“PROGRAM”)

    # この文法では改行が必要なので、余分な改行は省略する必要がある。
    while self.checkToken(TokenType.NEWLINE):
        self.nextToken()

    # プログラム中のすべてのステートメントを解析する。
    while not self.checkToken(TokenType.EOF):
        self.statement()

    # GOTOで参照される各ラベルが宣言されていることを確認する。
    for label in self.labelsGotoed:
        if label not in self.labelsDeclared:
            self.abort("Attempting to GOTO to undeclared label: " + label) ```

これでラベルは片付いた。パーサーが最後にすべきことは、変数が宣言されているかどうかをチェックすることだ。LET文やINPUT文では、まだ存在していなければ、宣言された変数のセットに追加します。変数が式の中で参照されている場合、パーサーはまずその変数が宣言されているかどうかをチェックします。

statement で LET を更新する：

``` {.prettyprint .lang-python} # “LET” ident = expression elif self.checkToken(TokenType.LET): self.nextToken()

        #  ident がシンボル・テーブルに存在するかどうかをチェックする。なければ宣言する。
        if self.curToken.text not in self.symbols:
            self.symbols.add(self.curToken.text)

        self.match(TokenType.IDENT)
        self.match(TokenType.EQ)
        
        self.expression() ```

statementのINPUTを更新する：

``` {.prettyprint .lang-python} # “INPUT” ident elif self.checkToken(TokenType.INPUT): self.nextToken()

        #変数がまだ存在しない場合は宣言する。
        if self.curToken.text not in self.symbols:
            self.symbols.add(self.curToken.text)

        self.match(TokenType.IDENT) ```

その後、primaryを更新する：

``` {.prettyprint .lang-python} # primary ::= number | ident def primary(self): print(“PRIMARY (“ + self.curToken.text + “)”)

    if self.checkToken(TokenType.NUMBER): 
        self.nextToken()
    elif self.checkToken(TokenType.IDENT):
        # 変数がすでに存在していることを確認する。
        if self.curToken.text not in self.symbols:
            self.abort("Referencing variable before assignment: " + self.curToken.text)
        self.nextToken()
    else:
        # Error!
        self.abort("Unexpected token at " + self.curToken.text) ```

以上がパーサーに対する最後の変更である！さて、前回と同じ入力でテストしてみよう。

Teeny Tiny Compiler
PROGRAM
STATEMENT-PRINT
EXPRESSION
TERM
UNARY
Error! Referencing variable before assignment: index

これで、当然のようにエラーが報告された。

もう少し複雑な入力でコンパイラーを動かしてみよう：

PRINT "How many fibonacci numbers do you want?"
INPUT nums
PRINT ""

LET a = 0
LET b = 1
WHILE nums > 0 REPEAT
    PRINT a
    LET c = a + b
    LET a = b
    LET b = c
    LET nums = nums - 1
ENDWHILE

:) おめでとう、Teeny Tinyパーサーが完成した！今のところ出力はきれいではないかもしれないが、この作業によって、次の段階であるコード出力がとても簡単になった。ソースコードはGithub repoにあります。

このチュートリアルのパート3に進み、コンパイラーからコードを出す方法を学んでください。その他のお勧めの本

Parsing (Wikipedia)
Writing an Interpreter in Go (Amazon)
Crafting Interpreters (Amazon, web)

Teeny Tinyコンパイラーを作ろう、その3

[7/5/2020]

ついにここまで来た。私たちのTeeny Tinyコンパイラー用のエミッターを作る時が来たのだ。名声と幸運はすぐそこだ！前回はレキサー（その1）とパーサー（その2）を実装しました。このチュートリアルのソースコードはGitHubのrepoにあります。

エミッターとは、コンパイルされたコードを生成するコンポーネントのことです。この場合、コンパイラーはCコードを生成します。幸運なことに、私たちのパーサーはCコードを簡単に生成できるように設計されている！ Cはとてもユビキタスなので、私たちはあなたの好きなCコンパイラ（例えば、GCCやClang）に頼って実行可能ファイルを作ってもらうことにします。つまり、私たちのコンパイラーは、アセンブリ・コードや複雑なコンパイラー・フレームワークを扱うことなく、プラットフォームに依存しないのだ。

このコンパイラのコーディングを始める前に、Teeny Tinyのコードとそれに対応するCコードの架空の例をいくつか書いた。これは、どのようなものがうまく変換され（つまり、Teeny Tinyの1行がCの1行に等しい）、どのようなものがうまく変換されないかを確認する良い練習になった。

Teeny Tinyのコードと、コンパイラに出力させたい同等のCコードの例を見てみよう。この例はフィボナッチ数列のnum値を計算するプログラムである。

PRINT "How many fibonacci numbers do you want?"
INPUT nums
PRINT ""

LET a = 0
LET b = 1
WHILE nums > 0 REPEAT
    PRINT a
    LET c = a + b
    LET a = b
    LET b = c
    LET nums = nums - 1
ENDWHILE

``` {.prettyprint .lang-c} #include

int main(void){ float nums, a, b, c;

printf("How many fibonacci numbers do you want?\n");
scanf("%f", &nums);
printf("\n");

a = 0;
b = 1;
while(nums>0){
    printf("%.2f\n", (float)(a));
    c = a+b;
    a = b;
    b = c;
    nums = nums-1;
}

return 0; } ```

上記のコードは、ほぼ1行ずつ変換される。PRINTがprintfに、INPUTがscanfに、といった具合だ。他にも違いがあることにお気づきだろう。Cのコードにはメイン関数があり、ライブラリを含み、最後に0を返す。また、Cのコードでは変数の宣言と代入の構文が異なり（宣言と代入を組み合わせたLET文の構文とは異なります）、変数がすべて先頭で宣言されていることもわかります（これは古いCの慣習です）。このような違いをコンパイラーは知っておく必要がある。他にもいくつか出てきますが、恐れることはありません！

エミッターの概要

では、このエミッターはどのように動作するのでしょうか？パーサーの各関数で、適切なCコードを生成するためにエミッターを呼び出します。エミッターは事実上、解析ツリーに沿って文字列を追加していくだけです。Teeny Tinyの各文法規則について、それがCコードにどのようにマッピングされるべきかを考えます。

下の図は、Teeny Tinyのコードを1行コンパイルしたものである。レキサー、パーサー、エミッターがどのように連携して動作するかの各ステップを示している。左側は関連するトークンが強調表示された入力コード、中央は現在の要素が強調表示された構文解析ツリー、右側は新しく追加されたテキストが強調表示されたエミッタ・コードを示している。

アニメーションを何度か見てみよう。エミッターはパース・ツリーを利用して、Cコードを断片的にエミュレートしている。コードを見れば、このことがよくわかるだろう。

コードのセットアップ

まず、teenytiny.py の main を更新して、これから作るエミッタを使うようにします：

``` {.prettyprint .lang-python} from lex import * from emit import * from parse import * import sys

def main(): print(“Teeny Tiny Compiler”)

if len(sys.argv) != 2:
    sys.exit("Error: Compiler needs source file as argument.")
with open(sys.argv[1], 'r') as inputFile:
    source = inputFile.read()

# レキサー、エミッター、パーサーを初期化する。
lexer = Lexer(source)
emitter = Emitter("out.c")
parser = Parser(lexer, emitter)

parser.program() # パーサーを起動する。
emitter.writeFile() # 出力をファイルに書き出す。
print("Compiling completed.")

main()

コンパイラーは、コマンドライン引数としてファイル名を入力用に開くことを依然として期待している。しかし、パーサー・オブジェクトがレキサーとエミッターを制御するようになった。次に、エミッタを実装します。以下のコードで **emit.py** を作成します：

``` {.prettyprint .lang-python}
# エミッター・オブジェクトは生成されたコードをトラッキングし、それを出力する。
class Emitter:
    def __init__(self, fullPath):
        self.fullPath = fullPath
        self.header = ""
        self.code = ""

    def emit(self, code):
        self.code += code

    def emitLine(self, code):
        self.code += code + '\n'

    def headerLine(self, code):
        self.header += code + '\n'

    def writeFile(self):
        with open(self.fullPath, 'w') as outputFile:
            outputFile.write(self.header + self.code)

これがエミッターのコードのすべてだ！これは単に文字列を付加するためのヘルパー・クラスである。codeは放出されるCコードを含む文字列で、headerには後でコードの前に追加するものが含まれ、fullPathはCコードを含むファイルを書き込むパスです。Cコードの断片を追加するにはemitを使用し、行末の断片を追加するにはemitLineを使用します。headerLineは、ライブラリ・ヘッダ、メイン関数、変数宣言など、Cコード・ファイルの先頭にCコードの行を追加するためのものです。最後に、writeFileはCコードをファイルに書き込む。

次に、エミッタを使用するために、parse.pyのparserの__init__**を少し変更します：

``` {.prettyprint .lang-python} def init(self, lexer, emitter): self.lexer = lexer self.emitter = emitter

    self.symbols = set()    # これまでに宣言したすべての変数。
    self.labelsDeclared = set() # 宣言されたすべてのラベルを記録する
    self.labelsGotoed = set() # すべてのラベルがGotoされているので、そのラベルが存在するかどうかがわかる。

    self.curToken = None
    self.peekToken = None
    self.nextToken()
    self.nextToken()    # カレントとピークを初期化するために、これを2回コールする。 ```

エミッターに必要なのはこれだけだ。あとはパーサーから適切なCコードで呼び出すだけだ。

ステートメントの出力

これからparse.pyの既存の関数を修正します。パーサ内部からエミッタ関数を呼び出します(そして、パート2でテストに使用したprint文を削除します)。

関数を順番に見ていき、programを見てみましょう。空のTeeny Tinyプログラムを翻訳するには、定型のCコードが必要です。本当に必要なのはmain関数だけですが、printfとscanfが使えるようにstdio.hをインクルードしておきましょう。でprogramを更新する：

``` {.prettyprint .lang-python} # program ::= {statement} def program(self): self.emitter.headerLine(“#include ") self.emitter.headerLine("int main(void){")

    # この文法では改行が必要なので、余分な改行は省略する必要がある。
    while self.checkToken(TokenType.NEWLINE):
        self.nextToken()

    # プログラム中のすべてのステートメントを解析する。
    while not self.checkToken(TokenType.EOF):
        self.statement()

    # 総括する。
    self.emitter.emitLine("return 0;")
    self.emitter.emitLine("}")

    # GOTOで参照される各ラベルが宣言されていることを確認する。
    for label in self.labelsGotoed:
        if label not in self.labelsDeclared:
            self.abort("Attempting to GOTO to undeclared label: " + label) ```

ここでの追加は、まずinclude文とmain関数から始めている。それから、self.statement()のすべてをループする。最後に、return 0;と閉じ括弧でmain関数を閉じなければならない。

このようにエミッターを使い続ける。初期コードを出力し、文法に基づいて他のパーサー関数を呼び出し、コールスタックを返す前にさらにコードを出力する。

これまでのエミッターをテストしてみよう。フィボナッチのコード例があるhello.teenyがまだ前回から存在していると仮定して、python3 teenytiny.py hello.teenyを実行します。予定通りであれば、ターミナルの最後の行が "Compiling completed."となり、out.cが作成されているはずです。出力されたコードの中身を確認してみましょう：

``` {.prettyprint .lang-c} #include int main(void){ return 0; }

今、コンパイラが何かをコンパイルした！

そうです、Teeny TinyコンパイラがCプログラムを生成できるようになったのです。 (MacやLinuxをお使いの場合は、*clang out.c*または*gcc out.c*を実行して実行ファイルを作成し、*./a.out*でプログラムを実行できる。まだ何も出力されない。 でももうすぐだ。もうすぐだ。Cコンパイラが使えない場合は、[Repl.it](https://repl.it/languages/c)を使ってブラウザでCコードを実行できる。

次に、**parse.py**の**statement**関数内の*PRINT*を更新します。print文には2つのケースがあることを思い出してください: 文字列を表示する場合と式の結果を表示する場合です。以下はそのコードです：

``` {.prettyprint .lang-python}
        # "PRINT" (expression | string)
        if self.checkToken(TokenType.PRINT):
            self.nextToken()

            if self.checkToken(TokenType.STRING):
                # 単純な文字列なので、それを表示。
                self.emitter.emitLine("printf(\"" + self.curToken.text + "\\n\");")
                self.nextToken()

            else:
                # 式を期待し、結果を float として表示する。
                self.emitter.emit("printf(\"%" + ".2f\\n\", (float)(")
                self.expression()
                self.emitter.emitLine("));")

Cコードの断片をどのように出力しているか見てみよう。うまくいけば、これがより意味を持ち始めるだろう。

もう一度hello.teenyでコンパイラーを実行し、out.cをチェックしてください：

``` {.prettyprint .lang-c} #include int main(void){ printf("How many fibonacci numbers do you want?\n"); printf("\n"); printf("%.2f\n", (float)()); return 0; }

これは素晴らしい。Teeny Tinyは文字列を印刷するコードを出力するようになった。お好きなCコンパイラで実行してみてください。注意すべき点は、3番目の*printf*が何もしていないことだ。これは、**expression**がまだ何も出力していないからだ。最終的にこれは数値を生成する。

次に、*IF*文と*WHILE*文のコードを置き換えてみましょう。見た目はほとんど同じだ：

``` {.prettyprint .lang-python}
        # "IF" comparison "THEN" block "ENDIF"
        elif self.checkToken(TokenType.IF):
            self.nextToken()
            self.emitter.emit("if(")
            self.comparison()

            self.match(TokenType.THEN)
            self.nl()
            self.emitter.emitLine("){")

            # 本文中に0個以上の記述がある。
            while not self.checkToken(TokenType.ENDIF):
                self.statement()

            self.match(TokenType.ENDIF)
            self.emitter.emitLine("}")

        # "WHILE" comparison "REPEAT" block "ENDWHILE"
        elif self.checkToken(TokenType.WHILE):
            self.nextToken()
            self.emitter.emit("while(")
            self.comparison()

            self.match(TokenType.REPEAT)
            self.nl()
            self.emitter.emitLine("){")

            # ループ本体に0個以上のステートメント。
            while not self.checkToken(TokenType.ENDWHILE):
                self.statement()

            self.match(TokenType.ENDWHILE)
            self.emitter.emitLine("}")

このコードをフィボナッチの例でテストしてみると、何かが大きく崩れていることに気づくだろう。Cのコードにはwhile(){が含まれている。うほっ。これは前と同じ問題で、expressionやcomparisonのような関数からは何も出力されない。しかし、ループの残りの部分は正しく見える。

LABELとGOTOのコードはかなり単純だ：

``` {.prettyprint .lang-python} # “LABEL “識別子 elif self.checkToken(TokenType.LABEL): self.nextToken()

        # このラベルがまだ存在しないことを確認する。
        if self.curToken.text in self.labelsDeclared:
            self.abort("Label already exists: " + self.curToken.text)
        self.labelsDeclared.add(self.curToken.text)

        self.emitter.emitLine(self.curToken.text + ":")
        self.match(TokenType.IDENT)

    # "GOTO"識別子
    elif self.checkToken(TokenType.GOTO):
        self.nextToken()
        self.labelsGotoed.add(self.curToken.text)
        self.emitter.emitLine("goto " + self.curToken.text + ";")
        self.match(TokenType.IDENT) ```

もっと面白いことをするために、すべてのテストはちょっと省略する。

このLETコードは少し変わっている。emitter.headerLineを呼び出すことがある。なぜか？なぜなら、Teeny Tinyで初めて変数が参照されるときは、C言語の変数宣言を呼び出し、それをmain関数の先頭に置かなければならないからだ（これは古いC言語の慣習である）。先に述べたように、これはTeeny TinyとCの構文の大きな違いの1つなので、コンパイラーは翻訳するために少し手間がかかる。Teeny Tinyは変数宣言と代入を区別しないが、Cは区別する。以下はそのコードである：

``` {.prettyprint .lang-python} # “LET” ident = expression elif self.checkToken(TokenType.LET): self.nextToken()

        #  シンボル・テーブルにidentが存在するかチェックする。なければ宣言する。
        if self.curToken.text not in self.symbols:
            self.symbols.add(self.curToken.text)
            self.emitter.headerLine("float " + self.curToken.text + ";")

        self.emitter.emit(self.curToken.text + " = ")
        self.match(TokenType.IDENT)
        self.match(TokenType.EQ)
        
        self.expression()
        self.emitter.emitLine(";") ```

よし、hello.teenyをコンパイルして、out.cを調べてみよう。

``` {.prettyprint .lang-c} #include int main(void){ float a; float b; float c; printf("How many fibonacci numbers do you want?\n"); printf("\n"); a = ; b = ; while(){ printf("%.2f\n", (float)()); c = ; a = ; b = ; nums = ; } return 0; }

このコードには間違いなくエラーがないわけではないし、フォーマットなしではちょっと読みにくい。変数の宣言がすべて一番上にあるのがわかるだろう！これはエキサイティングだ。では、何がうまくいっていないのか？a = ;*は確かに有効なCコードではない。すべての変数代入が壊れているようだ。実際、**expression**を呼び出すものはすべて（まだ）無効なコードを吐いている。しかし、かなり前進している！

さて、サポートする文の種類がもう1つ増えた： *INPUT*である。これにはいくつか注意すべき点がある。まず、参照される変数がまだ存在しない場合は、**emitter.headerLine**を使って宣言しなければならない。第二に、*scanf*がどのように動作するかのため、C特有のコードをいくつか含めなければならない。単に*scanf(\"%f\", &foo);*をemitすることもできるが、これではユーザが文字を入力したときのような無効な入力を処理できない。scanfが0を返したら、入力バッファをクリアし、入力変数を0にする。

注：これはTeeny Tinyの制限になる。ユーザー入力が値0だったのか、無効な入力だったのかを見分けることができない。これらは同じように扱われる。しかし、これを修正する方法はある。無効な入力が-999のようなわかりにくい値になるように修正したり、エラーメッセージを表示してループの中で有効な入力を求めたり、フラグにエラーコードを設定したりすることができる。プログラミング言語によって、このようなシナリオの扱いは異なります。しかし、今のところは0という値でうまくいくだろう。

思い切ってコードを書いてみよう。ちょっと不格好に見えるが、実際には無効な入力を処理するための定型文にすぎない。これがそれだ：

``` {.prettyprint .lang-python}
        # "INPUT" 識別子
        elif self.checkToken(TokenType.INPUT):
            self.nextToken()

            # 変数がまだ存在しない場合は、それを宣言する。
            if self.curToken.text not in self.symbols:
                self.symbols.add(self.curToken.text)
                self.emitter.headerLine("float " + self.curToken.text + ";")

            # scanfを出力するが、入力を検証する。無効な場合は、変数を0にセットし、入力をクリアする。
            self.emitter.emitLine("if(0 == scanf(\"%" + "f\", &" + self.curToken.text + ")) {")
            self.emitter.emitLine(self.curToken.text + " = 0;")
            self.emitter.emit("scanf(\"%")
            self.emitter.emitLine("*s\");")
            self.emitter.emitLine("}")
            self.match(TokenType.IDENT)

さっそくテストしてみよう。すべての文がCコードを出力するようになりました！

式の発行

最後にコードを出力する必要があるのは式です。Teeny Tinyのコードが有効なCコードであるためには、基本的に何も変更する必要がないため、この作業はほとんど必要ありません。つまり、Teeny Tiny の index * offset + 1 は C の index * offset + 1 でもあるということです。

We will first take care of comparison, which will only emit the specific operator.

``` {.prettyprint .lang-python} # comparison ::= expression ((“==” | “!=” | “>” | “>=” | “<” | “<=”) expression)+ def comparison(self): self.expression() # 少なくとも1つの比較演算子と別の式でなければならない。 if self.isComparisonOperator(): self.emitter.emit(self.curToken.text) self.nextToken() self.expression() # 0個以上の比較演算子と式を持つことができる。 while self.isComparisonOperator(): self.emitter.emit(self.curToken.text) self.nextToken() self.expression()

実際、これは非常に単純なので、**expression**、**term**、**unary**も同じように動作する。

``` {.prettyprint .lang-python}
    # expression ::= term {( "-" | "+" ) term}
    def expression(self):
        self.term()
        # 0以上の +/- と式を持つことができる。
        while self.checkToken(TokenType.PLUS) or self.checkToken(TokenType.MINUS):
            self.emitter.emit(self.curToken.text)
            self.nextToken()
            self.term()


    # term ::= unary {( "/" | "*" ) unary}
    def term(self):
        self.unary()
        # 0以上の*//と式を持つことができる。
        while self.checkToken(TokenType.ASTERISK) or self.checkToken(TokenType.SLASH):
            self.emitter.emit(self.curToken.text)
            self.nextToken()
            self.unary()


    # unary ::= ["+" | "-"] primary
    def unary(self):
        # Optional unary +/-
        if self.checkToken(TokenType.PLUS) or self.checkToken(TokenType.MINUS):
            self.emitter.emit(self.curToken.text)
            self.nextToken()        
        self.primary()

これで、primaryを除くすべての文法関数からコードが出力されたことになる。ここまでくれば、あとは数字リテラルか変数識別子しか出てこない：

``` {.prettyprint .lang-python} # primary ::= number | ident def primary(self): if self.checkToken(TokenType.NUMBER): self.emitter.emit(self.curToken.text) self.nextToken() elif self.checkToken(TokenType.IDENT): # 変数がすでに存在していることを確認する。 if self.curToken.text not in self.symbols: self.abort(“Referencing variable before assignment: “ + self.curToken.text)

        self.emitter.emit(self.curToken.text)
        self.nextToken()
    else:
        # Error!
        self.abort("Unexpected token at " + self.curToken.text) ```

ついでに、nlから*printを削除してください。

これで完了です！これでTeeny TinyはCコードにコンパイルされる！新しい例、average.teenyでテストしてみましょう：

# Compute average of given values.

LET a = 0
WHILE a < 1 REPEAT
    PRINT "Enter number of scores: "
    INPUT a
ENDWHILE

LET b = 0
LET s = 0
PRINT "Enter one value at a time: "
WHILE b < a REPEAT
    INPUT c
    LET s = s + c
    LET b = b + 1
ENDWHILE

PRINT "Average: "
PRINT s / a

この状態でTeeny Tinyを実行すると、以下のように表示されるはずだ：

Teeny Tiny Compiler
Compiling completed.

out.cを見てみると、こんな素晴らしいコードがある：

``` {.prettyprint .lang-c} #include int main(void){ float a; float b; float s; float c; a = 0; while(a<1){ printf("Enter number of scores: \n"); if(0 == scanf("%f", &a)) { a = 0; scanf("%*s"); } } b = 0; s = 0; printf("Enter one value at a time: \n"); while(b<a){ if(0 == scanf("%f", &c)) { c = 0; scanf("%*s"); } s = s+c; b = b+1; } printf("Average: \n"); printf("%.2f\n", (float)(s/a)); return 0; }

それをCコンパイラにかける。すごい。見ろよ。本物のコンパイラができた。 ボーランドの上を行く！

### Teeny Tinyのコンパイル

Teeny Tinyを使うのが少し面倒なことにお気づきだろうか。まず、Pythonスクリプトを実行しなければならない。次に、Cコンパイラーを実行する。3番目に、プログラムを実行する。これほど多くのステップを踏む必要はない。これらすべてをTeeny Tinyに組み込むこともできるし、スクリプトを書いて自動化することもできる。

友人の[Stephen Marz](https://blog.stephenmarz.com/)がBashスクリプトを作ってくれた：

``` {.prettyprint .lang-bash}
PYTHON="python3"
COMPILER="teenytiny.py"
CC="gcc"

function comp {
    BN=$(basename -s .teeny $1)
    TTOUTPUT=$(${PYTHON} ${COMPILER} $1 2>&1)
    if [ $? -ne 0 ]; then
        echo "${TTOUTPUT}"
    else
        mv out.c ${BN}.c
        CCOUTPUT=$(${CC} -o ${BN} ${BN}.c)
        if [ $? -ne 0 ]; then
            echo "${CCOUTPUT}"
        else
            echo "${TTOUTPUT}"
        fi
    fi
}

if [ $# -eq 0 ]; then
    for i in $(ls examples/*.teeny); do
        comp $i
    done
else
    comp $1
fi

ターミナルで bash build.sh hello.teeny と実行して、実行ファイルを ./hello のように実行すればいい。

プロジェクトは続く…

あなたのTeeny Tinyコンパイラーは動いている！独自の言語で書かれたコードがあれば、コンパイラーはコンパイルして実行できるCコードを生成する。これはかなりの偉業だ。もう少し機能を追加すれば、Teeny Tinyコードで書かれたTeeny Tinyコンパイラを作ることができるだろう！コンパイラのすべて

Teeny Tinyの完全なソースコードはGithub repoにあります。

チュートリアルはここで終わりですが、あなたのコンパイラの冒険はここで終わる必要はありません。構文を変えてもいいし、言語とコンパイラを少しずつ改良するために追加できる機能はたくさんある。例えば

式の括弧
論理演算子 (and, or, not)
ELSE IFとELSE
FORループ
2進数、16進数、8進数で記述された数値リテラル
コンパイラー・エラーを改善（例：どの行でエラーが発生したか）
複数のコードファイルの使用
パラメータと戻り値を持つ関数
レキシカルスコープ（scopeを参照）
標準ライブラリ（ファイル操作など）
抽象構文木表現
よりプリミティブな型（整数、文字列、ブーリアンなど）
配列
レコード型（構造体やタプルなど）
型チェック (型システムを参照)
コンパイラの最適化 (例: 定数の折りたたみ)
コンパイラのテストケース (単体テストおよびテスト駆動開発を参照)

最も注目すべきは、抽象構文木（AST）表現である。これは、このチュートリアルでは省かれていた主要なもののひとつで、基本的にすべてのコンパイラーが使っているものだ。これはコードの中間的な表現で、コードを出力する段階の前に、コードに対してあらゆる種類の解析や最適化を行うことができる。幸いなことに、私たちがコンパイラを作った方法は、ASTを作るのが非常に簡単だということを意味している！

次は何について書くべきか、私に教えてください。それまでは、以下の長いチュートリアルを読むことを強くお勧めする：

Goでインタプリタを書く (Amazon)
インタプリタの作成 (Amazon, web)