GAME言語からCへ変換するコンパイラをpythonで書いてみました。正確に言うとトランスパイラですが。

GAME言語コンパイラ - miep2.py

./miep2.py file.gm >out.cとすると、GAME言語で書かれたfile.gmをCのソースに変換し、out.cに出力します。

本当はMIEP2ではなく、MIEPにしたいのですが、MIEPという名前は、43年前に中学生の僕と師匠の浜田さんがMicro Integer Expression Processorとして、自作のゲーム言語互換インタプリタ・コンパイラシステムに既に名付けていたので、2が付きました。

out.cはccでコンパイル可能です。 cc out.c -o a.out、./a.outで実行することが出来ます。

一般に冗長さを許せば、低級なプログラム言語で書かれたソースは、より高級なプログラム言語に翻訳することが容易です。

C言語はチューリング完全です。GAME言語はチューリング完全かどうかですが、brainfuckがチューリング完全で、GAME言語でbrainfuckの全てのインストラクションが記述できるので、GAME言語もチューリング完全です。

最適化はできていません。エラーチェックが甘いです。
ccのインラインアセンブラを使用しているので、x86_64 linuxシステム用です。
!=n(gosub)と] (ret) が機械依存部で、それ以外は機械独立です。完全に機械独立にし、一般のCコンパイラに掛けることができるようにすることが今後の課題ですが、C言語の仕様上、サブルーチン呼び出しを記述するのは難しいかも知れません。

一応完成
version 1.0.0 2024/8/26

ちょっとヴァージョンアップ、改名。
version 1.0.1 2024/8/27

今後の課題の問題点

・for-next,do-untl文の、for文またはdo文一つに対して複数のnext文、until文がある場合には対応していません。
・for-next文の制御変数に配列が使えない
・for文の終値に変数を使うと、カウントアップとして扱われる。
・next文に２重以上の括弧があるとバグる。

本体

miep2.py


#!/usr/bin/python3
import sys
import re
lines=[]
cp=0
loopstack=[]
def out_header():
    print("#include <stdio.h>")
    print("#include <stdlib.h>")
    print("#include <string.h>")
    print("static short A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;")
    print("static unsigned char memory[65536]={0};")
    print("static int tmp,reminder;")
    print("static char buff[100]={0};")
    print("int itoa(char *s,int v) {if (v){int i=0,r;for(r=v;r/=10;i++);itoa(s,v/10);s[i++]=v%10+48;s[i]=0;}}");
    print("void pretprt(short c,short v) { itoa(buff,v); for(short j=0;j<c-strlen(buff);j++) printf(\" \"); printf(buff); }")
    print("void main() {")
    return

def out_tailer():
    print("}")
    return


def gethexstr(s,idx):
    d="0x"
    while idx<len(s) and s[idx] in '0123456789ABCDEF':
        d=d+s[idx]
        idx+=1
    return (d,idx)

def getdcmstr(s,idx):
    d=""
    while idx<len(s) and s[idx] in "0123456789":
        d=d+s[idx]
        idx+=1
    return (d,idx)

def term(s,idx):
    u=''
    if idx>=len(s):
        return s,-1

    if s[idx]=='(':
        (o,idx)=expression(s,idx+1)

        if s[idx]==')':
            idx+=1
        return ("("+o+")",idx) # normal end.

    elif s[idx]=='$' and idx+1<len(s) and s[idx+1].upper() in "0123456789ABCDEF":
        (o,idx)=gethexstr(s,idx+1)
        return (o,idx)

    elif s[idx] in "0123456789":
        (o,idx)=getdcmstr(s,idx)
        return (o,idx)

    elif s[idx]=='-':
        (o,idx)=term(s,idx+1)
        return "-"+o,idx

    elif s[idx]=='+':
        (o,idx)=term(s,idx+1)
        return "(+("+o+"))",idx

    elif s[idx]=='#':
        (o,idx)=term(s,idx+1)
        return "!("+o+")",idx

    elif s[idx]=='\'':
        (o,idx)=term(s,idx+1)
        u="(rand()%("+o+"))"
        return u,idx

    elif s[idx]=='%':
        (o,idx)=term(s,idx+1)
        u="(reminder)"
        return u,idx+1

    elif s[idx]=='$' and not xdigit(s[idx+1]):
        return "getchar()",idx+1

    elif s[idx]=='"':   # 文字定数
        return "'"+s[idx+1]+"'",idx+2

    elif s[idx]=='?':
        u="(scanf(\"%d\",&tmp),(short)tmp)"
        return u,idx+1

    elif s[idx].upper()>='A' and s[idx].upper()<='Z':
        if (idx+1)<len(s) and s[idx+1]==':': # 8 bit array
            l=s[idx].upper()
            p,idx=expression(s,idx+2)
            o="memory["+l+"+"+p+"]"
            return o,idx

        elif (idx+1)<len(s) and s[idx+1]=='(': # 16 bit array
            l=s[idx].upper()
            p,idx=expression(s,idx+1)
            o="*((short *)(&memory["+l+"+("+p+"*2)]))"
            return o,idx

        else: # variable
            idx+=1
            return (s[idx-1].upper()),idx
    return s,idx+1

