ここでは、コンパイラー作成の分野の重要な概念を実際に示してみました。 このような15分間の完成したストーリーは、複雑なトピックに飛び込む良い方法になる可能性があります。 以下に示されているものを受動的に読むのではなく、作業中のコードをチェックするのがいいだけです。

最初のエクスペリエンスが成功した場合、将来的にはコンパイラのテーマに関する他の15分間の「スケッチ」が期待できます。

議論されること

算術式コンパイラを作りましょう。 逆ポーランド記法 （RPNまたはPOLIZとも呼ばれる）のソーステキストを、スタックで動作する中間コードに変換するもの。 しかし、ここでは通訳なしで行うことができます。 次に、結果をすぐにC表現に変換します。 つまり、RPNからCへのコンパイラを取得します。

ところで、コンパイラーをPythonで作成します。 しかし、他のプログラミング言語を好む人を止めないようにしましょう。 以下の演習が役立ちます。以下のコードをお気に入りの言語に翻訳してください。 または、すでに完成した翻訳を使用します。

F＃実装（ gsomixによる ）：

最初のバージョン

SSAバージョン

解析から始めましょう

def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで何をしましたか？ スキャン機能は、ユーザーから逆ポーランド表記（「2 2 +」）で文字列を受け取ります。

出力では、中間表現を取得します。 以下に例を示します。

 [ ('Push', 2), ('Push', 2), ('Op', '+') ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そのため、すでにコンパイラを入手しています。 しかし、彼は非常に軽薄です。 最初はCコードについてだったことを思い出してください。

Cで放送しましょう

 def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで何が起こっていますか？ この関数の出力を見てみましょう（「2 2 +」と同じ例を使用）。

 st[sp] = 2; sp += 1; st[sp] = 2; sp += 1; st[sp - 2] = st[sp - 2] + st[sp - 1]; sp -= 1;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

はい、すでにCコードのように見えます。 配列stはスタックの役割を果たし、spはそのポインターです。 通常、仮想スタックマシンはこれらのもので動作します。

それはただのマシンそのものです-通訳、私たちは持っていません。 コンパイラがあります。 何を残しましたか？ Cプログラムに必要なフレームを追加する必要があります。

初めて完成したコンパイラ

 ST_SIZE = 100 C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { int st[%d], sp = 0; %s printf("%%d\n", st[sp - 1]); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code) def rpn_to_c(source): return C_CODE % (ST_SIZE, trans(scan(source))) print(rpn_to_c("2 2 +"))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このプログラムの出力をCコンパイラでコンパイルします。

続行する準備はまだできていますか？ それから、私たちが何をしたかを議論しましょう。 疑わしい点が1つあります。コンパイラーは定数式を変換し、コンパイル段階で簡単に計算できます。 それらをコードに変換しても意味がありません。 しかし、とりあえず、いくつかの引数が外部からスタックに到達できるようにしてみましょう。 私たちの開発の実際的な意味は後で与えることができるという事実に焦点を当てましょう。 今、最も単純なコンパイラを構築するという一般的なアイデアを得ることが重要ですよね？

SSAフォームコンパイラ

あなたは見出しが好きですか？ SSA-これはどのコンパイラにとっても非常に堅実に聞こえます。 そして今、この同じSSAを使用します。 これは何？ 順番に移動しましょう。

現在、仮想マシンなしでCコードを生成しています。 しかし、なぜスタック操作という形の基本が必要なのでしょうか？ これらの操作をCからの通常の変数での作業に置き換えましょう。 さらに、変数を保存しません-各式に新しい名前を付けます。 Cコンパイラにこれらすべてを処理させます。 各変数に値が1回だけ割り当てられることがわかります。 ところで、これはSSAの形式です。

これが新しいコンパイラです。

 C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { %s printf("%%d\n", %s); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): stack, code = [], [] name_cnt = 0 for tag, val in ir: if tag == "Push": code.append("int t%d = %d;" % (name_cnt, val)) stack.append("t%d" % name_cnt) name_cnt += 1 elif tag == "Op": a, b = stack.pop(), stack.pop() code.append("int t%d = %s %s %s;" % (name_cnt, b, val, a)) stack.append("t%d" % name_cnt) name_cnt += 1 return "\n".join(code), stack.pop() def rpn_to_c(source): return C_CODE % trans(scan(source)) print(rpn_to_c("2 2 +"))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Cコードにはスタックがなくなり、翻訳中にスタックの操作がシミュレートされることに注意してください。 コンパイルプロセスで使用されるスタックには値は含まれませんが、変数名が含まれます。

最終結果は次のとおりです。

 #include <stdio.h> int main(int argc, char** argv) { int t0 = 2; int t1 = 2; int t2 = t0 + t1; printf("%d\n", t2); return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まとめ

共同レッスンの時間が切れたようです。 私たちはプログラムをある言語から別の言語に翻訳することに従事していました。 これは、ソースからソースへの変換と呼ばれます。 または-単なる翻訳。コンパイルの同義語と見なすことができますが、通常、コンパイラはプログラムを高レベルの表現から低レベルの表現に変換します。 ソースからソースへの翻訳者向けの「トランスパイラー」という流行語もあります。 しかし、「トランスパイラー」についての言及は、コンパイラーの専門家にとって面倒な場合があります。注意してください！

コードを試してください。 フィードバックを待っています！