最適化Packrat Parserの空間計算量の計算手法の提案

IPSJ Web Site

Bibliographic Information

Other Title
  • サイテキ カ Packrat Parser ノ クウカン ケイサンリョウ ノ ケイサン シュホウ ノ テイアン
  • A Space Complexity Calculation Method of Optimized Packrat Parsers

Search this article

Abstract

従来主流の構文解析手法である LL や LR 法の欠点を解決する構文手法の 1 つとして packrat parsing という構文解析手法が注目を集めている．packrat parsing は，parsing expression grammar（PEG） という形式文法で表現できる任意の言語を扱うことができ，これは LL 法や LR 法よりも強力である．また，packrat parsing では解析を線形時間で行うことができる．しかし，packrat parsing では，構文解析の中間結果をすべてメモ化するため，メモリ使用量が線形になってしまうという欠点がある．我々の研究では，カット演算子を PEG に導入し，プログラマがカットを適切に挿入することで，実用上，メモ化ために必要なメモリ使用量がほぼ一定である packrat parser を生成できるpackrat parser 生成系を提案した．しかし，文法定義に対してカットが必要十分なだけ挿入できているかを確認するのは簡単ではなく，文法定義を入念にチェックしたうえで，実際に構文解析を行ってメモリ使用量を測定する必要があった．本論文では，カットによって拡張された PEG による文法定義を静的に解析することで，その文法定義から生成される packrat parser が必要とするメモリ使用量を推計する手法を提案する．本論文の提案手法を適用することで，実際に構文解析を行うことなしに，カットが必要十分なだけ挿入されているかどうかのチェックを機械的に行うことができる．提案手法は，先行研究で提案した packrat parser 生成系を実用で使ううえで重要な問題点を解決するものである．また，提案手法は，PEG から生成された packrat parser の空間計算量に対するカットのインパクトを測る 1 つの尺度を与えているといえる．

Packrat parsing is drawing attention of researchers as an alternative to mainstream parsing algorithms such as LL- or LR-family. Packrat parsing can handle any languages that parsing expression grammars (PEGs) can express and the set of languages is strictly larger than the one that LL- or LR-family can express. Also, packrat parsers parse any input in linear time. But packrat parsers require linear space because of memoization of all intermediate parsing results. In our previous study, we proposed to extend PEGs with cut operators to remove unneeded memoized space. If grammar writers properly insert cut into grammars, packrat parser generators can generate packrat parsers that only require almost constant space for memoization in practice. However, checking whether we have sufficient cut operators inserted in grammars is not an easy problem. Grammar writers have to check grammars carefully and measure heap usage by actually running the generated parser. In this presentation, we propose a static anaylysis method for PEG grammars with cut operators to automatically estimate the amount of space used by the generated parsers. Applying our method, grammar writers can automatically check whether sufficient cut operators are inserted without actually running the parser. Our method resolves an important and practical problem of the packrat parser generator proposed in our previous study. And also, our method provides a measure to the impact of cut operators on the space complexity of packrat parsers generated from extended PEGs.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top