A Family of Generalized LR Parsing Algorithms Using Ancestors Table (Special Issue on Natural Language Processing and Understanding)

スポンサーリンク

概要

• 論文の詳細を見る

• A family of new generalized LR parsing algorithms are proposed which make use of a set of ancestors tables introduced by Kipps [4]. As Kipps's algorithm does not give us a method to extract any parsing results, his algorithm is not considered as a practical parser but as a recognizer. In this paper, we will propose two methods to extract all parse trees from a set of ancestors tables in the top vertices of a graph-structured stack. For an input sentence of length n, while the time complexity of the Tomita parser can exceed O(n^3) for some context-free grammars (CFGs), the time complexity of our parser is O(n^3) for any CFGs, since our algorithm is based on the Kipps's recognizer. In order to extract a parse tree from a set of ancestors tables, it takes time in order n^2. Some preliminary experimental results are given to show the efficiency of our parsers over Tomita parser.

• 社団法人電子情報通信学会の論文
• 1994-02-25

著者

• Yamada K

  Faculty Of Engineering Tokyo Institute Of Technology

• YAMADA Koichi

  Faculty of Science and Technology, Seikei University

• Tanaka Hozumi

  Faculty Of Engineering Tokyo Institute Of Technology

• Suresh K.G.

  Faculty of Engineering, Tokyo Institute of Technology

• Suresh K.g.

  Faculty Of Engineering Tokyo Institute Of Technology

• Yamada Koichi

  Faculty Of Engineering Tokyo Institute Of Technology

関連論文

• Effects of Calcined Bauxite as a Water-holding Material and a Way of Mixing it with Soil on Tree Growth
• Water Use Efficiency of Trees in Arid Lands : Plasticity to Water Conditions
• Biomass Growth Estimation of an Afforestation Site and Natural Forests in an Arid Land of Western Australia
• Effect of temperature and light on germination of 12 afforested trees in South Western Australia
• Comparative Analysis between Biomass and Topographic Features in an Arid Land, Western Australia
• System Design, Data Collection and Evaluation of a Speech Dialogue System (Special Issue on Speech and Discourse Processing in Dialogue Systems)
• A Family of Generalized LR Parsing Algorithms Using Ancestors Table (Special Issue on Natural Language Processing and Understanding)

スポンサーリンク