| Item type |
Trans(1) |
| 公開日 |
2019-05-21 |
| タイトル |
|
|
タイトル |
一般化された解析表現文法とPackrat構文解析手法の提案 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
GPEG: A Generalized Foundation for Packrat Parsing |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[通常論文] 解析表現文法，Packrat構文解析法，一般化構文解析法 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
横浜国立大学大学院 |
| 著者所属 |
|
|
|
日本女子大学理学部数物科学科 |
| 著者所属(英) |
|
|
|
en |
|
|
Yokohama National University |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Mathematical and Physical Sciences, Japan Women's University |
| 著者名 |
多田, 拓
倉光, 君郎
|
| 著者名(英) |
Taku, Tada
Kimio, Kuramitsu
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
曖昧さのある形式文法から生成されたパーサは異なる解釈をした複数の結果が導出されうる．このような複数の可能性を試すパーサは非線形の計算時間を必要とし，プログラミング言語などの人工言語の構文解析において望ましくない．Parsing Expression Grammar（PEG）の強みは優先度付き選択と貪欲な繰り返しによって曖昧さがないように形式化されている点である．しかしながら，近年の文法推論や自然言語を含んだ解析への応用では曖昧さが重要となっている．本研究では，PEGに文法的な拡張を加えることで，曖昧さを追加した新しい形式化基盤Generalized PEG（GPEG）を提案する．GPEGは決定的なPEGの文法に対して，優先度なし選択を加えた拡張となっている．一般化構文解析手法であるGLRやGLLで構築される曖昧な木とは異なり，曖昧さを文法から制御可能であるため部分的に曖昧な木を構築する．さらに，本研究で提案しているgeneralized packrat parsingによって実用的な時間で構文解析が可能である． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Ambiguity in a formal grammar is undesirable in a parser generation of programming languages. The strength of Parsing Expression Grammars (PEGs) is ordered choice and greedy repetition which can eliminate ambiguity from grammars. Nevertheless, the elimination of ambiguity faces several new difficulties in grammar debugging and grammar inference. We propose a formal foundation of Generalized PEGs (GPEG) by introducing unordered choices. The ambiguity is still controlled, and GPEG allows partial ambiguous tree construction, unlike tree forests in a generalized parsing such as GLR and GLL parsing. The practical parsing can be built on a generalized packrat parsing. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464814 |
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO）
巻 12,
号 2,
p. 1-9,
発行日 2019-05-21
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7802 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TPRO1202002.pdf (797.9 kB)
