このノートでは、1 + 2 のような中置記法で書かれた式を、
+ 1 2 のような前置記法で書かれた式に変換する方法を取り上げます。
ここで説明する内容は、甲州計算機のバージョン 0.41 の
Infix.hs モジュールに対応します。
式 1 + 2 は 3 つの部分式 1 + 2 に分解できます。
それぞれの部分式に高さを割り当て、中置演算子の + の高さは 1 で、
演算子以外の部分式の高さは 0 であるとします。
高さを括弧に入れて書くと 1(0) +(2) 2(0) のようになります。
高さをコロン : の数であらわすと、つぎのように想像できます。
+
:
1 : 2
もっとも高い部分式で左右に分割すると考えると、
演算子 + の左の部分式 1 と右の部分式 2 が得られます。
その結果、+ (1) (2) のような前置記法の式へ変形できます。
式 1 + 2 * 3 が 1(0) +(2) 2(0) *(1) 3(0) という
高さが割り当てられるとすると、つぎのように視覚化できます。
+
: *
1 : 2 : 3
まず、+ (1) (2 * 3) という前置記法に変換され、
さらに、+ (1) (* (2) (3)) に変換されます。
+ と * のように演算子の高さが異なれば、あいまいさは生じませんが、
1 + 2 + 3 のように同じ高さの演算子が使われているときは、
左の演算子で分割し + (1) (2 + 3) とするか、
右の演算子で分割し + (1 + 2) (3) とするかを決める必要があります。
いま、+ の高さが 2 で右分割であるということを、
1(0) +(R2) 2(0) +(R2) 3(0) と書くとします。
高さと向きだけを抜き出すと、0 R2 0 R2 0 と書けます。
高さと左右の組み合わせについて、いくつか例を示します。
0L10L20→ (L2(0L10) (0)) → (L2(L1(0) (0))0)0L10L10→ (L1(0) (0L10)) → (L10(L1(0) (0)))0R10R10→ (R1(0R10) (0)) → (R1(R1(0) (0))0)
同じ高さで向きの異なる演算子があるときは、 左分割にするか右分割にするか定まらず、あいまいな式になります。 甲州計算機は、このような式に出会うと処理を中断します。
0L10R10→ あいまい
Infix.hs モジュールの構成をかんたんに説明します。
分割のための向き Left Right と高さ h :: Int を
Left h か Right h であらわします。
この型 Either Int Int に InfixHeight という別名を与えると、
トークン a を高さと向きに変換する関数
a -> InfixHeight を定義できます。
トークン a に内包された記号 b に対して
ih :: InfixHeight を割り当てる規則
htab :: [(b, ih), ...] と、内包された記号を取り出す
extract :: a -> b を組み合わせると、高さ関数
infixHeight extract htab :: a -> Infixheight を実際につくれます。
この高さ関数 ht :: a -> Infixheight を使って、
中置記法のトークン木 tree1 :: CodeTree a を
前置記法のトークン木に変換する関数 infixToPrefix ht tree1 を
定義できます。この関数は、必ず、トークン木を返せるわけではなく、
あいまいな演算子があるとき、その演算子のトークン tok :: a と
高さ ih :: Infixtoprefix のリスト Left [(ih, tok), ...]
を返して、どこがあいまいであるかを知らせます。
前置記法に変換できたときは、変換後の tree2 :: CodeTree a
を内包した Right tree2 を返します。
このディレクトリにある infix.hs を使うと、
中置記法が前置記法に変換された結果を確認できます。
このコマンドは、式を引数に与えると、中置演算子を先頭に移動した上で、
それに対応するトークン木を出力します。たとえば、
$ ./infix.hs "/a * /b + 10"
に対して、つぎの出力が得られます。
** /a * /b + 10
TreeB 1 - -
TreeL : TWord 1:8 0 "+"
TreeB 1 - -
TreeL : TWord 1:3 0 "*"
TreeL : TTerm 1:0 ["/a"]
TreeL : TTerm 1:5 ["/b"]
TreeL : TWord 1:10 0 "10"