2004-02-24

1+2*f(x,y,g(z))

上のような数式を認識するにはどうすればよいかを考えてみた。（てか、酒飲んでるし、疲れてるからこれぐらいしか考えられない。）
まず、必要なルール・目標を先に決めておく。

infix演算子とprefix演算子をあらかじめ決めておく。
演算子の優先順位を決める。
括弧の扱いを正確に決める。

まず、infix演算子とprefix演算子について。当たり前だけど、infix記法とprefix記法をごちゃ混ぜにするには、ごちゃ混ぜの状態から一意の木を生成できるだけのルールを考えなければならない。その第一歩目が、infix演算子とprefix演算子の区別すること。ということで、数値計算用の演算子はinfixで、その他のアルファベットで表記される関数はprefixとする。あたりまえやね。たとえば、次のような感じ。

infix = { +, -, *, / }
prefix = { f, g, h, succ }
other = { (, ), = }

さて考えた、infix演算子はbinaryな演算子である。さらに、binaryでもアルファベットで表記される関数はprefixの方が嬉しい。ということで、

記号で表記されて、しかもbinaryな演算子はinfixとする。
それ以外はすべてprefixとする。

と定義する＞明日の俺。
次に、演算子の優先順位について考える。普通は、こんな感じか？

prefix演算子（一般的な関数）
'*', '/'
'+', '-'

ただ、関数定義を自由に行えるので、一意に優先順位をつけることができるのか、そもそもそんなことに意味があるのかはよく分からない。ただ一般的に、加減算よりも乗除算のほうが優先順位が高いので、それは踏襲してもいいかな。
最後に、括弧の扱いについて考える。infix記法とprefix記法が混在した式の中には、２種類の括弧が存在する。一つは優先順位を明確にするための括弧。もう一つは、関数の引数の範囲を決めるための括弧。次のような感じ。

'(a + b) * c'
'f(x) + g(x, y, z)'
'(f(x) + g(x,y,z)) * h(y)'

最初のは計算木を一意に決めるために演算の優先順位を明確にするための括弧。二つ目は関数の引数の範囲を明確に決めるための括弧。最後のは、それらを混在するとどうなるかについて。
まず、infix記法および演算子の優先順位を導入することで、最初の括弧は必ず必要である。括弧で順序が規定されていない場合には前方一致で計算木を構築すれば良いけど、前方一致による計算木と人間が目で認識したときの計算木が必ずしも一致するわけではない。また、infix記法では括弧以外には計算木を一意に規定する、もしくは木の順序を変更する方法が存在しない。
二つ目の関数の引数の範囲を明確に決めるための括弧は必ずしも必要ない。どういうことかというと、関数（演算子）の引数が固定されている場合、prefix記法で表現される式は一意の木に変換できるためである。まあ、複数の意味を持つ可能性が少ないということ。これが、lispみたいに引数の数が固定でないときは一意の気に変換できないので、括弧が必要になる。また、演算子単体を引数としたい場合があると括弧が必要になるが、今回のプログラムではそこまでは想定しない。これは、パーサーを書くときにどうするかを具体的に考える。＞未来の俺
さて、唐突に項の分割の方法をどうしようかと思ったけど、それは後で考える。＞がんばれ、未来の俺

ぼうメモ帳

キター

TRS用ツール

infixとprefixのごちゃまぜについて