2017構文解析を行う際、世の中にはyaccのように生成規則から構文解析器を生成してもらえるツールが数多くあります。いったツールを使うまでは無いけど、自分でさっと作りたいなと思うときがあり、最近でいうとHaskellのQuasiQuotes周りでそういった場面がありました。自分で書くのであれば、再帰的下向き構文解析がやりやすいだろうというのが通説のようなので、その背景と実装方法についてまとめてみます。き構文解析に関する概要を箇条書きでまとめました。文脈自由文法でかつk文字先読みすれば次に解析するものが何か判断できる。backtrackをしなくて済む。LL(k)で解析できない文脈自由文法も多々存在するここではLL(1)文法で表現される数式を言語として考え、それを再帰下向きで構文解析してみることにします。四則演算を表現する文法を(正規表現を使用して)定義します。Form)でも同様の表記ができます。はじめの一歩をできるだけ単純にするために、解析対象の数式としてまずは以下の前提をおくことにします。7といった数式を扱うことができます。再帰的下向き構文解析では生成規則から演算子の優先順位が決定されます。演算子の優先順位が高く定義されています。再帰的下向き構文解析の利点の一つは、生成規則からプログラムを直感的に書きやすいというところだと思います。上記規則Fを処理する関数を単純化した擬似的コードで書くと以下のようになります。N()実装に規則が反映されており書きやすく読みやすいのですが、定義した文法によっては左再帰の問題が生じることがあります。上記の規則Eを単純にプログラムに落とし込むと以下のようになります。T()これだと関数Eの無限呼び出しになってしまいプログラムが終了しません。Wikipedia)なのですが、ここでは生成規則を書き換えることで対応したいと思います。あれば、下のようになります。empty)全体としては以下のようになります。LL(1)文法これで四則演算を行う数式の文法が定義できたのですが、パーサを実装する前に定義した文法が想定通りLL(1)なのかを確認したいと思います。LL(1)であれば一つのtokenの先読みで、しかもbacktracking無しに解析を行うことができるため、実装が簡単になります。与えられた際に、どの生成規則で解析を進めればよいかが常に判断できればよいということになります。下のような生成規則を考えます。生成規則を適用することで最終的に終端記号が生成されるものという感じになるかと思います。あればCの処理を行えばよいことがわかるため、LL(1)的に処理を進めることができます。読むだけでは次の生成規則がBなのかCなのかを判断することができず、このような文法はLL(1)とはなりません。\)となる必要があるということになります。LL(1)文法ならば、すべての生成規則について上の性質が満たされています。逆に上の性質が満たされていればLL(1)なのかというとそういうわけではありません。消費する」場合が、先読み1tokenでは判断できません。これはBが空文字を受け入れる場合に、Bで消費する先頭文字とBの後続の文字が一致すると判断に困るということであり、Bの後続の記号集合Followを考えてあげる必要がでてきます。実際にLL(1)文法であることは、各生成規則に対してFirst集合、Follow集合を求め、そこからDirector集合と呼ばれるものを計算することで確認することができます。Directorの具体的な求め方はこちらを参照としますが、今回対象としている数式の文法については以下のようになります。Fですが、これらの積が空集合となるため、今回定義した文法はLL(1)であるということができます。構文解析器を実装する準備が整ったので実装に進めます。実装にはPythonを使用しており、コードの全体はgithubリポジトリに配置しています。対象とする数式は幾分シンプルなものなので与えられた数式を直接計算結果の数値に変換してもよいのですが、応用の利きやすさから今回は一旦構文木に変換し、それを評価することで計算を行うことにしたいと思います。解析のためには以下の3つのクラスを用意しました。(recur_descent.py)構文木を表すクラスとして数値、二項演算子それぞれにNumExpr、TwoOpExprを用意します。変わった実装をしているわけではないためクラスの抜粋のみ記載します。self.right.evaluate())字句解析を行うクラスとしてCalcTokenizerを用意します。現在の用途だとスペースを飛ばして1文字ずつ読めばよいだけなのでその形で実装していますが、最終的なコードでは任意の(Pythonで表現できる)整数値や2文字以上のtokenを処理するように修正しています。構文解析器からはnext_tokenでtokenを取得できるようにしています。eの解析を行うところまでを抜粋しています。開始記号はEなのでparse関数ではそれに相当するexpr1を呼び出して解析を開始しています。各非終端記号に相当する関数の実装は生成規則をそのまま反映したものになっていることがわかると思います。e1これで簡単な数式の評価が行えるようになりました。‘-‘といった単項演算子を処理できるようにしたいと思います。(+3)といった数式が処理できるようになります。生成規則にこの変更を反映させます。‘/’といった二項演算よりも優先順位が高く、数値の前に付けられるものであるため、生成規則Fを以下のように修正します。9続いてコードにも変更を反映させます。上記生成規則Fに対応するメソッドfactor2にtokenが’+’、’-‘であった場合の処理を追加し、その場合UnOpExprという単項演算子用のexpressionを適用することにします。UnOpExprには渡された数値に-1をかけて返すラムダ式negを渡しています。eこれで単項演算子の評価が行えるようになりました。右結合演算子の追加これまであまり触れなかったのですが、二項演算子については優先順位の他に「左結合」か「右結合」かを考える必要があります。‘/’といった演算子は全て左結合性演算子でした。9のように連続した演算子の評価が左から行われるということになります。262144のように評価されます。このような演算子の結合性も生成規則上で定義することができます。Bという<rop>二項演算子の生成規則を考えてみます。先述のように’+’等ではここから生成規則を2つに分けて書き換えました。Bのように書き換えます。一見した見た目は違いますが、左再帰性を解決させつつ同一の構文を表すものになっています。この場合、<rop1>よりも<rop2>の評価が先に行われており、演算子の結合性としては右結合ということになります。以上を踏まえ、これまで構築した数式用の生成規則に上述のべき乗を追加した場合、生成規則は以下のように書き換えることができます。empty)あとはこの生成規則を基に実装にも手を加えれば、べき乗を右結合で正しく処理した計算を行うことができるようになります。SummaryLL(1)文法の解析であれば、再帰的下向き構文解析で比較的簡単に書くことができる演算子文法を扱う場合、優先順位と結合性に気をつける必要がある後者に関してですが、本記事の通り単純な実装を進めると、演算子が増えるにつれて実装がごちゃごちゃしてくるかもしれません。