（F）factorルール（factor -> '(' subexpr ')' | CHARACTER）
factorルールの実装は以下の通りです。
def factor(self):
if self.look.kind == Token.LPAREN:
# factor -> '(' subexpr ')'
self.match(Token.LPAREN)
node = self.subexpr()
self.match(Token.RPAREN)
return node
else:
# factor -> CHARACTER
node = Character(self.look.value)
self.match(Token.CHARACTER);
return node
factorルールでは、最初の1トークン（self.look）を見ると、どちらのルールを適用するかを決定できます。左括弧（'('）が現れた場合は、左側のルール（subexpr 全体を括弧で包むルール）ですので、 '('、subexpr、')' の順でトークンが現れるはずです。matchとsubexprメソッドを使い、この規則に沿って忠実にコーディングします。
各ルールからは、そのルールによって生成されるノードを返さなければなりません。括弧でsubexprを包むと言うルールは、計算の優先順位を表しているだけで特に演算は必要ないので、subexpr を表すノードが単純にそのままこのルールのノードとなります。
1つめのトークンがそれ意外の場合はelse:側に書かれており、2つ目のルールを適応します。このルールは任意の1文字を表すルールなので、Characterノードを生成して返します。matchを使い、このルール（ここにはToken.CHARACTERが現れる）の適用を終わらせておくことも忘れないようにしましょう。
（E）starルール（star -> factor '*' | factor）
starルールの実装は以下です。
def star(self):
# star -> factor '*' | factor
node = self.factor()
if self.look.kind == Token.OPE_STAR:
self.match(Token.OPE_STAR)
node = Star(node)
return node
まず、左右どちらのルールになったとしても、最初はfactorです。factorメソッドを呼び、factorを表すノードを得ておきます。
次のトークンを見た時に '*' であれば、左側のルールと言うことになります。このルールはスター演算を意味しますので、 元のノードからStarノードを作成してこのルールを表すノードとして返します。
それ以外の場合は右側のルールで、これはfactorのノードをそのまま返すだけで大丈夫です。
（D）seqルール（seq -> subseq | ''）
このルールでは、どちらのルールを利用すべきかを決定するのに少し考える必要があります。
まず、後者の''（空文字）であると言うルールが適応されたとしましょう。このとき、次のトークンが何になっているか考えてみます。seqが現れるのは、規則（B）です。規則（B）で左側のルールが適応されていれば seq の次は '|' です。また、subexprの展開元は規則（A）か（F）です。よって、規則（B）で右側が適応されている場合、展開元が規則（A）であれば次に続くのは文末（Token.EOF）、規則（E）であれば次に続くのは ')' となります。以上を総合すると、次に現れるトークンは '|' か Token.EOF か ')' と言うことになります。
続いて、前者のsubseqと言うルールが適応される場合、この次に続くトークンを考えてみます。subseqは規則（D）よりstarから始まります。starは規則（E）よりfactorから始まります。規則（F）により、factorは '(' か CHARACTER から始まります。
以上をまとめると、以下のようにルール分けが出来そうです。
- 最初のトークンが、'(' か CHARACTER → 左側のルール
- それ以外（'|'かEOFか')') → 右側のルール
これにそって場合分けして実装します。実装は以下です。
def seq(self):
if self.look.kind == Token.LPAREN \
or self.look.kind == Token.CHARACTER:
# seq -> subseq
return self.subseq()
else:
# seq -> ''
return Character("")
後者のルールの場合は、空文字を表すCharacterノードを返します。
（C）subseqルール（subseq -> star subseq | star）
左右どちらのルールでも、最初はstarなのでまずこのルールを適用します。その次にsubseqが続くかどうかを先ほどと同じように考察すると、（D）のときと同様の判定となることがわかります。よって、コードは以下となります。
def subseq(self):
node1 = self.star()
if self.look.kind == Token.LPAREN \
or self.look.kind == Token.CHARACTER:
# subseq -> star subseq
node2 = self.subseq()
node = Concat(node1, node2)
return node
else:
# subseq -> star
return node1
左のルールは、starで得られるノードとsubseqで得られるノードの連結演算を意味してます。よって、それぞれのノードをConcatノードにまとめて返します。
（B）subexprルール（subexpr -> seq '|' subexpr | seq）
subexprルールの実装は以下です。
def subexpr(self):
# subexpr -> seq '|' subexpr | seq
node = self.seq()
if self.look.kind == Token.OPE_UNION:
self.match(Token.OPE_UNION)
node2 = self.subexpr()
node = Union(node, node2)
return node
どちらのルールもseqから始まるので、最初にこれを適用します。
その次のトークンが '|' であれば、ルールの左側を適用します。'|' 、subexpr、と順番に現れることが期待されるので、その通りにルールを適用します。このルールは和集合演算を表していますので、seqで得られるノードとsubexprで得られるノードをUnionノードにまとめて返します。
次のトークンが '|' 以外の場合はルールの右側を適用し、seq で 得られるノードをそのまま返すだけです。
（A）（expression -> subexpr EOF）
このルールは分岐がありません。subexprの後に Token.EOF が来ることを確かめます。
def expression(self):
# expression -> subexpr EOF
node = self.subexpr()
self.match(Token.EOF)
# 構文木を実行し、NFAを作る
context = Context()
fragment = node.assemble(context)
return fragment.build()
これでpredictive parserの実装が終わりました。最上位規則であるexpressionメソッドを呼ぶことで、ノードがツリー状になった構文木を生成することができます。expressionメソッドでは、さらに、構文木にNFAを作成させる処理も実装しています。この処理に関しては、次回のNFA生成の説明の最後で解説します。
まとめ
今回は、以下の内容を説明しました。
- 正規表現のコンパイル
- 字句解析
- 構文解析
次回は、完成した構文木をNFAに変換します。
参考資料
- 『計算理論の基礎』Michael Sipser 著、渡辺治・太田和夫 訳、共立出版、2000年4月
- 『Compilers Principles, Techniques, & Tools』 Alfred V. Aho・Monica S. Lam・Ravi Sethi・Jeffrey D. Ullman 著、Addison-Wesley、2007年10月
