PROBLEM-SOLVING PROCEDURES FOR EFFICIENT SYNTACTIC ANALYSIS,
Abstract
The main purpose of this report is to present a logical framework in which the syntactic analysis problem can be represented. This framework originates from previous work on problem-solving procedures for theorem proving. Procedures for syntactic analysis are represented as reduction procedures where a problem undergoes a sequence of nested transformations that result in a set of simpler subordinate problems whose solution implies the solution of the original problem. The representation of the syntactic analysis problem provides a unifying basis for expressing a variety of syntactic analysis procedures, both existing ones as well as new, proposed, procedures. Such a common basis contributes to a better understanding and systemization of the programming of syntax-directed compilers and of other translators whose source language is a context-free fragment of natural language, e.g., some 'question-answering' systems. A useful concept of computational effort is defined, and it is used as a guide for the formulation of new efficient procedures. Heuristic procedures for syntactic analysis are suggested. Some features of these procedures are relevant to the design of advanced syntax-directed translators. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1968
- Accession Number
- AD0670575
Entities
People
- Saul Amarel
Organizations
- RCA Corporation