DETECTION OF GENERATIVE AMBIGUITIES IN CONTEXT-FREE MECHANICAL LANGUAGES.
MOORE SCHOOL OF ELECTRICAL ENGINEERING UNIV OF PENNSYLVANIA PHILADELPHIA
Pagination or Media Count:
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
- Computer Programming and Software
- Computer Hardware