{"updated":"2025-01-21T18:52:21.172061+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00082737","sets":["6164:6805:6806:6810"]},"path":["6810"],"owner":"10","recid":"82737","title":["左再帰に対応するPackrat Parserの実装"],"pubdate":{"attribute_name":"公開日","attribute_value":"2012-01-06"},"_buckets":{"deposit":"258e8cf5-c8e2-4ad5-b6a3-cbca7716122b"},"_deposit":{"id":"82737","pid":{"type":"depid","value":"82737","revision_id":0},"owners":[10],"status":"published","created_by":10},"item_title":"左再帰に対応するPackrat Parserの実装","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"左再帰に対応するPackrat Parserの実装"},{"subitem_title":"Implementation of Packrat Parser to Parse Left Recursive Grammars","subitem_title_language":"en"}]},"item_type_id":"18","publish_date":"2012-01-06","item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_18_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"熊本大学大学院自然科学研究科"},{"subitem_text_value":"熊本大学大学院自然科学研究科"},{"subitem_text_value":"熊本大学大学院自然科学研究科"}]},"item_18_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Kumamoto Graduate School of Science and Technology, Kumamoto University","subitem_text_language":"en"},{"subitem_text_value":"Kumamoto Graduate School of Science and Technology, Kumamoto University","subitem_text_language":"en"},{"subitem_text_value":"Kumamoto Graduate School of Science and Technology, Kumamoto University","subitem_text_language":"en"}]},"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/82737/files/IPSJ-SPRO2011009.pdf"},"date":[{"dateType":"Available","dateValue":"2012-01-06"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-SPRO2011009.pdf","filesize":[{"value":"301.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":"44"}],"accessrole":"open_date","version_id":"aade3ca9-502c-4f6d-82d4-6f172c6da41b","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2011 by the Information Processing Society of Japan"}]},"item_18_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"後藤, 勇太"},{"creatorName":"木山, 真人"},{"creatorName":"芦原, 評"}],"nameIdentifiers":[{}]}]},"item_18_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yuta, Goto","creatorNameLang":"en"},{"creatorName":"Masato, Kiyama","creatorNameLang":"en"},{"creatorName":"Hyo, Ashihara","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_5794","resourcetype":"conference paper"}]},"item_18_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"構文解析法でPackrat Parsingという手法がある．Packrat Parsingは，再帰下降構文解析にメモ化を組み合わせた手法であり，バックトラックや無限先読みを用いた解析において，線形時間で解析可能である．しかし，左再帰を含む文法は解析不可能である．そこで，従来は左再帰を含む文法を解析する際，左再帰部分を等価な右再帰に変換し，解析を行っていた．だが文法の変換を行うと構文木の構造が変化してしまう．また，特定の左再帰は変換できない．たとえば，閉路が存在する文法である．よって，この手法では解析できない文法がある．Alessandro Warthらは，左再帰を含む文法を，右再帰への変換無しに解析を可能にした．しかし，Alessandroらの手法では，同一の入力位置で左再帰が複数発生する文法において，特定の入力の解析に失敗する．そこで本研究では，左再帰を含む文法を右再帰への変換無しに解析でき，かつ従来手法の問題点に対応するPackrat Parserを提案・実装し，評価を行った． ","subitem_description_type":"Other"}]},"item_18_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Packrat Parsing is a kind of parsing method. Packrat Parsing is a combination of Recursive Descent Parsing and memoization that can parse backtracking and unlimited look-ahead in linear parse time. However, Packrat Parsing cannot parse left recursive grammars. Thus, traditional method transforms left recursive grammars into right recursive grammars. Unfortunately, syntax tree is changed by the transforming. Moreover, particular left recursive grammars cannot be transformed. Traditional method cannot parse particular grammars. Alessandro Warth et al made possible to support left recursive grammars without transforming in Packrat Parsing. However, the method cannot parse some grammars that have multiple left recursions at an input position. This paper presents imprementation and evaluation of Packrat Parser that possible to support left recursive grammars without transforming, and grammars that have multiple left recursions at an input position. ","subitem_description_type":"Other"}]},"item_18_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"55","bibliographic_titles":[{"bibliographic_title":"夏のプログラミング・シンポジウム2011報告集"}],"bibliographicPageStart":"49","bibliographicIssueDates":{"bibliographicIssueDate":"2012-01-06","bibliographicIssueDateType":"Issued"}}]},"relation_version_is_last":true,"weko_creator_id":"10"},"created":"2025-01-18T23:36:31.482630+00:00","id":82737,"links":{}}