article

Open access

Locally Least-Cost Error Recovery in Earley's Algorithm

Editor: Susan L. Graham Authors:

S. O. Anderson,

R. C. BackhouseAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 3, Issue 3

Pages 318 - 347

https://doi.org/10.1145/357139.357145

Published: 01 July 1981 Publication History

PDF eReader

References

[1]

AHo, A.V, ANO PETERSON, T.G. A m'mimum-distance error-correcting parser for context free languages. SIAM J. Comput. 1, 4 (1972), 305-312.

Google Scholar

[2]

ANDERSON, S.O., AND BACKHOUSE, R.C. Improvements to an insertion-only recovery technique. Submitted for publication.

Google Scholar

[3]

BACKHOUSE, R.C. Syntax of Programming Languages: Theory and Practice. Prentice-Hall International, London, 1979.

Crossref

Google Scholar

[4]

BACKHOUSE, R.C., AND CARRE, B.A. Regular algebra applied to path-finding problems. J. Inst. Math. Appl. 15, 2 (April 1975), 151--186.

Google Scholar

[5]

CARRIe, B.A. A network routing algebra. J. Inst. Math. Appl. 7, 3 (June 1971), 273-294.

Google Scholar

[6]

CIESINCER, J. A bibliography of error-handling. SIGPLAN Notices (ACM) 14, 1 (Jan. 1979), 16-26.

Google Scholar

[7]

DIJKSTRA, E.W. A note on two problems in connexion with graphs. Numer. Math. I (1959), 269- 271.

Google Scholar

[8]

DiON, B.A., AND FISCH}~;R, C.N. A least-cost error corrector for LR(I)-based parsers. Tech. Rep. 333, Computer Sciences Dep., Univ. Wisconsin-Madison, Sept. 1978.

Google Scholar

[9]

DUERR, B., HAETTICH, W., TROPF, H., AND WINKLER, G. A combination of statistical and syntactical pattern recognition applied to classification of unconstrained handwritten numerals. Pattern Recogn. 12 (1980), 189-199.

Google Scholar

[10]

EARLEY, J. An efficient context-free parsing algorithm. Commun. ACM 13, 2 (Feb. 1970), 94- 102.

Crossref

Google Scholar

[11]

FISCH}';R, C.N., MmTON, D.R., AND QUIRINC, S,B. Efficient LL(1) error-correction and recovery using only insertions. Acta Inf. 13, 2 (1980), 141-154.

Google Scholar

[12]

F~SCHER, C.N., MILTON, D.R., AND QUIRING, S.B. An efficient insertion-only error-corrector for LL(1) parsers. In Conf. Rec., 4th ACM Syrnp. Principles of Programming Languages, Los Angeles, Calif., Jan. 17-19, 1977, pp. 97-103.

Crossref

Google Scholar

[13]

Fu, K.S. Error-correcting parsing for syntactic pattern recognition. In Data Structure, Computer Graphics, and Pattern Recognition, A. Klinger et al. (Eds.). Academic Press, New York, 1977, pp. 449-492.

Google Scholar

[14]

GONZALEZ, R.C., AND Ti4OMASON, M.G. Syntactic Pattern Recognition. Addison-Wesley, Reading, Mass., 1978.

Google Scholar

[15]

KNUTI-I, D.E. On the translation of languages from left to right. Inf. Control 8, 6 (Dec. 1965), 6O7-639.

Google Scholar

[16]

LEVINSON, S.E. The effects of syntactic analysis on word recognition accuracy. Bell Syst. Tech. J. 57, 5 (May-June 1978), 1627-1644.

Google Scholar

[17]

LEVINSON, S.E., ROSENBERG, A.E., AND FLANAGAN, J.L. Evaluation of a word recognition system using syntax analysis. Bell Syst. Tech. J. 57, 5 (May-June 1978), 1619-1626.

Google Scholar

[18]

LYON, G. Syntax-directed least-errors analysis for context-free languages: A practical approach. Commun. ACM 17, 1 (Jan. 1974), 3-14.

Crossref

Google Scholar

[19]

SIPPU, $., AND SOISALON-$OINIEN, E. A scheme for LR(k) parsing with error recovery, Part III: Error correction. Int. J. Comput. Math. 8, 3 (1980), 189-206.

Google Scholar

[20]

TAI, K.C. Syntactic error-correction in programming languages. IEEE Trans. Softw. Eng. SE- 4, 5 (1978), 414-425.

Google Scholar

[21]

TARJAN, R.E. A unified approach to path-finding problems. Tech. Rep. STAN-CS-79-729, Computer Science Dep., Stanford Univ., Stanford, Calif., 1979.

Crossref

Google Scholar

[22]

TEITELBAUM, R. Minimal Distance Analysis of Syntax Errors in Computer Programs. Ph.D. dissertation, Computer Science Dep., Carnegie-Mellon Univ., Pittsburgh, Pa., Sept. 1975.

