3
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

pythonでx86コンパイラ自作(スタック指向言語編)

Forthコンパイラの記事が格好良くて触発されてしまい、Forth処理系を作った。
前回のC言語的なコンパイラと同様に、Pythonでx86-64のGNU Assembler向けのコードを出力する。

プロトタイプ実装

まずはとりあえず動くものをと思って最初に実装したのがこれ
初めてのアセンブリ言語の題材に良さそう。

forth_primitive.py
code = "6 3 + 2 - . 3 4 * 2 / 1 + . 2 3 drop dup dup 1 + + + 7 dup . . ."

def translator(token):
    if token.isdigit():
        print("    pushq $"+token)
    elif token == "+":
        print("    popq %rax")
        print("    addq %rax, (%rsp)")
    elif token == "-":
        print("    popq %rax")
        print("    subq %rax, (%rsp)")
    elif token == "*":
        print("    popq %rax")
        print("    imulq (%rsp), %rax")
        print("    movq %rax, (%rsp)")
    elif token == "/":
        print("    popq %rbx")
        print("    popq %rax")
        print("    cqto")
        print("    idivq %rbx")
        print("    pushq %rax")
    elif token == ".":
        print("    popq %rsi")
        print("    leaq IO, %rdi")
        print("    movq $0, %rax")
        print("    callq printf")
    elif token == "dup":
        print("    movq (%rsp), %rax")
        print("    pushq %rax")
    elif token == "drop":
        print("    addq $8, %rsp")

prologue = """\
    .text
    .globl main
main:
    pushq %rbp
    movq %rsp, %rbp
"""
epilogue = """\
    movq $0, %rax
    leaveq
    retq
    .data
IO:
    .string "%lld"
"""
print(prologue)
tokens = code.split()
for token in tokens:
    translator(token)
print(epilogue)

完成版

関数などを実装した完成版はここ

Forthの実装で特徴的なのは、演算のためのスタック(data stack)と、関数呼び出しのためのスタック(return stack)がそれぞれ必要なこと。
今回の実装では、data stackはrspレジスタでPUSH/POPしたけど、return stackは汎用レジスタとJMPを使って実装した。
(ちなみに、前述記事の実装では逆に、data stackを自前で用意して、return stackにCALL/RETを使っているみたい。)

呼び出すとき:

forth.py
    elif token in funcdict.keys():
        print("    addq $8, %r15")
        print("    leaq (_L"+str(label_id)+"), %rax")
        print("    movq %rax, (%r15)")
        print("    jmp "+token)
        print("_L"+str(label_id)+":")
        print("    subq $8, %r15")
        label_id += 1

戻ってくるとき:

forth.py
    elif token == ";":
        print("    movq (%r15), %rax")
        print("    jmp *%rax")

入れ子構造や再帰構造にも対応できることを確認。

test.fth
: sq dup * ;
: sqsq sq sq ;
3 sqsq . 

 ( >>> 81 )
test.fth
: factorial
    dup 1 > if 
    dup 1 - factorial * endif
;
5 factorial .

 ( >>> 120 )

あとCの関数呼び出しも実装した。
前述記事はWindows環境だけど、僕はLinux環境なのでSystem V ABIの呼出し規約に則って実装した。

forth.py
    elif token == "call": print("    callq "+tokens.pop(0))     
    elif token == "rax>": print("    pushq %rax")
    elif token == ">rdi": print("    popq %rdi")
    elif token == ">rsi": print("    popq %rsi")
f.c
#include <stdio.h>

int f(int a, int b){
    int c;
    c = a+b;
    printf("Hello form C!\n");
    return c;
}
test2.fth
: call_f
    >rdi >rsi
    call f
    rax>
;
200 100 call_f .

 ( >>> Hello from C! ) 
 ( >>> 300 ) 

今回の開発環境は以下の通り。

開発環境
   CPU: Intel(R) Core(TM) i7-4770HQ CPU @ 2.20GHz 64 bits
    OS: Ubuntu 14.04 LTS
   gcc: 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.3)
python: 3.6.0

感想

Forthは今回初めて触った。
最初はアセンブリ言語みたいな古代言語かと思いきや、意外と新食感だったかも。
Forth Standard 200x/16.1によると、"Forth is a language for direct communication between human beings and machines."とのこと。いいね。

参考資料

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
3
Help us understand the problem. What are the problem?