RSS
Twitter
Facebook
Ideally,
we would like a compiler to make as few changes as possible in processing an
incorrect input string. There are algorithms for choosing a minimal sequence of
changes to obtain a globally least-cost correction. Given an incorrect input
string x and grammar G,
these algorithms will find a parse tree for a related string y,
such that the number of insertions, deletions, and changes of
tokens required to transform x into
y is as small as possible. Unfortunately, these
methods are in general too costly to implement in terms of time and space, so
these techniques are currently only of theoretical
interest. Do note that a closest correct program may not be what the programmer
had in mind. Nevertheless, the notion of least-cost correction provides a
yardstick for evaluating errorrecovery techniques, and has been used for
finding optimal replacement strings for phrase-level recovery.
0 comments