他のバージョンの文書10 | 9.6 | 9.5 | 9.4 | 9.3 | 9.2 | 9.1 | 9.0 | 8.4 | 8.3 | 8.2 | 8.1 | 8.0 | 7.4 | 7.3 | 7.2

2.3. 構文解析過程

構文解析過程は 2 つの要素で構成されます。

2.3.1. パーサー

パーサーは、(平文 ASCII テキストとして渡される)問い合わせ文字列が正しい構文になっているかチェックしなければいけません。もし構文が正しい場合は 構文解析ツリーが作られて返されます。正しくない場合はエラーを返します。実装には Unix のよく知られたツールの lexyacc が使われています。

字句解析はファイル scan.l で 定義され、識別子SQL キーワード の認識をするものです。認識されたすべてのキーワードや識別子に対し トークンが生成されパーサーに渡されます。

パーサーはファイル gram.y の中で定義され、 文法ルールとルールが実行されたときに実行される アクションの組から構成されています。アクションのコード(実際は C 言語コード)は構文解析ツリーを作るのに使われます。

ファイル scan.l はプログラム lex を使って C のソースファイル scan.cに変換されます。そして gram.yyacc を使って gram.c に書き換えられます。これらの書き換えが終わると、パーサーを作るために通常の C コンパイラが使えるようになります。生成された C のファイルには絶対に変更を加えないでください。次に lexyacc が呼ばれたときに上書きされてしまいます。

Note: ここで言及した書き換えやコンパイルは通常 PostgreSQL のソースと一緒に配布される makefile を使って自動的に行われます。

yacc または gram.y で定義される文法ルールの詳しいことは本稿では説明しきれません。 lexyacc については本や資料がたくさん出ています。gram.y の文法の勉強を始める前に yacc の知識を得ておくことをお勧めします。その知識なしでは何が起こっているのか理解することは難しいでしょう。

問い合わせの処理時に PostgreSQL で使われるデータ構造をわかりやすく説明するため、処理の過程でこれらのデータ構造に加えられる様子を表す例を使いたいと思います。この例には引き続く節にわたってさまざまな記述と図示に使われているつぎのような簡単な問い合わせがあります。この問い合わせでは、「サプライヤーデータベース」 がすでに定義済であると仮定します。

Example 2-1. 単純な SELECT 文

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 句に対する 演算子ツリーは除いてあります)。

ツリーの頂点にあるのは SelectStmt ノードです。SQL 問い合わせ文の from 句で指定されるすべての項目に対し エイリアスという名前と、リレーション という名前の RelExpr ノードへのポインタを持った RangeVar ノードが作られます。すべての RangeVar ノードは SelectStmt ノードの fromClause フィールドに添付されたリストに集められます。

SQL 問い合わせ文のselect listに現れるすべての項目に対して、Attr ノードへのポインタを持つ ResTargetノードが作られます。Attr ノードはその項目のリレーション名属性 という名前の Value ノードへのポインタを持ちます。すべての ResTarget ノードは SelectStmt ノードのフィールド targetList と連結したリストにまとめられます。

図 \ref{where_clause} は、SelectStmt ノードのフィールド qual に付帯した SQL 問い合わせ Example 2-1 で与えられている where 句用の演算子ツリーを示しています。演算子ツリーの頂点の枝は AND 操作を表す A_Expr ノードです。このノードは 2 つのサブツリーを指し示す lexprrexpr という子枝を持ちます。 lexpr にくっ付けられたサブツリーはs.sno > 2 の条件を示し、rexpr に付けられたされたものは s.sno = se.sno を示しています。すべての属性に対してリレーション名と属性名を持った Value ノードへのポインタを保有する Attr ノードが作られます。問い合わせにあらわれる定数に対しては、定数の値を保有するために Const ノードが作成されます。

2.3.2. 書き換えプロセス

書き換えプロセスは、パーサーから引数としてツリーを受け取り、中身を再帰的に処理して行きます。SelectStmt ノードが見つかると、新しいデータ構造の頂点になる Query ノードに書き換えられます。図 ref{transformed} は、書き換えられたデータ構造を表しています(書き換えられた where 句の所はすべての部分をひとつの図に収めるスペースがないので \ref{transformed_where}に示してあります)。

FROM 句リレーション名がシステムに認識された場合、ここで照合が行われます。システムカタログ に存在するすべてのリレーション名に対して、リレーション名、 エイリアス名リレーション ID を持つRTEノードが作られます。ここからはリレーション ID は問い合わせで与えられるリレーション を参照するために使われます。すべての RTE ノードは、 Query ノードの rtable フィールドと結び付けられたレンジテーブルエントリリスト(range table entry list) に収容されます。問い合わせの中でシステムが認識できないリレーションが発見された場合は、エラーが返され問い合わせ処理はアボートされます。

次に、属性名が問い合わせで使われるリレーションの中に含まれているかチェックされます。見つかったすべての属性に対して、(列名を持った) Resdom ノードへのポインタと VAR ノードへのポインタを持つ TLE ノードが作られます。VAR ノードには 2 つの重要な数字があります。フィールド varno はリレーションの中での属性の場所を示します。もし属性の名前が見付けられない場合、エラーが返され問い合わせ処理はアボートされます。