“Structural connections” in formal languages
- 1 February 1964
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 7 (2) , 67-72
- https://doi.org/10.1145/363921.363931
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.Keywords
This publication has 4 references indexed in Scilit:
- A syntax directed compiler for ALGOL 60Communications of the ACM, 1961
- Report on the algorithmic language ALGOL 60Communications of the ACM, 1960
- A note on phrase structure grammarsInformation and Control, 1959
- On certain formal properties of grammarsInformation and Control, 1959