Packrat parserライブラリWoodrat用アルゴリズミックデバッガの実装

Packrat parsingとは，バックトラックのある再帰下降構文解析手法の一種であり，途中結果をメモ化することで，入力サイズに対して線形時間で解析を行うことができる．本研究室では，packrat parsingを用いたRuby用ライブラリWoodratを開発してきた．これを用いて構文解析を行う際にParsing Expression Grammar（PEG）と呼ばれる形式文法を用いるが，PEGの意味には直感的でない部分があり，正しい文法を書くことは簡単ではない．PEGを用いて文法を誤って定義した際に，誤りの発見を容易にするために，アルゴリズミックデバッギングを用いて，Woodrat用のデバッガを実装する．このデバッガは，プログラムの再帰的な実行をトレースしたものを木構造で表現し，その木構造に対してデバッグを行うことを可能とする．そして，ユーザからの入力を元にバグの含む範囲を狭めて，木構造のエラー箇所を半自動的に特定する．本発表では，アルゴリズミックデバッギングで用いられているsingle-steppingアルゴリズムやdivide-and-queryアルゴリズムなどいくつかのアルゴリズムを比較し，PEGに即したアルゴリズムのデバッガを提案する．

Woodrat is a library for Ruby developed in our laboratory to describe a parser and uses a parsing technique called packrat parsing. This technique uses a recursive-descent parsing with backtracking. By allowing arbitrary backtracking, both lexical analysis and syntax analysis can be performed together. In packrat parsing, a formal grammar called parsing expression grammar (PEG) is used to define grammar rules. When backtracking occurs at the time of parsing, the parse time may be an exponential time. Packrat parsers prevent this exponential growth by memoizing intermediate results, suppressing running time in linear order. However, packrat parsing has a disadvantage that it is difficult to find PEG grammar mistakes. In this presentation, in order to deal with this problem, We implement a debugger for Woodrat with a debugging method called algorithmic debugging. In algorithmic debugging, a trace of recursive calls in a program is represented by a tree structure, and debugging is performed on that tree structure. Based on the input from the user, it is possible to narrow the range of code which includes the bug and specify the erroneous part of the tree structure. In addition, we compared some algorithms such as single-stepping algorithm and divide-and-query algorithm used in algorithm debugging, and implemented the debugger with an algorithm based on PEG.