A forward move algorithm for LL and LR parsers

ABSTRACT

A wide variety of algorithms have been suggested for the repair of syntactic errors in a computer program. Since there is usually more than one possible repair for any syntax error, many algorithms employ a cost function to guide the the repair, and some [1,3,4,6], guarantee that the repair chosen will be least-cost, according to some definition. (The others, although guided by costs, do not guarantee least-cost in all cases.) Fischer et al. [4,6,7] define a “locally least-cost” repair using insertions and deletions, and provide algorithms for LL and LR parsers. A locally least-cost repair is a least-cost sequence of deletions and insertions such that one more symbol in the original string will be accepted by the parser. Backhouse [2,3] uses a similar definition. In both cases, the repair algorithms operate by examining a single symbol in the input at any time.

REFERENCES

• 1: Aho, Alfred V. and Thomas G. Peterson , "A minimum distance error correcting parser for context-free languages," SIAM Journal of Computing 1, 4, pp. 305-312 (1972).
• 2: S. O. Anderson , R. C. Backhouse, Locally Least-Cost Error Recovery in Earley's Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.3, p.318-347, July 1981 [doi>10.1145/357139.357145]
• 3: Roland C. Backhouse, Syntax of Programming Languages: Theory and Practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1979
• 4: Fischer, Charles N., Bernard A. Dion, and Jon Mauney, "A Locally Least-Cost LR Error-Corrector," ACM Transaction on Programming Languages and Systems, (to appear).
• 5: Fischer, Charles N. and Jon Mauney, "On the role of error productions in syntactic error correction," Computer Languages 5, pp. 131-139 (1981).
• 6: Fischer, Charles N., Donn R. Milton, and Jon Mauney, "A locally least-cost LL(1) error corrector," Tech. Report #371, University of Wisconsin (August 1979).
• 7: Fischer, Charles N., Donn R. Milton, and Sam B. Quiring, "Efficient LL(1) error correction and recovery using only insertions," Acta Informatica 13, 2, pp. 141-154 (1980).
• 8: Susan L. Graham , Charles B. Haley , William N. Joy, Practical LR error recovery, ACM SIGPLAN Notices, v.14 n.8, p.168-175, August 1979
• 9: Susan L. Graham , Michael Harrison and Walter L. Ruzzo, An Improved Context-Free Recognizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.415-462, July 1980 [doi>10.1145/357103.357112]
• 10: Susan L. Graham , Steven P. Rhodes, Practical syntactic error recovery, Communications of the ACM, v.18 n.11, p.639-650, Nov. 1975 [doi>10.1145/361219.361223]
• 11: Levy, J. P., "Automatic correction of syntax errors in programming languages," Acta Informatica 4, pp. 271-292 (1975).
• 12: Jon Mauney, Least-cost syntactic error repair using extended right context, 1983
• 13: Ajit B. Pai , Richard B. Kieburtz, Global Context Recovery: A New Strategy for Syntactic Error Recovery by Table-Drive Parsers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.18-41, Jan. 1980 [doi>10.1145/357084.357086]
• 14: Thomas J. Pennello , Frank DeRemer, A forward move algorithm for LR error recovery, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.241-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512786]
• 15: Ripley, G. David and Frederick C. Druseikis, "A Statistical Analysis of Syntax Errors," Computer Languages 3, pp. 227-240 (1978).
• 16: Tai, Kuo Chung, "Syntactic error correction in programming languages," IEEE Trans on Software Engineering SE-4, 5, pp. 414-425 (1978).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages

General Terms:
Algorithms, Languages