言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella
トップ > OMeta で書く、右再帰と左再帰

OMeta で書く、右再帰と左再帰

前回 http://d.hatena.ne.jp/propella/20071122/p1 S式電卓を作ると書いたけど、もう一度右再帰と左再帰について確認します。左再帰を書くと無限ループになるのが PEG の特徴らしいですが、OMeta では、どういうトリックかちゃんと左再帰も処理できます。とある数字(文字列)からとある数字(データ)を生成するプログラムを書いて、右再帰と左再帰の違いを確かめてみましょう。前回説明した以外に => によるアクションと、パラメータ付きのルールを使ってます。

まず左再帰を使った例。

ometa LNum {
  digit  ::= ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'):x
                                   => [x digitValue].
  number ::= <number>:n <digit>:d  => [n * 10 + d]
           | <digit>.
}

LNum matchAll: '4649' with: #number

短くて分かりやすい。では右再帰の例。

ometa RNum {
  digit        ::= ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'):x
                                                          => [x digitValue].
  number       ::= <numberSub 0>.
  numberSub :n ::= <digit>:d <numberSub (n * 10 + d)>:ds  => [ds]
                 | <empty>                                => [n].
}

RNum matchAll: '4649' with: #number

右再帰にこだわるほうが美しいと言ったけど、ちょっと分かりにくい。でも状態が必要であるという事がよく分かってむしろ良いような気もする。