Crossref

Google Scholar

[23]

WACNER, R.A. Order-n correction for regular languages. Commun. ACM 17, 5 (May 1974), 265- 268.

Crossref

Google Scholar

[24]

WAGNER, R.A., AND FISCHER, M.J. The string-to-string correction problem. J. ACM 21, 1 (Jan. 1974), 168-173.

Crossref

Google Scholar

[25]

WIRTH, N. Algorithms + Data Structures -- Programs. Prentice-Hall, Englewood Cliffs, N.J., 1976.

Crossref

Google Scholar

Cited By

View all

Kirschner LSoremekun EZeller ARothermel GBae D(2020)Debugging inputsProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380329(75-86)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380329
Stirling C(2006)Follow set error recoverySoftware: Practice and Experience10.1002/spe.438015030315:3(239-257)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380150303
Min KWilson W(2005)Integrated correction of ill-formed sentencesAdvanced Topics in Artificial Intelligence10.1007/3-540-63797-4_90(369-378)Online publication date: 30-Jul-2005
https://doi.org/10.1007/3-540-63797-4_90
Show More Cited By

Index Terms

Locally Least-Cost Error Recovery in Earley's Algorithm
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Error handling and recovery
  2. Software notations and tools
    1. Compilers
      1. Parsers

Recommendations

An Earley-type parsing algorithm for Tree Adjoining Grammars
ACL '88: Proceedings of the 26th annual meeting on Association for Computational Linguistics

We will describe an Earley-type parser for Tree Adjoining Grammars (TAGs). Although a CKY-type parser for TAGs has been developed earlier (Vijay-Shanker and Joshi, 1985), this is the first practical parser for TAGs because as is well known for CFGs, the ...
On the automatic generation of parsers providing locally least-cost error repairs
Syntax error recovery in parsing expression grammars
SAC '18: Proceedings of the 33rd Annual ACM Symposium on Applied Computing

Parsing Expression Grammars (PEGs) are a formalism used to describe top-down parsers with backtracking. As PEGs do not provide a good error recovery mechanism, PEG-based parsers usually do not recover from syntax errors in the input, or recover from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 3, Issue 3

July 1981

137 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/357139

Editor:
Susan L. Graham

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1981

Published in TOPLAS Volume 3, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
536
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kirschner LSoremekun EZeller ARothermel GBae D(2020)Debugging inputsProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380329(75-86)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380329
Stirling C(2006)Follow set error recoverySoftware: Practice and Experience10.1002/spe.438015030315:3(239-257)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380150303
Min KWilson W(2005)Integrated correction of ill-formed sentencesAdvanced Topics in Artificial Intelligence10.1007/3-540-63797-4_90(369-378)Online publication date: 30-Jul-2005
https://doi.org/10.1007/3-540-63797-4_90
Corchuelo RPérez, JRuiz AToro M(2002)Repairing syntax errors in LR parsersACM Transactions on Programming Languages and Systems10.1145/586088.58609224:6(698-710)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1145/586088.586092
Min KWilson WBoitet CWhitelock P(1998)Integrated control of chart items for error repairProceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics - Volume 210.3115/980691.980711(862-868)Online publication date: 10-Aug-1998
https://dl.acm.org/doi/10.3115/980691.980711
Tesar BJoshi APalmer M(1996)Computing optimal descriptions for Optimality Theory grammars with context-free position structuresProceedings of the 34th annual meeting on Association for Computational Linguistics10.3115/981863.981877(101-107)Online publication date: 24-Jun-1996
https://dl.acm.org/doi/10.3115/981863.981877
McKenzie BYeatman Cde Vere L(1995)Error repair in shift-reduce parsersACM Transactions on Programming Languages and Systems10.1145/210184.21019317:4(672-689)Online publication date: 1-Jul-1995
https://dl.acm.org/doi/10.1145/210184.210193
Dain J(1994)A practical minimum distance method for syntax error handlingComputer Languages10.1016/0096-0551(94)90006-X20:4(239-252)Online publication date: 1-Nov-1994
https://dl.acm.org/doi/10.1016/0096-0551%2894%2990006-X
van den Bosch P(1992)A bibliography on syntax error handling in context free languagesACM SIGPLAN Notices10.1145/131080.13109027:4(77-86)Online publication date: 1-Apr-1992
https://dl.acm.org/doi/10.1145/131080.131090
Fischer CMauney J(1992)A simple, fast, and effective LL(1) error repair algorithmActa Informatica10.1007/BF0117850229:2(109-120)Online publication date: 2-Apr-1992
https://dl.acm.org/doi/10.1007/BF01178502
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

An Earley-type parsing algorithm for Tree Adjoining Grammars

On the automatic generation of parsers providing locally least-cost error repairs

Syntax error recovery in parsing expression grammars

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations