基本概念

良く理解しておかなければならない僅かばかりの基礎的概念がある： 1) パーサ、 2) 一致判定[訳注："マッチ"と訳している箇所もある]、 3) スキャナ、そして 4) セマンティックアクションである。 これらの基本概念は相互に作用しあい、 各々の機能は織り交じって、フレームワーク全体を首尾一貫した一つのものとしている。

パーサ

フレームワークの中心がパーサである。 スキャナによって初めから終わりへとシーケンシャルに読み込まれたデータの線形(linear)な入力ストリームを、実際に認識するのがパーサである。 パーサは、文法ルールの形で明確に定義された仕様の集合に従った入力をマッチしようと試みる。 パーサは match object を通して、クライアントに成否を報告する。 成功した場合、パーサはクライアントが与えたセマンティックアクションを呼び出す。 最終的に、 戦略的な位置に置かれた(strategically-placed)セマンティックアクションが、 パーサによって渡されたデータや、そのセマンティックアクションが取り付けられたパーサの階層構造のコンテキストに依存した、 構造的な情報を抽出する。 (Finally, the strategically-placed semantic action extracts structural information depending on the data passed to it by the parser and the heirarchical context of the parser it is attached to.)

パーサはいくつかの種類のものからなる。 Spirit フレームワークは、定義済みパーサの拡張可能なセットと一緒に提供されている。 このパーサ類は、単純なものから複雑なものまで、様々な構文解析タスクを実行する。 概念としてのパーサは、公開された概念上のインターフェイス規約を持っている。 その規約に沿って、フレームワークの定義済みコンポーネントと共に動作する規格を満たしたパーサを誰でも書くことができる。 後の方で、パーサのこの概念上のインターフェイスの詳細の青写真を提供している。

フレームワークのクライアントは、普通、独自の手書きのパーサを書く必要はほとんどない。 Spirit は、構文解析／意味解析のあらゆる側面をカバーする膨大な定義済みパーサのレパートリーを持っている。 続く節では、このパーサのレパートリーについて考察していこう。 特定の機能が利用できないという珍しいケースでも、ユーザ定義のパーサを書くことは非常に簡単である。 パーサを書く際の容易さは、 Spirit の拡張性の主たる理由でもある。

プリミティブパーサとコンポジットパーサ

Spirit のパーサは二つのカテゴリーに分けられる：プリミティブパーサとコンポジットパーサである。 これら二つのカテゴリーは、おおよそ構文解析用語で言う終端記号と非終端記号と同じ意味である。 プリミティブパーサは分解不可能なアトミックなユニットである。 一方のコンポジットパーサは、他のパーサを組み合わせたパーサであり、それ自身も、プリミティブパーサや他のコンポジットパーサと組み合わせることが出来る。 例えば、次のような Spirit 式を考えてみよう：

    real_p >> *(',' >> real_p)

real_p は実数を構文解析するプリミティブパーサである。 式中のクォートで囲まれたコンマ ',' は短縮表現で、文字を一つ認識する別のプリミティブパーサ ch_p(',') と等価である。

上述の式は次の構文木に対応する：

次の式はシーケンスパーサを組み合わせる：

    ',' >> real_p

sequence パーサは二項コンポジットパーサであり、二つのパーサを組み合わせる。 同様に単項コンポジットパーサは、一つのパーサを組み合わせる。 単項コンポジットパーサは単一の対象だけを保持する。 二項コンポジットパーサと同様、単項コンポジットパーサは埋め込まれた対象の振る舞いを変えることができる。 具体的な例として Kleene star がある。 Kleene star が呼び出されると、そのただ一つの対象をゼロかそれ以上の回数呼び出す。 "ゼロかそれ以上"とは、 null 文字列 "" であっても Kleene star が一致判定の成功を返すという意味である。

次の式：

    *(',' >> real_p)

は上述のシーケンシャルなコンポジットパーサの全体を kleene_star の内側にラップしている。

最終的にこの式全体では、プリミティブパーサ real_p と上記の kleene_star を、 より高いレベルの別のコンポジットパーサ sequence に組み合わせている。

少数の単純なクラスが、組み合わされ、階層的に構造化されることで、 非常に強力なオブジェクト指向再帰下降型構文解析エンジンを形成する。 これらのクラスは、より複雑なパーサを構築するために必要な基盤を提供している。 最終的に組み合わせられるパーサは、無限に先読みできる非決定的な再帰下降型パーサである。

トップダウンの下降は階層構造を縦断する。 外側の sequence は最左辺の real_p パーサを呼び出す。 もし成功すれば、 kleene_star が次に呼び出される。 kleene_star は内側の sequence を、一致判定に失敗するか入力が尽きるまで繰り返し呼び出す。 その内側では、 ch_p('x') 、そして real_p がシーケンシャルに呼び出される。 いささか Pascal の構文図を想わせる次の図は、何が起きているのかを説明している。

