YAML 1.2 のバックトラック構文解析器の部分メモライズ化

YAML 1.2 のバックトラック構文解析器の試作品の続きです。この間、バグ取りを進めつつ、構文規則の読み込みを続けてきました。そして、いったん諦めたメモライズを部分的におこなってみました。今のテストでは、メモライズ化前後でのふるまいは変わっておらず、同じ解析木を生成していることが確認できています。

https://github.com/tociyuki/libyaml-parser-btrack-perl

生成規則を手動で展開してみて理解できた範囲では、ブロックノードの規則のほとんどは決定的で、バックトラックをおこしていた非決定的な規則のほとんどはフローノードとセパレータだということがわかってきました。容易に想像できるように、バックトラックで何度も重複して構文解析をおこなっている箇所はブロックとフローの両方のマッピングの暗黙のキーの箇所です。同じ行頭セパレータとキー候補のフローノードを何度も繰り返して解析していました。
そこがメモライズするべき箇所です。ところが、YAML 1.2 の構文規則では、キー候補のときは1行内で完結するコンテキストを指定してフローノードとして解析をおこない、後ろにコロンがなくキーでないと判断してもう一度おこなうときは、今度は複数行に伸びるフローノードとして処理します。この挙動に対応するため、コンテキストを指定してメモライズすることになるのですけど、一行完結ノードでない限りメモライズ自体が有効に働きません。
メモライズを有効に利用するにはコンテキストに依存せずに処理したものをメモライズしたいわけです。そこで、生成規則の後続記号を抜き出してチェックしてみたところ、すべての場合に複数行へ伸びるフローノードを一行完結で受理したとしても、その後の残りの行に当てはまる規則が存在しませんでした。ということは、複数行ノードは複数行ノードとしてしか受理する他にないことを意味します。このことは空白セパレータにも同様にあてはまります。それならば、元から複数行に伸びるノードはコンテキストに関係なく初めから複数行に伸びているとして扱えばいいわけです。その上で、一行完結ノードを要求してくる規則に対して、ここは複数行ノードだから失敗すると応答してやればいいわけです。
メモライズ化では、上の考え方でおこなっています。フローノードすべてを複数行コンテキストで処理しており、複数行コンテキストでの結果をメモライズします。一行完結フロー・ノードを要求してきた場合は、複数行ノードの場合は失敗を返し、そうでないときはメモライズ済みの結果を即答します。