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 thing or 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?

  • 1
    $\begingroup$ What you describe seems rather ad hoc. Is there any formalization of it so that it could be formally compared to other approaches. Formally compared does not necessarily mean theoretical comparison, but at least some formal references and definitions so that even experimental comparison can make sense. As it is I cannot be sure I understand enough to do it as you would do it. So I have no reference. But there are other techniques based on formal grammars that can achieve similar effects. Is there a reason for dismissing them? What is your potential problem with them? It may be a reverse answer $\endgroup$
    – babou
    Nov 25, 2014 at 16:08
  • $\begingroup$ @babou I agree, this does not seem rigorous enough. I will try to edit with an example to make this even more formal and rigorous. It will be followed shortly by the code. PS: I don't have any problem at all with formal grammar. In fact this is based on formal grammar, each filler is really just a context free grammar rule in essence. $\endgroup$
    – InformedA
    Nov 25, 2014 at 16:12
  • $\begingroup$ You seem to hail from the rule-based community (Grammatical Framework?). Are you familiar with statistical approaches to translation at all? The whole ngram business (used by Google, afaik), for instance. (That said, it seems to me that enriching a rule set by commmon mistakes is conceptually easy, if a pesky task.) $\endgroup$
    – Raphael
    Nov 25, 2014 at 16:39
  • $\begingroup$ @Raphael I am not familiar with statistical approach to translation, but I am aware of ngram business. I try to find a more balance approach with both statistics (on the ranking part) and the rule/model (on the parsing part). It is supposed to make the parser better with better use of both. $\endgroup$
    – InformedA
    Nov 25, 2014 at 16:52
  • $\begingroup$ @InstructedA I see. I attended a workshop on these things back in 2010; back then such a hybrid approach had not been attempted (iirc) and was hence subject to future research. I have not followed the community since, though. Note that there is Linguistics; if no answer is forthcoming here after a week or so, you can (re)ask there. $\endgroup$
    – Raphael
    Nov 25, 2014 at 16:58

1 Answer 1


I assume you already know about dynamic programming parsing, aka chart parsing. This is usually defined for Context-Free grammars (CFG), but can be extended to other grammatical formalisms, where it can make more or less sense, depending on the structural complexity of these algorithms. There are various papers describing chart parsing for specific formalisms, particularly in the computational linguistic literature. One general view of the underlying structure common to all these algorithms is described in a 1995 paper by Lang, and to be found in the Grune-Jacobs book, relies on a very simple view of parsing as an intersection of two languages: the first is the singleton regular language containing the sentence $w$ to be parsed, and the second being the language $L$ for which we are given a grammar $G$. The idea is that a single sentence $w$ can always be read as a FSA (or a regular grammar) 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$ (assume first $L$ to be a CF language, and $G$ a CFG), the old cross-product construction due to Bar-Hillel, Perles and Shamir (1961) to prove closure of CFL with regulr sets can be used with $A_w$ and $G$, and yield a new CF grammar $G_w$, which naturally generates only $w$ when $w\in L$, or the empty language $\emptyset$ when $w\notin L$. The important point is that, when $w\in L$, the grammar $G_w$ generates $w$ with exactly the same parse trees as the original grammar $G$, up to a renaming of non-terminal, though the correspondence between non-terminals is kept (let us ignore details). In other words, we just described a parser that yield a parse forest $G_w$ from which all the parse 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 just optimized variants of this very basic construction called parsing as intersection.

The nice point about it is that it lends itself to many variations. Closure under intersection with regular languages is a very common property, so that this is a guide for producing parsers for a great variety of formalisms, though it makes effective sense only for those that have a simple generating structure (loosely). Typically it works very well for tree adjoining grammars (TAG) an other mildly context sensitive languages.

Another point is that, rather than parse only strings, one can parse complete regular sets, keeping only the sentences that are also in the context-free language. And it is largely compatibles with the many "optimization" techniques commonly found in chart parsing

This is very important in natural language processing (NLP), and particularly in speech processing, since the result of the first pass of speech processor to identify the spoken words is usually not a single string of words, but what is usually called a word lattice (see Ambiguity and sharing in Natural Language Parsing, which is actually the title of an answer to a question).

The interesting point is that a word lattice (see diagram in previous reference) may be seen as a FSA that recognizes all the candidate sentences (after noise processing) that could be the sentence to be parsed. But chart parsing can be applied as well, as can the intersection construction.

Now, it may well be that the word lattice contains spurious words to be eliminated, or completely garbled sequences corresponding to arbitrary number of missing words, or misunderstood words. That can be modeled as a General Sequential Mapping (GSM) that does some editing on the input sentence, adding, removing or substituting words, possibly in a (finite) contextual way. Both regular and context free languages are preserved by GSM mapping. Typically, the editing GSM can be applied to the word lattice, yielding a new regual language and its FSA (possibly even with cycles). Then the parsing process is applied to that new FSA. This part is, I think, what you mainly wanted to describe in the question.

The next point is that not all proposed sentences, or not all corrections have the same likelyhood. Actually, word lattices may be weighted structures that give weights to the corresponding sentences in proportion to some likelyhood they they are correct.

Then the editing GSM can also have weighted transition corresponding to 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 (possibly probabilities) to determine what are the most likely parses of the given input according to the grammar used.

Note that I have been skipping the morphological analysis that recognizes words, and uses similar techniques to end up with the word lattice.

I am also skipping the use of attributes or feature structures, that can combine with the process, provided they meet some algebraic constraints.

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 trees in Natural Language Processing?"

  • $\begingroup$ Great elaboration. One thing I didn't recognize is that the Earley parser is actually something with special characteristics. I always thought that it is just the other style of CYK. Instead of going bottom up, it goes top down. $\endgroup$
    – InformedA
    Nov 26, 2014 at 22:35
  • $\begingroup$ Regarding Earley, I am no longer sure from memory. I will give a look at the parser to check, as there is a criterion for it (the shape of the forest). The criterion does not apply to CYK, as it is not a left-to-right parser. But Earley has another specificity, to compensate that it does not require the grammar to be made binary, which the algorithm does on the fly, with some consequences. BTW, is that the kind of answer you wanted? $\endgroup$
    – babou
    Nov 27, 2014 at 13:18
  • $\begingroup$ I was hoping to see what people have been doing, and you have lot of references in the answer. That is what I was hoping to see. Thank you. $\endgroup$
    – InformedA
    Nov 27, 2014 at 17:50
  • $\begingroup$ If the answer is ok, upvoting is not forbidden ...:) $\endgroup$
    – babou
    Nov 27, 2014 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.