1. はじめに

こんにちは。ホクソエムサポーター（名称審議中）の藤岡です。字句解析を紹介した前回の記事に続き、今回もsqlparseを中心に据えつつ狭義の構文解析について紹介・解説していきたいと思います。また、狭義の構文解析で得られる構文木を解析するためのいくつかのメソッドについても解説します。

2. 注意

本記事に書かれた内容は自分の理解に基づいたものであり、誤りが含まれている可能性がありますが、ご了承ください。
もしそういった不備にお気付きの際には、コメントでご指摘いただければ幸いです。
また、以下の解説ではSQLが何度か登場しますが、すべてHiveQLです。
今回のサンプルプログラムは説明用に作成したものであり、不具合等が含まれる可能性が多分にあります。
本記事の理解には木構造と字句解析についての簡単な知識が必要です。後者については、前回の記事を読んでいれば問題ないかと思います。
前回の記事で予告していた内容は~~尺不足~~諸般の事情により次回に持ち越しになりました。

3. 狭義の構文解析

狭義の構文解析とは、字句解析をして得られたトークン列に対して、ある文法規則に基づいた構文構造を与える処理です。この部分を厳密に扱うと難解になってしまうので、字句解析同様sqlparseにフォーカスして解説していきます。

3.1 構文木とは

sqlparseの場合*1、SQLクエリを字句解析して得られたトークン列（Statement, DML, Comment ... からなる系列）を入力として、構文木（parse tree） を返します。これはその名の通り木構造データで、その各要素は以下の通りです。

根ノード: 　入力クエリ全体を表すトークン。
内部ノード: 複数のトークンを束ねたトークン。
葉ノード: 　字句解析の結果得られた最小単位のトークン。

まず、以下のような簡単な例から作られる構文木を見ていきましょう。

SELECT
    id,
    age,
    CAST(age / 10 as integer) as generation
FROM ages

私たち人間がこのクエリを読むとき、ある程度のまとまりをもって解釈していきます。つまり、id, age, generationの三つのカラムをSELECTして、そのうちgenerationは CAST(age / 10 as integer) の結果で、他の二つはそのままagesテーブルから......といった具合です。また、generationを解釈するためには、まずageカラムがあり (age) 、それを10で割った値を作り (age / 10) 、最後にそれをIntegerにキャストする (CAST(age / 10 as integer)) といったように、意味的なまとまりで括りながら全体像をくみ上げるように理解していきます。

一方、上のクエリをたんに字句解析して空白を取り除いただけだと、以下のような結果が返ってきます。

tokens = [t for t in sqlparse.parse(sql_1)[0].flatten() if not t.is_whitespace]
tokens

>[<DML 'SELECT' at 0x112C43F48>,
 <Name 'id' at 0x1117190A8>,
 <Punctuation ',' at 0x111719108>,
 <Name 'age' at 0x111719348>,
 <Punctuation ',' at 0x1117193A8>,
 <Name 'CAST' at 0x1117195E8>,
 <Punctuation '(' at 0x111719648>,
 <Name 'age' at 0x1117196A8>,
 <Operator '/' at 0x111719768>,
 <Integer '10' at 0x111719828>,
 <Keyword 'as' at 0x1117198E8>,
 <Builtin 'integer' at 0x1117199A8>,
 <Punctuation ')' at 0x111719A08>,
 <Keyword 'as' at 0x111719AC8>,
 <Name 'genera...' at 0x111719B88>,
 <Keyword 'FROM' at 0x111719C48>,
 <Name 'ages' at 0x111719D08>]

この情報だけでは、先頭から順にSELECTがきて、idがきて、カンマがきて......という、人間の解釈方法とはかけ離れた読み方になってしまいます。このギャップを埋めるために必要なのは、トークン列中のとある部分列を意味や役割に照らし合わせながら適切なまとまりとして抜き出すこと、その操作を再帰的に繰り返し、最後に一つの意味を構築することの二つが必要です。

この操作こそが狭義の構文解析であり、その結果として得られるのが構文木です。 age / 10の構文木を図で表すと図1のようになります。