def expression(s,idx):
    (o,idx)=term(s,idx)
    w=o
    while True:
        if idx>=len(s):
            break
        if s[idx]=='+':
            op='+'
            idx+=1
        elif s[idx]=='-':
            op='-'
            idx+=1
        elif s[idx]=='/':
            op='/'
            idx+=1
        elif s[idx]=='*':
            op='*'
            idx+=1
        elif s[idx]=='=':
            op='=='
            idx+=1
        elif s[idx:idx+2]=='<>':
            op='<>'
            idx+=2
        elif s[idx:idx+2]=='<=':
            op='<='
            idx+=2
        elif s[idx:idx+2]=='>=':
            op='>='
            idx+=2
        elif s[idx]=='<':
            op='<'
            idx+=1
        elif s[idx]=='>':
            op='>'
            idx+=1
        else:
            break
        (v,idx)=term(s,idx)
        if op=='/':
            return ("((reminder="+w+"%"+v+"),("+w+"/"+v+"))",idx)
        w="("+w+op+v+")"
    return w,idx

def value(s,idx):
    return(int(s[idx:]))

def parse(l):
    global loopstack
    index=0
    while index<len(l):
        s=l[index]
        index+=1

        # Statements

        if s[0:2]=='#=':
            goto(value(s,2))

        elif s[0:2]=='!=':
            gosub(value(s,2))

        elif s[0:2]==';=':
            (o,idx)=expression(s,2)
            if__(o)

        elif s[0:3]=='??=':
            (o,idx)=expression(s,3)
            print(f"printf(\"%04x\",{o}); ",end='')

        elif s[0:3]=='?$=':
            (o,idx)=expression(s,3)
            print(f"printf(\"%02x\",{o}); ",end='')

        elif s[0:2]=='$=':
            (o,idx)=expression(s,2)
            print(f"printf(\"%c\",{o}); ",end='')

        elif s[0:2]=='.=':
            (o,idx)=expression(s,2)
            print(f"for(int i=0;i<{o};i++) printf(\" \"); ",end='')

        elif s[0:2]=='\'=':
            (o,idx)=expression(s,2)
            print(f"srand({o}); ",end='')

        elif s[0:2]=='?(':
            o,idx=getdcmstr(s,2)
            o=int(o)
            if s[idx:idx+2]==')=':
                idx+=2
                p,idx=expression(s,idx)
                print(f"pretprt((short){o},(short){p}); ",end='')
            else:
                pass
            pass

        elif s[0]==']':
            ret()

        elif s[0]=='"':
            print(f"printf({s}); ",end='')

        elif s[0]=='/':
            idx=0
            while idx<len(s) and s[idx]=='/':
                print("printf(\"\\n\"); ",end='')
                idx+=1

        elif s[0].upper()>='A' and s[0].upper()<='Z':
            if s[1]==':': # 8bit array
                ch=s[0].upper()
                v,idx=expression(s,2)
                if s[idx:idx+2]==')=':
                    idx+=2
                    w,idx=expression(s,idx)
                    print("memory["+ch+"+"+v+"]=",end='')
                    print(f"{w}; ",end='')

            elif s[1]=='(': # 16 bit array
                ch=s[0].upper()
                v,idx=expression(s,2)
                if s[idx:idx+2]==')=':
                    idx+=2
                    w,idx=expression(s,idx)
                    print("*((short *)(&memory["+ch+"+"+v+"*2]))=",end='')
                    print(f"{w}; ",end='')

            elif s[1]=='=': # assignment
                ch=s[0].upper()
                (o,idx)=expression(s,2)
                print(f"{ch}={o};",end='')
                if idx<len(s) and s[idx]==',': # for
                    (p,idx)=expression(s,idx+1)
                    print("while(1) { if (!(",end='')

                    try:
                        a,b=eval(o),eval(p)
                    except:
                        ies='<'
                    else:
                        ies='<' if a<b else '>'

                    print(f"{ch}{ies}={p})) break; ",end='')
                    loopstack+=["for"]
            else:
                pass

        elif s[0:3]=='@=(':
            i=loopstack.pop(-1) if loopstack else None

            if i=="do": # until
                v,idx=expression(s,2)
                print("} ",end='')
                print(f"while(!{v}); ",end='')

            elif i=="for": # next
                ch=s[3].upper()
                v,idx=expression(s,2)
                print(f"{ch}={v}; ",end='')
                print("} ",end='')

        elif s[0:2]=='@=': # next
            i=loopstack.pop(-1) if loopstack else None
            ch=s[2].upper()

            if i=="for":
                v,idx=expression(s,2)
                print(f"{ch}={v}; ",end='')
                print("} ",end='')

        elif s[0]=='@': # do
            print("do { ",end='')
            loopstack+=["do"]

        elif s[0:2]=='?=':
            v,idx=expression(s,2)
            print(f"printf(\"%d\",{v}); ",end='')

        else:
            pass
    return

