Adaptive correction of program statements

ABSTRACT

A method of analyzing statements in a programming language which can tolerate a considerable inaccuracy in their specification is proposed. This method involves principles at present mainly confined to studies in the area of artificial intelligence such as feature extraction, approximate tree matching, and strategy improvement by feedback from the matching process. A pilot program incorporating the principles is described and preliminary operating results are presented. A final section surveys further principles which are currently being investigated.

REFERENCES

• 1: Fu, K.S. Sequential Methods in Pattern Recognition and Machine Learning. Academic Press, New York, 1968.
• 2: W. A. Woods, Transition network grammars for natural language analysis, Communications of the ACM, v.13 n.10, p.591-606, Oct. 1970 [doi>10.1145/355598.362773]
• 3: Rosen Saul, Programming Systems and Languages., McGraw Hill Text, 1967
• 4: Hopgood, F.R.A. Compiling Techniques. Macdonald, London, 1969.
• 5: Jacques Emmett Lafrance, Syntax-directed error recovery for compilers, 1971
• 6: E. T. Irons, An error-correcting parse algorithm, Communications of the ACM, v.6 n.11, p.669-673, Nov. 1963 [doi>10.1145/368310.368385]
• 7: Backus, J.W. The syntax and semantics of the proposed international algebraic language of the Zmich ACM-GAMM Conference. Proc. Internat. Conf. on Information Processing, UNESCO, June 1959, pp. 125-132.
• 8: R. W. Conway , W. L. Maxwell, CORC—the Cornell computing language, Communications of the ACM, v.6 n.6, p.317-321, June 1963 [doi>10.1145/366604.366651]
• 9: Howard L. Morgan, Spelling correction in systems programs, Communications of the ACM, v.13 n.2, p.90-94, Feb 1970 [doi>10.1145/362007.362033]
• 10: Banerji, R.B. The Theory of Problem Soiving, an Approach to Artificial Intelligence. American Elsevier, New York, 1969.
• 11: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 12: Michie, D. "Memo" functions and machine learning. Nature 218 (1968), 19-22.
• 13: Partridge, D. Forthcoming Thesis, Department of Computing and Control, Imperial College, London U., England.
• 14: Kiss, G.R. Steps towards a model of word selection. In Machine Intelligence 4, D. Michie (Ed.), University Press, Edinburgh, 1969.
• 15: Good, I.J. The first ultra-intelligent machine. In Advances in Computers 6, Academic Press, New York, 1965, pp. 31-88.
• 16: Good, I.J. Creativity and duality in perception and recall. Proc. IEE/NPL Conf. on Pattern Recognition, IEE Conf. Pub. No. 42, London: IEE, 1968, pp. 228-237.
• 17: Longuet-Higgins, C., and Ortony, A. The adaptive memorisation of sequences. In Machine Intelligence 3, D. Michie (Ed.), University Press, Edinburgh, 1968.
• 18: Sparkes, J.J. Pattern recognition and a model of the brain. International J. Man-machine Studies 1, (1969), 263-278.
• 19: Winston, P.H. Learning structural descriptions from examples. Ph.D. Th., Dept. of Electrical Engineering, M.I.T., Cambridge, Mass. Project MAC, MIT, 1970.
• 20: Guzman, A. Decomposition of a visual scene into threedimensional bodies. Proc. AFIPS 1968 FJCC Vol. 33, AFIPS Press, Montvale, N.J. pp. 291-304.
• 21: Huesman, L.R. A study of hueristic learning methods for optimization tasks requiring a sequence of decisions. Proc. AFIPS 1970 SJCC, Vol. 36, AFIPS Press, Montvale, N.J., pp. 629-647.
• 22: L. E. Stanfel, Tree Structures for Optimal Searching, Journal of the ACM (JACM), v.17 n.3, p.508-517, July 1970 [doi>10.1145/321592.321601]
• 23: Yale N. Patt, Variable length tree structures having minimum average search time, Communications of the ACM, v.12 n.2, p.72-76, Feb. 1969 [doi>10.1145/362848.362853]
• 24: S. R. Arora , W. T. Dent, Randomized binary search technique, Communications of the ACM, v.12 n.2, p.77-80, Feb. 1969 [doi>10.1145/362848.362856]
• 25: Warshall, S., and Shapiro, R.M. A general-purpose tabledriven compiler Proc. AFIPS 1964 SJCC, Vol. 25, Spartan Books, New York, pp. 59-65.

INDEX TERMS

Keywords:
adaptive, approximate match, automatic parsing, compiler, linguistic pattern matching, program statement analysis, syntax analysis