登入選單

返回Google圖書搜尋

An Efficient Learning of Context-free Grammars for Bottom-up Parsers

Yasubumi SakakibaraShin Sedai Konpyūta Gijutsu Kaihatsu Kikō (Japan)

出版	Institute for New Generation Computer Technology, 1988
URL	http://books.google.com.hk/books?id=AzX6HAAACAAJ&hl=&source=gbs_api

註釋

Furthermore for a practical use, we require that the grammar should be learned from positive-only examples and the grammar should be learned efficiently. To achieve those requirements, we present an efficient algorithm for learning a context-free grammar from positive examples of structural descriptions. Structural descriptions of a context-free grammar are unlabelled parse trees of the grammar, the shapes of parse trees. Thus the input to the learning algorithm is a finite set of shapes of parse trees. We show that the learning algorithm learns a grammar which is structurally equivalent to the unknown grammar and achieves the polynomial time bound."