Accession Number : AD0636319

Title :   DETECTION OF GENERATIVE AMBIGUITIES IN CONTEXT-FREE MECHANICAL LANGUAGES.

Corporate Author : MOORE SCHOOL OF ELECTRICAL ENGINEERING UNIV OF PENNSYLVANIA PHILADELPHIA

Personal Author(s) : Gorn, Saul

Report Date : 1962

Pagination or Media Count : 27

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)

Descriptors :   (*CONTEXT FREE GRAMMARS, PROGRAMMING LANGUAGES), SYNTAX, SEMANTICS, FLOW CHARTING, DATA PROCESSING, INPUT OUTPUT DEVICES, MAGNETIC TAPE, ALGORITHMS

Subject Categories : Linguistics
      Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE