OPGを利用したアドホックな並列データ処理系

• リュウ, ケイコウ

• 井原, 央翔

• 田浦, 健次朗

書誌事項

タイトル別名

• Parallel Ad-hoc Data Processing System Using Operator Precedence Grammar

抄録

アドホックなデータ向けのパーサジェネレータは，逐次に動くパーサを生成するものが多く，プロセッサの計算資源を十分に利用できず，大規模なデータを効率良く解析できない．OPGと呼ばれる形式文法はその性質から並列パーサに応用できるが，並列スキャナを必要とする点では，実装が複雑になりがちである．本研究では，通常のOPGよりスキャナを取り除き，マルチコアの特徴を活かせるパーサを生成できるパーサジェネレータの実装を行う．さらに，JSONの文法をスキャナレスなOPGにする試みを行い，その実用性について検討する．OPGは，local parsabilityと呼ばれる，入力の途中から構文解析を始めることができるという性質をもち，文法中にある演算子に着目して考案された形式文法である．この性質を利用すれば，最良の場合プロセッサの数に従いスループットが線形に大きくなるようなパーサを作成できる．

Most parser generators for ad-hoc data can only generate sequential parsers, which cannot fully use the computational resource, and are not suitable for parsing large data. Though operator precedence grammars (OPGs) can be used by parallel parsers, we still need parallel scanner, which may result in a complex implementation. In this research, we remove the scanner from common OPGs, and implement a parser generator which can generate parsers work on multi-core computers. We also try to represent the grammar of JSON to scannerless OPG, and consider the practical use of the system. OPGs have a feature named local parsability, which allows us to reduce only a part of the whole input string. Thanks to this feature, we can make parsers such that the throughput grows linearly along with the processor counts.

収録刊行物

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

  情報処理学会論文誌プログラミング（PRO） 12 (1), 12-12, 2019-01-30

キーワード

• [発表概要]

詳細情報

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