OMeta

http://www.cs.ucla.edu/~awarth/ometa/

眠くて微妙な事が何も出来ないので軽く OMeta について書きます。OMeta とは、http://lambda-the-ultimate.org/node/2477 によって一躍有名になったメタ言語 - プログラミング言語を書くためのプログラミング言語 - です。果たして単なる PEG パーサと一体どこが違うのか私もよく分かっていないので、そのあたりの事を勉強したいと思います。OMeta にはスクイークや「イアンのやつ」の実装がありますが、最近 Web ブラウザで実行出来る Javascript 版が公開されたのでそちらを試します。

OMeta で何が出来るか？

http://www.cs.ucla.edu/~awarth/ometa/ometa-js/ を開くと、OMeta で作成された Smalltalk 言語のデモで遊ぶ事が出来ます。この例では、OMeta は Smalltalk ソースを javascript に変換して実行しています。例えば 1 + 2 * 3 を選択して [print it] ボタンを押してみてください。答えの 6 が表示されます。答えが違うって？Smalltalk には演算子という概念が無く、+ や * は引数を一つ取るメッセージです。javascript 的に無理やり書くと ( 1.+(2) ).*(3) のようになります。

余談ですが、このようなプログラム開発環境を Smalltalk では Workspace と呼び、大変重視しています。しかしOMeta 自身とは独立しているので、もしもあなたのアプリケーションで OMeta を使いたい場合に Workspace を含める必要はありません。

次に、123 printString size を print it すると、3 が表示されます。これは、123 を文字列にした物('123')のサイズ(3)という意味です。このように裸のシンボルが置かれていると、それは引数を取らないメッセージと解釈されます。これも javascript 的に書くと、123.printString().size() になります。

一つ飛ばして self inform: 'hello', ' world' を選択して [do it] ボタンを押してください。"hello world" というアラートが表示されます。inform: のようにコロンがついたシンボルは一つ以上の引数を取るメッセージです。例によって javascript 的に書くと、self.inform( 'hello'.,('world') ) になります。コンマは文字列の連結を行うメッセージです。

と、Smalltalk の文法について書き出すときりが無いので、残りはネットで調べてください。OMeta では、Smalltalk 文を文法に混ぜるので、覚えた方が良いです。

単純な文法

さて、ここで重要なのは、Smalltalk 言語で遊ぶだけではなく、あなた自身で Smalltalk を作る事が出来る事です。しかもウェブブラウザの中に。Smalltalk だけでなくどんな言語でも作る事が出来ます。OMeta は言語マニアの為のオールインワンツールとして開発されました。とはいえ最初から Smalltalk は難しすぎるので単純な例から。テキストボックスの中を全部削除して次の文を試してみましょう。

ometa M {
  ruleX  ::= $x.
  ruleXS ::= <ruleX>+.
}.
M match: $x with: #ruleX.
M matchAll: 'xxxxx' with: #ruleXS.

最初の ometa クラス名 { 文法 } の形が文法定義で、作成された文法の利用例が続きます。文法は、ルール名 ::= パターン のように書きます。ルール名とは難しく言うと非終端記号とも呼びますが、パターンにマッチした文字列を後で参照するのに使います。この例では、"x" にマッチする ruleX という文法を、後で + のように参照しています。+ は、「一つ以上要素が続く」意味です。

実際に解析を実行する match:with: は、引数を一つだけマッチし、matchAll:with: はストリームとみなしてマッチします。ただし、javascript の性質(文字と文字列を区別しない)からか、真面目に実装されてませんので、matchAll:with: だけ覚えていると良いと思います。

これらを do it しても、何も起こりません。何も起こらないのは正しい証拠。試しに以下を do it して、どういう時にエラーになるか試してみてください。

M matchAll: 'yyyyyy' with: #ruleXS.
M matchAll: 'xyyyyy' with: #ruleXS.

'xyyyy' までマッチされてしまう所が PEG(解析表現文法)の特徴です。ここはまず面食らう点かもしれません。文法の記述方法には、他に導出規則というのがありますが、これは PEG と全く異なった考えです。導出規則で定義された文法とは、ある開始記号をルールに基づき書き換えて行く際に現れる可能性の事です。だから文字列の全体がマッチの対象です。しかし PEG では、文字列の先頭からある条件に基づ検査して行く事が文法の定義になっています。だから文字列の全体をマッチさせたい時は、自分でそのような文法を定義する必要があります。

この二つの全く異なった文法表現の関係は非常に興味深いトピックですが、省略します。

do it の代わりに print it を押した方は、なにやら表示された事に気づくと思いますが、その話はちょっと長くなりそうなので一旦休みます。

PEG を試す

PEG について語らずに話を続けるのは難しそうなので、ここで S 式の簡単なパーサーを作りながら PEG を覚えます。パーサーというのは、文字列を文法どおり読み込んで何かを返すプログラムの事です。でも最初は、何を返すかは考えないで、文法があってるかどうかだけを問題にします(合ってる時は何もせず、間違っているとエラーになります)。文法は以下の通り。

• 式の例: (+ 3 (* 4 5))
• 全体をカッコでくくる
• カッコの中は (演算子 何か 何か)
• 何かのところには、数字か式が入る。
• 演算子は + - * / のどれか記号。

では一番簡単そうな演算子からボトムアップ式に。ちょっとずつテストコードを書きながらやりましょう。

ometa SEXP {
  operator ::= '+' | '-' | '*' | '/'.
}

SEXP matchAll: '*' with: #operator. "演算子 とは、+ - * / のどれか"

先ほどのように、SEXP という文法名(なんでもよい)を指定して {} の中に「ルール名 ::= パターン.」の形で文法を記述します。| は「順序つき選択」を表し、+ - * / のどれかが現れたら operator というルールにマッチしたとみなされます。順序つきというのは、一つでもマッチする要素を見つけたらそれ以上検索を行わないという事です。ちなみに PEG で順序つき選択というと / の記号を使うようですが、作者の好みで(?) | になっています。以下 ::= の行は ometa SEXP {} の中に書き足していってください。

digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'.
number ::= <digit>+.

SEXP matchAll: '+ 1 2' with: #digit. "数字とは、0 1 2 3 4 5 6 7 8 9 のどれかである"
SEXP matchAll: '1234' with: #number. "数値とは、数字が一つ以上並んだもの"

次は数字です。digit は数字一文字にマッチし、number は + の効果で続く digit 全てを検索します。一度定義した文法を他の文法に埋め込む際は、このように <> で包みます。

space ::= (' ' | '\n')+.

SEXP matchAll: '  ' with: #space. "空白 とは、1つ以上の「 」"

これは、カッコの中の単語を分けるための空白を定義します。そして最後にざっくり再帰的な式全体を定義します。

inner ::= <operator> <space> <expr> <space> <expr>.
 expr ::= <number> | '(' <inner> ')'.

SEXP matchAll: '+ 3 4' with: #inner. "中身とは、演算子と式に空白を挟んだもの"
SEXP matchAll: '(+ 3 4)' with: #expr. "式とは、数字か中身をカッコで包んだ物"
SEXP matchAll: '(+ 3 (+ 4 5))' with: #expr. "再帰していても良いです"

と言うわけで、ここまで全部を纏めて書きます。to it する時は、コメントのつもりのクォートは選択しないで下さい。

ometa SEXP {
  operator ::= '+' | '-' | '*' | '/'.
  digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'.
  number ::= <digit>+.
  space ::= (' ' | '\n')+.
  inner ::= <operator> <space> <expr> <space> <expr>.
  expr ::= <number> | '(' <inner> ')'.
}

SEXP matchAll: '*' with: #operator. "operator とは、+ - * / のどれか"

SEXP matchAll: '7' with: #digit. "数字とは、0 1 2 3 4 5 6 7 8 9 のどれかである"
SEXP matchAll: '1234' with: #number. "数値とは、数字が一つ以上並んだもの"

SEXP matchAll: '  ' with: #space. "space とは、1つ以上の空白"

SEXP matchAll: '+ 3 4' with: #inner. "中身とは、演算子と式に空白を挟んだもの"
SEXP matchAll: '(+ 3 4)' with: #expr. "式とは、数字か中身をカッコで包んだ物"
SEXP matchAll: '(+ 3 (+ 4 5))' with: #expr. "再帰していても良いです"

このあと電卓を作る予定。

おまけ: OMeta のサンプルをローカルで動かす。

svn co http://jarrett.cs.ucla.edu/svn/ometa-js/
cd ometa-js
svn co http://jarrett.cs.ucla.edu/ometa-js/projects/