TAILIEUCHUNG - Báo cáo khoa học: "AN EXTENDED LR PARSING ALGORITHM FOR GRAMMARS USING FEATURE-BASED SYNTACTIC CATEGORIES "

This paper proposes an LR parsing algorithm modified for grammars with feature-based categories. The proposed algorithm does not instantiate categories during preprocessing of a grammar as proposed elsewhere. As a result, it constructs a minimal size of GOTO/ACTION table and eliminates the necessity of search for GOTO table entries during parsing. | AN EXTENDED LR PARSING ALGORITHM FOR GRAMMARS USING FEATURE-BASED SYNTACTIC CATEGORIES Tsuneko Nakazawa Beckman Institute for Advanced Science and Technology and Linguistics Department University of Illinois 4088 FLB 707 s. Mathews Urbana IL 61801 USA tsuneko@ ABSTRACT This paper proposes an LR parsing algorithm modified for grammars with feature-based categories. The proposed algorithm does not instantiate categories during preprocessing of a grammar as proposed elsewhere. As a result it constructs a minimal size of GOTO ACTION table and eliminates the necessity of search for GOTO table entries during parsing. 1 Introduction The LR method is known to be a very efficient parsing algorithm that involves no searching or backtracking. However recent formalisms for syntactic analyses of natural language make maximal use of complex feature-value systems rather than atomic categories that have been presupposed in the LR rnethod. This paper is an attempt to incorporate feature-based categories into Tomita s extended LR parsing algorithm Tomita 1986 . A straightforward adaptation of featurebased categories into the algorithm introduces the necessity of partial instantiation of categories during preprocessing of a grammar as well as a nontermination problem. Furthermore the parser is forced to search through instantiated categories for desired GOTO table entries during parsing. The major innovations of the proposed algorithm include the construction of a minimal size of GOTO table that does not require any preliminary instantiation of categories or a search for them and a reduce action which performs instantiation during parsing. Some details of the LR parsing algorithm are assumed from Aho and Ullman 1987 and Aho and Johnson 1974 and more formal definitions and notations of a featurebased grammar formalism from Pollard and Sag 1987 and Shieber 1986 . 2 The LR Parsing Algorithm The LR parser is an efficient shift-reduce parser with optional lookahead. .

• Báo cáo khoa học
• AN EXTENDED LR PARSING
• ALGORITHM FOR GRAMMARS
• FEATURE BASED SYNTACTIC CATEGORIES
• scientific reports
• model language
• process natural language
• Dialog Control
• Natural Language System
• Dialog Control in a Natural Language System
• Expanding the Horizons
• Natural Language Interfaces
• Phil Hayes
• PROSPECTS OR PRACTICAL
• NATURAL LANGUAGE SYSTEMS
• Workshops
• NATURAL LANGUAGE
• INTERACTION WITH MACHINES
• Long Papers
• COMPUTER INTEBFACE DESIGN MURRAY TUROFF DEPARTMENT OF COMPUTER
• IiVFORMATION SCIENCE IIEW JERSEY INSTITUTE OF TECHNOLOGY
• EVALUATION OF NATURAL LANGUAGE
• INTERFACES TO DATABASE SYSTEMS
• A PANEL DISCUSSION
• database query system
• J
• Norwood Crout
• INTERFACES TO DATA BASE SYSTEMS
• Bozena Henisz
• INTERPRETING NATURAL LANGUAGE
• DATABASE UPDATES
• S
• Jermld Kaplan Jim David
• TRANSPORTABLE NATURAL LANGUAGE
• INTERFACES TO DATABASES
• Gary G
• Hendrlx and William H
• Lewis
• DATABASES THEORETICAL
• TECHNICAL ISSUES
• TRANSPORTABLE NATURAL LANGUAGE INTERFACES
• PROBLEMS AND TECHNIQUES
• Barbara J
• Grosz
• THEORETICAL TECHNICAL ISSUES
• NATURAL LANGUAGE ACCESS TO DATABASES
• R
• Petrick
• Domain Independent
• Database Access Systems
• ISSUES IN NATURAL LANGUAGE
• ACCESS TO DATABASES
• A LOGIC PROGRAMMING PERSPECTIVE
• Sharon C
• Salveter David Maier
• PLANNING NATURAL LANGUAGE
• EXPRESSIONS REFERRING
• Douglas E
• Appelt
• THE TEXT SYSTEM
• NATURAL LANGUAGE GENERATION
• Kathleen R
• M
• MENTING A DATABASE
• KNOWLEDGE REPRESENTATION
• THE KEY TO THE SELECTION PROBLEM
• E
• Jeffrey Conklin David D
• McDonald
• A KNOWLEDGE ENGINEERING
• NATURAL LANGUAGE UNDERSTANDING
• Stuart C
• Shapiro
• NATURAL LANGUAGE TEXTS
• NECESSARILY GRAMMATICAL
• EVEN COMPLETE
• UNGRAMHATICALITY
• EXTRA GRAMMATICALITY
• NATURAL LANGUAGE UNDERSTANDING SYSTEMS
• Taxonomy
• Descriptions
• Individuals in Natural
• Language Understanding
• The Use of Ooject Special Knowledge
• Natural Language Processing
• Mark H
• Bursteln