講演抄録/キーワード |
講演名 |
2012-05-14 15:15
制限付き後戻り下向き構文解析器では認識不可能な文脈自由言語について ○松原俊一(青学大) COMP2012-11 |
抄録 |
(和) |
近年構文解析手法としてよく使われているのが,有界な先読み付きの決定性構文解析と制限付き後戻り構文解析である.本研究では後者の手法で扱える文脈自由言語族を,理論的な側面から調べる.これまでにも制限付き後戻り構文解析では扱えない文脈自由言語の存在が指摘されているが,理論的な点からの議論はなされていない.そこで具体的な文脈自由言語に対して制限付き後戻り構文解析不可能なことを示すための一つのアプローチを提案する. |
(英) |
Recently, deterministic parsing with bounded lookahead and limited backtrack top-down parsing have been used for parsing language syntax. This paper investigates theoretical aspects of limited backtrack top-down parsing. In particular, a new approach is proposed to resolve the problem whether there exists a context-free language that cannot be parsed by the limited backtrack top-down method. |
キーワード |
(和) |
解析表現文法 / 制限付き後戻り構文解析 / 文脈自由言語 / 形式言語 / 通過列論法 / / / |
(英) |
parsing expression grammar / limited backtrack parsing / context-free language / formal language / crossing sequence argument / / / |
文献情報 |
信学技報, vol. 112, no. 24, COMP2012-11, pp. 45-50, 2012年5月. |
資料番号 |
COMP2012-11 |
発行日 |
2012-05-07 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-11 |