Accession Number : AD0670577

Title :   A REPRESENTATION SYSTEM FOR PARSING PROCEDURES,

Corporate Author : RCA LABS PRINCETON N J

Personal Author(s) : Walters,Daniel A.

Report Date : MAY 1968

Pagination or Media Count : 326

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)

Descriptors :   (*COMPUTATIONAL LINGUISTICS, *PROBLEM SOLVING), CONTEXT FREE GRAMMARS, PHRASE STRUCTURE GRAMMARS, PROGRAMMING LANGUAGES, COMPUTER LOGIC, THEOREMS, SYNTAX, MACHINE TRANSLATION, COMPUTER PROGRAMMING

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE