E. T. Irons
Abstract
This paper defines the concept of “structural connection” in a mechanical language in an attempt to classify various formal languages according to the complexity of parsing structures on strings in the languages. Languages discussed vary in complexity from those with essentially no structure at all to languages which are self-defining. The relationship between some existing recognition techniques for several language classes is examined, as well as implications of language structure on the complexity of automatic recognizers.
- 1 CHOMSKY, N. On certain formal properties of grammars. Informat. Contr. 2, 137,167.Google Scholar
- 2 ----. A note on phrase structure grammars. Informat. Contr. 2, 393-395.Google Scholar
- 3 PAUL, M. A General Processor for Certain Formal Languages. Gymbalie Languages in Data Processing, Gordon and Breach, London 1962, pp. 65-74.Google Scholar
- 4 EICKEL, J., PAUL, M., BAUER, F. L., SAMUELSON, K. "A Syntax Controlled Generator of Formal Language Processors." Inst. fur Ant. Math. Univ. Mainz. (September, 1962).Google Scholar
- 5 BACKU8, J. W. The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference. Proc. Internat. Conference on Information Processing, UNESCO, June, 1959, pp. 125-132.Google Scholar
- 6 NAUR, PETER (Ed.) Report on the algorithmic language ALGOL 60. Comm. ACM 3 (1960), 299-314. Google ScholarDigital Library
- 7 IRONS, E. T. A syntax-directed compiler for ALGOL 60. Comm. ACM 4 (1961), 51-55. Google ScholarDigital Library
Index Terms
- “Structural connections” in formal languages
Recommendations
Formal Semantics of Programming Languages
These notes give an overview of the main frameworks that have been developed for specifying the formal semantics of programming languages. Some of the pragmatic aspects of semantic descriptions are discussed, including modularity, and potential ...
Informal and Formal Requirements Specification Languages: Bridging the Gap
The differences between informal and formal requirements specification languages are noted, and the issue of bridging the gap between them is discussed. Using structured analysis (SA) and the Vienna development method (VDM) as surrogates for informal ...
Representing Structural Language Features in Formal Meta-languages
Intelligent Computer MathematicsAbstractStructural language features are those that introduce new kinds of declarations as opposed to those that only add expressions. They pose a significant challenge when representing languages in meta-languages such as standard formats like OMDoc or ...
Comments