A Contextual Recognition System for Formal languages

Stephen C. DardenIJCAI 1969

Introduction

In the late 1960s, the primary bottleneck for digital computing was the translation of human-readable text into machine-readable code. Early optical character recognition (OCR) systems, or "character classifiers," were notoriously noisy, particularly when processing hand-printed text. While a human reader can intuitively correct a typo like FOR I := 1 STBP 10 to STEP, standard compilers are brittle; a single misread character typically results in a total syntax failure. This paper proposes a contextual post-processor designed to bridge the gap between imperfect hardware and the rigid requirements of formal programming languages like ALGOL, FORTRAN, and LISP.

System Architecture

The proposed system operates by exploiting the inherent redundancy found in formal languages. Unlike natural language, formal languages have strict rules regarding vocabulary, statistics, and syntax that can be leveraged to "guess" the correct characters in a garbled string.

The multi-stage contextual recognition system architecture, showing the flow from noisy input to final corrected text.

The process begins with a "Noisy Transducer" that generates a P-list (Probability list). Instead of outputting a single definitive character, the recognizer provides a list of possible alternatives for each position, ranked by confidence. This P-list then passes through three distinct stages of redundancy exploitation: vocabulary matching, name-space clustering, and structural parsing.

Three Stages of Error Correction

1. Vocabulary Redundancy: Extended-Dictionary Matching

The first stage identifies high-probability keywords such as DIMENSION, CONTINUE, or BEGIN. The system compares garbled substrings against a known dictionary of basic symbols using a specialized distance measure.

The mathematical definition of the distance measure d(U,V) used for dictionary matching.

As shown in the distance formula, the system calculates the similarity between the P-list ($U$) and dictionary entries ($V$). By matching these "anchors" first, the system significantly reduces the search space for subsequent stages.

2. Statistical Redundancy: Name-space Clustering

While keywords are known in advance, variable names (identifiers) are not. However, identifiers are statistically redundant because they are frequently reused within a single program. The system clusters "name-like" substrings of identical length. If the OCR inconsistently reads a variable as XMAX four times and XNAX once, the clustering algorithm can determine they are likely the same identifier, correcting the outlier based on the majority consensus.

3. Structural Redundancy: RODEN-form Parsing

The final and most innovative stage is the error-correcting parser. To facilitate this, the author introduces RODEN-form grammar. This is a specific transformation of Context-Free Grammars (CFGs) that eliminates recursion and adjacent non-terminals. This "self-positioning" grammar allows the parser to scan the text and find the most likely valid syntactic structure, even when characters are missing ("drops") or extra characters are present ("adds").

Results and Performance

The system was evaluated using simulated OCR data based on real-world confusion matrices for hand-printed text. In a key test involving a 272-character ALGOL program with an initial error rate of 33.1%, the system successfully identified 31 out of 43 instances of names, capturing at least one instance of every unique identifier used.

The ultimate goal of this multi-stage approach was to achieve an uncorrected error rate of less than 1%. By using high-confidence basic symbols as structural anchors, the system avoids the "staggering complexities" of full semantic analysis while providing a robust solution for early digital data entry.

Conclusion

This research demonstrates that the "messiness" of early OCR can be mitigated by treating formal language rules as a feature rather than a constraint. By combining dictionary matching, identifier clustering, and specialized grammar parsing, the system transforms noisy, unreadable data into high-quality digital code, paving the way for more resilient human-computer interfaces.

Summary updated

BibTeX
@inproceedings{darden1969contextual,
  author = {Stephen C. Darden},
  title = {{A Contextual Recognition System for Formal languages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1969},
}
Figure