構文解析過程は二つの部分から構成されます：
gram.yとscan.lで定義され ている パーサはUnixのツールyacc と lexを使って作られています。
変換プロセス はパーサから返されたデータ構造の 変更や追加をします。
パーサは問い合わせ文字列(ASCIIテキストとして渡される)が正しい構文になる ように チェックしなければいけません。もし構文が正しい場合は構文解析 ツリーが作られ返されます。 正しくない場合はエラーが返されます。実装にはUnixのよく知られたツールで ある lexとyaccが使わ れています。
字句解析はファイルscan.l で定義 されており、識別子やSQLキーワード の認識をします。認識されたすべての キーワードや識別子に対してトークンが作られパーサ に渡されます。
パーサはファイルgram.yの中で定義されており、 文法ルールとルールが実行されたときに起こる アクションのセットから構成されています。 アクションのコード(Cコードで書かれています)は構文解析ツリーを作るのに 使われます。
ファイルscan.lはプログラムlex を使ってCのソースファイルscan.cに変換されます。 そしてgram.yはyaccを 使って gram.cに書き換えられます。これらの書き換えが終る と、パーサを作るために通常のCコンパイラが使えるようになります。作られた Cのファイルには変更を加えないで下さい。次にlex かyaccが呼ばれた時にそれらは 上書きされてしまいます。
Note: ここで述べられた書き換えやコンパイルは通常Postgres のソースと 一緒に配布されるメイクファイル を使って自動的に行われます。
yaccやgram.yで定義される 文法ルールの詳しい説明は本稿では説明しきれません。lex やyaccについては本や資料が沢山出ています。 gram.yの文法の勉強を始める前にyacc の知識を得ておくことをお勧めします。その知識を持たないと、何が起こって いるのか理解するのが 難しいと思います。
問い合わせを処理するために Postgresで使われるデータ構造をわかりやすく 説明するため、 処理の過程でこれらのデータ構造に加えられる様子を表す例を使いたいと思い ます。 この例はこれからのセクションの様々な説明でも使われる簡単な問い合わせを 含んでいます。 この問い合わせではサプライヤーデータベースで使わ れるテーブル は既に定義済であると仮定しています。
Example 2-1. 単純なセレクト文
select s.sname, se.pno
from supplier s, sells se
where s.sno > 2 and s.sno = se.sno;
図\ref{parsetree}はExample 2-1で与えられる問い合わせ のために gram.yで定義された、ルールとアクションによって 作られる構文解析ツリーを表します。(一つの図で 両方のデータ構造 を見せるスペースがなかったため、\ref{where_clause}で表される where句のための演算子ツリー は入っていません。)
Treeの頂点にあるのはSelectStmtというノードです。 SQLの問い合わせのfrom句に現れる全てのソース テーブルに対しエイリアスの名前と、 リレーションの名前を持つ RelExprノードのポインタを 持つRangeVarノードが作られます。 全てのRangeVarノードはSelectStmt ノードのfromClauseフィールドに付けられたリストに 集められます。
SQL問い合わせのセレクトリストに現れるそれぞれの 項目に対して、 Attrノードへのポインタを持つResTarget ノード が作られます。 Attrノードはその項目のリレーション名 と 属性の名前を持つValueノードへのポインタ を持ちます。すべての ResTargetノードはSelectStmt ノードのフィールド targetListと接続されたリストにまとめられます。
図 \ref{where_clause} はSelectStmtノードのフィールド qual に付随されたExample 2-1で与えられる、SQL問い合わせの where句のための 演算子ツリーを表します。 演算子ツリーの頂点の節はAND操作を表すA_Expr ノードです。 このノードは二つのサブツリーを指すlexpr とrexprという 子節を持ちます。lexprに付随されたサブツリーは s.sno > 2 の条件を表し、rexprに付随されたものは s.sno = se.sno を表します。それぞれの属性に対してリレーションの名前と属性名 を持つValueノードへのポインタを持つAttr ノードが 作られます。問い合わせにあらわれる定数に対しては、定数の値を 保持するためにConstノードが作られます。
書き換えプロセスはパーサから引数としてツリーを 受け取り、その中を再帰的に移動します。 もしSelectStmtノードが見つかった場合、それは新しい データ構造の頂点になるQueryノードに書き換えられます。 図\ref{transformed}は、書き換えられたデータ構造を表しています。 (一つの図で全てを示すスペースがなかったため、 書き換えられたwhere句の 部分は\図ref{transformed_where}で示されています。)
もしFROM句のリレーション名 がシステム に認識された場合、ここで照合が行われます。システムカタログ に存在するすべてのリレーション名に対して、リレーション名、 エイリアス名 、そしてリレーションIDを持つRTE ノードが作られます。 ここからはリレーションIDは問い合わせで作られるリレーション を参照するために使われます。すべてのRTEノードは、 Queryノードの rtableフィールドと結びつけられた レンジテーブルエントリーリスト (range table entry list) に納められます。もしも問い合わせの中でシステムが認識できないリレーション が発見された場合、 エラーが返され問い合わせプロセスはアボートされます。
次に、属性名が問い合わせで使われる リレーション の中に含まれているかがチェックされます。 見つかった全ての属性に対して、 Resdom ノード(カラム名を持ちます)へのポインタとVAR ノードへのポインタを持つ TLE節が作られます。VARノードには重要 な二つの数字があります。 フィールドvarno は上でエントリーリストが作った範囲の なかで現在の 属性を持つリレーションのポジションを示します。フィールド varattno はリレーション内の属性のポジションを示します。もし属性の名前が見付けられ ない場合、 エラーが返され問い合わせプロセスはアボートされます。