アーキテクチャ 1.0

「へたれBASIC」処理系を一通り作ってみてから見直してみると、 ごちゃごちゃの依存関係を持った クラス集団になってしまいました。学級崩壊の様相を呈しています。(まさか!)
でも、せっかくオープンソースでやって行こうと考えているので、 クラスの関係や内容が一体どうなっているのかを、ここで解説したいと思います。
僕の書いたコードを読んでみようというユニークな方がいらっしゃいましたら参考にして下さいませ。 後で自分で見返して開発の見通しにするためにもこれを書きます。基本的なことしかやってないので、どの解説もローレベル(←2通りの意味でね)なテーマばかりです。

処理の流れと、クラス模様の概観
「へたれBASIC」が行う処理の流れは、まずCInterpreterというクラスが舵取り役となって、 様々なクラスや関数が連携しあって(依存しあって)翻訳処理を進めて行きます。 ソースコードの最後まで翻訳が終わると、 CMachineクラスのオブジェクトが翻訳結果に従って、処理を実行して行きます。 これらの処理の流れはmain()関数の文中で、各オブジェクトに対する操作として記述されています。
ここで翻訳時の各クラスや関数の処理の分担について説明してみます。

main()はCInterpreterのInterpret()というメンバ関数を呼び出します、 この関数はソースコードを読み進めて、 実行コードの生成や、データ領域の設定など、実行時環境の構築を行います。
ソースコードの字句解析や構文解析は、それぞれyylex()、yyparse()という関数が行いますが、 CInterpreterはこれらの関数とのやり取りをラッピングしており、 CInterpreterのメンバ関数Interpret()のみからyyparse()が呼ばれ、yylex()はyyparse()のみ により呼ばれています。 また若干の例外はありますが、 これらの関数の内部からCInterpreterのメンバ以外の関数が 呼び出されることもないような設計にしています。

yyparse()は構文解析の過程でCInterpreterのGenXXXX()や、 MakeXXXX()というメンバ関数を呼び出して行きます。 これらの関数は各々の構文解析の段階に対応して、実行環境を用意するための意味的な処理を行う関数です。
CInterpreterは構文解析の過程で、組込みオブジェクトm_Treeを使って構文木の生成を行っています。 ただし現バージョンでは構文木のクラス化は不完全です。 CInterpreterは計算式を処理するために構文木を組み立てますが、構文木は文の構造までは表しておらず、 一つ一つの計算式を読み終える毎にm_Treeの内容は初期化可能です。 こうした理由から、CInterpreterがyyparse()から呼び出されるメンバ関数は、 意味的な検査と構文木の生成を行うMakeXXXX()と、 意味的な検査と実行コードの生成を行うGenXXXX()という2種類のバージョンに分れています。

CInterpreterは実行コード領域に書き出す各々のコマンドを、 型情報を表す抽象クラス「CDataType」のサブクラスに問い合わせる形で得ています。 各CDataTypeサブクラスはCInterpreterからコマンドのIDを受け取り、 自分の型に見合った処理を行う関数のポインタを返します。 これらの関数はCMachine内の組込みオブジェクトであるデータ(スタック)領域に対する操作を行います。 関数によってはコード領域など、他のCMachine内のオブジェクトと処理に必要な値のやり取りをします。 これらの関数はCMachineのメンバではありませんが、CMachineと互いに強く依存しているため、 CMachineのメンバ関数であってもおかしくない関数です。(メンバ関数にすると、型の種類を増やした時、 CMachineのインターフェイスを変更する必要が出てくるので、クラス外の関数としました。) これらの関数はOP_HANDLERという名前でtypedefされていて、 各CDataTypeサブクラスの実装部ファイル内に、ファイルスコープを持つ関数(static)として定義されています。 またOP_HANDLERはCMachineの実体へのアクセスをその引数や戻り値を介して行うのではなく、 CDataTypeサブクラスの静的メンバSetMachine()によってファイルスコープ上に設定される、 CMachineオブジェクトへのポインタを通じて操作を行います。
CDataTypeのサブクラスは型情報を表すと同時に、 実装の上ではCMachineが作り出す実行環境の一部と同居しています。
また、分岐やループなど、特定の型とは関係ない制御関連のコマンドはCMachineのGetCtrlHandler()に 問合せをしています。

