簡易なC言語コンパイラを実現(part 1)

この部分から,簡易C言語コンパイラを徐々に実現する.简易とは、C言语の基准に従って、部分的な文法を无视し、难易度を适切に下げ、基本的な机能を含むC言语コンパイラを実现することである.コンパイルプロセスに重点を置き、アセンブリとリンクプロセスは既存のコンパイラで完了します.難易度に応じて,まず前処理過程をスキップし,コンパイル段階の文法解析に直接入る.まず、次の簡単なC言語コードから始めましょう.

int main()
{
    return (2 + 2) * 2 - 8;
}

私は古典的なHello World!のコードを使っていません.そのいくつかの簡単なコードは、非常に多くの知識に関連しているからです.今、コンパイラの実現方法を浅く深く理解する必要があります.その時になってから振り返って、その古典的なコードを分析します.上のコードはとても簡単です.ヘッダファイルがなく、メイン関数が1つしかなく、関数の内部で簡単な4つの演算を行い、結果を返します.結果は計算しやすい.しかし、私たちの目的はコンパイラを実現し、最終的にコンピュータCPUチップの演算ユニットにこの結果を解くことであることを忘れないでください.そのため,システム的な面から考え,このような計算過程に類似した問題をより多く処理する必要がある.前述したように、構文解析は、ソースコードを個々のtokenに分解することです.たとえば、ここではソースコードを次のtokenに分解することができます.
int
main
(
)
{
return
(
2
+
2
)
*
2
-
8
;
}
皆さんも理解したと思いますが、文法分析はこのコードを一つ一つ分解することです.連続する文字については、スペースに遭遇するまでtokenとして構成します.もちろん改行も含まれます.したがって、int mainを誤ってintmainと書くと、intとmainに分割されることなくtokenとなる.これは定義された変数または関数名である可能性があります.もちろん、プログラマーがスペースで区切らなかっただけです.簡単ではないでしょうか.以下、Pythonでこの機能を実現します.もちろん、水を飲んで井戸を掘る人を忘れないで、私はこのブログの文章(Let's Build A Simple Interpreter)の中で使った方法と構想に沿っています.先に述べたtokenクラスを定義します.

class Token(object):
    def __init__(self, type, value, pos=None):
        self.type = type
        self.value = value

tokenは単純に1つのキー値に対応するMapとして理解できる.ここで、上記のC言語コードで使用されるtokenの名前は、次のとおりです.

# algebra
PLUS          = 'PLUS'
MINUS         = 'MINUS'
MUL           = 'MUL'
# scope
LPAREN        = 'LPAREN'
RPAREN        = 'RPAREN'
BEGIN         = 'BEGIN'
END           = 'END'
# symbol
ID            = 'ID'
SEMI          = 'SEMI'
EOF           = 'EOF'
# reserved keywords
INT           = 'INT'
RETURN        = 'RETURN'

大文字で表すのはpythonのキーワードを区別するためです.これらの準備があれば,文法解析の専用クラス:Lexerを定義することができる.

class Lexer(object):
    def __init__(self, text):
        self.text = text
        self.pos = 0
        self.current_char = self.text[self.pos]

    def next(self):
        """obtain the next the `pos` pointer ."""
        self.pos += 1
        if self.pos > len(self.text) - 1:
            self.current_char = None  # Indicates end of input
        else:
            self.current_char = self.text[self.pos]

    def get_next_token(self):
        """Lexical analyzer. One token at a time."""
        while self.current_char is not None:
            if self.current_char.isspace():
                self.skip_whitespace()
                continue

            if self.current_char.isalpha():
                return self.identifier()

            if self.current_char.isdigit():
                return self.number()

            if self.current_char == '+':
                self.next()
                return Token(PLUS, '+')

            if self.current_char == '-':
                self.next()
                return Token(MINUS, '-')

            if self.current_char == '*':
                self.next()
                return Token(MUL, '*')

            if self.current_char == '(':
                self.next()
                return Token(LPAREN, '(')

            if self.current_char == ')':
                self.next()
                return Token(RPAREN, ')')

            if self.current_char == '{':
                self.next()
                return Token(BEGIN, '{')

            if self.current_char == '}':
                self.next()
                return Token(END, '}')

            if self.current_char == ';':
                self.next()
                return Token(SEMI, ';')

        return Token(EOF, None)

このコードのEOF(eofと同じ)は、ファイル終了子を表し、ソースコードの一部がすべて読み込まれたことを示します.Lexerクラスには、スペース、数値、識別子をそれぞれ処理する3つの関数が欠けていることに注意してください.これらの関数を定義すると、Lexerオブジェクトをインスタンス化して、最初のC言語コードを処理することができます.get_next_token()をループ呼び出して、分割された各tokenを得る.同様に,より複雑なソースコードを扱う場合,C言語文法の定義に従ってtokenの名前を増やし,現在の文字が一致するか否かを判断することで,対応するtokenをそのまま扱うことができる.その3つのメンバー関数を単独で提案したのは,実装方法が各文字がtokenである可能性があると仮定することを決定したからである.しかし、スペース、数字、またはフラグなどについては、他の代数記号のように1文字だけを判断することなく、複数の文字を1つのtokenに構成する必要がある場合があります.したがって,個別の関数で処理する必要がある.たとえば、数値の処理は次のようになります.

    def number(self):
        result = ''
        while self.current_char is not None \
                and self.current_char.isdigit():
            result += self.current_char
            self.next()

        return Token(INT, int(result), self.line)

注意すべきは、コンパイラが浮動小数点演算をサポートしていないことです.後でアセンブリ言語の生成を行う過程で,浮動小数点演算は完全な大きな塊と言える.コンパイラを理解する観点から,整数型演算を理解したことを把握すると,もうほとんど差がない.その後、興味があれば、コンパイラが浮動小数点型をサポートする方法を完全に拡張することができ、原理はあまり悪くありません.同様に、空白文字の処理も同様です.

    def skip_whitespace(self):
        # isspace contains '', '
', '\t', etc.
        while self.current_char is not None \
                and self.current_char.isspace():

            self.next()

次に、フラグの処理を行います.

    def identifier(self):
        """Handle identifiers and reserved keywords, and macro definition replace"""
        result = ''
        while self.current_char is not None and (self.current_char.isalnum() or self.current_char == '_'):
            result += self.current_char
            self.next()

        token = RESERVED_KEYWORDS.get(result.upper(), Token(ID, result))
        return token

ここではRESERVED_KEYWORDSを使用しました.その名の通り、RESERVED_KEYWORDSは予め定義された保留キーワード辞書です.

RESERVED_KEYWORDS = {
    'INT': Token('INT', 'int'),
    'RETURN': Token('RETURN', 'return'),
}

これで、文法分析の内容は分析済みです.
簡易なC言語コンパイラ(part 0)を実現簡易なC言語コンパイラ(part 2)を実現簡易なC言語コンパイラ(part 3)を実現簡易なC言語コンパイラ(part 4)を実現簡易なC言語コンパイラ(part 5)を実現簡易なC言語コンパイラ(part 6)を実現簡易なC言語コンパイラ(part 7)を実現簡易なC言語コンパイラ(part 8)を実現簡易なC言語コンパイラ(part 9)を実現する簡易なC言語コンパイラ(part 10)を実現簡易なC言語コンパイラを実現(part 11)