オブジェクトを埋め込むことや再起と組み合わされたコンポジションの柔軟性は、 構文解析することへの独自のアプローチを開拓する。 サブクラスは、任意の計算量(complexity)の集約やアルゴリズムを自由に形成できる。 僅かなプリミティブクラスだけをコンポジションすることで、複雑なパーサを作り上げることができるのである。

フレームワークは、一切の制限なく、拡張可能なように設計されている。 新しいプリミティブパーサやコンポジットパーサは、取るに足らないものから複雑なものに至るまで、いつでも加えられる。 コンポジションはコンパイル時に（静的に）起こる。 これは、C++の式テンプレートとテンプレートメタプログラミングの、豊かな柔軟性によって可能となっている。

最終的には一つのコンポジットパーサが得られる。 このパーサはプリミティブパーサやより小さなコンポジットパーサの合成されたものである。 この埋め込んでいくという戦略が、任意の複雑さ(complexity)の EBNF 式を完全にモデル化する階層的構造を構築する能力を与えてくれる。 組み立て部品であるプリミティブパーサとコンポジットパーサについては、後に詳しく紹介する。

スキャナ

パーサと同様に、スキャナも抽象的な概念である。 スキャナの仕事は、シーケンシャルな入力データストリームをパーサに供給することである。 スキャナは STL に適合した二つのイテレータ、 first と last から組み合わされる。 first は参照で、 last は値で保持される。 イテレータ first が参照で保持されているのは、パーサが位置を変更できるようにするためである。 スキャナがどのように振る舞うかはポリシーの組が決定する。パーサはスキャナからデータを抽出し、 メンバ関数によってイテレータを適切な位置に合わせる。

これらのポリシーの込み入った知識は、ほとんどの場合まったく必要ない。 しかし、スキャナの基本的な API の知識は、完全準拠した Spirit パーサを書くために必要である。 スキャナの API は別のセクションで概要を述べることになる。 加えて、パワーユーザや我々の中の冒険心のある人々のために(for the power users and the adventurous among us)、 まるまる一つのセクションをスキャナポリシーを網羅するのに充てている。 スキャナポリシーは Spirit を非常に柔軟で拡張性のあるものにしている。 例えば、いくつかのポリシーはデータをフィルタするために変更されるだろう。 現実的な例として、大文字小文字を区別しない入力を構文解析するなら、 大文字小文字の区別のないスキャナポリシーにすれば便利だろう。 別の例としては、入力から空白を取り除くスキャナポリシーがある。

一致判定(match)

パーサは概念上のメンバ関数 parse を持っている。この関数はスキャナを取り、一致判定(match)オブジェクトを返す。 一致判定オブジェクトの基本的な機能は、パーサの呼び出し元に、構文解析が成功したか（あるいは失敗したか）を報告することである； つまり、もし parse 関数が成功すれば真、失敗すればそれ以外と評価する。 もし構文解析に成功すれば、一致判定オブジェクトは（match.length()を用いて）一致した文字数を報告するためにも問い合わされるだろう。 一致判定に成功すればその長さは非負であり、構文解析に失敗した場合の典型的な長さは -1 である。 長さがゼロであることは完璧に有効で、一致判定に成功したことを表している。

パーサは、それに関連付けられた属性データを持っている。 例えば、 real_p パーサはそれに関連付けられた数値データを持つ。 この属性は構文解析された数字である。 この属性は、返される一致判定オブジェクトへ渡される。 一致判定オブジェクトは、この属性を得るために問い合わされる。 このデータは一致判定が成功したときのみ有効である。

セマンティックアクション

コンポジットパーサは階層構造を形成している。 構文解析は最上位の親パーサから進行する。 この親パーサは構文解析タスクをその子からそのまた子へと再帰的に委譲・分配し、最終的にプリミティブパーサに達するまで繰り返す。 セマンティックアクションをこの階層構造のさまざまな点に接続することで、 要は、平坦な線形入力ストリームを構造化された表現に変換することが出来る。 これはパーサが本質的に行うことである。

上述の例をもう一度見てみよう：

    real_p >> *(',' >> real_p)

関数（あるいはファンクタ）を real_p パーサの中へフックすることで、 入力から数字を取り出すことが出来る：

    real_p[&f] >> *(',' >> real_p[&f])

ここで f は一つの引数を取る関数である。 [&f] は関数 f でパーサをフックし、 real_p が有効な数字を認識した時に関数 f が呼ばれるようにする。 その後、関数は適切な処理を行うが、それはその関数に依存する。 例えば、その数字をベクタに詰め込むこともできる。 あるいはひょっとして、もし ',' を '+' に置き換えてわずかに文法を変更すれば、 総和を計算する原始的な電卓を作ることも出来る。

Copyright © 1998-2003 Joel de Guzman

Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.

Japanese Translation Copyright © 2003 Kent.N

オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント（英語）