Orz日記 by Akio Morita

_ [SAD][YaSAI]PEGパーサーバグ修正

PEGのメモの状態やルールの適用順をダンプしながら調べることで 左再帰の実装のバグを特定＆修正出来た。

左再帰マークの付いたルールが、左再帰のループの根元のルールが 終了した後に再評価される際に、既に存在しない根元のルールを 探して再帰スタックをたどってしまうのが原因だった。 左再帰実装の元ネタ論文では考慮されていないケースと思われる。

おそらく、文法の書き方によっては避けられる(左再帰に含まれるルール集合 の上位ルールに唯一性が成り立つ場合とか)と思うが、パーサーの性能で 文法記述が制約されるのは気にくわないので修正。 左再帰の根元となるルールが適用中かどうかを記録するフラグを増設して、 根元のルールの適用が終了後に左再帰マークの付いたメモを見つけたら メモから削除するようにして解決した。

修正済みのパーサーで、Map演算子の左オペランドが Function演算子や Unset演算子で終端される構文が正しく解析できるようになった。

構文解析の進捗解析用に生成されるログは、約113MB、285万行に及んだ。 もう少し文法記述を改良してダイエットしたほうが良いのかもしれない。 もちろん、正しく動作する文法記述を完成させてからの話ではあるが...