Continuous Grammars

Abstract

After defining appropriate metrics on strings and parse trees, the classic definition of continuity is adapted and applied to functions from strings to parse trees. Grammars that yield continuous mappings are of special interest, because they provide a sound theoretical framework for syntax error correction. Continuity justifies the approach, taken by many error correctors, to use the function output (the parse tree), and all the additional information it provides, in order to find corrections to the function input (the string). We prove that all Bounded Context grammars are continuous and that all continuous grammars are Bounded Context Parseable grammars, giving a characterization of continuous grammars in terms of possible parsing algorithms.