文献

J-GLOBAL ID：201802222804335896   整理番号：18A1341374

静的に配置したメモリを備えるPackratパーサ構築のためのCライブラリの実装

Implementation of C Library for Constructing Packrat Parser with Statically Allocated Memory

著者 (2件)： Sugimoto Yuta (Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba) ,  Maeda Atusi (Department of Computer Science, Graduate School of Systems and Information Engineering, University of Tsukuba)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 26  ページ： 335-344(J-STAGE)  発行年： 2018年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Packrat構文分析は,バックトラッキングおよびメモ化による再帰的降下構文分析法である。この手法に基づくパーサは,別々の語彙分析器を必要とせず,バックトラッキングにより,これらのパーサが広範囲の複雑な構文構築物を扱うことを可能にする。実行時間の指数関数的拡大を防ぐため,メモ化を用いて線形空間消費コストにおける線形時間複雑性をもたらす。本研究では,C言語におけるPackrat構文解析を用いてパーサを書き込むために使用できるCPEG-aライブラリを提案した。本ライブラリは,パーサ結合器とは異なり,構文を表現するためにランタイムデータ構造を必要とせず,プログラマが内部ドメイン固有言語(DSL)における構文規則を記述することを可能にした。構文規則を単にプレーンCマクロにより表現した。ランタイムルーチンは,メモ化のためにメモリ領域を動的に割り当てない。その代わりに静的に割り当てたアレイを,メモ化キャッシュテーブルとして用いた。こうしてプログラマは,特定のメモリ管理機能に依存せず,固定サイズのメモリ(入力ストリングを除いて)を必要とする,CPEGによる実用的パーサを実装することができた。使用性を強化するために,メモ化パラメータを制御するチューニングメカニズムと共に外部DSLからCPEGへの変換器を提供した。Javaスクリプトオブジェクト表記とJavaソースファイルを構文化する場合,他のシステムと比較した構文分析時間を与えた。実験結果は,CPEGの性能が他のライブラリと同等であることを示した。(翻訳著者抄録)

シソーラス用語： *記憶割当 ,  *構文分析 ,  C言語 ,  *ライブラリ【計算機】 ,  プログラマ ,  記録 ,  プログラミング言語 ,  アレイ回路 ,  簡易言語 ,  計算機ファイル
準シソーラス用語： Javaスクリプト ,  ソースファイル ,  ドメイン固有言語 ,  パーザ ,  メモランダム ,  メモリアレイ ,  *メモリ割当

著者キーワード (4件)： パッカットパージング ,  DSL ,  C言語 ,  パージング

分類 (3件)： 計算機システム開発  (JD02010R) ,  記憶装置  (JC04060F) ,  自然語処理  (JE06000L)

引用文献 (21件)：

• [1] Bloschetsov, A.: JSON Serialization Benchmarks (online), <https://github.com/bura/json-benchmarks> (accessed 2017-06-24).
• [2] ECMA: ECMA-404: The JSON Data Interchange Format, ECMA International (online), available from <http://www.ecma-international.org/publications/files/ECMA-ST/ECMA-404.pdf> (accessed 2017-06-22).
• [3] Ford, B.: Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Functional Pearl, Proc. 7th ACM SIGPLAN International Conference on Functional Programming, ICFP '02, New York, NY, USA, pp.36-47, ACM (online), DOI: 10.1145/581478.581483 (2002).
• [4] Ford, B.: Parsing Expression Grammars: A Recognition-based Syntactic Foundation, Proc. 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '04, New York, NY, USA, pp.111-122, ACM (online), DOI: 10.1145/964001.964011 (2004).
• [5] Frey, D.: Taocpp/PEGTL: Parsing Expression Grammar Template Library (online), available from <https://github.com/taocpp/PEGTL> (accessed 2017-06-24).

タイトルに関連する用語 (4件)： パーサ ,  構築 ,  ライブラリ ,  実装