f:id:kazuya_fujioka:20200211011756j:plain — `age / 10`の構文木

四角で囲われた部分がトークンです。この図では、トークンと対応する文字列が四角の中に表記されています。このように、字句解析の結果では元のクエリのうち狭い範囲と対応するトークンがたくさん並んでいる状態だったのが、狭義の構文解析によって一つに統合されているのが分かります。そして、この図だと少し分かりにくいですが、きちんと木構造になっているのが分かります。

では、今度はトークンの表記を少し変えてみます。

f:id:kazuya_fujioka:20200211011932j:plain — `age / 10` の構文木（トークンでの表記）

この図から、構文木の各ノードはその対応する部分文字列の意味を表していることが見てとれます。つまり、構文木は様々なレベルにおけるクエリの意味を格納したデータであると言い換えることができます。

それでは、上の例における構文木をsqlparseを使って見てみましょう。

# 1. 除算の演算子を取り出す。
t = tokens[8]
> <Operator '/' at 0x111719768>

# 2. 除算の演算を取り出す。
str(t.parent), t
> 'age / 10'
('age / 10', <Operation 'age / ...' at 0x1121180C0>)

/は演算子を表すOperatorトークンで表現されています。この演算は2つの項ageと10とを合わせたage / 10というまとまりとして解釈されるのが自然です。実際、その親（parent属性）にはage / 10と対応するトークンオブジェクトが格納されていることが分かります。加えて、このトークンオブジェクトは演算を表すOperationトークンとなっています。

この結果から、age, /, 10の3つの文字列に対応するトークンは、age / 10に対応するOperationトークンの子孫とみなすことができます。

当然、age, 10に対応するトークンからもそれぞれage / 10に対応するトークンへと遡ることができます。

#1. `age`のgrandparent
tokens[7].parent.parent
> <Operation 'age / ...' at 0x1121180C0>

#2. `10`のparent
tokens[9].parent
> <Operation 'age / ...' at 0x1121180C0>

では、このOperationトークンの先祖をさらに辿っていくとどうなるでしょうか？

str(t.parent.parent), t.parent.parent
> ('age / 10 as integer', <Identifier 'age / ...' at 0x112118138>)

str(t.parent.parent.parent), t.parent.parent.parent
> ('(age / 10 as integer)', <Parenthesis '(age /...' at 0x111DC2C00>)

str(t.parent.parent.parent.parent), t.parent.parent.parent.parent
> ('CAST(age / 10 as integer)', <Function 'CAST(a...' at 0x111DC2CF0>)

と、このように意味的なまとまりを段階的に構成しながら、どんどんとトークンどうしが統合されていっていることが見て取れます。

図で表すと以下の通りです。

f:id:kazuya_fujioka:20200211012852j:plain — `CAST(age / 10 as integer)`の構文木

もっとも、age / 10 as integerがIdentifierトークンとして解釈されてしまっている（=型を表すintegerがエイリアスだと判定されている）ように、sqlparse.parseの結果には意味的に誤ったトークンも時折見られます。

プログラムに組み込む際はきちんとテストケースを作るか、それが難しい場合は実際の挙動を確認しつつ組み込むのが確実です。

3.2 構文木の利点

クエリをトークンの木として扱えることの真価は、クエリが複雑である場合に発揮されます。例えば、以下のクエリを考えてみます。

SELECT
    id,
    a.age,
    a.generation,
    g.gender
FROM (
    SELECT
        id,
        age,
        CAST(age / 10 as integer) as generation
    FROM ages
) a
INNER JOIN genders g
ON a.id = g.id

前の例との大きな違いはサブクエリの存在です。 SQLではサブクエリを再帰的にもつことができる、つまりサブクエリの中に別のサブクエリ、ということが理論上は制限なく繰り返されるため、これをトークンの列を使って解析するのは骨が折れる作業です。

一方、木構造ではこうした再帰構造を部分木として表現することができるので、部分問題に分割して解くことができます。また、よく使われるデータ構造であり、その解析をより一般的な問題に落とし込んで解くことができます。例えば、サブクエリを全部探索する問題は、ただの部分木探索問題へと落とし込むことができます。 sqlparseを使えば、実装も簡単です。

