構文解析
字句解析から送られて来たトークンの意味を理解して構文木を作るプロセスを、「構文解析」と言います。本格的な構文解析器は、通常 yacc 等のツールを利用して自動で作ることが多いですが、今回の正規表現の文法は単純なので自作してしまいます。
文法規則
構文解析を実装するため、まず、正規表現の文法規則をもっと具体的に記述します。最初のルールを基に、以下のように文法規則を作り込みました。
- （A） expression -> subexpr EOF
- （B） subexpr -> seq '|' subexpr | seq
- （C） seq -> subseq | ''
- （D） subseq -> star subseq | star
- （E） star -> factor '*' | factor
- （F） factor -> '(' subexpr ')' | CHARACTER
このような記法で表す文法は、「文脈自由文法」（CFG: Context-free Grammer）と呼ばれます。各ルール中で左側に現れる名前を「変数」または「非終端記号」と呼びます。この文法規則では、変数は全て小文字で書きました。逆に、右側にしか現れない名前は、終端記号と呼びます。今回の終端記号は、シングルクォートでくくった文字（'|'等）や大文字で記載されたトークン種別（CHARACTER, EOF）です。
各変数は、右辺に書かれた変数や終端記号に展開できます。また、規則中の | は、or の意味です。a -> b | 'C' と書いた場合は、b または 'C' のどちらかに展開できると言う意味になります。
それでは、この文法規則を細かく見てみましょう。（A）～（F）の各規則は、以下のようなルールです。
- 規則（F） factor : 'a', '(ab|c*)' 等
括弧で包まれたsubexprかCHARACTER。つまり1文字。
- 規則（E） star : 'a*', 'a', '(ab)*'等
factorそのままか、factorの後ろに*をつけたもの。
- 規則（D） subseq : 'ab', 'a*bc', '(ab)*cd'等
starを再帰的に1個以上繋げたもの。要素を連結して文字列とする。
- 規則（C） seq : '(ab)*cd', ''等
文字列か空文字。規則（B）で空文字に対する和集合演算を許すための規則。
- 規則（B） subexpr : 'a|b', 'a*bc|(ab)*cd|' 等
seqを'|'によって1個以上再帰的に繋いだもの。
- 規則（A） expression : 'a*bc|(ab)*cd|' + EOF 等
subexprの末尾にEOF（文字列の終端）を要求するもの。
もう一つ例として、「(A|BC)*」と言う正規表現が、この文法規則からどのように導出されるかを見てみます。
導出はまず、最初は「expression」から始まります。これにルール（A）を施すと、「subexpr EOF」となります。さらに最左の変数subexprに（B）を施すと「seq EOF」とすることができます。以降も同様に展開を繰り返します。
expression
─（A ）⇒ subexpr EOF
─（B右）⇒ seq EOF
─（C左）⇒ subseq EOF
─（D右）⇒ star EOF
─（E左）⇒ factor '*' EOF
─（F左）⇒ '(' subexpr ')' '*' EOF
─（B左）⇒ '(' seq '|' subexpr ')' '*' EOF
─（C左）⇒ '(' subseq '|' subexpr ')' '*' EOF
─（D右）⇒ '(' star '|' subexpr ')' '*' EOF
─（E右）⇒ '(' factor '|' subexpr ')' '*' EOF
─（F右）⇒ '(' 'A' '|' subexpr ')' '*' EOF
─（B右）⇒ '(' 'A' '|' seq ')' '*' EOF
─（C左）⇒ '(' 'A' '|' subseq ')' '*' EOF
─（D左）⇒ '(' 'A' '|' star subseq ')' '*' EOF
─（E右）⇒ '(' 'A' '|' factor subseq ')' '*' EOF
─（F右）⇒ '(' 'A' '|' 'B' subseq ')' '*' EOF
─（D右）⇒ '(' 'A' '|' 'B' star ')' '*' EOF
─（E右）⇒ '(' 'A' '|' 'B' factor ')' '*' EOF
─（F右）⇒ '(' 'A' '|' 'B' 'C' ')' '*' EOF
全ての段階において、一番左側に登場する変数を展開しています。また、この表記で（C左）等と言うのは、規則（C）の|の左側のルールで展開したと言う意味です。規則を順に適用することで、「(A|BC)*」を導出することができました。
Parserクラスの実装
文法が厳密になったので、後はこれを解析できるように構文解析器を作りましょう。Parserクラスは、構文解析ロジックのメイン部分となるクラスです。今回は、予言的パーサ（predictive parser）と呼ばれる方式で構文解析器を実装します。
予言的パーサでは、関数の再帰呼び出しを利用してトップダウンで解析を行います。まず、各ルールの左辺の変数名をそのまま関数名とします。そして各関数において、最初の数トークンを読み、次に適応すべきルールを決定します。決まったルールに従って、含まれる変数名に該当する関数を再帰的に呼び出して終端記号を目指します。
例えば、「factor -> '(' subexpr ')' | CHARACTER」と言うルールにおいて、1つ目のトークンが Token.LPAREN型( '(' ）であれば、前者の「'(' subexpr ')'」 と言うルールを適用すべきであることが分かります。よって、このルールに沿って再帰的にsubexpr関数を呼びます。逆に、1つ目のトークンがToken.CHARACTER型であれば、後者の「CHARACTER」と言うルールを採用すべきですので、新しいCharacterノードを作成して返します。
予言的パーサでは文法規則に左再帰があると無限ループに陥り、うまく処理ができません。「左再帰」とは、右辺の左端に左辺の変数自身が現れる規則のことです。つまり、「subseq -> star subseq」と言う規則はOKですが、これを「subseq -> subseq star」と言う規則にはできません。後者の規則を予言的パーサとして組むと、subseq関数内で「subseq star」のルールが選択された場合、状態を変化させる前にそのままsubseq関数が呼び出されます。しかし状態が変わってないので、次のsubseq関数呼び出しでもまた「subseq star」のルールが選択され、このまま無限ループとなります。
「subseq -> star subseq」のように左再帰とならないルールとすれば無限ループは起きないのですが、この場合ルールが右結合の規則として評価されてしまいます。つまり、 文字列 abcd は実際は a(b(cd)) と連結処理されてるものと見なされます。しかし、正規表現の和集合演算と連結演算は結合順序が関係ないため、このように右結合文法として定義しても十分動作します。
以上のような理由から、今回は文法規則において全ての規則を右結合としました。なお、引き算、割り算等のような、5-3-2が5-(3-2)のように右結合になると結果が変わってしまう演算に予言的パーサを適応する場合は、工夫が必要です。
フィールド定義とトークンの読み込み
では、Parserクラスを実装します。まず、Parserクラスのコンストラクタと、全体を通して利用するトークンを読み込むメソッドの実装は以下となります。
class Parser(object):
def __init__(self, lexer):
self.lexer = lexer
self.look = None
# 最初の文字を読む
self.move()
def match(self, tag):
if self.look.kind != tag:
# 予期せぬトークンが来たら、エラー終了
raise Exception("syntax error")
self.move()
def move(self):
self.look = self.lexer.scan()
コンストラクタには、トークンを生成してもらうためのLexerインスタンスを渡します。Lexerは、lexerフィールドに保持します。また、現在読み込み中のトークンを保持するためのlookと言うフィールドも用意しています。
Lexerからトークンを読み込んでlookにセットするためのメソッドは、2種類あります。move()は、Lexerから単純にトークンを読む時に使います。match()は、エラーチェック付きのトークン読み込みメソッドです。トークンが、引数で渡した型と違うものであれば構文エラーを出します。これは、左括弧と右括弧の対応を取る場合などに使います。右括弧を期待しているのに他のトークンが来てしまった場合は、構文エラーです。
次は、各規則をボトムアップで下から順番に実装します。
