Language Correction Using Probabilistic Grammars

Error correction of programming languages has been effected in a heuristic fashion; error correction in the information-theoretic sense is very precise. The missing link is provided through probabilistic grammars. This paper provides the theoretical foundation for the precise construction of an error correcting compiler. The concept of code distance is extended to account for syntax in language. Grammar modifications are demonstrated so that a probabilistic parsing algorithm corrects various kinds of linguistic errors using an ideal observer rule. A generalized error correcting algorithm is described.