A REPRESENTATION SYSTEM FOR PARSING PROCEDURES,
Abstract
The report describes a system for representing a class of parsing procedures for context-free phrase-structure languages. The system, called RS, is based on the reduction systems of problem solving used in such areas as machine theorem proving. The report discusses in great detail the requirements for obtaining an accurate and detailed dynamic description in RS of a given parsing procedure, and defines a model of a procedure to be a representation in RS satisfying these requirements. Models are presented for a large number of existing parsing procedures, and these models are used to display similarities and discrepancies among the procedures. An extension of RS is presented that allows the development of new and much more flexible parsing procedures. This extension utilizes the property of reduction systems that the solution methods used for different problems can be chosen independently of each other. A procedure is presented in this extended system which has available to it both extensions of the models previously developed and efficient processors for deterministic sub-grammars of a given grammar. This procedure is proved to be a solution algorithm for any derivation problem, regardless of which solution techniques are used. The report discusses the suitability of RS as a research tool, a specification language, and a tutorial vehicle, and how it can be used for these purposes. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1968
- Accession Number
- AD0670577
Entities
People
- Daniel A. Walters
Organizations
- RCA Corporation