2026-05-20T01:36:19Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00177701 2025-01-20T05:24:13Z 934:935:8954:9017

解析表現文法の指数時間性についての考察 On Time Exponentially of Parsing Expression Grammars 山口, 大輔 山口, 真弥 千田, 忠賢 倉光, 君郎 Daisuke, Yamaguchi Shin'ya, Yamaguchi Nariyoshi, Chida Kimio, Kuramitsu [発表概要] 再帰下降構文解析は人気の実装方法であるが，バックトラッキングにより，最悪ケースにおいて指数時間を要することが知られている．現実のパーサでは，最悪ケースはほとんど発生しないが線形時間性を保証することは難しい．本研究では，再帰下降構文解析の形式モデルとしてPEGを用い，PEGの文法定義から線形時間性を判定する方法に取り組んだ． Parsing expression grammar is a modern formal language. Although PEG-based parsers require an exponential time in the worst case, it is known that most of the parsers can compute in linear time. However, the linearity or the exponentially is not guaranteed yet. In this study, we classify a class of PEG thet requires exponentioal time to analysis. Then we consider the judgement algorithm based on the classification. journal article 情報処理学会 2017-02-27 application/pdf 情報処理学会論文誌プログラミング（PRO） 2 10 2 2 1882-7802 AA11464814 https://ipsj.ixsq.nii.ac.jp/record/177701/files/IPSJ-TPRO1002005.pdf jpn