DETECTION OF GENERATIVE AMBIGUITIES IN CONTEXT-FREE MECHANICAL LANGUAGES.
Abstract
The author considers the problem of detecting those words in a 'context-free' mechanical language which can be derived from the defining 'productions' in essentially more than one way. The problem of finding a single algorithm accepting the generative specifications of such languages, and determining in a finite time whether or not such 'ambiguities' exist, is known to be unsolvable. The author, however, by defining the 'generative levels' with respect to the production system for each word of the language, specifies a processor called a 'limited ambiguity detector' whose main component is a 'derivation generator'; the latter works with a mixed language including the object language and a portion of the syntax language belonging to the class of generalized prefix languages as recently defined by the author. Such a detector would be supplied by the user with a value of a natural number parameter n, and would find all ambiguities through level n, with print-outs which might read: 'level 375 is finished and all is well', or 'level 379 is finished, and the following words are ambiguous with the following derivations at levels less than or equal to 379'. This detector is a fairly efficient four-tape processor. The fact that it can be designed is useful information to 'standardizers' who want to certify, for unambiguity up to level n, specified context-free languages, such as the syntactic part of ALGOL. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1962
- Accession Number
- AD0636319
Entities
People
- Saul Gorn
Organizations
- Moore School of Electrical Engineering