またCInterpreterはソースコードから、yylex()が識別子(ID)として切り出した 文字列の種類を判断する処理を行っていますが、 その情報を文字列と共に保持しておくのが、CIdTable型のインスタンスです。 CInterpreterはソースコードから識別子を見つける毎に、CIdTableオブジェクトに その文字列の問い合わせを行い、その意味に即した処理を行うようになっています。

翻訳時の各種のエラーは、ほとんどの場合関数の戻り値としてエラー値を返すという形で、 呼び出し元にエラーの報告が伝播して行きます。多くの関数は、呼び出した先の関数でエラーがあれば、 自分の処理を打ち切って適当な後始末を行った後、エラー値を呼び出し元に返します。
最終的にCInterpreter内のMakeXXXX()や、GenXXXX()で、 FireError()がコールされ、標準エラー出力にエラーメッセージが出力されます。 MakeXXXX()や、GenXXXX()は基本的にyyparse()から呼ばれている関数ですが、これらの関数のエラー値をyyparse()がチェックすることは無く、致命的なエラー以外は、 何事も無かったように翻訳処理を続行します。 このため、一回の翻訳でソースコード中の複数のエラーを報告することができます。
構文上のエラーがあるとyyparse()はyyerror()を呼び出しますが、この関数はCInterpreterのFireError() をコールするようになっています。構文上のエラーは一行単位でリカバリできるよう、生成規則 を記述しました。

以上の処理の流れを大まかに図解してみました。 全てのクラスやインターフェイスを図示した訳ではありません。

yyparse()は正常に最後までソースコード読み進めると、 Interpret()に0を返して処理を抜けます。
最後にInterpret()は 実行時のデータ領域をする処理や、未解決のジャンプ先の後埋め処理などを行って処理を抜けます。


実行時環境・CMachineクラスについて
「へたれBASIC」はインタープリタ言語とはいうものの、一旦ソースコードを中間的な データ構造に翻訳し、そのデータ構造を実行するための関数を呼び出す方式を採ってます。
翻訳を司っていたのは、主にCInterpreter::Interpret()という関数でしたが、 生成された中間コードを実行するのが、CMachine::Go()という関数です。

実行に必要な情報は基本的にCMachineのデータメンバとして組込まれています。 中間コードを保持しているメンバはCCodeというクラスのインスタンスのm_codeという変数です。 このオブジェクトはコマンドハンドラ関数の アドレスや、それぞれの関数がその処理に必要とする値などが配列として並んだデータ構造と なっています。
CMachine::Go()は最初にm_codeの先頭を読み取って、値をOP_HANDLER型の関数ポインタとして、 呼び出します。呼び出した関数がエラー値を戻さなければ(0を返すならば)、読み取る位置を1つ進めて、そこの値をOP_HANDLER型の関数ポインタとして呼び出すという処理をずっと繰り返し続けます。
コード領域の最後にはCInterpreter::Interpret()によってfuncEnd()のアドレスが挿入されています。funcEnd()は 戻り値として-1を返しますので、Go()はループを抜けて、データ領域の後始末を行ってから処理を終えます。

CMachineにはコード領域の他にも、変数の値や実行の途中の計算結果を保持しておくためにCStack<TypedData>クラスのm_stackDataというデータメンバが組み込まれています。CStackはテンプレートクラスで任意の型の変数をスタックとして保持する事ができます。保持する対象となっているTypedDataという型は、処理の対象となる値とその削除用関数アドレスがセットになった構造体です。処理対象の値は各OP_HANDLER関数の中で任意の型にキャストされて使用されます。しかしその値の元々の型はint型(32ビット整数型)になっていて、もっと大きなデータを扱う場合は、別の場所にデータを確保して、TypedDataのメンバにはそのポインタをセットするという方法を採っています。プログラムの実行が終了した時にそのポインタを削除する処理を行う必要から、TypedDataには削除用関数のアドレスを保持するメンバも設けました。CMachine::Go()は実行ループを抜けた後に、残っている全てのデータの削除用関数を呼び出します。
CInterpreter::Interpret()がソースコード中で使われていた変数や定数を、このm_stackDataに予めPushしておくため、スタックの底には変数や定数の実現値が積まれています。
m_stackDataは実行の過程で(OP_HANDLERによって)計算される一時的な値を保持しておくためにも使われます。これらの値はCInterpreter::Interpret()によってPushされていた値のすぐ上から積まれます。

スタック上のデータ構造

