1. A computer-implemented method performed by a data processing apparatus, the method comprising: identifying, from input sentences, first input sentences that do not successfully parse by any parsing rule in a set of parsing rules, each of the parsing rules being associated with an action, and wherein each parsing rule causes a user device to perform the action associated with the parsing rule in response to an input sentence received from the user device being successfully parsed by the parsing rule; determining, for each first input sentence, a quality score that is a measure of user satisfaction that is dependent on user interactions with search results at the user device from which the first input sentence was received; selecting, as candidate input sentences, each first input sentence having a quality score that is less than a quality score threshold, wherein the quality score threshold corresponds to a user satisfaction threshold; and for each candidate input sentence, determining whether the candidate input sentence is to be associated with one of a plurality of actions and upon a positive determination generates a parsing rule for the candidate input sentence, wherein the generated parsing rule is associated with the one of the plurality of actions and a successful parse of an input sentence received at a user device by the generated parsing rule causes the user device to perform the one of the plurality of actions associated with the generated parsing rule.