The issue of completing incomplete sentences has actually been adressed
formally. There are many way to view it. Modifying the grammar is a
possibility, but not the best method in my opinion, at least if you
are too crude about it. There are very generic techniques for ill-formed input that can be used to modify in various ways a non-grammatical input sentence, so as to make it grammatical. It can even use weights on the types of modifications considered so as to choose modifications with the smallest weight.
Your problem is a special case. Existing general CF parsing algorithms (not necessarily as currently implemented) can handle that for you without any
modification of the grammar. Instead, to explain it succintly, you can
modify the sentence by adding automatically special wildcard symbols between words that can
stand either for any part of speech, or for a sequence of parts of
speech of arbitrary length, wherever you wish to allow for more
words. Then a chart parser can actually parse this input and produce a
parse forest that represents all the possible sentences that would fit
your sequence of words, with the necessary additions where you allowed it. Actually this parse forest is a grammar of the language specialized so
that it generates only grammatical sentences that fit your initial
pattern. Any small sentence that you generate with that grammar will
be an answer to your problem.
It sounds a bit too easy, but it really is, and it works. It is a very general technique for correcting ill-formed input, and actually subsumes several specialized techniques that have been proposed in the literature.
You can find a description of this technique in a rather old paper:
Parsing Incomplete Sentences - B. Lang - Coling 88
(see section 4). It can also be found in the Grune-Jacobs book on parsing techniques in
the chapter "Parsing as Intersection". The general idea regarding ill-formed input is also described succintly in a paper on parsing as intersection: "Recognition can be harder than parsing".
The original technical description of the chart parsing technique may seem too mathematical or a
bit outdated, and the description by Grune and Jacobs may be simpler to read.
If you want to understand it more simply, think of your initial
sequence augmented with wild cards as a finite state automaton that generates all sequences of
words that you would consider acceptable if they were grammatical.
For example, with the notation of the paper where ? stands for a
single part of speech and * stands for any sequence, the sequence:
The red dog ? absolutely * always
may be read as an automaton with a linear structure, except for a
loop (on the state between absolutely and always) that can generate an arbitrary number of parts of speech.
?
/ \
The red dog ? absolutely \ / always
o ----> o ----> o ----> o ---> o ----------> o --------> O
Then chart parsing can be applied to such an automaton to produce a
shared forest for all the grammatical sequences in the language of the
finite state automaton.
Of course, you may actually put more special symbols than you actually need. This will only result in more candidate sentences.
Applying a chart parser to such an automaton can be done in the same
way that chart parsers can be applied to word lattices in speech
recognition. A word lattice can also be viewed as a finite state
automaton.
Indeed, all this falls into a more general framework that understands
parsing as a way of computing the intersection of a phrase structure
language (not necessarily Context-Free) and a finite state automaton
representing a set of candidate sentences. The result is a parse forest for all the grammatically acceptable sentences that can be generated by the (non necessarily deterministic) finite state automaton.
This represent a basic skeleton for the sentence completion procedure. Then you may
have to use other devices to actually choose the words you want to
insert in place of the missing parts of speech. But that may depend on
your lexicon and semantic issues. It become more an issue of sentence generation, based on the result of an initial parse of what is given to you.
You may have to worry about semantics, but syntactic correctness is ensured.
Regarding the use of NLTK and Python for the purpose, I am not sure of
the adequacy of it as currently programmed, since I am not a user of
NLTK. However, since NLTK contains a general context-free parser, it
should be possible to modify it to get the result described above, as
general CF parsers all work more or less on the same principles. There
may be one subtle point about handling "input loops", which amounts to
handling infinite ambiguity, often ignored by general CF parsers.
