Rubyのコンパイラをデカルト言語を使って作りましょう。
しかし、フルセットの偉大なるrubyの仕様では、ちょっとここで作って説明するというわけにはいきませんし、私には完璧なRubyを作る知識も能力もございません。そこで、思い切り簡略化した仕様とします。
昔々、Tiny BASICという、とてもかわいいBASIC言語があったと聞きます。なんと、8bitプロセッサでメモリが4KBしかなくても動いたそうです。
Tiny BASICのような簡単で簡略化されたTiny Rubyのコンパイラを作ることとしましょう。簡略化の過程で本来のRubyのもつ特徴や長所が失われてしまいますが、ちょっと見た目が似ているソースがコンパイルできるくらいのものにはしてみましょう。
(Tiny Rubyのプログラムを手っ取り早く見たい人は、ダウンロードにリリースされている"example-0.7.0"を参照してください。 example/tinyrubyの下に完成版のTiny Rubyのコンパイラがあります。)
次に示すような仕様とします。
1. データ型は整数(int)のみ
2. 変数はローカル変数のみで、変数名は英字1文字でaからzまでのみ
3. 文の間は、;セミコロンか改行で区切られる。
4. printメソッドが使える。printメソッドの中で文字列が使える
5. 制御構文はif, whileが使える。elsifは使えない。
6. timesメソッドが使える。
7. メソッドとクラスの新規定義はできない。
8. 条件として比較演算は使えるがand, or, notのような論理演算は使えない。
9. コメントは、#から行末まで。
10. ソースコードを読み込み、Cのソースを出力する。
この仕様だと、以下のようなプログラムが書けるのですが、はたして、Rubyのソースに見えるでしょうか？
# Tiny Ruby の例題 a=1; b=2 c= a + b print "display ", c, "\n"; 10.times do print a a = a + 1 end print "\n"
このようなコンパイラが、デカルト言語では割と簡単につくることができるのです。
デカルト言語では、字句解析(入力ソースをトークンに分解する処理)は、非常に簡単に書けます。 トークンとは、"if", "else","end", 演算子, コンマ, セミコロン, 数字列, 変数などの構文を解析するときの、文字の塊の最小単位です。
"if", "else","end"といったような決まった固定された文字列の場合は、そのまま文字列として書けば良いです。
デカルト言語 - 並列ロジック プログラミング言語
edit "if"
"else"
"end"
演算子、コンマ、セミコロンも同様です。
"*" "-" "," ";"
実は、上のような英字だけのトークンや、記号１字のトークンの場合は、デカルト言語では""でくくる必要もありません。"if"でもifでも大丈夫です。両者は同じものとされます。 英字と記号が組み合わされたトークンでは、たとえばaの１番を表す"a-1"というトークンがあった場合、デカルト言語はa-1と書いてあるとトークンを aと-1に分解してしまうので"a-1"と""で括らなければならないのです。 しかし、今回のTiny Rubyでは、トークンがトークンであることを目立たせるために、基本的に英記号トークンは""でくくることとします。
数字列については、組み込み述語である<NUM>が使えます。
<NUM>
""で括られた文字列は、組み込み述語<STRINGS>が使えます。
変数は、小文字英字一文字と決めたのですが、このような可変な構造を持ったトークンを任意に設定するには、<TOKEN>述語を使います。<TOKEN>述語の引数に字句解析の構文を付けると任意のトークンを合成できます。ここでは、一定の範囲の文字を字句解析できる<RRANGE>組み込み述語を使うことにしましょう。
<TOKEN _ <RANGE _ a z>>
これで、aからz までの一文字を抜き出します。_は無名変数であり、字句解析した結果が設定されます。 しかし、今回の場合は、TOKENの無名変数には、RANGEの無名変数と同じものが設定されることになります。よって、TOKEN述語は無くても問題ないため、変数はRANGE述語だけで構成することになります。
<RANGE _ a z>
詳しくは、次の「3. Tiny Rubyの構文解析」を見てから、もう一度本項を見ると分かりやすいと思います。
さっそくですが、Tiny Rubyの構文をデカルト言語で書いてみます。
<TinyRuby> <プログラム> <EOF>;
<プログラム> {[<実行文> { ";" <実行文> } ] (<コメント> | <CR>) };
<実行文> <if文> | <while文> | <print文> | <times文> | <代入文> | <数式>;
<if文> "if" <条件式> <プログラム> [ "else" <プログラム> ] "end";
<while文> "while" <条件式> <プログラム> "end";
<times文> (<NUM> | <変数>) "." "times" "do" <プログラム> "end";
<print文> "print" <表示項目> { "," <表示項目> } ;
<表示項目> (<STRINGS> | <NUM> | <数式> );
<代入文> <変数> "=" <数式>;
<数式> <expradd>;
<expradd> <exprmul> { "+" <exprmul> | "-" <exprmul> };
<exprmul> <exprID> { "*" <exprID> | "/" <exprID> };
<exprID> "+" <exprterm> | "-" <exprterm> | <exprterm>;
<exprterm> "(" <数式> ")" | <NUM> | <変数>;
<条件式> <数式> (">=" | ">" | "==" | "!=" | "<=" | "<") <数式>;
<変数> <RANGE _ a z>;
<コメント> "#" <SKIPCR>;
文法規則を書いただけのようにも見えますが、デカルト言語では、この規則をプログラムとして直接受け付けることができます。
これで、「1. Tiny Rubyの仕様」で日本語で書かれていたときには曖昧であった部分がなくなり、Tiny Rubyの言語仕様が厳密に定義されました。 どのような構文をどのような順序で、何を書けばよいのかがすべて定義されているのです。
ただし、これは、構文を定義したものであり、まだ、コンパイル結果を出力する機能は付けてない状態です。これだけでは、Tiny Rubyのソースを入力しても、コンパイルはできません。コンパイル結果を出力する部分や、入力ファイルを準備してこの構文にインプットする部分のプログラムが必要となります。
詳細な説明は、次項で行っていきます
順番に構文を見ていきましょう。
<TinyRuby> <プログラム> <EOF>;
これは、TinyRubyは、プログラムと最後のEOFでできていることを表しています。
EOFとは、End Of Fileのことでソースファイルの末尾に来たことを意味します。
<プログラム> {[<実行文> { ";" <実行文> } ] (<コメント> | <CR>) };
｛｝の括弧は０回以上の繰り返しを意味します。
プログラムは、実行文をセミコロン(;)か改行で区切ったものの繰り返しです。
プログラムの後ろにはコメントが付けられます。実行文がないコメントだけの行もありえます。
<実行文> <if文> | <while文> | <print文> | <times文> | <代入文> ;
実行文は、if文、while文、print文、times文、代入文のいずれかです。
<if文> "if" <条件式> <プログラム> [ "else" <プログラム> ] "end";
[]の括弧は省略可能であることを意味します。
if文は、見てのとおりです。elseは省略できます。
<while文> "while" <条件式> <プログラム> "end";
<times文> (<NUM> | <変数>) "." "times" "do" <プログラム> "end";
<print文> "print" <表示項目> { "," <表示項目> } ;
while, times, printも、構文の並びをそのまま表示しているだけです。 times文で、先頭が数字NUMか変数しか使えないのは大きな制限です。
<数式> <expradd>;
<expradd> <exprmul> { "+" <exprmul> | "-" <exprmul> };
<exprmul> <exprID> { "*" <exprID> | "/" <exprID> };
<exprID> "+" <exprterm> | "-" <exprterm> | <exprterm>;
<exprterm> "(" <数式> ")" | <NUM> | <変数>;
数式は、優先度の低いほうから高いほうに向かって処理を積み上げています。
最も優先度の高いのはexptermであり、（）で括られた数式や数値と変数を処理します。
次に単項の+-を処理するexprIDです。+1とか-aとかの符号付きの項目を処理します。
次がexprmulの乗除算であり、最後がexpraddの加減算となります。数式の処理では、掛け算と割り算を足し算と引き算より優先して計算しますね。
<変数> <RANGE _ a z>;
変数は、aからzまでの小文字とするために、デカルト言語特有のRANGE述語を使って字句解析します。RANGEは２つの引数の範囲にある文字と合致します。
<コメント> "#" <SKIPCR>;
コメントは#から、改行までです。SKIPCRは、改行まで構文解析を行わずにスキップさせます。
その他構文は、ほぼそのまま構文を並べているだけです。
では、この構文の定義に実際にコンパイルするための処理を追加しましょう。
前項で作成した構文プログラムに、ソースをコンパイルした結果を出力する機能を付けていきます。
print述語とprintf述語で、該当する文法に対するコンパイル結果を出力します。
print述語は、単純な文字列の出力に使われ、自動的に出力後に改行されます。
printf述語は、引数に%フォーマットと\エスケープシーケンスを使って、可変な引数を柔軟に出力するのに使います。 たとえば、C言語でprintf("%d\n", num);は、デカルト言語では、<printf <%_"%d" num> <\_n>>となります。
３つめのインデントでprint系の処理を行っているところがC言語の結果を出力しているところです。元のRuby言語のソースがどのようなC言語のソースに変換されているかを想像しながら見てください。
「３．Tiny Rubyの構文解析」の構文と見比べると、分かりやすいかも知れません。
最初に、<TinyRuby>を実行したときの処理について示します。
<TinyRuby> <print "#include <stdio.h>">
<print "int main() {">
<print "int a,b,c,d,e,f,g,h,i,j,k,l,m;">
<print "int n,o,p,q,r,s,t,u,v,w,x,y,z;">
<プログラム> <EOF> <print "exit(0);">
<print "}">
;
この部分は、Tiny Rubyの初期化と終了処理を行っています。
実行されると次に示すようなC言語に変換されます。
#include <stdio.h>
int main() {
int a,b,c,d,e,f,g,h,i,j,k,l,m;
int n,o,p,q,r,s,t,u,v,w,x,y,z;
途中の処理(<プログラム> <EOF>)
exit(0);
}
変数はすべて事前に定義しています。 途中の処理には、Tiny Rubyのプログラムをコンパイルした結果が入ります。
<プログラム> {[<実行文> { ";" <実行文>}] (<コメント> | <CR>)};
<実行文> <if文> | <while文> | <print文> | <times文> | <代入文> ;
上記の２つの処理には、とくにコンパイル結果を出力する処理はありません。
<if文> "if" <printf "if (">
<条件式> <printf ") {" <\_n>>
<プログラム>
[
"else" <printf "} else {" <\_n>>
<プログラム>
]
"end" <printf "}" <\_n>>
;
if文は、以下のようなC言語に変換されます。
if(条件式) {
プログラム
}
条件式とプログラムの部分は、後に説明する<条件式>と<プログラム>に記述されている処理が変換されて展開されます。
else節がある場合には以下のようなC言語に変換されます。
if(条件式) {
プログラム
} else {
プログラム
}
次はwhile文を見ていきましょう。
<while文> "while" <printf "while (">
<条件式> <printf ") {" <\_n>>
<プログラム>
"end" <printf "}" <\_n>>
;
while文は、以下のようなC言語の出力を生成させます。
while(条件式){
プログラム
}
どんどん行きます。次はtimesメソッドです。
<times文> (<NUM #n> | <変数 #n>)
"." "times" <printf "{int ct; for (ct=0; ct<">
<printf #n>
<printf "; ct++) {" <\_n>>
"do"
<プログラム>
"end" <printf "}}" <\_n>>
;
timesメソッドは、for文に変換されるのですが、ループ回数をどうやって制御するかが問題となります。
ここではカウンタとして変数ctをローカルな変数として使います。このように{int ct; ～}としておくと、複数のtimesメソッドをネストさせても大丈夫です。
以下のようにC言語に変換されます。
{
int ct;
for (ct=0; ct<回数; ct++) {
プログラム
}
}
print文は、文字列STRINGS, 数値NUM, 変数を表示できるようにprintf文に展開されます。
<print文> "print" <表示項目> {"," <表示項目>};
<表示項目>
<STRINGS #s>
<printf 'printf("%s", "' #s '");'
<\_n>>
| <NUM #n>
<printf 'printf("%d", ' #n ');'
<\_n>>
| <変数 #v>
<printf 'printf("%d", ' #v ');'
<\_n>>
;
次は代入文です。 変数と=と数式で構成されます。
<代入文> <変数 #v>
"=" <printf #v>
<printf " = ">
<数式> <printf ";" <\_n>>
;
C言語では、以下のようになります。
変数 = 数式;
数式は、Tiny Rubyの構文の中では最も複雑なものです。 しかし、どのようなC言語に変換されるか想像しながら、ひとつひとつ変換のためのprintf文を追加していけば、実はそんなに複雑でもありません。
<数式> <expradd>;
<expradd> <exprmul>
{ "+" <printf "+">
<exprmul>
| "-" <printf "-">
<exprmul>
}
;
<exprmul> <exprID>
{ "*" <printf "*">
<exprID>
| "/" <printf "/">
<exprID>
| "/" <printf "/">
<exprID>
}
;
<exprID> "+" <exprterm>
| "-" <printf "-">
<exprterm>
| <exprterm>
;
<exprterm> "(" <printf "(">
<数式>
")" <printf ")">
| <NUM> <GETTOKEN #n>
<printf #n>
| <変数 #v> <printf #v>
;
<条件式> <数式>
(">=" | ">" | "==" | "!=" | "<=" | "<")
<GETTOKEN #op>
<printf #op>
<数式>
;
<変数 #x>
<RANGE #x a z>
;
最後です。
コメントは、デカルト言語の改行まで読み飛ばすSKIPCR述語を使います。
そのためコメント部分は、C言語として何もは出力されません。
<コメント> "#" <SKIPCR>
;
これでC言語へ変換する構文を一通り追加しました。お疲れさまです。
次は、コンパイルするために入力ソースと出力ファイルを処理する部分を追加します。
コンパイラ本体である<TinyRuby>は以下の処理から起動されます。
<compile>
::sys<args #x>
::sys<nth #inputfile #x 1>
::sys<suffix #outputfile #inputfile c>
<print inputfile #inputfile>
<print outputfile #outputfile>
::sys<openw #outputfile
::sys<openr #inputfile <TinyRuby>>>
;
?<compile>;
順に説明していきましょう。
1. args述語は、コマンドラインの引数を変数#xに設定してます。
2. 次のnth述語はargsで得た引数の２つ目(nthでは最初の要素が0から始まる)を取り出して入力ファイル#inputfileに設定しています。
3. suffix述語は#inputfileの拡張子をcに変換して、出力ファイル#outputfileに設定します。
4. printで入力ファイルと出力ファイルを画面に表示します。
5. openw述語で出力ファイルをオープンし、openr述語で入力ファイルをオープンして、コンパイラ本体であるTinyRuby述語を呼び出します。
6. ?<compile>で、上の処理を実行しています。
これですべての処理の説明が終わりました。
ソース全体をここに置きます。
<compile>
::sys<args #x>
::sys<nth #inputfile #x 1>
::sys<suffix #outputfile #inputfile c>
<print inputfile #inputfile>
<print outputfile #outputfile>
::sys<openw #outputfile
::sys<openr #inputfile <TinyRuby>>>
;
<TinyRuby> <print "#include <stdio.h>">
<print "int main() {">
<print "int a,b,c,d,e,f,g,h,i,j,k,l,m;">
<print "int n,o,p,q,r,s,t,u,v,w,x,y,z;">
<プログラム> <EOF> <print "exit(0);">
<print "}">
;
<プログラム> {[<実行文> { ";" <実行文>}] (<コメント> | <CR>)};
<実行文> <if文> | <while文> | <print文> | <times文> | <代入文> ;
<if文> "if" <printf "if (">
<条件式> <printf ") {" <\_n>>
<プログラム>
[
"else" <printf "} else {" <\_n>>
<プログラム>
]
"end" <printf "}" <\_n>>
;
<while文> "while" <printf "while (">
<条件式> <printf ") {" <\_n>>
<プログラム>
"end" <printf "}" <\_n>>
;
<times文> (<NUM #n> | <変数 #n>)
"." "times" <printf "{int ct; for (ct=0; ct<">
<printf #n>
<printf "; ct++) {" <\_n>>
"do"
<プログラム>
"end" <printf "}}" <\_n>>
;
<print文> "print" <表示項目> {"," <表示項目>};
<表示項目>
<STRINGS #s> <printf 'printf("%s", "' #s '");' <\_n>>
| <NUM #n> <printf 'printf("%d", ' #n ');' <\_n>>
| <変数 #v> <printf 'printf("%d", ' #v ');' <\_n>>
;
<代入文> <変数 #v>
"=" <printf #v>
<printf " = ">
<数式> <printf ";" <\_n>>
;
<数式> <expradd>;
<expradd> <exprmul>
{ "+" <printf "+">
<exprmul>
| "-" <printf "-">
<exprmul>
}
;
<exprmul> <exprID>
{ "*" <printf "*">
<exprID>
| "/" <printf "/">
<exprID>
}
;
<exprID> "+" <exprterm>
| "-" <printf "-">
<exprterm>
| <exprterm>
;
<exprterm> "(" <printf "(">
<数式>
")" <printf ")">
| <NUM> <GETTOKEN #n>
<printf #n>
| <変数 #v> <printf #v>
;
<条件式> <数式>
(">=" | ">" | "==" | "!=" | "<=" | "<")
<GETTOKEN #op>
<printf #op>
<数式>
;
<変数 #x>
<RANGE #x a z>
;
<コメント> "#" <SKIPCR>
;
?<compile>;
前項で示したTiny Rubyコンパイラをファイルtinyrubyとして保存してください。 ここでは、例としてRubyのソースとして、trb1.rbを例題として使います。
trb1.rbには以下を保存しておいてください。
# Tiny Ruby example No.1
a=1; b=2
c= a + b
print "display ", c, "\n";
10.times do
print a
a = a + 1
end
print "\n"
実行します。
1. デカルト言語の引数にtinyrubyのプログラムとコンパイルするRubyソースを指定します。
$ descartes tinyruby trb1.rb
2. ソースに指定したRubyソースの拡張子を c に変換したC言語のソースが出力されているはずです。 それを、Cコンパイラでコンパイルします。
$ gcc trb1.c -o trb1
3. 出来上がったプログラムを実行してみてください。
$ ./trb1 display 3 12345678910
4. 試しに本家ホンモノのrubyで実行してみます。
$ ruby trb1.rb display 3 12345678910
同じ結果が出ました。感激です。
「8. Tiny Rubyの実行」で、trb1.rbをコンパイルした結果出力であるtrb1.cの中身を見てみましょう。
#include <stdio.h>
int main() {
int a,b,c,d,e,f,g,h,i,j,k,l,m;
int n,o,p,q,r,s,t,u,v,w,x,y,z;
a = 1;
b = 2;
c = a+b;
printf("%s", "display ");
printf("%d", c);
printf("%s", "\n");
{int ct; for (ct=0; ct<10; ct++) {
printf("%d", a);
a = a+1;
}}
printf("%s", "\n");
exit(0);
}
インデントが無く読みづらいですが、確かにC言語のソースに見えます。
タブを適切に入れてインデントを直してみます。
#include <stdio.h>
int main()
{
int a, b, c, d, e, f, g, h, i, j, k, l, m;
int n, o, p, q, r, s, t, u, v, w, x, y, z;
a = 1;
b = 2;
c = a + b;
printf("%s", "display ");
printf("%d", c);
printf("%s", "\n");
{
int ct;
for (ct = 0; ct < 10; ct++) {
printf("%d", a);
a = a + 1;
}
}
printf("%s", "\n");
exit(0);
}
どうでしょうか、元のTiny Rubyのソースが、C言語のソースに変換されているのが分かるでしょうか。
実は、デカルト言語で作成したコンパイラには、ある弱点があります。
それについは、「デカルト言語によるコンパイラ言語の作成: 続Tiny Rubyコンパイラの作成(2)」で対応策も含めて説明したいと思います。
[PageInfo]
LastUpdate: 2010-04-10 10:45:02, ModifiedBy: hniwa
[License]
Creative Commons 2.1 Attribution
[Permissions]
view:all, edit:login users, delete/config:login users