パーサは二段階で構成されています。
gram.y と scan.l ファイルで定義されたパーサは UNIX の yacc と lex ツールを使って構築されます。
変換プロセスはパーサから戻されたデータ構成に 変更と引数づけを行います。
パーサは(シンプルな ASCII テキストで届けられた)問合せ文字列が 正しい構文であるかどうかを調べます。構文が正しければパースツリーが 生成されて戻されますが、正しくない場合エラーが返されます。 実装するには UNIX では良く知られているツール、 lex と yacc が使用されます。
lexer は scan.l ファイルで 定義され、識別子、 SQL キーワードその他を認識する役割を持っています。 見つかった全てのキーワード又は識別子に対し token が発行されパーザに渡されます。
パーサは gram.y ファイルで定義され、 文法 rule とその rule が放った アクション(action)の組みで構成されます。 アクションのコードは(実際にはCプログラムです)パースツリーを生成する のに使用されます。
scan.l ファイルは、プログラム lex により C のソースファイル scan.c に、gram.y ファイルは yacc により gram.c に変換されます。これらの変換後、 通常の C コンパイラでパーサが生成可能となります。生成された C の ファイルは、次回 lex 又は yacc が呼ばれたときに上書きされるため、 変更をしてはいけません。
Note: ここで記述した変換とコンパイルは通常 Postgres ソース配付物に同梱される makefiles で自動的に行われます。
yacc 又は gram.y で規定されている文法 rule の詳細は本論文の範疇を越えるものです。 lex 及び yacc に関しては多数の書籍やドキュメントが存在します。gram.y で規定されている文法 rule を学ぶ前に yacc を熟知しておかないと、そこに何が書いてあるのか多分理解できないでしょう。
問合せ処理のために Postgres が使用する データ構造をより良く理解するため、それぞれのステージでデータ構造 に対して行われる変更について例示することにします。
Example 22-1. 単純な Select
この例は簡単な問合せで、以降の節を通して色々な場面での 記述と図とで参照されます。 問合せは The Supplier Database で与えられる テーブルが既に定義されているものと仮定しています。
select s.sname, se.pno
from supplier s, sells se
where s.sno > 2 and s.sno = se.sno;
図 \ref{parsetree} は 単純な Selectこの例は簡単な問合せで、以降の節を通して色々な場面での 記述と図とで参照されます。 問合せは The Supplier Database で与えられる テーブルが既に定義されているものと仮定しています。 select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno; で与えられた問合せに対しての gram.y で与えられた 文法 rule とアクションによって生成されたパースツリーを示しています。 図 \ref{where_clause} で示した where 句による 演算子ツリーは、二つのデータ構造 を一つの図にまとめることが紙面の大きさの制約上出来ないため、 省略してあります。
ツリーの最上ノードは SelectStmt ノードです。 SQL の問合せでの from 句の全ての項目 に対してエイリアス名を持った RangeVar ノードと、リレーション 名を持った RelExpr ノードへのポインタが生成されます。 全ての RangeVar ノードは SelectStmt ノードの fromClause に付けられるリスト にまとめられます。
SQL の問合せでの select list の全ての項目 に対して Attr ノードへのポインタを持った ResTarget ノードが生成されます。 Attr ノードはその項目の リレーション名と、属性 名を持った Value ノードへのポインタを所持します。 全ての ResTarget ノードは SelectStmt ノードの targetList フィールドに接続されるリストに納められます。
図 \ref{where_clause} は SelectStmt ノードの qual フィールドに添付される、例 単純な Selectこの例は簡単な問合せで、以降の節を通して色々な場面での 記述と図とで参照されます。 問合せは The Supplier Database で与えられる テーブルが既に定義されているものと仮定しています。 select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno; で示した 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 ノードは、 問合せノード の rtable フィールドに接続する range table entry list にまとめられます。 システムに登録されていないリレーションが検出された場合はエラーが返され 問合せ処理は終了します。
次に問合せで与えられたリレーションの中に 属性名が 用いられているかどうか検証されます。 検出された全ての属性に対し（カラム名を持った）Resdom ノードと VAR ノードへのポインタを持った TLE ノードが生成されます。 VAR ノードには重要な二つの数値が あります。varattno フィールドは、上で作られた range table entry list にある現在の属性を持ったりレーションの場所を 知らせます。 varattno フィールドはりレーション内での属性の位置 知らせます。 属性名が検出されなかった場合はエラーが返され問合せ処理は終了します。