I have some background in natural language processing and I know that all parsers (top down or bottom up, or mix), at least when I studied just about a few years ago, cannot handle any error. A small error like a grammatical one or a spelling one will result in unexpected parsed tree.This is unacceptable in natural language in most cases. Thus I have been trying to find a way to make a new one with a different approach.The basic general abstract idea is that I will use a top down dynamic programming approach.Given a string of text with $n$ tokens, several top down fillers will be generated. These fillers will look at the tokens to see if they can find and fill constituents that they are missing. Because of this, these fillers might leave gap after they have found everything they need. This is supposed to make the parser more robust.An example will be best to illustrate this idea:Given the sentence: I saw the ordinary thing.One top down filler can be. $S \rightarrow Subj - Verb - Object$.This filler will try to look for span that it can use to fill its expectation of seeing a $Subject$ followed by $Verb$ and $Object$. This means it will deployed three other fillers in sequence. The first one is $Subj$. This filler will scan and add to the cache three possible subjects which are $I$, $saw$, $thing$. $I$ is put in span $[1,1]$, $Saw$ in span $[2,2]$, $thing$ in span $[5,5]$. This will result in a total of three potential pending parse trees. Then with each of these pending parse tree, $Verb$ filler is deployed to scan the span after each possible subject. $Object$ filler is deployed to scan the rest.With the above approach, sentences such as I .. eh... saw the big thingor similar constructs do not cause problem because fillers look for what they need and fill them into the tree. This problem is dealt with when all fillers have completed. Fillers that leave lot of gaps (unused tokens) will not generate parses having high score compared to parses generated by fillers that use up all tokens.This is also my approach to deal with subject-verb agreement and male-female as well as singular-plural agreement. You deal with them at the ranking stage so that you can give your parser much better error tolerance. Sentences such as Maybee they ehh can get something can still be parsed. One resulting parse will just not use Maybee. The top parses will then be used again, this time to look for unused tokens. Unused tokens will be processed with spelling correction, did-you-mean style. One can see how it works with incorrect sentences like This is a valide argument. Even incorrect sentences like They did got it are still parsed ok.There will be other fillers which cannot find all they need such as conditional sentence filler. $CondS \rightarrow If - S - [then] - S$. Some filler such as imperative $ImpS \rightarrow [Please] - Verb - Object$ will complete most of the times because it can find all it needs abeit leaving gaps, but then it is a ranking problem to make sure that the correct one is returned.So my Question is: Has anyone ever thought of this approach? Any reference papers?If nobody used it before what may be the potential problem?
Natural Language Parser that can handle syntactic and lexical errors
reference request;natural language processing
I assume you already know about dynamic programming parsing, aka chartparsing. This is usually defined for Context-Free grammars (CFG), butcan be extended to other grammatical formalisms, where it can makemore or less sense, depending on the structural complexity of thesealgorithms. There are various papers describing chart parsing forspecific formalisms, particularly in the computational linguisticliterature. One general view of the underlying structure common to allthese algorithms is described in a 1995 paper by Lang, and to be foundin the Grune-Jacobs book, relies on a very simple view of parsing asan intersection of two languages: the first is the singleton regularlanguage containing the sentence $w$ to be parsed, and the second beingthe language $L$ for which we are given a grammar $G$. The idea isthat a single sentence $w$ can always be read as a FSA (or a regulargrammar) as in the following example for the sentence $abac$$$q_0 \stackrel{a}\longrightarrow q_1 \stackrel{b}\longrightarrow q_2\stackrel{a}\longrightarrow q_3 \stackrel{c}\longrightarrow q_f$$Using this FSA $A_w$ and the grammar $G$ of the language $L$ (assumefirst $L$ to be a CF language, and $G$ a CFG), the old cross-productconstruction due to Bar-Hillel, Perles and Shamir (1961) to proveclosure of CFL with regulr sets can be used with $A_w$ and $G$, andyield a new CF grammar $G_w$, which naturally generates only $w$ when$w\in L$, or the empty language $\emptyset$ when $w\notin L$. Theimportant point is that, when $w\in L$, the grammar $G_w$ generates$w$ with exactly the same parse trees as the original grammar $G$, upto a renaming of non-terminal, though the correspondence betweennon-terminals is kept (let us ignore details). In other words, we justdescribed a parser that yield a parse forest $G_w$ from which all theparse trees for $w$ can be extracted, simply by using the grammar$G_w$ as a generator.As it turns out, the dynamic programming chart parsers are justoptimized variants of this very basic construction called parsing asintersection.The nice point about it is that it lends itself to many variations.Closure under intersection with regular languages is a very commonproperty, so that this is a guide for producing parsers for a greatvariety of formalisms, though it makes effective sense only for thosethat have a simple generating structure (loosely). Typically it worksvery well for tree adjoining grammars (TAG) an other mildly contextsensitive languages.Another point is that, rather than parse only strings, one can parsecomplete regular sets, keeping only the sentences that are also in thecontext-free language. And it is largely compatibles with the manyoptimization techniques commonly found in chart parsingThis is very important in natural language processing (NLP), andparticularly in speech processing, since the result of the first passof speech processor to identify the spoken words is usually not asingle string of words, but what is usually called a word lattice(see Ambiguity and sharing in Natural Language Parsing, which isactually the title of an answer to a question).The interesting point is that a word lattice (see diagram in previousreference) may be seen as a FSA that recognizes all the candidatesentences (after noise processing) that could be the sentence to beparsed. But chart parsing can be applied as well, as can theintersection construction.Now, it may well be that the word lattice contains spurious words tobe eliminated, or completely garbled sequences corresponding toarbitrary number of missing words, or misunderstood words. That can bemodeled as a General Sequential Mapping (GSM) that does some editingon the input sentence, adding, removing or substituting words,possibly in a (finite) contextual way. Both regular and context freelanguages are preserved by GSM mapping. Typically, the editing GSM canbe applied to the word lattice, yielding a new regual language and itsFSA (possibly even with cycles).  Then the parsing process is appliedto that new FSA.  This part is, I think, what you mainly wanted todescribe in the question.The next point is that not all proposed sentences, or not allcorrections have the same likelyhood. Actually, word lattices may beweighted structures that give weights to the corresponding sentencesin proportion to some likelyhood they they are correct.Then the editing GSM can also have weighted transition correspondingto some standard likelyhood that such error may have occurred.Finally, the (CF) grammar of the language itself may be weighted.The dynamic programming construction can use these weight (possiblyprobabilities) to determine what are the most likely parses of thegiven input according to the grammar used.Note that I have been skipping the morphological analysis thatrecognizes words, and uses similar techniques to end up with the wordlattice.I am also skipping the use of attributes or feature structures, thatcan combine with the process, provided they meet some algebraicconstraints.The algebraic constraints (that concern also the numerical weights)are related to the algebraic structures of the grammars themselves.Typically, a CF derivation backbone (that is more than CF languages)relies on semiring structures.A CF rule such as $X\to VXW | aV$ may be read as an equation of the form $X = V\cdot X\cdot W \cup \{a\}\cdot W$ where the wariables take their values in sets of sentences (i.e. in languages). The domain of languages is a semi-ring under the two operations: Union $\cup$ and concatenation $\cdot$. And a context-free grammar is a specific kind of equation in that domain.You should find more on this use of semirings in Goodman's Parsing Inside-Out 1998.There are some other references in my answer to the question Is there a favoured data structure for storing ambiguous parse treesin Natural Language Processing?