| Item type |
Trans(1) |
| 公開日 |
2017-06-16 |
| タイトル |
|
|
タイトル |
Regularity of Linear Parsing Expression Grammars |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Regularity of Linear Parsing Expression Grammars |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[発表概要] |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
Graduate School of Electronic and Computer Engineering, Yokohama National University |
| 著者所属 |
|
|
|
Graduate School of Electronic and Computer Engineering, Yokohama National University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Electronic and Computer Engineering, Yokohama National University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Electronic and Computer Engineering, Yokohama National University |
| 著者名 |
Nariyoshi, Chida
Kimio, Kuramitsu
|
| 著者名(英) |
Nariyoshi, Chida
Kimio, Kuramitsu
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
PEGs are formalized by Ford in 2004, and have several pragmatic operators (such as ordered choice and unlimited lookahead) for better expressing modern programming language syntax. Since these operators are not explicitly defined in the classic formal language theory, it is significant and still challenging to argue PEG's expressiveness in contexts of the formal language theory. Since PEGs are relatively new, there are several unsolved problems. One of the problems is that revealing a subclass of PEGs that is equivalent to DFAs. This allows to apply some techniques from the theory of regular grammar to PEGs. In this presentation, we define Linear PEGs, a subclass of PEGs that is equivalent to DFAs. Surprisingly, LPEGs are formalized by only excluding some patterns of recursive nonterminal in PEGs, and include the full set of ordered choice, unlimited lookahead, and greedy repetition, which are characterized for PEGs. Although the conversion judgement of parsing expressions into DFAs is undecidable in general, the formalism of LPEGs allow a syntactical judgement of parsing expressions. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
PEGs are formalized by Ford in 2004, and have several pragmatic operators (such as ordered choice and unlimited lookahead) for better expressing modern programming language syntax. Since these operators are not explicitly defined in the classic formal language theory, it is significant and still challenging to argue PEG's expressiveness in contexts of the formal language theory. Since PEGs are relatively new, there are several unsolved problems. One of the problems is that revealing a subclass of PEGs that is equivalent to DFAs. This allows to apply some techniques from the theory of regular grammar to PEGs. In this presentation, we define Linear PEGs, a subclass of PEGs that is equivalent to DFAs. Surprisingly, LPEGs are formalized by only excluding some patterns of recursive nonterminal in PEGs, and include the full set of ordered choice, unlimited lookahead, and greedy repetition, which are characterized for PEGs. Although the conversion judgement of parsing expressions into DFAs is undecidable in general, the formalism of LPEGs allow a syntactical judgement of parsing expressions. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464814 |
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO）
巻 10,
号 3,
p. 19-19,
発行日 2017-06-16
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7802 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TPRO1003010.pdf (27.1 kB)
