The use of grammatical inference for designing programming languages

ABSTRACT

Both in designing a new programming language and in extending an existing language, the designer is faced with the problem of deriving a “natural” grammar for the language. We are proposing an interactive approach to the grammar design problem wherein the designer presents a sample of sentences and structures as input to a grammatical inference algorithm. The algorithm then constructs a grammar which is a reasonable generalization of the examples submitted by the designer. The implemention is presently restricted to a subclass of operator precedence grammars, but a second algorithm is outlined which applies to a larger class of context-free grammars.

REFERENCES

• 1: Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]
• 2: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL and it formal definition: Part 1, Communications of the ACM, v.9 n.1, p.13-25, Jan. 1966 [doi>10.1145/365153.365162]
• 3: Knuth, D.E. Semantics of context-free languages. Mathem. Systems Theory 2, 2 (1968), 127-145.
• 4: Stefano Crespi-Reghizzi, The mechanical acquisition of precedence grammars, 1970
• 5: Crespi-Reghizzi, S. An effective model for grammar inference. IFIPS Cong., Ljublijana, 1971.
• 6: Biermann, A.W. and Feldman, J.A. A survey of results in grammatical inference. Internat. Conf. on Frontiers in Pattern Recognition, Honolulu, Jan. 1971.
• 7: Crespi-Reghizzi, S. Reduction of enumeration in grammar acquisition. 2nd. Internat. Conf. on Artificial Intelligence, London, 1971.
• 8: Biermann, A. A grammatical inference program for linear languages. 4th. Hawaii Internat. Conf. on System Sciences, Honolulu, 1971, pp. 121-123.
• 9: Gold, M.E. Language identification in the limit. Inf. and Control 10 (1967), 447-474.
• 10: Feldman, J.A. Some decidability results on grammatical inference and complexity. A.I. Memo No. 93.1, Computer Science Dept., Stanford U., May 1970.
• 11: James Jay Horning, A study of grammatical inference, 1969
• 12: Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
• 13: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 14: Edgar T. Irons, Experience with an extensible language, Communications of the ACM, v.13 n.1, p.31-40, Jan. 1970 [doi>10.1145/361953.361966]

INDEX TERMS

Keywords:
extensible languages, grammar design, identification in the limit, inference, language definition