(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月