def adjust_go(n):
    for i in lines:
        if i>=n:
            return i
    return -1

def ret():
    print("__asm__ (\"ret\" : : :); ",end='')

def if__(o):
    print(f"if (!({o})) ",end='')
    goto(cp+1)
    return

def gosub(n):
    print(f"__asm__ goto(\"call %l[l{adjust_go(n)}]\" : : : :l{adjust_go(n)}); ",end='')
    return

def goto(n):
    if n==-1:
        print("return; ",end='')
        return
    print(f"goto l{adjust_go(n)}; ",end='')
    return

def getl(line):
    ln=line.replace('\n','')
    split_s=re.split(r'\s+(?=(?:[^"]*"[^"]*")*[^"]*$)',ln)
    s=[i for i in split_s if i]
    try:
        n=int(s[0])
    except:
        return (-1,[""])
    else:
        return (n,s[1:])

def pass1(file):
    global lines
    f=open(file,"rt")
    while True:
        l=f.readline()
        if not l:
            break
        (n,s)=getl(l)
        if n==-1:
            pass
        else:
            lines+=[n]
    f.close()
    return

def pass2(file):
    global lines,cp
    f=open(file,"rt")
    while True:
        l=f.readline()
        if not l:
            break
        (n,s)=getl(l)
        if n==-1:
            pass
        else:
            print(f"l{n}: ",end='')
            cp=n
            if s:
                parse(s)
            print("")
    f.close()
    return

def compile(file):
    pass1(file)
    pass2(file)

def main():
    out_header()
    compile(sys.argv[1])
    out_tailer()
    return

if __name__=='__main__':
    if len(sys.argv)!=2:
        print("Usage: miep2.py file.gm >out.c")
        exit(1)
    main()
    exit(0)

サンプルプログラム素数発生

sieve.gm

#!/usr/bin/gamec
1*** sieve.gm エラトステネスの篩により素数を求めるプログラム
2*** アルゴリズムは、「C言語による標準アルゴリズム事典」奥村晴彦著によります。
6*** 
10  "Primes up to " M=? N=(M-3)/2
20  F=0
100  C=1
110  "2 "
120  J=0,N F:J)=1 @=J+1
150  J=0,N
160     ;=#F:J) #=200
170         P=J*2+3
175         Z=P !=230
180         ;=J+P<=N K=J+P,N F:K)=0 @=K+P
190         C=C+1
200  @=J+1
210 / ?=C " PRIMES" /
220 #=-1
230 ?=Z " " ]

コンパイル後のコード

sieve.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static short A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;
static unsigned char memory[65536]={0};
static int tmp,reminder;
static char buff[100]={0};
int ia(char *s,int v) {if (v){int i=0,r;for(r=v;r/=10;i++);ia(s,v/10);s[i++]=v%10+48;s[i]=0;}}
void pretprt(short c,short v) {
ia(buff,v); 
for(short j=0;j<c-strlen(buff);j++) printf(" "); 
printf(buff); 
}
void main() {
l10: printf("Primes up to "); M=(scanf("%d",&tmp),(short)tmp);N=((reminder=((M-3))%2),(((M-3))/2));
l20: F=0;
l100: C=1;
l110: Z=2;__asm__ goto("call %l[l230]" : : : :l230); 
l120: J=0;while(1) { if (!(J<=N)) break; memory[F+J]=1; J=(J+1); } 
l150: J=0;while(1) { if (!(J<=N)) break; 
l160: if (!(!(memory[F+J]))) goto l170; goto l200; 
l170: P=((J*2)+3);
l175: Z=P;__asm__ goto("call %l[l230]" : : : :l230); 
l180: if (!(((J+P)<=N))) goto l190; K=(J+P);while(1) { if (!(K<=N)) break; memory[F+K]=0; K=(K+P); } 
l190: C=(C+1);
l200: J=(J+1); } 
l210: printf("\n"); printf("%d",C); printf(" PRIMES"); printf("\n"); 
l220: return; 
l230: pretprt((short)4,(short)Z); printf(" "); __asm__ ("ret" : : :); 
}

実行結果

$ ./miep2.py sieve.gm >t.c
$ cc t.c
$ ./a.out
Primes up to 1000
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 
168 PRIMES
$

一言

僕はもう、疲労困憊らです。

参考文献など

ゲーム言語ドキュメント
コンパイラ構成論　近代科学社