正規表現エンジンを作ろう（3）では、簡単のためすべて演算が右結合となるように構文解析を実装しました。ただ、ちょっとこれは乱暴過ぎたかなと反省もしてます。
そんなわけで、
なお、引き算、割り算等のような、5-3-2が5-(3-2)のように右結合になると結果が変わってしまう演算に予言的パーサを適応する場合は、工夫が必要です。
こちらの方法を紹介します。
Wikipediaにも書いてますが、左再帰は以下のように解決できます。
A → Aα | β
こんな規則を、
A → βA' A' → ε | αA'
こう書き換えられます。これでどちらも、βααα... を導出する文法となります*1。こいつを利用すれば、今回のコンパイラでも左再帰を解決できます。
ただし、左結合性を維持するためには、文法規則に含まれる「処理*2」まで含めて考える必要があります。連結演算の文法規則は、処理まで含めると以下のようになっています。
subseq -> subseq star {subseq.r = Concat(subseq.r, star.r)}
| star {subseq.r = star.r}で、{}で表したのが処理であり、.rと言うのは、各生成規則に紐づく属性で、returnする値だと思って下さい。例えば、 subseq.r = star.r ってのは、 subseq()内から return star(); することを意味します。
さて、このように処理まで含めた表記を先の変換方法と比べますと、
A => subseq
α => star {subseq.r = Concat(subseq.r, star.r)}
β => star {subseq.r = star.r}となりますので、A' を 「_subseq」 と言う名前で導入すると、完成するルールは以下のようになります。
subseq -> star {subseq.r = star.r} _subseq
_subseq -> ε
| star {subseq.r = Concat(subseq.r, star.r)} _subseqsubseq.rを_subseqで使ってるので、こいつを_subseq()に渡せるようにします。_subseqが、subseqの戻り値(subseq.r)を変換してくようなイメージです。εに至ったら何もしません・・・つまり変換をしません。
コードにすると以下です。
def subseq(self): # subseq -> star {star} subseq_ node = self.star() # ← {subseq.r = star.r} return self._subseq(node) def _subseq(self, node1): if self.look.kind == Token.LPAREN \ or self.look.kind == Token.CHARACTER: # _subseq -> star {Concat()} _subseq node2 = self.star() node = Concat(node1, node2) # ← {subseq.r = Concat(subseq.r, star.r)} return self._subseq(node) else: # _subseq -> ε return node1
_subseq()は末尾再帰なんで、ループに出来ます。そうすると、_subseq()は再帰呼び出しのない関数になるので、subseq()の中にまとめられます。
def subseq(self): # subseq -> star {star} subseq_ node = self.star() while True: if self.look.kind == Token.LPAREN \ or self.look.kind == Token.CHARACTER: # _subseq -> star {Concat()} _subseq node2 = self.star() node = Concat(node, node2) continue else: # _subseq -> ε break return node
これで、左結合的な文法となりました。
参考文献
ドラゴンブックの手法そのまんまです。
