私は長い間、コンパイラの作成はエリートの大部分であり、単純な人間のプログラマーはこの科学を理解できないと信じていました。 私はこれがそうではないことを証明しようとします。
投稿では、わずか300行のコードを書き留めて、1時間以内に独自のCライクな言語コンパイラを作成する方法を検討します。 ボーナスとして、これにはソースがコンパイルされるバイトコードの仮想マシンコードが含まれます。
コンパイラはPythonで作成されます。 私はこの言語が大好きですが、場所によってはコードが不器用になることがあります。 何かが間違っている場合-個人的に書いてください。
はい、コンパイラは完全に露骨にTiny-Cに基づいています。
文法
始める前に、私たちの言語が正確にできることを決めましょう。
彼はほとんど何もできません。
-唯一のデータ型はintです
-すべての変数はグローバルです。 合計26個の変数があります（az）
-数学演算のうち、「+」と「-」のみがサポートされています
-唯一の比較演算子は「<」です
-言語構造から-条件文if、if / else、while、do / while
それだけです 配列、関数、構造はありません。 ここに私たちの言語で得られた文法があります：
<program> ::= <statement> <statement> ::= "if" <paren-expr> <statement> | "if" <paren-expr> <statement> "else" <statement> | "while" <paren-expr> <statement> | "do" <statement> "while" <paren-expr> | "{" { <statement> } "}" | <expr> ";" | ";" <paren-expr> ::= "(" <expr> ")" <expr> ::= <test> | <id> "=" <expr> <test> ::= <sum> | <sum> "<" <sum> <sum> ::= <term> | <sum> "+" <term> | <sum> "-" <term> <term> ::= <id> | <int> | <paren-expr> <id> ::= "a" | "b" | ... | "z" <int> ::= <digit>, { <digit> } <digit> ::= "0" | "1" | ... | "9"
これはEBNFの形式の文法エントリです。 このエントリの大まかな意味は次のとおりです。
プログラムは単一のステートメントです。
演算子は、条件付き（if..else ...）、周期的（while ...）、および単純な演算子（たとえば、「a = 2 + 3」）です。
条件付きおよび循環には、条件式と本体（演算子の形式）が含まれます。 通常の演算子はセミコロンで終わります。 演算子を中括弧でグループ化すると、複合演算子が得られます。
式は、変数の値への合計または割り当てのいずれかです。
ここで、合計は用語の加減算のシーケンスです。
用語は、括弧内の数値、変数、または式です。
変数はa〜zの文字です。 数字は、0から9までの数字のセットです。
これらすべての困難は、ソースコードを自動的に分析する方法をコンパイラに伝えるために必要です。 たとえば、「if」という単語に出会いました。つまり、括弧で囲まれた式の後に演算子が続きます。
字句解析器
コンパイラはテキストファイル（ソース）を受け取ります。 このファイル内のトークンを抽出するには、 字句解析プログラムが必要です。 つまり 「a = 3 + 42;」という行は、字句解析プログラムが「識別子：a」、「演算子=」、「番号3」、「演算子+」、「番号42」、「文字;」の形式で表示する必要があります。 字句解析器は、文字のシーケンスでのみ機能します。 彼にとって、「ab if =」という行も意味をなしており、完全に正しい。
そのため、字句解析プログラムは次のトークンを認識する必要があります。
-数字
-変数識別子
-キーワード：if、else、while、do
-文字+、-、<、=、{、}、（、）、;
-ファイルの終わり
ソースコードは次のようになります。
class Lexer: NUM, ID, IF, ELSE, WHILE, DO, LBRA, RBRA, LPAR, RPAR, PLUS, MINUS, LESS, \ EQUAL, SEMICOLON, EOF = range(16) # SYMBOLS = { '{': LBRA, '}': RBRA, '=': EQUAL, ';': SEMICOLON, '(': LPAR, ')': RPAR, '+': PLUS, '-': MINUS, '<': LESS } # WORDS = { 'if': IF, 'else': ELSE, 'do': DO, 'while': WHILE } # , ch = ' ' # , - def error(self, msg): print 'Lexer error: ', msg sys.exit(1) def getc(self): self.ch = sys.stdin.read(1) def next_tok(self): self.value = None self.sym = None while self.sym == None: if len(self.ch) == 0: self.sym = Lexer.EOF elif self.ch.isspace(): self.getc() elif self.ch in Lexer.SYMBOLS: self.sym = Lexer.SYMBOLS[self.ch] self.getc() elif self.ch.isdigit(): intval = 0 while self.ch.isdigit(): intval = intval * 10 + int(self.ch) self.getc() self.value = intval self.sym = Lexer.NUM elif self.ch.isalpha(): ident = '' while self.ch.isalpha(): ident = ident + self.ch.lower() self.getc() if ident in Lexer.WORDS: self.sym = Lexer.WORDS[ident] elif len(ident) == 1: self.sym = Lexer.ID self.value = ord(ident) - ord('a') else: self.error('Unknown identifier: ' + ident) else: self.error('Unexpected symbol: ' + self.ch)
next_tok（）メソッドでは、アナライザーは次のトークンを受け取ります。 トークンのタイプはsym属性から取得でき、その値（変数または数値の場合）はvalue属性から取得できます。
アナライザーはスペースを無視し、現在の文字が言語の特殊文字であるかどうかを確認し、そうでない場合は数字または識別子であるかどうかを確認します。 つまり 桁1に達すると、アナライザーは、数字以外の文字を検出するまで文字を減算し続けます。 識別子は同じ方法でチェックされます（文字番号の代わりに）。
パーサー
これはおそらくコンパイラの最も複雑なコンポーネントです。 彼のタスクは、字句解析器から受け取ったトークンを使用して、階層と関係がコードの構造を反映する一種のツリーを形成することです。 例：
"if (a < 0) a = 5;" IF +-LESS | +-VAR(a) | +-NUM(0) +-SET +-VAR(a) +-NUM(5)
パーサーによって構築されるツリーはノードで構成されます。 ノードには、タイプ（IF、LESS、SET、VAR ...）、値（数値または変数の場合）、およびいくつかの子オペランドノード（コード内-op1、op2、op3）があります。 ifの場合、条件とthen / elseブランチが格納され、forループの場合、条件とループの本体が格納されます。
ノードを説明するために、Nodeクラスを導入します。 パーサークラスとノードクラスのコードは次のとおりです。
class Node: def __init__(self, kind, value = None, op1 = None, op2 = None, op3 = None): self.kind = kind self.value = value self.op1 = op1 self.op2 = op2 self.op3 = op3 class Parser: VAR, CONST, ADD, SUB, LT, SET, IF1, IF2, WHILE, DO, EMPTY, SEQ, EXPR, PROG = range(14) def __init__(self, lexer): self.lexer = lexer def error(self, msg): print 'Parser error:', msg sys.exit(1) def term(self): if self.lexer.sym == Lexer.ID: n = Node(Parser.VAR, self.lexer.value) self.lexer.next_tok() return n elif self.lexer.sym == Lexer.NUM: n = Node(Parser.CONST, self.lexer.value) self.lexer.next_tok() return n else: return self.paren_expr() def summa(self): n = self.term() while self.lexer.sym == Lexer.PLUS or self.lexer.sym == Lexer.MINUS: if self.lexer.sym == Lexer.PLUS: kind = Parser.ADD else: kind = Parser.SUB self.lexer.next_tok() n = Node(kind, op1 = n, op2 = self.term()) return n def test(self): n = self.summa() if self.lexer.sym == Lexer.LESS: self.lexer.next_tok() n = Node(Parser.LT, op1 = n, op2 = self.summa()) return n def expr(self): if self.lexer.sym != Lexer.ID: return self.test() n = self.test() if n.kind == Parser.VAR and self.lexer.sym == Lexer.EQUAL: self.lexer.next_tok() n = Node(Parser.SET, op1 = n, op2 = self.expr()) return n def paren_expr(self): if self.lexer.sym != Lexer.LPAR: self.error('"(" expected') self.lexer.next_tok() n = self.expr() if self.lexer.sym != Lexer.RPAR: self.error('")" expected') self.lexer.next_tok() return n def statement(self): if self.lexer.sym == Lexer.IF: n = Node(Parser.IF1) self.lexer.next_tok() n.op1 = self.paren_expr() n.op2 = self.statement() if self.lexer.sym == Lexer.ELSE: n.kind = Parser.IF2 self.lexer.next_tok() n.op3 = self.statement() elif self.lexer.sym == Lexer.WHILE: n = Node(Parser.WHILE) self.lexer.next_tok() n.op1 = self.paren_expr() n.op2 = self.statement(); elif self.lexer.sym == Lexer.DO: n = Node(Parser.DO) self.lexer.next_tok() n.op1 = self.statement() if self.lexer.sym != Lexer.WHILE: self.error('"while" expected') self.lexer.next_tok() n.op2 = self.paren_expr() if self.lexer.sym != Lexer.SEMICOLON: self.error('";" expected') elif self.lexer.sym == Lexer.SEMICOLON: n = Node(Parser.EMPTY) self.lexer.next_tok() elif self.lexer.sym == Lexer.LBRA: n = Node(Parser.EMPTY) self.lexer.next_tok() while self.lexer.sym != Lexer.RBRA: n = Node(Parser.SEQ, op1 = n, op2 = self.statement()) self.lexer.next_tok() else: n = Node(Parser.EXPR, op1 = self.expr()) if self.lexer.sym != Lexer.SEMICOLON: self.error('";" expected') self.lexer.next_tok() return n def parse(self): self.lexer.next_tok() node = Node(Parser.PROG, op1 = self.statement()) if (self.lexer.sym != Lexer.EOF): self.error("Invalid statement syntax") return node
このパーサーは、parse（）メソッドから始めて再帰的に動作します。
最初に、彼は「プログラム」ノードを作成します。そのノードの子がプログラムのメインオペレーターになります。
演算子はstatement（）メソッドで生成されます。 このメソッドでは、最初のトークンがチェックされ、if / else、while、do / while、複合ステートメント（中括弧で始まる場合）、またはセミコロンで終わる単一ステートメントのみが形成されます。
演算子を構築するとき、expr（）メソッドが使用されます-式を取得し、paren_expr（）-括弧内の式を取得します。
式は、用語で構成される合計から構築されるチェックから構築されます。 そして、用語は、括弧内の数字、変数、および式で構成されます。 ジャックが建てた家の中。
そのような再帰。 ご覧のとおり、これらのメソッドは上記の文法の概念に対応しています。
parse（）メソッドの出力で、プログラムのツリーを含むクラスNodeのオブジェクトを取得します。 これで、このツリーをマシンコードに変換できます。
機械コード
特別な仮想マシンの単純なバイトコードにコンパイルします。 仮想マシンはスタックされるため、 登録よりもはるかに簡単です。 彼女の可能な指示は次のとおりです。
FETCH x - x STORE x - x PUSH n - n POP - ADD - SUB - LT - (a < b). - 0 1 JZ a - 0 - a. JNZ a - 0 - a. JMP a - a HALT -
たとえば、演算子「a = 2; b = 5;”は、次の一連の命令に変換されます。
PUSH 2 STORE 0 PUSH 5 STORE 1
仮想マシンのコードは非常に簡単です。 すべてrunメソッドで説明されています。
IFETCH, ISTORE, IPUSH, IPOP, IADD, ISUB, ILT, JZ, JNZ, JMP, HALT = range(11) class VirtualMachine: def run(self, program): var = [0 for i in xrange(26)] stack = [] pc = 0 while True: op = program[pc] if pc < len(program) - 1: arg = program[pc+1] if op == IFETCH: stack.append(var[arg]); pc += 2 elif op == ISTORE: var[arg] = stack.pop(); pc += 2 elif op == IPUSH: stack.append(arg); pc += 2 elif op == IPOP: stack.append(arg); stack.pop(); pc += 1 elif op == IADD: stack[-2] += stack[-1]; stack.pop(); pc += 1 elif op == ISUB: stack[-2] -= stack[-1]; stack.pop(); pc += 1 elif op == ILT: if stack[-2] < stack[-1]: stack[-2] = 1 else: stack[-2] = 0 stack.pop(); pc += 1 elif op == JZ: if stack.pop() == 0: pc = arg else: pc += 2 elif op == JNZ: if stack.pop() != 0: pc = arg else: pc += 2 elif op == JMP: pc = arg; elif op == HALT: break print 'Execution finished.' for i in xrange(26): if var[i] != 0: print '%c = %d' % (chr(i+ord('a')), var[i])
実際のコンパイラーであるコードジェネレーターを記述する必要があります。
コンパイラ
私たちの創造の冠。 ソースコードは次のとおりです。
class Compiler: program = [] pc = 0 def gen(self, command): self.program.append(command) self.pc = self.pc + 1 def compile(self, node): if node.kind == Parser.VAR: self.gen(IFETCH) self.gen(node.value) elif node.kind == Parser.CONST: self.gen(IPUSH) self.gen(node.value) elif node.kind == Parser.ADD: self.compile(node.op1) self.compile(node.op2) self.gen(IADD) elif node.kind == Parser.SUB: self.compile(node.op1) self.compile(node.op2) self.gen(ISUB) elif node.kind == Parser.LT: self.compile(node.op1) self.compile(node.op2) self.gen(ILT) elif node.kind == Parser.SET: self.compile(node.op2) self.gen(ISTORE) self.gen(node.op1.value) elif node.kind == Parser.IF1: self.compile(node.op1) self.gen(JZ); addr = self.pc; self.gen(0); self.compile(node.op2) self.program[addr] = self.pc elif node.kind == Parser.IF2: self.compile(node.op1) self.gen(JZ); addr1 = self.pc; self.gen(0) self.compile(node.op2) self.gen(JMP); addr2 = self.pc; self.gen(0) self.program[addr1] = self.pc self.compile(node.op3) self.program[addr2] = self.pc elif node.kind == Parser.WHILE: addr1 = self.pc self.compile(node.op1) self.gen(JZ); addr2 = self.pc; self.gen(0) self.compile(node.op2) self.gen(JMP); self.gen(addr1); self.program[addr2] = self.pc elif node.kind == Parser.DO: addr = self.pc self.compile(node.op1) self.compile(node.op2) self.gen(JNZ); self.gen(addr); elif node.kind == Parser.SEQ: self.compile(node.op1) self.compile(node.op2) elif node.kind == Parser.EXPR: self.compile(node.op1); self.gen(IPOP) elif node.kind == Parser.PROG: self.compile(node.op1); self.gen(HALT) return self.program
gen（）メソッドは、新しいバイト（コマンドまたは引数）をプログラム（バイトのリスト）に追加します。
compile（）メソッドは、プログラム全体をコンパイルします。 実際、このメソッドはノードのツリーを再帰的に走査します。 ノードのタイプごとに対応するコードが生成されます。
条件付きステートメントとループのトリックに注意してください。 JMP / JZの後、最初に0を書き込みます。ブランチ自体がコンパイルされ、このブランチを実行しないように行くべきアドレスがわかっている場合、値0は実際のアドレスに変更されます。
テスト中
ここに完全なコンパイラソースがあります。 スクリプトを使用して実行および確認しました（Lexerからstdinを読み取らせています）。
echo " i = 3;" | ./cc.py echo " { a=3; b=5; }" | ./cc.py echo " { a = 1; b = 2; c = a + b; }" | ./cc.py echo " { a = 5; b = 2; c = a - b; }" | ./cc.py echo " { a = 5; b = 2; c = b < a; }" | ./cc.py echo " { a = 5; if (a < 10) a = 33; }" | ./cc.py echo " { a = 5; if (10 < a) a = 33; else { a = 1; b = 2; } }" | ./cc.py echo " { a = 10; do { a = a - 2;} while (3 < a); }" | ./cc.py echo " { a = 1; b = 5; while (a < b) { a = a + 3; }}" | ./cc.py
車は正しい答えを出すように見えた。
次は？
コンパイラにはアプリケーションがありません。 しかし、経験は得られます。
コンパイラをさらに記述したいと思います。 次に、単純な構文の言語から始めることをお勧めします。 TinyBasicまたはPL / 0 。
他のコンパイラのソースを読みたい場合は、Bellard（ otcc ）、 tinyc 、 tcc 、 smallC 、 lccの作業に注意することをお勧めします。