Edit distance into a DCFL

Question

I would like to generate helpful parser errors, telling the user how to fix their program.

Specifically I have a deterministic context-free language $L$, given in the form of an $LR(1)$ grammar. I have a syntactically invalid string $w$ (i.e. $w \not\in L$). I would like to find some $w^* \in L$ which minimizes the edit distance $d(w, w^*)$ between $w^*$ and $w$, i.e. there is no $w' \in L$ such that $d(w, w') < d(w, w^*)$.

What are the state-of-the-art techniques for attacking this kind of problem? I can find shortest repairs in $O(n^3)$ time with a modified CYK algorithm for arbitrary grammars; I would like to make use of the fact that I have an LR(1) grammar to speed up the process, if possible.

Answer 1

It would appear the language edit distance problem for the class of deterministic context-free languages requires cubic time.

In Language Edit Distance Approximation via Amnesic Dynamic Programming (Jayaram and Saha, https://rajeshjayaram.com/mainb-3.pdf), it is shown that cubic time is required for the ultralinear languages, which are exactly those recognized by some finite-turn PDA.

According to The equivalence problem for deterministic finite-turn pushdown automata (Valiant, https://www.sciencedirect.com/science/article/pii/S0019995874908390, either "view PDF" online or "download full issue" to use your own viewer),

The class of finite-turn machines can be described as the intersection of the class of deterministic pushdown automata (Ginsburg and Greibach, 1966) with the class of nondeterministic finite-turn pushdown automata (Ginsburg and Spanier, 1966).

The Jayaram-Saha and Valiant papers refer to the same Ginsburg-Spanier paper (paywalled at https://epubs.siam.org/doi/10.1137/0304034), so I assume they mean the same thing.

So if cubic time is required for some (proper) subclass of deterministic languages, we cannot solve the language edit distance problem for the whole class in less than cubic time.

But we can also solve the language edit distance for arbitrary context-free languages in cubic time, so the mere fact of determinism doesn't buy us anything extra.

Disclaimer: I have not fully read the Jayaram-Saha paper. Their lower bound may be conditional on some widely-believed hypothetical lower bound.