Directed random generation of sentences

ABSTRACT

The problem of producing sentences of a transformational grammar by using a random generator to create phrase structure trees for input to the lexical insertion and transformational phases is discussed. A purely random generator will produce base trees which will be blocked by the transformations, and which are frequently too long to be of practical interest. A solution is offered in the form of a computer program which allows the user to constrain and direct the generation by the simple but powerful device of restricted subtrees. The program is a directed random generator which accepts as input a subtree with restrictions and produces around it a tree which satisfies the restrictions and is ready for the next phase of the grammar. The underlying linguistic model is that of Noam Chomsky, as presented in Aspects of the Theory of Syntax. The program is written in FORTRAN IV for the IBM 360/67 and is part of a unified computer system for transformational grammar. It is currently being used with several partial grammars of English.

REFERENCES

• 1: CHOMSKY, NOAM. Aspects of the Theory of Syntax. MIT Press, Cambridge, Mass., 1965.
• 2: Robert W. Doran, 360 O.S. FORTRAN IV free field input/output subroutine package, Stanford University, Stanford, CA, 1967
• 3: Joyce Friedman, A computer system for transformational grammar, Stanford University, Stanford, CA, 1968
• 4: Joyce Friedman , Robert W. Doran, A formal syntax for transformational grammar, Stanford University, Stanford, CA, 1968
• 5: GROSS, L. N. On-line programming system user's manual. MTP-59, The MITRE Corp., Bedford, Mass., 1967.
• 6: --. M.I.T. Rule Tester. MIT, 1968. (unpublished)
• 7: LONDE, D. L., AND SCHOENE, W.J. TGT: Transformational Grammar Tester. Syst. Develop. Corp., Santa Monica, Calif., 1967.
• 8: MEYERS, L. F., AND YANG, J. Chinese grammars and the computer at the Ohio State University. Project on Linguistic Analysis, Rep. No. 10, Res. Found., Ohio State U., Columbus, Ohio, May, 1965, pp. 28--37.
• 9: OYELARAN, OLASOPE O. AF test grammar, AF-13, Comput. Sci. Dep., Stanford U., Stanford, Calif., Sept. 1967.
• 10: Toshiyuki Sakai , Makoto Nagao, Sentence generation by semantic concordance, Proceedings of the 1965 conference on Computational linguistics, p.1-21, May 19-21, 1965, Bonn, Germany [doi>10.3115/990314.990330]
• 11: PARTEE, B. H., SCHAOHTER, P., STOCKWELL, R., et al. Working papers, UCLA-Air Force English Syntax Conf., Sept. 4--15, 1967. (multilithed)
• 12: YNGVE, VICTOR H. Random generation of English sentences, Proc. 1961 Int. Conf. on Machine Translation of Languages and Applied Language Analysis, Teddington, H.M.S.O., London, 1962, pp. 66-80.
• 13: ZWICKY, A. M., FRIEDMAN, J., HALL, B., AND WALKER, D. E. The MITRE syntactic analysis procedure for transformational grammar. Proc. AFIPS 1965 Fall Joint Comput. Conf., Vol. 27, Pt. 1, Spartan Books, New York, pp. 317-326. Also MTP-9, The MITRE Corp., Bedford, Mass., 1965.
• 14: KLIMA, E.S. Current developments in generative grammar. Kybernetika 1 (1965), 184---197.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Design, Human Factors, Languages, Theory

Keywords:
computational linguistics, language processing, natural language syntax, sentence generation, syntax, transformational grammar