Syntax-directed least-errors analysis for context-free languages: a practical approach

ABSTRACT

A least-errors recognizer is developed informally using the well-known recognizer of Earley, along with elements of Bellman's dynamic programming. The analyzer takes a general class of context-free grammars as drivers, and any finite string as input. Recognition consists of a least-errors count for a corrected version of the input relative to the driver grammar. The algorithm design emphasizes practical aspects which help in programming it.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 2: Bollinger, H. The HELP metacompiler, a compiler writing tool. 1968 Annual Spring Meeting, General Motors Committee on Engineering Computations.
• 3: Chomsky, N. On certain formal properties of grammars. information and Control 2,2 (Feb. 1959), 137-167.
• 4: Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
• 5: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 6: Jay Clark Earley, An efficient context-free parsing algorithm, 1968
• 7: Eggers, 13. Zur Theorie and Praxis Selbstkorrigierender Regulaerer Sprachen. Dr.rer.nat. dissertation. Technischen Universitaet Hanover, 1972.
• 8: Eggers, B. Error reporting, error treatment and error correction in ALGOL translation, Part II. Second Annual Meeting, G.I. Karlsruhe, Oct. 1972.
• 9: Evans, A., Jr. An ALGOL 60 compiler. In .4nnual Review in Automatic Programming. Pergamon Press, New York, 1964.
• 10: Feldman, J.A., and Curry, J.E. The compiler-compiler in a time-sharing environment. Summer Engineering Conf. on Advanced Computer Organization. U. of Michigan, Ann Arbor, Mich., 1967.
• 11: Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]
• 12: Hopcroft, J.E., and Ullman, J.D. Error correction for formal languages. Digital Syst. Lab. Rep. 52. Princeton U., Princeton, N.J., 1966.
• 13: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 14: 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]
• 15: E. B. James , D. P. Partridge, Adaptive correction of program statements, Communications of the ACM, v.16 n.1, p.27-37, Jan. 1973 [doi>10.1145/361932.361940]
• 16: C B Jones, Formal development of correct algorithms: An example based on earley's recogniser, ACM SIGACT News
• 17: Kovalevsky, V.A. Sequential optimization in pattern recognition and pattern description. Preprint supplement booklet I, IFIP Cong., Edinburgh, 1968, pp. 1146--1151.
• 18: Jacques LaFrance, Optimization of error recovery in syntax-directed parsing algorithms, ACM SIGPLAN Notices, v.5 n.12, December 1970 [doi>10.1145/987452.987454]
• 19: Jacques Emmett Lafrance, Syntax-directed error recovery for compilers, 1971
• 20: Ronald Paul Leinius, Error detection and recovery for syntax directed compiler systems, 1970
• 21: Jean-Pierre Levy, Automatic correction of syntax errors in programming languages, 1971
• 22: Lyon, G.E. Least-errors recognition of mutated contextfree sentences in time n log n. Proc. Sixth Princeton Conf. on Inform. Syst. and Sci. Princeton, N.J., 1972, pp. 115-118.
• 23: Lyon, G.E. Time IP log n least-errors recognition of ungrammatical sentences of context-free languages. Mental Health Res. Inst. Comm. # 292. U. of Michigan, Ann Arbor, Mich. 1972.
• 24: Gordon Edward Lyon, A syntax-directed least-errors recognizer for context-free languages, 1972
• 25: Peterson, T.G. From a private discussion with the author, March 22, 1972.
• 26: Thomas G. Peterson, Syntax error detection, correction and recovery in parsers, 1972
• 27: Peterson, W.W. Error-Correcting Codes. The MIT Press, Cambridge, Mass., 1961.
• 28: Ray Teitelbaum, Context-free error analysis by evaluation of algebraic power series, Proceedings of the fifth annual ACM symposium on Theory of computing, p.196-199, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804050]
• 29: Wegbreit, B. Studies in extensible programming languages. Ph.D. diss. Harvard U., 1970.
• 30: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]
• 31: Younger, D.H. Recognition and parsing of context-free languages in time n3 . Information and Control 10,2 (Feb. 1967), 189-208.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Design, Languages, Performance, Reliability, Theory

Keywords:
arbitrary input strings, context-free grammars, dynamic progamming, least-errors connection, parsing, separability, state merging, stored subanalysis