{"updated":"2025-01-20T00:41:06.208820+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00191428","sets":["934:935:9346:9537"]},"path":["9537"],"owner":"11","recid":"191428","title":["解析表現文法に基づくC++のパーサコンビネータ実装の実行速度の比較"],"pubdate":{"attribute_name":"公開日","attribute_value":"2018-09-20"},"_buckets":{"deposit":"8071e600-dd46-467a-ab41-64efda84ca94"},"_deposit":{"id":"191428","pid":{"type":"depid","value":"191428","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"解析表現文法に基づくC++のパーサコンビネータ実装の実行速度の比較","author_link":["441526","441525","441524","441523"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"解析表現文法に基づくC++のパーサコンビネータ実装の実行速度の比較"},{"subitem_title":"Comparison among the Runtime Performance of PEG-based Parser Combinator Implementations Written in C++","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[発表概要] ","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2018-09-20","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"芝浦工業大学大学院理工学研究科"},{"subitem_text_value":"芝浦工業大学大学院理工学研究科"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Engineering and Science, Shibaura Institute of Technology","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Engineering and Science, Shibaura Institute of Technology","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/191428/files/IPSJ-TPRO1103005.pdf","label":"IPSJ-TPRO1103005.pdf"},"date":[{"dateType":"Available","dateValue":"2020-09-20"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO1103005.pdf","filesize":[{"value":"98.4 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"15"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"a54a204e-0803-48af-b976-88b814d10ed4","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2018 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"今泉, 良紀"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"篠埜, 功"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yoshiki, Imaizumi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Isao, Sasano","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464814","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7802","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"PEG（Parsing Expression Grammar，解析表現文法）は文法規則に曖昧さのない形式文法であり，プログラミング言語の構文記述に有用である．PEGによる文法は再帰下降構文解析器と対応しているため，パーサコンビネータによる簡易な実装によってPEGの文法から実際に動作するパーサが得られる．特にEDSL（Embedded Domain Specific Language）によるパーサコンビネータ実装は，パーサの記述のし易さを確保しつつ，意味規則の記述などの点でホスト言語との接続が簡潔であるという利点がある．また，バックトラックのある再帰下降構文解析器は素朴な実装では入力長に対して最悪指数関数時間を要するが，再帰下降構文解析にメモ化を組み合わせたパックラット構文解析という手法によって入力長に対して線形時間で解析が可能となる．本発表では，C++で記述されたPEGに基づくパーサコンビネータ実装として，Boost.Spirit.X3，cpp-peglib，PEGTL，matcha2の4つの実装の実行性能について比較した結果と，これらの中で最も実行速度の速いmatcha2の実装の詳細について報告する．","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"PEGs (parsing expression grammars) are used for formally describing unambiguous grammars and thus are useful to describe the syntax of programming languages. Grammars described by PEGs are recognized by recursive descent parsers, which are obtained by combining parser combinators. By embedding combinators based on PEGs in some language, it becomes easy to construct parsers with semantic actions by having interoperability with the host language. Although it takes exponential time in the worst case to execute the parsers with backtracking in naive implementation, packrat parsers operate in linear time with respect to the input length by using memoization. In this presentation, we compare the runtime performance of four PEG-based parser combinators implemented in C++: Boost.Spirit.X3, cpp-peglib, PEGTL, and matcha2. Furthermore, we also report the implementation detail of matcha2, which runs fastest among them.","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"24","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicPageStart":"24","bibliographicIssueDates":{"bibliographicIssueDate":"2018-09-20","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicVolumeNumber":"11"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"created":"2025-01-19T00:57:18.979552+00:00","id":191428,"links":{}}