There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word. Can something similar be done with an Earley parser? I'm finding it hard to understand the algorithm, let alone answer this question.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Well, PDA are closed against many operations with NFA, so this should be possible in principle. Adapting Earley seems to be a rote exercise, since we are allowed to use a counters in items. Am I missing something? $\endgroup$– RaphaelCommented Jul 31, 2015 at 7:06
-
$\begingroup$ @Raphael Yes This is the general idea. My answer is longer, as it is difficult to assess what users know or do not know. $\endgroup$– babouCommented Jul 31, 2015 at 8:14
-
$\begingroup$ plz cite a ref/ sketch defn for "Levenshtein Automata". know of one that might qualify, but which one are you referring to? $\endgroup$– vznCommented Jul 31, 2015 at 15:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The answer is yes. However I would not do that with an Earley parser because there are simpler ones with the same capabilities.
Basically, Earley parser belongs to a family of general context-free parsers, that produces all possible parses for a given string, when the grammar is ambiguous.
There are two ways (at least) of understanding these parsers:
as dynamic programming interpretation of a pushdown automaton corresponding to the grammar on the input string;
as the the construction of the intersection of the grammar with a finite state automaton.
When parsing a single string, the finite state automaton to be considered is a linear automaton that recognizes only the string $w$ to be parsed, one symbol at a time (number of state is $|w|+1$). If you apply the cross-product construction of a FA $A$ and a CF garmmar $G$ (Bar Hillel, Perlis, Shamir 1961), you get a new CF grammar that is a new grammar $F$ which generates $\mathcal L(A)\cap\mathcal L(G)$. The interesting point usually overlooked is that $F$ preserves the parse-trees used by $G$, up to non-terminals renaming (due to cross-product).
Thus if the FA $A$ generates only your input string, the grammar $F$ will generate only that string (if it is in $\mathcal L(G)$, otherwise it generates the empty language $\emptyset$). Furthermore, it generates it with all the parse-trees that $G$ could use to generate it.
This grammar $F$ is what is usually called a shared parse forest, and all general CF parsing algorithms are a more or less optimized version of the cross-product construction, whether CYK, Earley, generalized LR or LL, or others. So all I am saying applies to them too.
But, as you see, this generalizes to parsing a whole regular set, if anyone is interested in doing that.
That is precisely your question. You have a string $w$. You want to parse it up to some variations defined by a finite state transducer, which in your case is a transducer that produces all strings within some given Levenshtein edit distance of $w$ (but the origin of the transducer is immaterial). The set of those strings is a regular set that can be defined by a FA, with weighted transition that can compute the edit distance of each string.
If you do the cross-product with your grammar $G$, you get a shared parse forest grammar $F$ that generates all the strings in the intersection. Furthermore, you get the weights on some of the rules so that you can compute the edit distance of each of the accepted strings.
If desirable, this can be used to keep only the strings with minimal distance.
However, this can be improved a bit since composition with finite state machines is associative.
If you always use the same, finite state transducer, as is the case in your question, the right way to go about is to compose the Grammar $G$ and the transducer (here the Levenshtein automaton), independently of the input string. This gives you a weighted grammar that you can use to parse the input string $w$. The problem is that parsing with the brutal intersection construction with give you strings at any Levenshtein distance, i.e. $\Sigma^*$.
It would be easy to prune that construction to get the same result as before, but the best way is a more controlled intersection construction, such as the dynamic programming organization used by most parsers in the literature, including Earley's, and use it to avoid generating useless rule by computing distances and aborting any computational path when it exceeds the desired threshold. Dynamic programming can also be used to compute directly the parse-forest (or parse-tree) for the string that have the shortest distance to the input.
-
$\begingroup$ think this is helpful but also maybe "reading too much" into the question so saying something like "this is precisely your question" cannot really be accurate. youve taken a rather vague question not strictly formalized, and (attempted to?) formalize it yourself. there is probably more than one way to formalize the original somewhat-vague idea. think it might be helpful to 1st carefully define what the Levenshtein DFA constructions do (there are some known/ investigated, but which ones are we talking about?) and then explain how this concept could be generalized to CFLs. $\endgroup$– vznCommented Jul 31, 2015 at 15:47
-
1$\begingroup$ I actually give different formalizations, that complement each other. There are subtleties I did not get into, such as the exact use of weights in the process, which depends on the precise result you want to get. My purpose is not just to give an answer that has little interest in my own opinion, but to give a wider understanding of the problem. The choice of the edit distance used is immaterial, it works for anything that can be expressed with a weighted finite state transducer. $\endgroup$– babouCommented Jul 31, 2015 at 15:50