数式の再帰的下向き構文解析

構文解析を行う際、世の中にはyaccのように生成規則から構文解析器を生成してもらえるツールが数多くあります。しかしそういったツールを使うまでは無いけど、自分でさっと作りたいなと思うときがあり、最近でいうとHaskellのQuasiQuotes周りでそういった場面がありました。 自分で書くのであれば、再帰的下向き構文解析がやりやすいだろうというのが通説のようなので、その背景と実装方法についてまとめてみます。 1. 再帰的下向き構文解析 再帰的下向き構文解析に関する概要を箇条書きでまとめました。 文脈自由文法に対する構文解析法の一つ 下向き -> 構文木を考えたときに、root側からleafへと解析が進む 出現するtokenと構文規則を元に何を解析するのか予想しながら下へ進む 予想する、という表現を最初見たときに少ししっくりこなかったが、それは恐らくLL(k)で考えているため LL(k)文法で

[sh19910711]

"LL(k)文法 / 文脈自由文法でかつk文字先読みすれば次に解析するものが何か判断できる > backtrackをしなくて済む / もちろんLL(k)で解析できない文脈自由文法も多々存在"

[zyxwv]

左再帰の除去