Syntax-directed least-errors analysis for context-free languages
Communications of the ACMPublished 1 January 1974Open access
Gordon Lyon
Citations83
SJR quartileQ1
SJR score1.15
SNIP3.34
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A least-errors recognizer is developed informally using the well-known recognizer of Earley, along with elements of Bellman's dynamic programming, and takes a general class of context-free grammars as drivers and any finite string as input.
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.
Keywords
Computer Science
ScienceDynamic Programming
13,088 Citations1966Richard Bellman
The more the authors study the information processing aspects of the mind, the more perplexed and impressed they become, and it will be a very long time before they understand these processes sufficiently to reproduce them.
Information and ControlOn certain formal properties of grammars
1,565 Citations1959Noam Chomsky
A sequence of restrictions that limit grammars first to Turing machines, then to two types of system from which a phrase structure description of the generated language can be drawn, and finally to finite state Markov sources are shown to be increasingly heavy.
Formal Languages and Their Relation to Automata
1,341 Citations1969John E. Hopcroft, Jeffrey D. Ullman
The theory of formal languages as a coherent theory is presented and its relationship to automata theory is made explicit, including the Turing machine and certain advanced topics in language theory.
Nuclear Science and EngineeringFormal Languages and their Relation to Automata
1,004 Citations1970James B. Morris
Information and ControlRecognition and parsing of context-free languages in time n3
947 Citations1967D. H. Younger
A recognition algorithm is exhibited whereby an arbitrary string over a given vocabulary can be tested for containment in a given context-free language and it is shown that it is completed in a number of steps proportional to the “cube” of the number of symbols in the tested string.
Communications of the ACMAn efficient context-free parsing algorithm
817 Citations1970Jay Earley
A parsing algorithm which seems to be the most efficient general context-free algorithm known is described and appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.
Communications of the ACMDesign of a separable transition-diagram compiler
437 Citations1963Melvin E. Conway
A COBol compiler design is presented which is compact enough to permit rapid, one-pass compilation of a large subset of COBOL on a moderately large computer.
Communications of the ACMEULER: A generalization of ALGOL and its formal definition: Part 1
232 Citations1966Niklaus Wirth, Helmut Weber
In this section the algorithmic language EULER is described first informally and then formally by its syntax and semantics, creating a language which is simpler and yet more flexible than ALGOL 60.
Communications of the ACMTranslator writing systems
199 Citations1968Jerome A. Feldman, David Gries
A critical review of recent efforts to automate the writing of translators of programming languages is presented and various approaches to automating the postsyntactic aspects of translator writing are discussed.
Communications of the ACMAn error-correcting parse algorithm
65 Citations1963Edgar T. Irons
It is the author's opinion that those algorithms which do the best job of error recovery are those which are restricted to simpler forms of formal languages.
Acta InformaticaAutomatic correction of syntax-errors in programming languages
63 Citations1975J. -P. L�vy
A formal model for automatic error-correction that considers clusters of errors, using a local context to determine the corrections, can be embedded in left-to-right recognizers.
Formal development of correct algorithms
30 Citations1972Cliff B. Jones
This paper contains the formal development of a correct algorithm from an implicit definition of the task to be performed, each step of the development can be accompanied by a proof of its correctness.
Studies in Extensible Programming Languages
27 Citations1980Ben Wegbreit
A theoretical treatment of an extension facility for syntax that generalizes the notion of context-free grammars to allow the syntax of a language to be a function of its generated strings and studies the formal properties of such Grammars and presents an efficient algorithm for parsing their languages.
Context-free error analysis by evaluation of algebraic power series
20 Citations1973Ray Teitelbaum
Optimal error analysis with respect to a context-free language may be viewed as the evaluation of an algebraic power series, and the number of symbol insertions, deletions and/or replacements needed for correction is minimized.
Communications of the ACMAdaptive correction of program statements
13 Citations1973E. B. James, Derek Partridge
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.
ACM SIGPLAN NoticesOptimization of error recovery in syntax-directed Parsing algorithms
6 Citations1970Jacques E. LaFrance
Lecture notes in economics and mathematical systemsError Reporting, Error Treatment, and Error Correction in Algol Translation — Part 1
5 Citations1973C. H. A. Koster
In this note some pragmatic observations are given concerning the error treatment in, especially, ALGOL compilers.
ACM SIGPLAN NoticesOptimization of error recovery in syntax-directed parsing algorithms
5 Citations1970Jacques E. LaFrance
Deep Blue (University of Michigan)A Syntax-directed Least-errors Recognizer For Context-free Languages.
2 Citations1972Gordon Lyon