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

書誌事項

タイトル別名
  • Implementation of an Algorithmic Debugger for Packrat parser Library 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.

収録刊行物

詳細情報 詳細情報について

  • CRID
    1050002213759985408
  • NII論文ID
    170000181635
  • NII書誌ID
    AA11464814
  • ISSN
    18827802
  • Web Site
    http://id.nii.ac.jp/1001/00202877/
  • 本文言語コード
    ja
  • 資料種別
    article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