The Algorithm Design Manual Second Edition

Stop and Think: Parsimonious Parserization

Problem:

Programs often contain trivial syntax errors that prevent them from

compiling. Given a context-free grammar G and input string S, find the smallest

number of character substitutions you must make to S so that the resulting string

is accepted by G.

Solution:

This problem seemed extremely difficult when I first encountered it.

But on reflection, it seemed like a very general version of edit distance, which is

addressed naturally by dynamic programming. Parsing initially sounded hard, too,

but fell to the same technique. Indeed, we can solve the combined problem by

generalizing the recurrence relation we used for simple parsing.

Define M



[i, j, X] to be an integer function that reports the minimum number of

changes to substring S[i, j] so it can be generated by nonterminal X. This symbol

will be generated by some production x

→ yz. Some of the changes to s may be

k=i

---

300

8 .

D Y N A M I C P R O G R A M M I N G

Figure 8.10: Two different triangulations of a given convex seven-gon

to the left of the breaking point and some to the right, but all we care about is

minimizing the sum. In other words,

M



[i, j, X] =

min

(

X

→Y Z)∈G

j

min

i=k

M



[i, k, Y ] + M



[k + 1, j, Z]

The boundary conditions also change mildly. If there exists a production X

→

α, the cost of matching at position i depends on the contents of S[i], where S[i] = α,

M [i, i, X] = 0. Otherwise, it is one substitution away, so M [i, i, X] = 1 if S[i]

= α.

If the grammar does not have a production of the form X

→ α, there is no way to

substitute a single character string into something generating X, so M [i, i, X] =

∞

for all i.