論理型言語による構文解析法YAPについて

概要

論文の詳細を見る
自然言語を対象とした論理型言語による構文解析法としては,これまでにDCGパーサ(以下単にDCGと略称する),BUP,SAXが存在する.本論文では,これらとは異なる新しい方法YAPについて提案する.YAPの特徴は次のとおりである.(1)DCG,BUP,SAXがそれぞれ縦型下降式,縦型上昇式,横型上昇式に基づいているのに対して,YAPは横型下降式を採っている.(2)左回帰規則,e規則を共に許している.(3)KnuthのLR手法を暖昧さを含む一般のCFGにまで適用できるように改めたEarleyの手法と,基本的には等価であるが,入力解析と解析木作成の一体化や解析表でなくスタックの使用,それに処理の効率化などの点で改良を行っている(4)YAPの時間的,空間的能率は,入力の長さをnとした時に,媛昧さを含まない文法の場合はo(n2)である.また,解析パス数が定数オーダの場合はo(n)である.(5)論理型言語によるパーサの動作は,基本的にはSAXと同様に文法規則の右辺の要素ごとに対応したホーン節の集合として定義される.ただしホーン節は,右辺の要素が規則のどの位置に存在するかによって,左端型,中間型,右端型の3種類に分けられる.そしてスタック情報の授受によって相互に関連づけられる.
一般社団法人情報処理学会の論文
1988-09-15