Packrat Parsingの表引きによる高速化

• 矢口, 拓実

• 池袋, 教誉

• 前田, 敦司

書誌事項

タイトル別名

• Speed Improvement of Packrat Parsing Using Table Look-Up

抄録

Packrat Parsingは，広範囲な構文規則を解析できる構文解析手法である．この手法では，解析が成功するまで構文を探索するバックトラックを用い，一度解析した解析対象文字列の位置と結果を保存するメモ化と呼ばれる手法によって解析時間を線形時間に保っている．既存の多くのPackrat Parsing実装は，PEG（Parsing Expression Grammer）で記述された文法規則を，再帰呼び出しによるバックトラックとメモ化表を用いるプログラムに変換するが，このような処理系の実行速度は，正規表現に基づいて表引きを用いた字句解析器と，同じく表引きとスタックを用いて処理を進めるLALR(1)などのパーサアルゴリズムの組み合わせと比較すると，一般的に劣っている．本発表では，Packrat Parsingの高速化のため，解析の意味が変化しない範囲で表引きによって構文解析を進める手法を検討する．本発表では，Packrat Parsingの処理の中に可能な限り表引きをとり入れることで，実行速度を向上させる手法を提案する．また，基本的な実行方式としてはMedeirosらの提案した仮想マシン方式を改良したものを採用している．既存の手法と比較した性能評価の結果を示す．

Packrat Parsing is a parsing technique which is applicable to wide range of grammars. In this method, the parser tries to find a match in grammar rules and backtracks when necessary. The algorithm is guaranteed to run in linear time with a technique called memoization, which records every position in input string it tried to parse and result of parsing procedure for that position. Many of existing packrat parser implementation translates grammar rules described in PEG (Parsing Expression Grammar) to recursive programs which performs backtracking and memoization. Throughput of resulting parser generally tends to be slower than conventional parser implementation which combines a lexical analyzer, which uses table-based automata generated from regular expressions, and a parser, which also uses tables and stacks based on non-backtracking algorithms e.g. LALR(1). In this paper, we propose an implementation method for Packrat Parsing which relies on extensive use of table look-up. In our implementation, we have tried to use table look-up operation as far as possible to enhance throughput. It is based on a variant of PEG abstract machine proposed by Medeiros and Ierusalimschy. We also present performance measurement result in comparison with other existing implementations.

収録刊行物

• 情報処理学会論文誌プログラミング（PRO）

  情報処理学会論文誌プログラミング（PRO） 9 (1), 14-14, 2016-02-26

キーワード

• [発表概要]

詳細情報

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