Consistent Binary Tree Layout(3)

算術式を記述するにはいくつかの方法があります。算数、数学に使われる中値記法はその一つです。中値記法は、英語ではInfix Notationと表記されます。計算機で使用される言語では、数学のように大括弧(bracket)、中括弧(brace)、括弧(parenthesis)を使い分けず、括弧のみで記述されることが多いかと思います。

A * (((B + C) * D * E) + F)

中値記法では括弧を注意深く取り扱わないと算術式の意味合いが異なってしまいます。例えば、上の算術式の括弧を省略すると、全く別の算術式となります。

A * B + C * D * E + F

また、この算術式ではBとCの和とD、およびEの積を取りますが、括弧が欠落しているため、結果は変わらずとも、以下に示すように演算の順序に曖昧さが残ります。

A * ((((B + C) * D) * E) + F)
A * (((B + C) * (D * E)) + F)

このエントリでは、後の算術式、DとEの積を優先するものを元に解説を進めます。

それでは、この算術式の解析木(Parse Tree)を可視してみましょう。

解析木から中値記法による算術式の抽出を行う場合は、木を通りがけ順にて走査します。しかし、前述したように、中値記法では括弧を注意深く扱わないと算術式の意味合いが異なってしまいます。この解析木の場合もそれに該当します。括弧の処理の実装は一般的に多少複雑になるかと思います。

さて、木の走査法に通りがけ順、行きがけ順および帰りがけ順があるように、算術式の記法にも中値記法以外に前置記法、後置記法があります。前置記法はまた、ポーランドの論理学者が考案したことにより、ポーランド記法とも呼ばれています。英語では、Prefix Notation、またPolish Notationと表記されます。

今回取り上げている算術式を前置記法で表すと以下のようになります。本エントリで扱っている二項演算であれば、中値記法とは異なり、括弧を必要としません。前置記法の応用としてはLispやScheme等の言語で用いられる、S式が有名です。

* A + * + B C * D E F

可読性を上げるため、また二項以外の演算対象を扱うため、括弧を使って記述することがあります。括弧を用いると、上述の例は以下となります。

(* A (+ (* (+ B C) (* D E)) F))

また、括弧を伴うことにより、改行やインデントの手法を明確に定義することが出来ます。これは、算術式全体の可読性を向上させることに貢献します。

(* A
   (+
    (*
     (+ B C)
     (* D E))
    F))

前置記法での算術式では、先の中値記法で見られたような演算順序の曖昧さはありませんが、演算子や演算対象間を区切る記号が必要となります。この区切り記号はデリミタと呼ばれ、英語ではdelimiterと表記されます。空白記号や改行がデリミタとして多く用いられます。

さて、解析木から前置記法による算術式の抽出を行う場合は、木を行きがけ順にて走査します。以下の可視は、先日のエントリにて解説した、行きがけ順による配置を基調とし、行きがけ順の走査を可視したものです。上と左が転置していますが、あたかもインデントを伴ったS式のようであり、可視性が高いように感じます。接点を部分木よりも優先する行きがけ順の性質上、自ずと演算子が部分木の主題となるからでしょうか。

最後に解説する後置記法は逆ポーランド記法とも呼ばれます。英語では、Postfix Notation、またReverse Polish Notionと表記されます。本ブログにおいて可視に使用しているPostScriptでも採用している記法です。後置記法を用いた言語は、演算対象をあたかもスタックに積み上げてから演算する様からスタック言語とも呼ばれます。実際、データ構造にスタックを用いる実装もあるようです。

今回取り上げている算術式を後置記法で表すと以下のようになります。

A B C + D E * * F + *

前置記法も後置記法と同様、括弧を必要としませんが演算順序に曖昧さはありません。また、デリミタを必要とします。

解析木から後置記法による算術式の抽出を行う場合は、木を帰りがけ順にて走査します。また、解析木を評価する際にも、木を帰りがけ順にて走査しつつ評価する実装は多く見られます。以下の可視は、帰りがけ順による配置を基調とし、帰りがけ順の走査を可視したものです。

さて、今回のエントリではあまり目にする機会が少ないであろう、行きがけ順、および帰りがけ順を接点の配置の基調とした木の可視の応用例を紹介しました。両者を比較すると、行きがけ順を用いた可視はトップダウン的であり、帰りがけ順を用いた可視はボトムアップ的にも見えます。何れも同じ解析木なのですが、表現方法を変えるだけで実に様々な側面が見えてくるものです。

また、演算対象の接点群には何れの走査方法でも同じ順序で訪れます。これは、解析木を走査する際の特徴の一つです。興味深いですね。

次回のエントリでは、帰りがけ順の解説にて言及したスタック構造を可視し、帰りがけ順を用いた可視と比較してみようかなと思っています。