結局どうやって使ったらいいのよ、というのを簡単にまとめておく。背景説明はどうでもいい人は最後のサンプルまで飛ばしてくれてよい。「左再帰の文法」とはその意味を反映した構文木で表現した場合に、左側の枝のほうが深くなる再帰になる文法を「左再帰の文法」と言う。いう意味なので、左再帰の文法を持っている。ように、右辺の先頭に自分自身が現れる。これをやはりナイーブに再帰下降パーサに実装すると、評価(実行)が無限再帰(無限ループ)に陥るものになってしまう。これのワークアラウンドを「左再帰の除去」と呼んでいるが、それが具体的に指すものは一定していないようである。(なお、ここで例として示した構文定義には、トークンを一つ先読みしただけではどちらの展開をすべきかわからないので、左再帰と同様にLL(1)パーサにできない、という問題もあるが、そちらの対策は「左くくりだし」という本質的には似ているが、別のものとして分類されている変換であることに注意すること。教科書的には、こちらが「左再帰の除去」とされていることが多い(と思う)。A^{\prime}\end{eqnarray}のように変換する(詳細はここでは略す)。ここでひとつ注意が必要なのは、この変換によって文法が「右再帰の文法」に変換されてしまっていることである。「言語」の外部定義すなわち「構文規則が(受け入れる|生成する)終端記号列」としては等価な変換だと言えるが、「言語」の内部定義として「構文規則によって作られる構文木」というものを考えるならば、違うものに変換されてしまっているわけである。実用的には、こちらのほうが重要なことが多い。記法内での再帰によるループを使ってこちらの形で書ける。前述の算術の式は、次のどちらかになる。型を持ち上げたような(順序とかちょっと違うが)型であることが見てとれると思う。リストの要素の間に、第1引数の演算子を左結合で入れたり、右結合で入れたりする演算子だと見ることができる。第1引数にリスト的な構文で要素になるもののパーサを、第2引数に演算子を消化して二分木を合成する関数を返すパーサを渡してやることにより、「左再帰の文法のパーサ」を返すコンビネータだとわかる。具体例として簡単だが動作するサンプルを示す。chainl(chainl1)は、左再帰のユースケースのほとんどの場合である、算術式のようなパターンについて、無限ループになったりすることのない左再帰のパーサ、を簡単に作れるようになっているものである、と言える。余談ウィキペディアには、文法の左再帰性を保ったまま変換する方法があるかのような感じで書かれているが、文献で読んだ記憶がない&ちょっと検索したぐらいでは出てこない。(意味規則を含んだ定義を、意味を壊さないように意味規則ごと変換するという手法は論文が見つかる。ように記述して演算子の結合性を指定できるのは、複数の規則にまたがって再帰的定義をして煩雑になったり、ループを指定する構文を作って意味アクションの指定をややこしくしたりすることなく、シンプルな定義だけでたいていのユースケースをカバーする、うまい設計だということがわかる。*1:なお、要出典タグを付けたのは私である。最初にソースコードを示します。月別アーカイブMathJax読み込みはてなブログをはじめよう!metanestさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。