Parsing Practice Questions

The global error correction problem formalises error recovery as finding the string w' ∈ L(G) that minimises the edit distance d(w, w') - the minimum number of insertions, deletions (and sometimes substitutions) to transform w into a valid string w'. This is the theoretical foundation of global correction. The edit distance between an erroneous program and its nearest correct version tells us the 'severity' of the errors. While theoretically clean, computing this optimally requires O(|w|³) time via DP/CYK and is too expensive for production compilers, which use faster heuristic strategies like panic mode instead.

Error productions add explicit grammar rules that match common mistakes programmers make - e.g., a production for a missing semicolon or a doubled operator. When such a production fires, the compiler emits a precise error message. The key limitation is coverage: error productions only handle errors the grammar designer anticipated. Novel or unusual errors fall through to generic panic mode recovery, which gives much less informative messages. Additionally, adding many error productions can significantly grow the grammar and parser tables. This technique works best for languages with a small set of extremely common errors.