言語実装者会議とは
- Agda Implementors Meeting
- Haskell Implementors Workshop
- Coq Implementors Workshop
- Scheme Implementors Workshop
など、言語の実装者の集まりの会議です。
どんな言語の実装者会議なの？
- 個人的に作成している言語の実装者会議です
- 作った言語を発表してもらいます
- グループを作り協力して開発します
- 小さい言語の仕様策定のワークショップを行います
- 作る言語の仕様や役割を話し合って決めます
- 話し合いで決まったことを各自が実装します
- 相互に書いたコードを実行してみます
Before
- BNFを覚えると良いらしいけどわけわかんね
- ドラゴンブック読む
- LR構文解析がわからなくてBNF嫌いになる
- Yacc使ってみてコンフリクトでつまづく
- BNFきらいだ、めんどくさい！！
- 再帰降下型パーサで十分！
- 仕様書くのめんどくさい。辛い
After
- 再帰降下型パーサ作ってみる
- パーサコンビネータ使ってみてわかるぞ！
- パーサコンビネータ作ってみてわかるぞ！
- BNFっぽいものの良さがわかった！
- よくわからんけど、Yaccを使って楽しいぞ！
- 仕様書くの簡単だぞ。楽しいぞ！
今回は、仕様の書き方に注目します。
どうやって協力するの？
- 現状、似たような言語の実装が数多く作られています。
- 似たような言語を実装する人たちが1つの処理系を作ったほうが楽しいはずです。
- 仕様をサンプルコードとBNFで大まかに決めます。
- 大きすぎる仕様では話をまとめるのが大変です。
- 仕様が小さい言語をしっかり実装します。
仕様の決め方
- いくつかのグループを作ります。
- サンプルコードを書いて意思の統一します。
- BNFを書いて仕様を書きます。
- わからないことはマイクとプロジェクタで使って質問してわかる人に教えてもらいましょう。
- 仕様からチュートリアルを作ります
- 感想を話し合います
- 字句解析の仕様を書きます
- パーサと抽象構文を決めてパーサを実装して問題ないかを確認します。
- 次に作る仕様を決めてバージョンアップします。
作る言語の種類の例
- Scala風の言語でif,whileと文字列と関数、クロージャがある、静的型付け言語
- Ruby風の言語で以下同文
- Python風言語で以下同文
- ML風の言語で以下同文
- 他にやりたいものがあれば好きに作りましょう。
作業内容
- サンプルコードを書く
- BNFを書く
- 表示的意味論の仕様を書く
- 標準組み込み関数を書く
- 操作的意味論を書く（できれば）
- 型付け規則を書く(できれば）
サンプルコード
1 + 22
1 + 2 * 3
(1 + 2) * 3
(if (1+2*3) 4+5*6 else 6+7)+1
足し算と、掛け算ができて、かっこで優先順位を変えられ、if式が使え流言語を作ります。
BNFの例
exp ::= exp "+" exp
| exp "*" exp
| int
| "(" exp ")"
| "if" "(" exp ")" exp "else" exp
ここから仕様を起こそう！
仕様
exp ::= exp "+" exp 足し算
| exp "*" exp 掛け算
| int 整数
| "(" exp ")" かっこ
| "if" "(" exp ")" exp "else" exp if式
式は、足し算、引き算、int型があり、カッコでネストできて、if文が使えます。
このような書き方は一目で見るのに適しています。
名前をつける例
exp ::= bin_exp | simple_exp | if_exp
bin_exp ::= exp "+" exp
| exp "*" exp
simple_exp ::= int
| "(" exp ")"
if_exp ::= "if" "(" exp ")" exp "else" exp
式と、2項演算子式と、シンプル式と、if式に分けて書きます。
仕様が大きくなった場合は書きやすくなります。
式
exp ::= bin_exp | simple_exp | if_exp
式には、二項演算子式と単純式とif式があります。
二項演算子式
bin_exp ::= exp "+" exp
| exp "*" exp
二項演算式には"+"と"*"があります。
| 優先順位 | 演算子 | 結合性 |
|---|---|---|
| 1 | + | 左結合 |
| 2 | * | 左結合 |
単純式
simple_exp ::= int
| "(" exp ")"
単純式には、整数と、かっこでくくった式があります。
if式
if_exp ::= "if" "(" exp ")" exp "else" exp
if式はexpの式が0なら1つ目の式を、0以外なら"else"の後ろの式を実行します。
チュートリアルを書く
次にチュートリアルを書いてみましょう。
式
この言語には式しかありません。
二項演算子式と単純式とif式があります。
1+2
2*3
(1)
if(0)1 else 3
(if(0)1 else if(1) 2 else 3)*2
大まかな言語の売りを書きます。
二項演算子式
二項演算式には"+"と"*"があります。
1 + 2
1 * 2
*の方が結合順位が高いので、1 + 2 * 3は1 + (2 * 3)という意味になります。
単純式
単純式は整数とかっこでくくった式があります。
整数は0や123といった数です。
0
123
かっこは結合の優先順位を変更可能です
(1)
((123*2))+1
if式
if(0) 1 else 2
if式はexpの式が0なら1つ目の式を、0以外なら"else"の後ろの式を実行します。
この例では0なので結果は1になります。
感想
このような形でチュートリアルを書きます。
このBNFや仕様、チュートリアルを書いてみると、いろいろ思うことがあるでしょう。
- 単純式を先に書いたほうがチュートリアル書くのに順番を変えたほうがよかった
- 字句解析のこと書いてないぞ
次にちょっと字句解析を書いてみましょう。
字句解析
コメントはありません。
空白は、" " "\t" "\r" "\n" です。
整数
int ::= ('0' | ... | '9')+
記号
( ) + *
キーワード
if else
次にすること
- 変数宣言と、変数の使い方を作ります。
- 関数宣言と、関数呼び出しを作ります。
と拡張してみましょう。