デカルト言語 - 並列ロジック プログラミング言語
edit[FrontPage ← 先頭のページに戻る]
== Tiny Pythonコンパイラの作成
Pythonのコンパイラをデカルト言語を使って作りましょう。
デカルト言語では、Tiny Rubyを以前に作成しています。
ここでは、同様に仕様を簡略化した、Tiny Pythonを作成します。
Tiny Rubyと同様に思い切り簡略化した仕様とします。
なお、Tiny Rubyでの記述とオーバーラップする部分もありますが、
ここのTiny Pythonについての記述は、こちらを単独で読んでも分かるように記述
していきましょう。
Tiny Rubyの記述を既にお読みの方は、共通部分や相違部分について考えながら
読んでいくと面白いと思います。
(なお、最新のリリース0.14.0でないと動かないのでご注意ください。)
=== 1. Tiny Pythonの仕様
次に示すような仕様とします。
[[BR]]
1. データ型は整数(int)のみ
2. 変数はローカル変数のみで、変数名は英字1文字でaからzまでのみ
3. 文の間は、;セミコロンか改行で区切られる。
4. printが使える。printの中で文字列が使える。
5. 制御文はif, while, forが使える。elifは使えない。
6. if, while, forの制御文のブロックは、インデント（字下げ）で表す。
7. クラス、メソッドの新規定義はできない。
8. 条件として比較演算は使えるがand, or, notのような論理演算は使えない。
9. コメントは、#から行末まで。
10. ソースコードを読み込み、Cのソースを出力する。
[[BR]]
この仕様だと、以下のようなプログラムが書けるのですが、はたして、Pythonのソースに見えるでしょうか？
{{{
# Tiny Python の例題
a=3
if a >= 1 :
a = 0
b = 1
print a, b
c = 1
print c, 1
}}}
=== 2. Tiny Pythonの字句解析
デカルト言語では、字句解析(入力ソースをトークンに分解する処理)は、非常に簡単に書けます。
トークンとは、"if", "else","for", 演算子, コンマ, セミコロン, 数字列, 変数などの構文を解析するときの、文字の塊の最小単位です。
"if", "else","for"といったような決まった固定された文字列の場合は、そのまま文字列として書けば良いです。
{{{
"if"
"else"
"for"
}}}
演算子、コンマ、セミコロンも同様です。
{{{
"*"
"-"
","
";"
}}}
実は、上のような英字だけのトークンや、記号１字のトークンの場合は、デカルト言語では""でくくる必要もありません。"if"でもifでも大丈夫です。両者は同じものとされます。
英字と記号が組み合わされたトークンでは、たとえばaの１番を表す"a-1"というトークンがあった場合、デカルト言語はa-1と書いてあるとトークンを aと-1に分解してしまうので"a-1"と""で括らなければならないのです。
しかし、今回のTiny Pythonでは、トークンがトークンであることを目立たせるために、基本的に英記号トークンは""でくくることとします。
数字列については、組み込み述語である<NUM>が使えます。
{{{
<NUM>
}}}
""で括られた文字列は、組み込み述語<STRINGS>が使えます。
変数は、小文字英字一文字と決めたのですが、このような可変な構造を持ったトークンを任意に設定するには、<TOKEN>述語を使います。<TOKEN>述語の引数に字句解析の構文を付けると任意のトークンを合成できます。ここでは、一定の範囲の文字を字句解析できる<RRANGE>組み込み述語を使うことにしましょう。
{{{
<TOKEN _ <RANGE _ a z>>
}}}
これで、aからz までの一文字を抜き出します。_は無名変数であり、字句解析した結果が設定されます。
しかし、今回の場合は、TOKENの無名変数には、RANGEの無名変数と同じものが設定されることになります。よって、TOKEN述語は無くても問題ないため、変数はRANGE述語だけで構成することになります。
{{{
<RANGE _ a z>
}}}
詳しくは、次の「3. Tiny Pythonの構文解析」を見てから、もう一度本項を見ると分かりやすいと思います。
=== 3. Tiny Pythonの構文解析
さっそくですが、Tiny Pythonの構文をデカルト言語で書いてみます。
{{{
<TinyPython> { <プログラム> } <EOF>;
<プログラム> <制御文> | <プログラム文> ;
<プログラム文> [<実行文> { ";" <実行文>}] [<コメント>] <CR>;
<ブロック> ":" { <プログラム>};
<制御文> ( <if文> | <while文> | <for文> ) ;
<実行文> ( <print文> | <代入文>) ;
<if文> "if" <条件式> <ブロック> [ "else" <ブロック> ] ;
<while文> "while" <条件式> <ブロック>;
<for文> "for" <変数 #i>
"in" "range" "(" (<NUM #n> | <変数 #n>) ")"
<ブロック>
;
<print文> "print" <表示項目> { "," <表示項目> };
<表示項目> (<STRINGS #s> | <数式>);
<代入文> <変数 #v> "=" <数式>;
<数式> <expradd>;
<expradd> <exprmul> { "+" <exprmul> | "-" <exprmul> };
<exprmul> <exprID> { "*" <exprID> | "/" <exprID> };
<exprID> "+" <exprterm>
| "-" <exprterm>
| <exprterm>;
<exprterm> "(" <数式> ")"
| <NUM>
| <変数 #v>
;
<条件式> <数式>
(">=" | ">" | "==" | "!=" | "<=" | "<") <数式>;
<変数 #x> <RANGE #x a z>;
<コメント> "#" <SKIPCR>;
}}}
文法規則を書いただけのようにも見えますが、デカルト言語では、この規則をプログラムとして直接受け付けることができます。
これで、「1. Tiny Pythonの仕様」で日本語で書かれていたときには曖昧であった部分がなくなり、Tiny Pythonの言語仕様が厳密に定義されました。
どのような構文をどのような順序で、何を書けばよいのかがすべて定義されているのです。
ただし、これは、構文を定義したものであり、まだ、コンパイル結果を出力する機能は付けてない状態です。これだけでは、Tiny Pythonのソースを入力しても、コンパイルはできません。コンパイル結果を出力する部分や、入力ファイルを準備してこの構文にインプットする部分のプログラムが必要となります。
また、Tiny Pythonの場合は、インデント(字下げ)によるブロックが、このような構文の定義だけでは表現できません。上記で<ブロック>となっている部分について、後の項で別にインデントの機能を付け加えることにします。
詳細な説明は、次項で行っていきます
=== 4. 構文の詳細
順番に構文を見ていきましょう。
[[BR]]
{{{
<TinyPython> { <プログラム> } <EOF>;
}}}
｛｝の括弧は０回以上の繰り返しを意味します。
これは、!TinyPythonは、プログラムの繰り返しと最後のEOFでできていることを表しています。
EOFとは、End Of Fileのことでソースファイルの末尾に来たことを意味します。
[[BR]]
{{{
<プログラム> <制御文> | <プログラム文> ;
}}}
プログラムは、制御文かプログラム文で構成されます。
制御文とは、if, while, forなどのプログラムの流れを制御するための文です。
[[BR]]
{{{
<プログラム文> [<実行文> { ";" <実行文>}] [<コメント>] <CR>;
}}}
プログラム文は、実行文をセミコロン(;)か改行で区切ったものの繰り返しです。
プログラムの後ろにはコメントが付けられます。実行文がないコメントだけの行もありえます。
[[BR]]
{{{
<ブロック> ":" { <プログラム>};
}}}
ブロックはif、while、for文のような制御文の条件が一致した場合や、
繰り返し実行するプログラムの一連の流れを指定するものです。
[[BR]]
{{{
if a >= 1 :
a = 0
b = 1
print a, b
}}}
上記でいえば、if文の末尾の':'からprint文までの範囲がブロックであり、
条件a >= 1が合致したときに実行されます。
本当は、ブロックには、字下げ(インデント)の処理を追加しなければならない
のですが、それは後の項で説明します。
[[BR]]
{{{
<制御文> ( <if文> | <while文> | <for文> ) ;
<実行文> ( <print文> | <代入文>) ;
}}}
制御文は、if文、while文、for文のいずれかです。
実行文は、print文または代入文です。
[[BR]]
{{{
<if文> "if" <条件式> <ブロック> [ "else" <ブロック> ] ;
}}}
[]の括弧は省略可能であることを意味します。
条件が満たされた場合には、ifに対応するブロックの中の文が実行されます。
条件が合致しない場合に、elseがあればそれに対応するブロック内の文が実行されます。
elseは省略できます。
[[BR]]
{{{
<while文> "while" <条件式> <ブロック>;
}}}
条件が満たされた場合には、ブロックの中の文が繰り返し実行されます。
[[BR]]
{{{
<for文> "for" <変数 #i> "in" "range" "(" (<NUM #n> | <変数 #n>) ")"
<ブロック>
;
}}}
for文では、"in range"を使った回数指定の繰り返しができるようにします。
[[BR]]
{{{
for 変数 in range(繰り返し数)
ブロック
}}}
のような構文を可能にしています。繰り返し数は、定数または変数が指定できます。
[[BR]]
{{{
<print文> "print" <表示項目> { "," <表示項目> };
<表示項目> (<STRINGS #s> | <数式>);
}}}
print文は、表示項目を","で区切った引数を表示します。
表示項目としては、文字列または数式を指定できるようにしています。
[[BR]]
{{{
<数式> <expradd>;
<expradd> <exprmul> { "+" <exprmul> | "-" <exprmul> };
<exprmul> <exprID> { "*" <exprID> | "/" <exprID> };
<exprID> "+" <exprterm> | "-" <exprterm> | <exprterm>;
<exprterm> "(" <数式> ")" | <NUM> | <変数>;
}}}
数式は、優先度の低いほうから高いほうに向かって処理を積み上げています。
最も優先度の高いのはexptermであり、（）で括られた数式や数値と変数を処理します。
次に単項の+-を処理するexprIDです。+1とか-aとかの符号付きの項目を処理します。
次がexprmulの乗除算であり、最後がexpraddの加減算となります。数式の処理では、掛け算と
割り算を、足し算と引き算より優先して計算しますね。
[[BR]]
{{{
<変数> <RANGE _ a z>;
}}}
変数は、aからzまでの小文字とするために、デカルト言語特有のRANGE述語を使って字句解析
します。RANGEは２つの引数の範囲にある文字と合致します。
[[BR]]
{{{
<コメント> "#" <SKIPCR>;
}}}
コメントは#から、改行までです。SKIPCRは、改行まで構文解析を行わずにスキップさせます。
次に、pythonの特徴的なブロックの字下げ(インデント)の機能を付けましょう。
=== 5. インデント(字下げ)によるブロック構造の実現
INDENT述語を使って、インデントによるブロック構造を実現します。
INDENT述語は次に示すような述語です。
[[BR]]
{{{
<INDENT 変数>
カレント行のインデントのスペースの長さを変数に設定します。
タブは、8文字と数えます。マルチバイト文字の空白は2文字と数えます。
引数が変数ではなく、数の場合は、カレント行のインデントのスペースの長さ
と比較し一致していればtrueになります。
}}}
つまり、INENT述語は、カレント行のインデントの長さを調べ、
引数が変数ならばその値を設定します。
引数にインデントの長さが既に設定されていれば、カレント行の
インデントと比較します。
この述語を使って、インデントを調べ、ブロックの範囲を特定しましょう。
[[BR]]
{{{
<ブロック> ":" <INDENT #n0> // (1)
<SKIPSPACE>
<INDENT #n> // (2)
{
<SKIPSPACE>
<INDENT #n> // (3)
<プログラム>
}
<SKIPSPACE>
<INDENT #n0> // (4)
;
}}}
INDENT述語の使われている(1)では、ブロックの前のインデントを調べて
変数#n0に設定します。
例えば、if文ならば、ifの開始位置のインデントを#n0に設定します。
[[BR]]
{{{
if a >= 1 :
↑ この位置を#n0に設定する。
}}}
(1)の下に書いてある<SKIPSPACE>は、空白、タブ、および改行を飛ばします。
それらを飛ばした最初の文字がブロックの最初の行の先頭文字になるのです。
よって、(2)のINDENTでは、ブロックの最初の行のインデントが#nに設定されます。
その後の{}のループの中では、#nには既にインデントが設定されているので
(3)では、ブロックが継続しているかチェックします。インデントの値が#nと
一致しなくなるとこのブロックを抜けることになります。
そして、(4)のINDENTでは、(1)で設定したブロックの外側のインデントの
値#n0と同じインデントに戻ったことを確認します。
インデントは、見えない文字である空白、タブ、改行に大きな影響を受けるので
構文解析をするには、INDENTのような特殊な述語を必要となるのです。
=== 5. ブロック外のインデント
インデントはブロック内だけではありません。
ブロックの外、つまり、プログラムの開始からインデントが揃っていることを
チェックしなければなりません。
{{{
# Tiny Python の例題
a=3
if a >= 1 :
a = 0
b = 1
print a, b
c = 1
print c, 1
}}}
上記では1から3行目までと、if文のブロックの最後のprint文以降の文の先頭が
インデント０で揃っていることをチェックする処理を追加します。
前の「4. 構文の詳細」で、最初に説明した以下の構文を見直します。
[[BR]]
{{{
<TinyPython> { <プログラム> } <EOF>;
}}}
これを以下のように変更します。
[[BR]]
{{{
<TinyPython> {
<SKIPSPACE>
<INDENT 0>
<プログラム>
}
<SKIPSPACE>
<INDENT 0>
<EOF>;
}}}
上記のように、プログラムの前後で、インデントが０であることをチェックします。
これで、インデントのための処理は、すべて説明しました。
では、実際に動くコードについては、「デカルト言語によるコンパイラ言語の作成: Tiny Pythonコンパイラの作成(その2)」
で説明します。