from sqlparse.tokens import DML
from sqlparse.sql import TokenList, Token

def iter_subqueries(token: Token):
    if token.ttype == sqlparse.tokens.DML:
        yield token.parent
    if not isinstance(token, TokenList): # リーフノードの場合は子を探索しない
        return
    for t in token:
        yield from iter_subqueries(t)

実行してみると、うまく動くことがわかります。

sql_2 = """
SELECT
    id,
    a.age,
    a.generation,
    g.gender
FROM (
    SELECT
        id,
        age,
        CAST(age / 10 as integer) as generation
    FROM ages
) a
INNER JOIN genders g
ON a.id = g.id
"""
list(iter_subqueries(sqlparse.parse(sql_2)[0]))

> [<Statement ' SELEC...' at 0x11287C8B8>, <Parenthesis '( ...' at 0x11287C840>]

構文木の部分木として表すことのできるのは、サブクエリだけではありません。例えば、3.1節のサンプルのような関数やその引数、SELECT節の中のカラムリスト、JOINの条件節など、様々な部分を部分木として取り出すことができます。

4. 構文木の走査

構文木を解析するときには、3節のように親や子、兄弟を渡り歩いていくように進めていきます。このように木のノードを辿っていくことを走査（traverse）と言います。 sqlparseの構文木を構成するトークンオブジェクトには、構文木の走査を簡単に実装するための種々のメソッドや属性が定義されています。本節ではそれらを簡単に紹介します。

4.1 親子の参照

sqlparseのトークンオブジェクト（sqlparse.sql.Token）はそれぞれが構文木における親への参照情報を持っています。加えて、葉ノード以外のトークンオブジェクト（sqlparse.sql.TokenList）は子への参照情報も持っています。

親へはparent属性、子へはtokens属性から参照できます。後者については、トークンオブジェクトに対して直接インデックスを指定してもOKです。例えば、token.tokens[0]はtoken[0]と同じ結果を返します。

4.2 子の走査・探索

基本的に構文木を走査する場合には根から葉へと進んでいきます。つまり、あるトークンtが与えらたとき、その子t.tokens[0], t.tokens[1], ..., t.tokens[i], ..., t.tokens[N]を再帰的に解析していくプロセスです。 0-Nのインデックスiを直接人手で扱うのもいいですが、sqlparseのトークンオブジェクトにはそれをサポートする種々のメソッドが定義されているので、それらを活用した方が確実です。ここでは、それらの機能を紹介します。

4.2.1 先頭トークンの取得

まず、一番シンプルに走査するなら先頭の子トークンを取り出すことになると思います。先頭トークンはtoken_firstメソッドから参照できます。必須の引数はなく、t.token_first()とするだけでもOKです。

なお、単に先頭を取り出すだけならばt[0]でいいと思われるかもしれませんが、このメソッドの真骨頂は、状況に応じてコメントと空白をスキップすることができる点です。コメントをスキップするにはskip_cm引数をTrueに、空白をスキップするにはskip_ws引数をTrueにします。

ただし、戻り値はトークンのインデックスなので、トークンオブジェクト自体を取り出す場合にはt.tokens[t.token_first()]としましょう。該当するトークンがない場合にはインデックスの代わりにNoneが返ってきます。

4.2.2 前後のトークンの取得

あるノードからその前後の兄弟トークンへと辿っていくときには、 token_next, token_prevの2つのメソッドを使います。例えば、tとその子トークンuのインデックスi_uが与えられたとき、 t.token_next(i_u)とすれば、その次のトークンが得られます。token_prevも同じ使い方で1つ前のトークンを取得できます。

ただし、戻り値はタプル(u, i_u)なので、間違えないように注意してください。また、token_firstと同様の方法でコメントや空白のスキップも可能です。該当するトークンがない場合には(None, None)が返ってきます。

4.2.3 マッチングによる探索（ちょっと発展）

コールバック関数による条件指定*2をすることで、その条件にマッチした最初のトークンを探し出すことができます。

使うのはtoken_matchingメソッドです。第一引数にコールバック（もしくはそのリストないしタプル）を渡し、第二引数に探索範囲の先頭となるトークンのインデックスを渡します。

コールバックの戻り値は、マッチした場合にif文の中で真と判定され、それ以外の場合に偽だと判定されるような定義とします。第一引数で複数のコールバックを渡した場合、それらのいずれかを満たす（OR）を満たすトークンが返ってきます。

例えば、文字列が"foo"となっている最初のトークンを探索する場合、

t.token_matching(lambda t: t.value=="foo", 0)

とします。他にも、IFとELSEのいずれかのKeywordトークンとマッチさせる場合には、

t.token_matching(lambda t: t.match(Keyword, "IF") or t.match(Keyword, "ELSE"), 0)

もしくは

t.token_matching([lambda t: t.match(Keyword, "IF"), lambda t: t.match(Keyword, "ELSE")], 0)

とすればOKです。

戻り値はトークンのインデックスです。マッチしなかった場合にはNoneが返ってきます。

4.2.4 トークンインデックスの取得

トークンオブジェクトが得られているけれど、そのインデックスが不明という場合にはtoken_indexメソッドを使います。 tとその子トークンuが与えられたとき、uのインデックスi_uはt.token_index(u)で得られます。 uがtの子ではない場合にはValueErrorがraiseされるので注意しましょう。

4.3 値の解析

基本的にはvalue属性を正規表現等で解析するだけなのですが、いくつかのケースはsqlparseに定義されている機能を使った方が確実なので、それらも簡単に紹介します。

4.3.1 名前の取得

テーブルやサブクエリ、変数等はユーザーが定義した名前やエイリアスを持っている場合があり、それらは以下の4メソッドで取得できます。

get_real_name: 名前を返す。
get_alias: エイリアスを返す。
get_name: 呼び出し名を返す。エイリアスと名前が両方定義されている場合は、そのトークンが存在する場所での名称を返す。
get_parent_name: parent_name (table_foo.col_barであればtable_foo) を返す。

いずれも、値が取得できなかった場合にはNoneを返します。

4.3.2 引数の取得

Functionクラスのトークンオブジェクトは、その対応する関数の引数をget_parametersメソッドで取り出すことができます。

戻り値は各引数を表現したトークンです。

4.3.3 CASE文の各条件の取得

CASE文で指定される複数の条件は、Caseクラスのトークンオブジェクトに定義されているget_casesメソッドで取り出すことができます。

戻り値は(条件, 値)という形式のタプルのリストです。 ELSEの場合は条件の値がNoneになります。

4.3.4 値の正規化

value属性に入っている値は解析対象のクエリの文字列そのままなので、 SELECTが"Select"、" select"として格納されている可能性があります。一方でnormalize属性には正規化済みの値（上の例では共通して"SELECT"）が入っているので、各種キーワードを解析したい場合にはこちらを使いましょう。

5. おわりに

ここまでの2回の記事でsqlparseを使うための前提知識をあらかた押さえることはできると思います。

とはいえ、sqlparseは「どんな機能があるのか」が分かった上で「それをどう活用するのか」という部分を理解するのが重要なライブラリだと思います。そこで、次回の記事では（今度こそ）実際にsqlparseを本格的に活用するサンプルを紹介したいと思います。

一応、次回解説するサンプルコードは記事の公開に先立って公開します。プログラムを動かして遊べるように簡単なインターフェースも実装しているので、よければ遊んでみてください。

github.com

Pythonプログラミングという観点からも、これまでより高度な内容になりますが、次回もぜひ読んでいただければ幸いです。

Python実践入門 ── 言語の力を引き出し、開発効率を高める (WEB+DB PRESS plusシリーズ)

作者:陶山嶺
出版社/メーカー: 技術評論社
発売日: 2020/01/24
メディア: 単行本（ソフトカバー）

*1:このように書いていますが、自分の知る限りでは狭義の構文解析の入出力はたいていの場合で sqlparse と同様です。

*2:Pythonだとsorted関数におけるkey引数が代表例です。

株式会社ホクソエムのブログ

R, Python, データ分析, 機械学習

sqlparse 入門 - 狭義の構文解析編 -