| Item type |
Trans(1) |
| 公開日 |
2017-02-27 |
| タイトル |
|
|
タイトル |
解析表現文法の指数時間性についての考察 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
On Time Exponentially of Parsing Expression Grammars |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[発表概要] |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
横浜国立大学 |
| 著者所属 |
|
|
|
横浜国立大学 |
| 著者所属 |
|
|
|
横浜国立大学 |
| 著者所属 |
|
|
|
横浜国立大学 |
| 著者所属(英) |
|
|
|
en |
|
|
Yokohama National University |
| 著者所属(英) |
|
|
|
en |
|
|
Yokohama National University |
| 著者所属(英) |
|
|
|
en |
|
|
Yokohama National University |
| 著者所属(英) |
|
|
|
en |
|
|
Yokohama National University |
| 著者名 |
山口, 大輔
山口, 真弥
千田, 忠賢
倉光, 君郎
|
| 著者名(英) |
Daisuke, Yamaguchi
Shin'ya, Yamaguchi
Nariyoshi, Chida
Kimio, Kuramitsu
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
再帰下降構文解析は人気の実装方法であるが，バックトラッキングにより，最悪ケースにおいて指数時間を要することが知られている．現実のパーサでは，最悪ケースはほとんど発生しないが線形時間性を保証することは難しい．本研究では，再帰下降構文解析の形式モデルとしてPEGを用い，PEGの文法定義から線形時間性を判定する方法に取り組んだ． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464814 |
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO）
巻 10,
号 2,
p. 2-2,
発行日 2017-02-27
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7802 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TPRO1002005.pdf (77.0 kB)