1つのコード領域と、1つのスタック領域だけあれば、大抵の処理を行うことができるのですが、 1つのスタック領域に色々なデータ構造を詰め込んで表現するのが面倒だったので、「へたれBASIC」では配列の領域や、ループ、 サブルーチンコール用の管理領域を保持するために、特別な変数を用意しました。
配列を保持するためにCDynArrayクラスのm_DArrayというデータメンバを用意しました。このCDynArrayというクラスは、実際にはCHashedList<TypedData>のtypedefで、ハッシュ表をベースにして実装しています。CHashedListクラスの機能を利用して、動的連想配列をサポートすることにしました。動的連想配列は、添字として整数だけではなく、文字列も受け付けることができ、値をセットした時点で自動的に領域が確保されますから、配列の大きさを決めておく必要がありません。普通の配列(静的に確保され、整数の添字しか受け付けない配列)と比べれば効率は随分と悪くなりますが、インタープリタ言語は動的なのがウリ(?)なので、これで良しとしました。ただ、「へたれBASIC」は文字列処理機能が貧弱なので、連想配列にするメリットはあまりないです(爆)。まあ、これからの課題ということで…(^^;
ループやサブルーチンコール用の管理領域(データ構造としてはどちらもスタックです)は、CMachine::Go()が定義されているのと同じ場所に、ファイルスコープを持つ変数として宣言されています。なぜCMachineのメンバではないのかというと、単純に手抜きだったりします(爆)。

各種OP_HANDLER関数の働きは基本的には、これらのデータ領域の間でデータの出し入れを行ったり、データのコンソール入出力、そして処理の分岐を行うものです。

型システム・CDataTypeについて
「へたれBASIC」では型に関わる処理は、翻訳エンジンであるCInterpreterが 各CDataTypeサブクラスのインスタンスの助けを借りる形で実現しています。
CDataTypeは型に関係する処理を寄せ集めた抽象クラスで、インターフェイスの統一性が乏しいの ですが、大まかにその機能を分類してみると次のようになります。 CDataTypeサブクラスを便宜上「型クラス」、そのインスタンスを「型変数」と呼ぶことにします。

型等価判定
ある型変数と別の型変数が等価(同じ)かどうかを調べる処理です。 具体的にはCDataType::IsEquel()という関数がその判定を行い結果をbool値で返します。 この機能の実現のため、各型クラスのコンストラクタでは、 クラス毎に一意となるIDを割り振る処理を行っています。 IsEquel()はこのIDを比較することで、クラスの違いを認識しています。 また、同じクラスのインスタンス同士であった場合は、より細かい型の同定を行わなければいけません。 例えば“関数”という型の場合、(言語仕様によっても違ってきますが) 関数名と引数の個数や型が一致しなければ、同じ型と見なすことはできません。 IsEquel()にはこうした処理も行うものもあります。 しかし、大抵の場合はクラスが同じかどうかだけ分かれば良い場合が多いので、 型クラスにはsGetId()という静的関数も用意しました。これは型クラスのIDを返す関数なので、 返された値同士を比較すればクラスの違いをチェックできます。
定数などの実現値の保持
型クラスにはソースコード中に定数値として表れる数値や文字列を保持するためのメンバ変数があります。CInterpreterのメンバ関数で定数値に適した型変数が生成された後、 その定数の実現値が型変数のメンバに代入されます。 この値は翻訳処理を終えた後に、CMachineのデータ領域にPush()されたり、 コード領域に書き込まれたりします。
記憶クラスの分類
記憶クラスは、ある変数(実現値)が、実行時にどこに置かれるのかを表す情報です。 「へたれBASIC」では「変数」、「コード領域のオペランド」の2つを分類しています。 変数はデータ領域の底に積まれますが、「コード領域のオペランド」の場合は、コード領域に OP_HANDLERが直接取り込むための値として書き込まれます。 翻訳語の後処理の中で、各型クラスは記憶クラス情報を元に処理を分岐するものがあります。 データを置いておく場所は、他にも配列用の領域などもありますが、 記憶クラスについては現バージョンではしっかりとした定義付けを行っておらず、 1つ1つの型クラスの実装の中で、適当に記憶場所を決定しているものが多いです。 スコープなどの概念を取り入れ出したら、もっとしっかりと定義する必要がでてくるかと思います。
コマンド処理関数の提示
四則演算や、参照(PUSH)、代入(POP)、型変換、などの処理をCInterpreterのメンバ関数から要求 され、 その型に見合った処理を行う関数のアドレスを返します。要求された処理が、 その型に見合ったものでない場合は、エラー値を設定してから0を返します。 呼び出し側は0が返された場合は、 その型変数が持っているエラー値を取得して、エラーを報告します。
実行時環境の一部
型クラスが定義されているファイルスコープでは、 実行時の処理を行うOP_HANDLER関数も一緒に定義されています。 各OP_HANDLER関数は、型クラスのSetMachine()という関数によって設定されるポインタ を通じてCMachine(実行時環境)のインスタンスを操作します。
各CDataTypeクラスは変数を表すものであっても定数のものでも、CInterpreterのMake〜()やGen〜()に よって生成され、m_idTable(記号表)に吊るされて管理されます。 定数の場合は名前がないので、CInterpreterによって他と重複しない仮の名前を付けられてから 吊るされます。 CDataTypeクラスは翻訳処理を行っている間、Make〜()やGen〜()の中で 構文木のノードの属性値を通じて参照されたり、記号表から辞書引きされます。

各種下請けクラスたち
「へたれBASIC」には翻訳処理や、プログラミング言語としての機能を支援するため、下請けとなって機能するクラスが幾つかあります。
CStrは文字列型を扱うクラスで、文字列の連結やコピーなどを「+」や「=」などの演算子を使って行えるようにオーバロードを施しています。
CStringBufferクラスは文字列を登録しておいて、後から識別番号を指定することでその文字列に参照できるクラスです。何のために使うのかというと、yylex()が切り出してきた文字列を保管しておくために使われています。yyparse()はyylex()から受け取った属性値を内部のスタックに保持しているので、CInterpreter内の関数がその属性値を知る頃には、yylex()はソースコードのもっと後方の文字列を読み取っている状態です。このためyylex()内部の文字列バッファのアドレスを属性値として受け取っても、意味のある文字列を受け取ることはできません。そのためyylex()では識別子を切り出した時点で、CStringBufferクラスのインスタンスにその文字列を登録し、属性値としてその識別番号を返すという処理(アクション)を行うようにしています。
CStackは任意の型の変数をスタック構造で保持するためのテンプレートクラスです。Push()やPop()などのスタックには必須の操作を行う関数を用意していますし、スタックに積まれたデータを配列として参照することも出来ます。
CDagはデータを木構造に保持するために用意したクラスですが、 このクラスは抽象化が不完全でして、木構造を保持するというよりは、 任意の4つのint型の組み合わせを保持するという表現の方が、 このクラスのインターフェイスを正確に説明しています。 この4つのint型は、CDag型の変数を使っているCInterpreterのMake〜()やGen〜()などの関数の中で、 任意の型へキャストして使われています。
CHashedListクラスは任意の型のデータをハッシュ表に記憶するためのテンプレートクラスです。ハッシュ表は数値や文字列をキーに使って特定のデータを比較的高速に見つけ出すことができるデータ構造です。1つ1つの項目がリスト構造になっている配列として実装されています。検索を始める時に、どのリスト構造(バケット)を検索するのかを予め計算しておくことができるので、一本のリストを頭から検索するのと比べ、平均して高速に検索することができるのです。

ハッシュ表

CIdTableは記号表といって、文字列をキーにして任意のデータを保持・検索のできるデータ構造を表すクラスです。記号表の要素として使っているのがCIdentiferというクラスで、ソースコードに現れる識別子と、その内容(変数なのか、ラベルなのかなど)をセットにした構造体となっています。
記号表の実装にはハッシュ表がしばしば使われるのですが、CIdTableはCHashedListとは一切無関係に実装されています。何故なのかといへば、CIdTableの方がCHashedListより先に作られたからです(爆×3)。

エラーレポート処理
「へたれBASIC」では"error.h"というヘッダファイルで、エラーメッセージの文字列の配列と、対応するエラー番号が定義されています。
これらのエラーは翻訳中のエラーであった場合は、CInterpreter::PutError()が標準エラー出力にエラーを書き出し、実行時の場合は、CMachine::PutError()がエラーを書き出します。何故一つにまとまってないのかというと、アドホックな開発工程の賜物…(爆^爆)。

 
前のページへ  次のページへ
言語処理系の制作に戻る
もくじに戻る